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.
