D graph library

w0rp devw0rp at gmail.com
Wed May 15 10:40:02 PDT 2013


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.


More information about the Digitalmars-d mailing list