D graph library

[w0rp]

On Wednesday, 8 May 2013 at 16:14:05 UTC, H. S. Teoh wrote:
> Does it make sense to have a common interface between, say, 
> directed and
> non-directed graphs? That is, are there algorithms that can 
> operate on
> both, or do most of the interesting algorithms only work on one 
> or the
> other? I'm just wondering if it's worth the trouble of doing
> compile-time (or runtime) checks if we could just have two 
> unrelated
> graph types.

I suggest building the graphs as structs with policy based 
design, possibly having separate policies for how the graphs are 
stored in memory, possibly not. So the basic graph structure 
would be like this.

// Struct so stack allocation becomes possible later.
struct GraphImplementation(GraphPolicy)
if (isGraphPolicy!GraphPolicy){
     GraphPolicy graphPolicy = GraphPolicy();
}

The graph policies could look like this.

struct DigraphPolicy(Node, Weight) {
     // This could be the first naive policy to get the ball 
rolling.
     // unit test to verify a few basic algorithms first, optimise 
later.
     Weight[Node][Node] edgeMap;

     ...
}

The policies can then offer methods for accessing and mutating 
the graphs. So that would be stuff like bool addNode(Node), bool 
removeNode(Node), bool addEdge(Node, Node), NodeRange!Node 
neighbors(Node), etc. All of the internals of GraphImplementation 
could then access the very basic things through these methods, 
and then expose a few to the users by wrapping/aliasing the 
functions. Perhaps encapsluation + alias this is the way to go 
here.

{
    ... alias graphPolicy this; // Now we expose addNode(Node), 
etc.
}

Then for your final trick, you could throw in a few templates to 
bring it all together.

template isGraphPolicy(T) { ... }
template isSomeGraph(T) { ... }
template NodeType(SomeGraph) { ... }
template EdgeType(SomeGraph) { ... }

Most importantly...

template Digraph(Node, Weight = int) {
     auto Digraph = GraphImplementation!(DigraphPolicy!(Node, 
Weight));
}

Then we are back to basics:

auto graph = Digraph!char;
graph.addEdge('a', 'b'); // bla, bla, bla

I think doing things in this way makes it easy to get the ball 
rolling, but also easy to add in optimisations later. ("Aha, this 
is an undirected graph, I can assume this... static if") I think 
the most important thing is to get the graph basics right, then 
to worry about how storage works, etc. later.