1 module anansi.adjacencylist;
2 
3 import std.algorithm,
4        std.conv,
5        std.range,
6        std.stdio,
7        std.traits,
8        std.typecons,
9        std.typetuple;
10 import anansi.container, anansi.traits;
11 
12 
13 struct AdjacencyList (alias VertexStorage = VecS,
14                       alias EdgeStorage = VecS,
15                       Directionality = DirectedS,
16                       VertexProperty = NoProperty,
17                       EdgeProperty = NoProperty)
18 {
19 public:
20     alias VertexDescriptor = VertexStorage.IndexType;
21 
22     enum IsUndirected = is(Directionality == UndirectedS);
23     enum IsBidirectional = is(Directionality == BidirectionalS);
24     enum IsDirected = !(IsUndirected || IsBidirectional);
25 
26     /** 
27      * The main storage object for edges. Holds the source and destination
28      * vertices for the graph, plus any property object.
29      */
30     private static struct Edge {
31         this(VertexDescriptor src, VertexDescriptor dst,
32              EdgeProperty value = EdgeProperty.init)
33         {
34             _src = src;
35             _dst = dst;
36             static if (isNotNone!EdgeProperty) {
37                 _property = value;
38             }
39         }
40 
41         private VertexDescriptor _src;
42         private VertexDescriptor _dst;
43 
44         public @property VertexDescriptor source() { return _src; }
45         public @property void source(VertexDescriptor v) { _src = v; }
46 
47         public @property VertexDescriptor target() { return _dst; }
48         public @property void target(VertexDescriptor v) { _dst = v; }
49 
50         private EdgeProperty  _property;
51         public @property ref inout(EdgeProperty) value() inout {
52             return _property;
53         }
54     }
55 
56     private alias EdgeList = List!Edge;
57     private alias EdgeIndex = EdgeList.Node*;
58 
59     /**
60      * A handle that can be used by callers to identify a given edge.
61      */
62     public static struct EdgeDescriptor {
63         package VertexDescriptor src;
64         package VertexDescriptor dst;
65         package const(EdgeList.Node)* edgeIndex;
66     }
67 
68     /**
69      * The main storage object for vertices. Maintains the collection of out-
70      * (and optionally in-) edges for the vertex, plus any property values.
71      */
72     private static struct Vertex {
73         public alias EdgeContainer = EdgeStorage.Store!EdgeIndex;
74 
75         private EdgeContainer _outEdges;
76         static if (IsBidirectional) {
77             private EdgeContainer _inEdges;
78         }
79 
80         public this(VertexProperty p) {
81             static if (isNotNone!VertexProperty) {
82                 _property = p;
83             }
84         }
85 
86         public this(this) {
87             _outEdges = _outEdges.dup;
88             static if (IsBidirectional) {
89                 _inEdges = _inEdges.dup;
90             }
91         }
92 
93         public auto addOutEdge(EdgeIndex edge) {
94             return _outEdges.push(edge);
95         }
96 
97         public void eraseOutEdge(EdgeIndex edge) {
98             eraseEdge(_outEdges, edge);
99         }
100 
101         private static void eraseEdge(ref EdgeContainer edges, EdgeIndex edge) {
102             auto r = find(edges[], edge);
103             assert (!r.empty, "Attempt to remove an edge that doesn't exist");
104             edges.eraseFrontOfRange(r);
105         }
106 
107         auto outEdges() const { return _outEdges[]; }
108 
109         @property public size_t outDegree() const {
110             return _outEdges.length;
111         }
112 
113         static if (IsBidirectional) {
114             public void addInEdge(EdgeIndex edge) {
115                 _inEdges.push(edge);
116             }
117 
118             public void eraseInEdge(EdgeIndex edge) {
119                 eraseEdge(_inEdges, edge);
120             }
121 
122             auto inEdges() const { return _inEdges[]; }
123 
124             @property public size_t inDegree() const {
125                 return _inEdges.length;
126             }
127         }
128 
129         static if (isNotNone!VertexProperty) {
130             private VertexProperty _property;
131 
132             public @property ref inout(VertexProperty) property() inout {
133                 return _property;
134             }
135         }
136     }
137 
138     /**
139      * The main vertex store.
140      */
141     VertexStorage.Store!Vertex _vertices;
142 
143     /**
144      * The main edge store
145      */
146     EdgeList _edges;
147 
148 public:
149     // ------------------------------------------------------------------------
150     // Vertex operations
151     // ------------------------------------------------------------------------
152 
153     /**
154      * Adds a new vertex to the graph.
155      *
156      * Params:
157      *   value = The property value to associate with the vertex, if any.
158      *
159      * Returns: Returns a VertexDescriptor referencing the newly-added vertex.
160      */
161     VertexDescriptor addVertex(VertexProperty value = VertexProperty.init) {
162         return _vertices.push(Vertex(value)).index;
163     }
164 
165     @property vertexCount() const {
166         return _vertices.length;
167     }
168 
169     /**
170      * Returns a forward range that yields the descriptors for each vertex in
171      * the graph. The order of the vertices is undefined.
172      */
173     @property auto vertices() inout {
174         return _vertices.indexRange();
175     }
176 
177     static if (!isNone!VertexProperty) {
178         ref inout(VertexProperty) opIndex(VertexDescriptor v) inout {
179             return _vertices.get_value(v).property;
180         }
181     }
182 
183     /**
184      * Removes a vertex from the graph. The complexity of this operaton
185      * varies with the storage class. For storage classes that have
186      * stable indexes, this is O(1). For classes with unstable indexes
187      * this is at least O(n), where n is the number of edges in the graph,
188      * due to the VertexDescriptors in all the edges having to be fixed up.
189      *
190      * This is the *minimum* complexity, because the underlying storage may
191      * impose its own complexity costs on erasing the vertex itself as well.
192      *
193      * Params:
194      *   vertex = The VertexDescriptor of the vertex to erase.
195      */
196     void removeVertex(VertexDescriptor vertex) {
197         _vertices.erase(vertex);
198         static if( !VertexStorage.IndexesAreStable ) {
199             foreach(ref e; _edges[]) {
200                 e.source = _vertices.rewriteIndex(vertex, e.source);
201                 e.target = _vertices.rewriteIndex(vertex, e.target);
202             }
203         }
204     }
205 
206 public:
207     // ------------------------------------------------------------------------
208     // Edge operations
209     // ------------------------------------------------------------------------
210 
211     /**
212      * A tuple with some names to help unpacking the result of an addEdge call.
213      */
214     alias AddEdgeResult = Tuple!(EdgeDescriptor, "edge", bool, "addedNew");
215 
216     /**
217      * Adds an edge to the graph.
218      *
219      * Params:
220      *  src = The VertexDescriptor of the edge's starting point.
221      *  dst = The VertexDescriptor of the new edge's end point.
222      *  value = The value to associate with the new edge, if any.
223      *
224      * Returns: Returns an AddEdgeResult value, containinf the descriptor of
225      *          the edge, and a flag to let you know if it was newly created
226      *          (true), or the edge already esisted and the graph type doesn't
227      *          support parallel edges, so the returned descriptor refers to
228      *          the pre-existing edge (false).
229      */
230     AddEdgeResult addEdge(VertexDescriptor src,
231                           VertexDescriptor dst,
232                           EdgeProperty value = EdgeProperty.init) {
233 
234         EdgeIndex newEdge = _edges.insertBack(Edge(src, dst, value));
235         Vertex* pSrc = &_vertices.get_value(src);
236         pSrc.addOutEdge(newEdge);
237 
238         static if (IsUndirected) {
239             Vertex* pDst = &_vertices.get_value(dst);
240             pDst.addOutEdge(newEdge);
241         }
242         else static if (IsBidirectional) {
243             Vertex* pDst = &_vertices.get_value(dst);
244             pDst.addInEdge(newEdge);
245         }
246 
247         return AddEdgeResult(EdgeDescriptor(src, dst, newEdge), true);
248     }
249 
250     /**
251      * Removes an edge from the graph.
252      */
253     void removeEdge(EdgeDescriptor edge) {
254         VertexDescriptor src = cast(VertexDescriptor) edge.src;
255         VertexDescriptor dst = cast(VertexDescriptor) edge.dst;
256         Vertex* srcVertex = &_vertices.get_value(src);
257         EdgeIndex idx = cast(EdgeIndex) edge.edgeIndex;
258 
259         srcVertex.eraseOutEdge(idx);
260 
261         static if (IsUndirected) {
262             Vertex* dstVertex = &_vertices.get_value(dst);
263             dstVertex.eraseOutEdge(idx);
264         }
265         else static if (IsBidirectional) {
266             Vertex* dstVertex = &_vertices.get_value(dst);
267             dstVertex.eraseInEdge(idx);
268         }
269 
270         _edges.remove(idx);
271     }
272 
273     /**
274      * Fetches the descriptor of the source vertex of the given edge.
275      *
276      * Params:
277      *   edge = The descriptor of the edge to query.
278      *
279      * Returns: The descriptor of the supplied edge's source vertex.
280      */
281     VertexDescriptor source(EdgeDescriptor edge) const {
282         return cast(VertexDescriptor) edge.src;
283     }
284 
285     /**
286      * Fetches the descriptor of the target vertex of the supplied edge.
287      *
288      * Params:
289      *   edge = The descriptor of the edge you want to query.
290      */
291     VertexDescriptor target(EdgeDescriptor edge) const {
292         return cast(VertexDescriptor) edge.dst;
293     }
294 
295     /**
296      * Lists the outbound edges of a given vertex.
297      *
298      * Params:
299      *   vertex = The descriptor of the vertex to query.
300      *
301      * Returns: Returns a range containing the edge descriptors of the
302      *          supplied vertex's outbound edges.
303      */
304     auto outEdges(VertexDescriptor vertex) const {
305         static struct OutEdgeRange {
306             alias EdgeRange = Vertex.EdgeContainer.ConstRange;
307 
308             this(VertexDescriptor src, EdgeRange r) {
309                 _src = src;
310                 _r = r;
311             }
312 
313             @property bool empty() { return _r.empty; }
314 
315             @property EdgeDescriptor front() {
316                 auto edge = _r.front;
317 
318                 static if (IsUndirected) {
319                     auto s = edge.value._src;
320                     auto d = edge.value._dst;
321                     auto src = (s == _src) ? s : d;
322                     auto dst = (s == _src) ? d : s;
323                 }
324                 else{
325                     auto src = edge.value._src;
326                     auto dst = edge.value._dst;
327                 }
328 
329                 return EdgeDescriptor(cast(VertexDescriptor)src,
330                                       cast(VertexDescriptor)dst,
331                                       cast(EdgeIndex)(edge));
332             }
333 
334             void popFront() { _r.popFront(); }
335 
336             private EdgeRange _r;
337             private VertexDescriptor _src;
338         }
339 
340         static assert(isInputRange!OutEdgeRange);
341         static assert(is(ElementType!OutEdgeRange == EdgeDescriptor));
342 
343         return OutEdgeRange(vertex, _vertices.get_value(vertex).outEdges());
344     }
345 
346     size_t outDegree(VertexDescriptor vertex) const {
347         return _vertices.get_value(vertex).outDegree;
348     }
349 
350     static if (IsBidirectional) {
351         size_t inDegree(VertexDescriptor vertex) const {
352             return _vertices.get_value(vertex).inDegree;
353         }
354 
355         auto inEdges(VertexDescriptor vertex) const {
356             static struct InEdgeRange {
357                 alias EdgeRange = Vertex.EdgeContainer.ConstRange;
358 
359                 this(EdgeRange r) { _r = r; }
360 
361                 @property bool empty() { return _r.empty; }
362 
363                 @property EdgeDescriptor front() {
364                     auto edge = _r.front;
365                     auto s = edge.value._src;
366                     auto d = edge.value._dst;
367                     return EdgeDescriptor(cast(VertexDescriptor)s,
368                                           cast(VertexDescriptor)d,
369                                           cast(EdgeIndex)edge);
370                 }
371 
372                 void popFront() { _r.popFront(); }
373 
374                 private EdgeRange _r;
375                 private VertexDescriptor _src;
376             }
377 
378             static assert(isInputRange!InEdgeRange);
379             static assert(is(ElementType!InEdgeRange == EdgeDescriptor));
380 
381             return InEdgeRange(_vertices.get_value(vertex).inEdges());
382         }
383     }
384 
385     static if (!isNone!EdgeProperty) {
386         ref EdgeProperty opIndex(EdgeDescriptor e) {
387             return (cast(EdgeIndex)e.edgeIndex).valueRef.value;
388         }
389 
390         ref const(EdgeProperty) opIndex(EdgeDescriptor e) const {
391             return e.edgeIndex.valueRef.value;
392         }
393     }
394 
395     /**
396      * Fetches the total number of edges in the graph. For debugging purposes
397      * only.
398      */
399     @property size_t edgeCount() const {
400         return _edges.length;
401     }
402 
403     auto edgesBetween(VertexDescriptor from, VertexDescriptor to) {
404         return filter!(e => target(e) == to)(outEdges(from));
405     }
406 }
407 
408 // ----------------------------------------------------------------------------
409 // Unit Tests
410 // ----------------------------------------------------------------------------
411 
412 unittest {
413     writeln("AdjacencyList: Custom storage type");
414 
415     struct ArrayS {
416         alias IndexType = size_t;
417         enum IndexesAreStable = true;
418 
419         static struct Store(ValueType) {
420             alias Range = ValueType[];
421 
422             auto push(ValueType value) {
423                 size_t rval = _store.length;
424                 _store ~= value;
425                 return PushResult!(typeof(rval))(rval, true);
426             }
427 
428             void erase(IndexType index) {
429                 assert (false, "Not Implemented");
430             }
431 
432             void eraseFrontOfRange(ValueType[] range) {
433                 assert (false, "Not Implemented");
434             }
435 
436             auto indexRange() const {
437                 return iota(0, _store.length);
438             }
439 
440             ref inout(ValueType) get_value(IndexType index) inout {
441                 return _store[index];
442             }
443 
444             @property auto dup() {
445                 return Store(_store.dup);
446             }
447 
448             @property size_t length() const {
449                 return _store.length;
450             }
451 
452             ValueType[] _store;
453 
454             alias ConstRange = const(ValueType)[];
455 
456             alias _store this;
457         }
458     }
459 
460     AdjacencyList!(ArrayS, ArrayS, DirectedS, char, string) g;
461     auto v = g.addVertex('a');
462     assert (g[v] == 'a');
463 }
464 
465 unittest {
466     writeln("AdjacencyList: Adding a vertex with no property.");
467     foreach(VertexStorage; TypeTuple!(VecS, ListS)) {
468         foreach(EdgeStorage; TypeTuple!(VecS, ListS)) {
469             foreach(Directionality; TypeTuple!(DirectedS, UndirectedS, BidirectionalS)) {
470                 AdjacencyList!(VertexStorage, EdgeStorage, Directionality) g;
471                 auto v1 = g.addVertex();
472                 auto v2 = g.addVertex();
473                 auto v3 = g.addVertex();
474 
475                 assert (g.vertexCount == 3,
476                         "Bad vertex count. Exepected 3, got " ~
477                         to!string(g.vertexCount));
478 
479                 foreach(x; zip(g.vertices(), [v1, v2, v3][])) {
480                     assert (x[0] == x[1], "Mismatched vertex descriptors");
481                 }
482             }
483         }
484     }
485 }
486 
487 unittest {
488     writeln("AdjacencyList: Adding a vertex with a property.");
489     foreach(VertexStorage; TypeTuple!(VecS, ListS)) {
490         foreach(EdgeStorage; TypeTuple!(VecS, ListS)) {
491             foreach(Directionality; TypeTuple!(DirectedS, UndirectedS, BidirectionalS)) {
492                 AdjacencyList!(VertexStorage, EdgeStorage, Directionality, string) g;
493                 auto v1 = g.addVertex("alpha");
494                 auto v2 = g.addVertex("beta");
495                 auto v3 = g.addVertex("gamma");
496 
497                 foreach(x; zip(g.vertices(), ["alpha", "beta", "gamma"][])) {
498                     assert (g[x[0]] == x[1], "Mismatched vertex descriptors");
499                 }
500             }
501         }
502     }
503 }
504 
505 unittest {
506     writeln("AdjacencyList: Vertex properties are assignable.");
507     foreach(VertexStorage; TypeTuple!(VecS, ListS)) {
508         foreach(EdgeStorage; TypeTuple!(VecS, ListS)) {
509             foreach(Directionality; TypeTuple!(DirectedS, UndirectedS, BidirectionalS)) {
510                 AdjacencyList!(VertexStorage, EdgeStorage, Directionality, string) g;
511                 auto v1 = g.addVertex("alpha");
512                 auto v2 = g.addVertex("beta");
513                 auto v3 = g.addVertex("gamma");
514 
515                 assert (g[v2] == "beta");
516                 g[v2] = "narf";
517 
518                 foreach(x; zip(g.vertices(), ["alpha", "narf", "gamma"][])) {
519                     assert (g[x[0]] == x[1], "Mismatched vertex properties");
520                 }
521             }
522         }
523     }
524 }
525 
526 unittest {
527     struct Test { int i; }
528 
529     writeln("AdjacencyList: Vertex properties are mutable.");
530     foreach(VertexStorage; TypeTuple!(VecS, ListS)) {
531         foreach(EdgeStorage; TypeTuple!(VecS, ListS)) {
532             foreach(Directionality; TypeTuple!(DirectedS, UndirectedS, BidirectionalS)) {
533                 AdjacencyList!(VertexStorage, EdgeStorage, Directionality, Test) g;
534                 auto v1 = g.addVertex(Test(0));
535                 auto v2 = g.addVertex(Test(1));
536                 auto v3 = g.addVertex(Test(2));
537 
538                 assert (g[v2].i == 1);
539                 g[v2].i = 42;
540                 assert (g[v2].i == 42);
541             }
542         }
543     }
544 }
545 
546 unittest {
547     writeln("AdjacencyList: Erasing a vertex.");
548     foreach(VertexStorage; TypeTuple!(VecS, ListS)) {
549         foreach(EdgeStorage; TypeTuple!(VecS, ListS)) {
550             foreach(Directionality; TypeTuple!(DirectedS, UndirectedS, BidirectionalS)) {
551                 alias Graph = AdjacencyList!(VertexStorage, EdgeStorage, Directionality, char, string);
552                 Graph g;
553 
554                 /* artificial scope for namespacing */ {
555                     auto a = g.addVertex('a');
556                     auto b = g.addVertex('b');
557                     auto c = g.addVertex('c');
558 
559                     auto ac = g.addEdge(a, c, "ac");
560                     auto ca = g.addEdge(c, a, "ca");
561 
562                     g.removeVertex(b);
563                 }
564 
565                 assert (g.vertexCount == 2,
566                     Graph.stringof ~ ": Expected vertex count to be 2, got: " ~
567                     to!string(g.vertexCount));
568 
569                 // assert that we only have the vertices we expect
570                 auto vertices = array(g.vertices());
571                 foreach(x; zip(vertices, ['a', 'c'])) {
572                     assert (g[x[0]] == x[1],
573                         Graph.stringof ~ ": Mismatched vertex descriptors");
574                 }
575 
576                 // assert the a -> c edge still holds
577                 auto a = vertices[0];
578                 auto c = vertices[1];
579                 auto ac = g.outEdges(a).front;
580                 assert (g.source(ac) == a,
581                     Graph.stringof ~ ": Source(ac) should be a");
582 
583                 assert (g.target(ac) == c,
584                     Graph.stringof ~ ": Target(ac) should be c");
585 
586                 // assert the c -> a edge still holds
587                 auto ca = g.outEdges(c).front;
588                 assert (g.source(ca) == c,
589                     Graph.stringof ~ ": Source(ca) should be c");
590 
591                 assert (g.target(ca) == a,
592                     Graph.stringof ~ ": Target(ca) should be a");
593 
594             }
595         }
596     }
597 }
598 
599 version (unittest) {
600     void checkEdges(Graph)(ref Graph g,
601                            string name,
602                            Graph.VertexDescriptor src,
603                            Graph.VertexDescriptor[] outTargets,
604                            Graph.VertexDescriptor[] inTargets) {
605         auto outEdges = array(g.outEdges(src));
606         auto outDegree = g.outDegree(src);
607         assert (outDegree == outTargets.length,
608                 Graph.stringof ~ ": Expected " ~ name ~
609                 " to have out degree of " ~ to!string(outTargets.length) ~
610                 ", got " ~ to!string(outDegree));
611 
612         assert (outEdges.length == outTargets.length,
613                 Graph.stringof ~ ": Expected " ~ name ~ " to have exactly " ~
614                 to!string(outTargets.length) ~ " out edge(s), got " ~
615                 to!string(outEdges.length));
616 
617         foreach (t; outTargets) {
618             assert (any!(e => g.target(e) == t)(outEdges),
619                     Graph.stringof ~ ": Expected target from " ~ name ~
620                     " was not in out edges.");
621         }
622 
623         static if (g.IsBidirectional) {
624             auto inDegree = g.inDegree(src);
625             assert (inDegree == inTargets.length,
626                     Graph.stringof ~ ": Expected " ~ name ~
627                     " to have in degree of " ~ to!string(inTargets.length) ~
628                     ", got " ~ to!string(inDegree));
629 
630             auto inEdges = array(g.inEdges(src));
631             foreach (t; inTargets) {
632                 assert (any!(e => g.source(e) == t)(inEdges),
633                         Graph.stringof ~ ": Expected source in " ~ name ~
634                         " was not in in-edges.");
635             }
636         }
637     }
638 }
639 
640 unittest {
641     writeln("AdjacencyList: Adding edges works as expected.");
642     foreach(VertexStorage; TypeTuple!(VecS, ListS)) {
643         foreach(EdgeStorage; TypeTuple!(VecS, ListS)) {
644             foreach(Directionality; TypeTuple!(DirectedS, UndirectedS, BidirectionalS)) {
645                 alias Graph = AdjacencyList!(VertexStorage, EdgeStorage, Directionality, char, string);
646 
647                 Graph g;
648 
649                 // Graph layout
650                 //      B
651                 //    / | \
652                 //   A  |  C
653                 //      | /
654                 //      D
655 
656                 auto vA = g.addVertex('a');
657                 auto vB = g.addVertex('b');
658                 auto vC = g.addVertex('c');
659                 auto vD = g.addVertex('d');
660 
661                 auto addUniqueEdge = delegate(Graph.VertexDescriptor s, Graph.VertexDescriptor d) {
662                     auto tmp = g.addEdge(s, d, to!string(g[s]) ~ " --> " ~ to!string(g[d]) );
663                     assert(tmp.addedNew, Graph.stringof ~ ": Edge must be unique.");
664                     return tmp.edge;
665                 };
666 
667                 auto eAB = addUniqueEdge(vA, vB);
668                 auto eBC = addUniqueEdge(vB, vC);
669                 auto eCD = addUniqueEdge(vC, vD);
670                 auto eBD = addUniqueEdge(vB, vD);
671 
672                 assert (g.edgeCount == 4, "edgeCount should be 4");
673 
674                 checkEdges!Graph(g, "A", vA, [vB], []);
675                 checkEdges!Graph(g, "B", vB, g.IsUndirected ? [vA, vC, vD] : [vC, vD], [vA]);
676                 checkEdges!Graph(g, "C", vC, g.IsUndirected ? [vB, vD] : [vD], [vB]);
677                 checkEdges!Graph(g, "D", vD, g.IsUndirected ? [vB, vC] : [], [vB, vC]);
678             }
679         }
680     }
681 }
682 
683 unittest {
684     import std.algorithm.comparison : equal;
685 
686     writeln("AdjacencyList: Removing edges works as expected.");
687     foreach(VertexStorage; TypeTuple!(VecS, ListS)) {
688         foreach(EdgeStorage; TypeTuple!(VecS, ListS)) {
689             foreach(Directionality; TypeTuple!(DirectedS, UndirectedS, BidirectionalS)) {
690                 alias Graph = AdjacencyList!(VertexStorage, EdgeStorage, Directionality, char, string);
691 
692                 Graph g;
693 
694                 // Graph layout
695                 //      B
696                 //    / |
697                 //   A  |  C
698                 //      | /
699                 //      D
700 
701                 auto vA = g.addVertex('a');
702                 auto vB = g.addVertex('b');
703                 auto vC = g.addVertex('c');
704                 auto vD = g.addVertex('d');
705 
706                 auto addUniqueEdge = delegate(Graph.VertexDescriptor s, Graph.VertexDescriptor d) {
707                     auto tmp = g.addEdge(s, d, to!string(g[s]) ~ " --> " ~ to!string(g[d]) );
708                     assert(tmp.addedNew, Graph.stringof ~ ": Edge must be unique.");
709                     return tmp.edge;
710                 };
711 
712                 auto eAB = addUniqueEdge(vA, vB);
713                 auto eBC = addUniqueEdge(vB, vC);
714                 auto eCD = addUniqueEdge(vC, vD);
715                 auto eBD = addUniqueEdge(vB, vD);
716 
717                 assert (equal(g.edgesBetween(vA, vB), [eAB])); // TODO: Check for multigraph.
718 
719                 assert (g.edgeCount == 4, "edgeCount should be 4");
720 
721                 g.removeEdge(eBC);
722 
723                 assert (g.edgeCount == 3, "edgeCount should be 3");
724 
725                 checkEdges!Graph(g, "A", vA, [vB], []);
726                 checkEdges!Graph(g, "B", vB, g.IsUndirected ? [vA, vD] : [vD], [vA]);
727                 checkEdges!Graph(g, "C", vC, g.IsUndirected ? [vD] : [vD], []);
728                 checkEdges!Graph(g, "D", vD, g.IsUndirected ? [vB, vC] : [], [vB, vC]);
729 
730                 assert (g[eAB] == "a --> b");
731                 assert (g[eBD] == "b --> d");
732                 assert (g[eCD] == "c --> d");
733             }
734         }
735     }
736 }
737 
738 unittest {
739     writeln("AdjacencyList: Edge properties are mutable.");
740 
741         foreach(VertexStorage; TypeTuple!(VecS, ListS)) {
742         foreach(EdgeStorage; TypeTuple!(VecS, ListS)) {
743             foreach(Directionality; TypeTuple!(DirectedS, UndirectedS, BidirectionalS)) {
744                 alias Graph = AdjacencyList!(VertexStorage, EdgeStorage, Directionality, char, string);
745 
746                 Graph g;
747 
748                 // Graph layout
749                 //      B
750                 //    / |
751                 //   A  |  C
752                 //      | /
753                 //      D
754 
755                 auto vA = g.addVertex('a');
756                 auto vB = g.addVertex('b');
757                 auto vC = g.addVertex('c');
758                 auto vD = g.addVertex('d');
759 
760                 auto addUniqueEdge = delegate(Graph.VertexDescriptor s, Graph.VertexDescriptor d) {
761                     auto tmp = g.addEdge(s, d, to!string(g[s]) ~ " --> " ~ to!string(g[d]) );
762                     assert(tmp.addedNew, Graph.stringof ~ ": Edge must be unique.");
763                     return tmp.edge;
764                 };
765 
766                 auto eAB = addUniqueEdge(vA, vB);
767                 auto eBC = addUniqueEdge(vB, vC);
768                 auto eCD = addUniqueEdge(vC, vD);
769                 auto eBD = addUniqueEdge(vB, vD);
770 
771                 assert (g[eBC] == "b --> c", "Property should be readable");
772                 g[eBC] = "some value";
773                 assert (g[eBC] == "some value");
774             }
775         }
776     }
777 }