D graph library

[Joseph Rushton Wakeling]

On 05/11/2013 07:08 PM, H. S. Teoh wrote:
> Well, maybe what we can do is to make a list of attributes that are
> needed by various graph algorithms, and see if there's a way to distill
> them into a small set of attributes without too many scattered attribute
> checks. For example, if we can categorize graphs into a small set of
> types (ala input range, forward range, etc.) plus a small number of
> optoinal attributes, that would be ideal, I think.

Sure, we can have a go at this.

> Are there actually algorithms that depend on having an .edges property?
> AFAIK, most iterate over nodes in some way.

I have written code that iterates over edges (see my "dregs" code on GitHub).
In the case of the problem I was addressing, it enabled the most space-efficient
storage of the data.

There's no reason why an algorithm should be required to assume the existence of
an edges() property, but for an explicit graph type I think having an edges()
property is generally expected (and is certainly implemented in all the examples
I've looked at).

> Hmm. Maybe something similar to std.range.SortedRange would be useful:
> 
> 	struct BipartiteGraph(G) {
> 		enum isBipartite = true;
> 		G impl;
> 		alias impl this;
> 	}
> 
> 	BipartiteGraph!G verifyIsBipartite(G)(G graph) {
> 		// verifies bipartiteness of G and returns graph wrapped
> 		// in a BipartiteGraph!G.
> 	}
> 
> 	auto createBipartiteGraph(T...)(T graphData) {
> 		// return an instantiation of BipartiteGraph that's
> 		// guaranteed to be bipartite by construction.
> 	}
> 
> 	auto someBipartiteAlgo(G)(BipartiteGraph!G graph) {
> 		// freely assume bipartiteness of graph
> 	}
> 
> This way we can make use of the type system to statically ensure
> bipartiteness, while still allowing runtime verifications of arbitrary
> graphs.

Yes, that could be nice.  Bear in mind that the BipartiteGraph type would have
to not just have a boolean claiming bipartiteness, but checks to ensure that
edges added did not violate the bipartite property.

> Aha. I think we found the source of contention here. You're thinking
> about concrete graph types that can be used for general graph
> applications, whereas I'm thinking of Phobos-style generic graph
> algorithm *templates* that can process any graph-like type satisfying
> certain requirements.

Yes, that seems to be the main source of our differences of opinion.  I entirely
agree with you about the need for generic graph algorithm templates, but we do
need graph types as well, and most of my specifications were intended with those
in mind.

> In that light, I think it makes sense to provide a set of concrete graph
> types that people can use (e.g., an adjacency list type, an incidence
> list type, matrix representations maybe, to list a few commonly-used
> graph representations), but the algorithms themselves will be generic
> templates that can work with any concrete type as long as it has the
> attributes required by the algorithm. The concrete graph types (which
> may themselves be templates, e.g. to allow arbitary node types or edge
> labels) will of course satisfy (most of) these requirements by default,
> so they can be immediately used with the algorithms without further ado.
> At the same time, the user can decide to create their own graph types,
> and as long as the target algorithm's prerequisites are satisfied, it
> can be used with those custom types.

I think we've come to some broad agreement here ... :-)

> Actually, I'll be on vacation for a week and a half, with probably
> spotty internet connectivity, so no need to hurry. :)

So, have fun, and look forward to catching up with you when you get back :-)