On Wednesday, 15 May 2013 at 17:21:24 UTC, Joseph Rushton
Wakeling wrote:
On 05/15/2013 09:29 AM, w0rp wrote:
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.
What advantage does this have over just defining a few
different structs, e.g.,
struct Graph {
// undirected graph
}
struct Digraph {
// directed graph
}
... which each define certain expected interfaces such as
nodes(), edges(), etc.?
Not objecting, just curious. :-)
There are two advantages.
1. Some functions for undirected and directed graphs are either
identical or nearly identical. So you can write a single
implementation with different policies.
2. Storage implementation can be interchangeable, as you change
the storage for a graph by changing its policy.
Point 1 could be equally addressed by writing free template
functions for the graphs. (So two structs and free functions work
work there.) Point 2 is more interesting because a different
method of storage (stack vs heap, nested map vs some array
combination) implies a different addNode(Node) function, and so
on. So the policies let you swap the underlying implementation
out via a template parameter without having to write another
struct to deal with it.
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.
... why returning bool? Again, not objecting, just curious.
bool is a nice convenience for "did this change anything?" So you
return false when addNode actually had no effect, say when the
node was already in the graph. This idea is basically borrowed
from Java collections.
If you think about that in D terms you might start with arrays
from and to, and
e.g. edges() would return lockstep(from, to). I suspect we
could also do many
nice things with D based around those fundamental structures.
I think writing functions that return ranges for the graphs
(vertices, edges, neighbours, etc.) and building the algorithms
based on these ranges is the right way to go.
