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).
