D graph library

[w0rp]

On Wednesday, 15 May 2013 at 18:38:59 UTC, Joseph Rushton 
Wakeling wrote:
> On 05/15/2013 08:28 PM, w0rp wrote:
>> I don't think that's too useful or necessary. A graph is at 
>> its heart a pair (V,
>> E) where V is the vertex set and E is the edge set. So addNode 
>> is really just V'
>> = V ∪ {n} for some node n. I think it's best to just allow 
>> redundantly adding a
>> node, which ought to be an O(1) function.
>
> In the same way as one could add a word to a dictionary, say?
>
> Consider that it's possible to have multigraphs where there 
> _can_ be multiple
> edges from one node to another.  You might well want to 
> explicitly enforce the
> user's awareness of error if they try adding multiple edges to 
> the wrong type of
> graph.

I have considered 'multigraphs,' which is kind of like having an 
STL multimap in my mind. Having policies again makes the 
implementation a little easier. I would prefer to not have 
addNode throw exceptions when applied redundantly. Not throwing 
is very familiar behaviour if you think in terms of set theory. 
Then you can have a separate function to support runtime checks 
to make sure you don't trip over yourself when really don't want 
to add more than once.

void addNodeOnce(SomeGraph)(SomeGraph graph, NodeType!SomeGraph 
node)
if (isSomeGraph!SomeGraph)
in {
     assert(!graph.hasNode(node));
} body {
     graph.addNode(node);
} out {
     // Let's go all the way with this.
     assert(graph.hasNode(node));
}

Now you have graph.addNodeOnce(node).