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 storeage 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 /*= VertexProperty.init*/) {
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 
404 // ----------------------------------------------------------------------------
405 // Unit Tests
406 // ----------------------------------------------------------------------------
407 
408 unittest {
409     writeln("AdjacencyList: Custom storage type");
410 
411     struct ArrayS {
412         alias IndexType = size_t;
413         enum IndexesAreStable = true;
414 
415         static struct Store(ValueType) {
416             alias Range = ValueType[];
417 
418             auto push(ValueType value) {
419                 size_t rval = _store.length;
420                 _store ~= value;
421                 return PushResult!(typeof(rval))(rval, true);
422             }
423 
424             void erase(IndexType index) {
425                 assert (false, "Not Implemented");
426             }
427 
428             void eraseFrontOfRange(ValueType[] range) {
429                 assert (false, "Not Implemented");
430             }
431 
432             auto indexRange() const {
433                 return iota(0, _store.length);
434             }
435 
436             ref inout(ValueType) get_value(IndexType index) inout {
437                 return _store[index];
438             }
439 
440             @property auto dup() {
441                 return Store(_store.dup);
442             }
443 
444             @property size_t length() const {
445                 return _store.length;
446             }
447 
448             ValueType[] _store;
449 
450             alias ConstRange = const(ValueType)[];
451 
452             alias _store this;
453         }
454     }
455 
456     AdjacencyList!(ArrayS, ArrayS, DirectedS, char, string) g;
457     auto v = g.addVertex('a');
458     assert (g[v] == 'a');
459 }
460 
461 unittest {
462     writeln("AdjacencyList: Adding a vertex with no property.");
463     foreach(VertexStorage; TypeTuple!(VecS, ListS)) {
464         foreach(EdgeStorage; TypeTuple!(VecS, ListS)) {
465             foreach(Directionality; TypeTuple!(DirectedS, UndirectedS, BidirectionalS)) {
466                 AdjacencyList!(VertexStorage, EdgeStorage, Directionality) g;
467                 auto v1 = g.addVertex();
468                 auto v2 = g.addVertex();
469                 auto v3 = g.addVertex();
470 
471                 assert (g.vertexCount == 3,
472                         "Bad vertex count. Exepected 3, got " ~
473                         to!string(g.vertexCount));
474 
475                 foreach(x; zip(g.vertices(), [v1, v2, v3][])) {
476                     assert (x[0] == x[1], "Mismatched vertex descriptors");
477                 }
478             }
479         }
480     }
481 }
482 
483 unittest {
484     writeln("AdjacencyList: Adding a vertex with a property.");
485     foreach(VertexStorage; TypeTuple!(VecS, ListS)) {
486         foreach(EdgeStorage; TypeTuple!(VecS, ListS)) {
487             foreach(Directionality; TypeTuple!(DirectedS, UndirectedS, BidirectionalS)) {
488                 AdjacencyList!(VertexStorage, EdgeStorage, Directionality, string) g;
489                 auto v1 = g.addVertex("alpha");
490                 auto v2 = g.addVertex("beta");
491                 auto v3 = g.addVertex("gamma");
492 
493                 foreach(x; zip(g.vertices(), ["alpha", "beta", "gamma"][])) {
494                     assert (g[x[0]] == x[1], "Mismatched vertex descriptors");
495                 }
496             }
497         }
498     }
499 }
500 
501 unittest {
502     writeln("AdjacencyList: Vertex properties are assignable.");
503     foreach(VertexStorage; TypeTuple!(VecS, ListS)) {
504         foreach(EdgeStorage; TypeTuple!(VecS, ListS)) {
505             foreach(Directionality; TypeTuple!(DirectedS, UndirectedS, BidirectionalS)) {
506                 AdjacencyList!(VertexStorage, EdgeStorage, Directionality, string) g;
507                 auto v1 = g.addVertex("alpha");
508                 auto v2 = g.addVertex("beta");
509                 auto v3 = g.addVertex("gamma");
510 
511                 assert (g[v2] == "beta");
512                 g[v2] = "narf";
513 
514                 foreach(x; zip(g.vertices(), ["alpha", "narf", "gamma"][])) {
515                     assert (g[x[0]] == x[1], "Mismatched vertex properties");
516                 }
517             }
518         }
519     }
520 }
521 
522 unittest {
523     struct Test { int i; }
524 
525     writeln("AdjacencyList: Vertex properties are mutable.");
526     foreach(VertexStorage; TypeTuple!(VecS, ListS)) {
527         foreach(EdgeStorage; TypeTuple!(VecS, ListS)) {
528             foreach(Directionality; TypeTuple!(DirectedS, UndirectedS, BidirectionalS)) {
529                 AdjacencyList!(VertexStorage, EdgeStorage, Directionality, Test) g;
530                 auto v1 = g.addVertex(Test(0));
531                 auto v2 = g.addVertex(Test(1));
532                 auto v3 = g.addVertex(Test(2));
533 
534                 assert (g[v2].i == 1);
535                 g[v2].i = 42;
536                 assert (g[v2].i == 42);
537             }
538         }
539     }
540 }
541 
542 unittest {
543     writeln("AdjacencyList: Erasing a vertex.");
544     foreach(VertexStorage; TypeTuple!(VecS, ListS)) {
545         foreach(EdgeStorage; TypeTuple!(VecS, ListS)) {
546             foreach(Directionality; TypeTuple!(DirectedS, UndirectedS, BidirectionalS)) {
547                 alias Graph = AdjacencyList!(VertexStorage, EdgeStorage, Directionality, char, string);
548                 Graph g;
549 
550                 /* artificial scope for namespacing */ {
551                     auto a = g.addVertex('a');
552                     auto b = g.addVertex('b');
553                     auto c = g.addVertex('c');
554 
555                     auto ac = g.addEdge(a, c, "ac");
556                     auto ca = g.addEdge(c, a, "ca");
557 
558                     g.removeVertex(b);
559                 }
560 
561                 assert (g.vertexCount == 2,
562                     Graph.stringof ~ ": Expected vertex count to be 2, got: " ~
563                     to!string(g.vertexCount));
564 
565                 // assert that we only have the vertices we expect
566                 auto vertices = array(g.vertices());
567                 foreach(x; zip(vertices, ['a', 'c'])) {
568                     assert (g[x[0]] == x[1],
569                         Graph.stringof ~ ": Mismatched vertex descriptors");
570                 }
571 
572                 // assert the a -> c edge still holds
573                 auto a = vertices[0];
574                 auto c = vertices[1];
575                 auto ac = g.outEdges(a).front;
576                 assert (g.source(ac) == a,
577                     Graph.stringof ~ ": Source(ac) should be a");
578 
579                 assert (g.target(ac) == c,
580                     Graph.stringof ~ ": Target(ac) should be c");
581 
582                 // assert the c -> a edge still holds
583                 auto ca = g.outEdges(c).front;
584                 assert (g.source(ca) == c,
585                     Graph.stringof ~ ": Source(ca) should be c");
586 
587                 assert (g.target(ca) == a,
588                     Graph.stringof ~ ": Target(ca) should be a");
589 
590             }
591         }
592     }
593 }
594 
595 version (unittest) {
596     void checkEdges(Graph)(ref Graph g,
597                            string name,
598                            Graph.VertexDescriptor src,
599                            Graph.VertexDescriptor[] outTargets,
600                            Graph.VertexDescriptor[] inTargets) {
601         auto outEdges = array(g.outEdges(src));
602         auto outDegree = g.outDegree(src);
603         assert (outDegree == outTargets.length,
604                 Graph.stringof ~ ": Expected " ~ name ~
605                 " to have out degree of " ~ to!string(outTargets.length) ~
606                 ", got " ~ to!string(outDegree));
607 
608         assert (outEdges.length == outTargets.length,
609                 Graph.stringof ~ ": Expected " ~ name ~ " to have exactly " ~
610                 to!string(outTargets.length) ~ " out edge(s), got " ~
611                 to!string(outEdges.length));
612 
613         foreach (t; outTargets) {
614             assert (any!(e => g.target(e) == t)(outEdges),
615                     Graph.stringof ~ ": Expected target from " ~ name ~
616                     " was not in out edges.");
617         }
618 
619         static if (g.IsBidirectional) {
620             auto inDegree = g.inDegree(src);
621             assert (inDegree == inTargets.length,
622                     Graph.stringof ~ ": Expected " ~ name ~
623                     " to have in degree of " ~ to!string(inTargets.length) ~
624                     ", got " ~ to!string(inDegree));
625 
626             auto inEdges = array(g.inEdges(src));
627             foreach (t; inTargets) {
628                 assert (any!(e => g.source(e) == t)(inEdges),
629                         Graph.stringof ~ ": Expected source in " ~ name ~
630                         " was not in in-edges.");
631             }
632         }
633     }
634 }
635 
636 unittest {
637     writeln("AdjacencyList: Adding edges works as expected.");
638     foreach(VertexStorage; TypeTuple!(VecS, ListS)) {
639         foreach(EdgeStorage; TypeTuple!(VecS, ListS)) {
640             foreach(Directionality; TypeTuple!(DirectedS, UndirectedS, BidirectionalS)) {
641                 alias Graph = AdjacencyList!(VertexStorage, EdgeStorage, Directionality, char, string);
642 
643                 Graph g;
644 
645                 // Graph layout
646                 //      B
647                 //    / | \
648                 //   A  |  C
649                 //      | /
650                 //      D
651 
652                 auto vA = g.addVertex('a');
653                 auto vB = g.addVertex('b');
654                 auto vC = g.addVertex('c');
655                 auto vD = g.addVertex('d');
656 
657                 auto addUniqueEdge = delegate(Graph.VertexDescriptor s, Graph.VertexDescriptor d) {
658                     auto tmp = g.addEdge(s, d, to!string(g[s]) ~ " --> " ~ to!string(g[d]) );
659                     assert(tmp.addedNew, Graph.stringof ~ ": Edge must be unique.");
660                     return tmp.edge;
661                 };
662 
663                 auto eAB = addUniqueEdge(vA, vB);
664                 auto eBC = addUniqueEdge(vB, vC);
665                 auto eCD = addUniqueEdge(vC, vD);
666                 auto eBD = addUniqueEdge(vB, vD);
667 
668                 assert (g.edgeCount == 4, "edgeCount should be 4");
669 
670                 checkEdges!Graph(g, "A", vA, [vB], []);
671                 checkEdges!Graph(g, "B", vB, g.IsUndirected ? [vA, vC, vD] : [vC, vD], [vA]);
672                 checkEdges!Graph(g, "C", vC, g.IsUndirected ? [vB, vD] : [vD], [vB]);
673                 checkEdges!Graph(g, "D", vD, g.IsUndirected ? [vB, vC] : [], [vB, vC]);
674             }
675         }
676     }
677 }
678 
679 unittest {
680     writeln("AdjacencyList: Removing edges works as expected.");
681     foreach(VertexStorage; TypeTuple!(VecS, ListS)) {
682         foreach(EdgeStorage; TypeTuple!(VecS, ListS)) {
683             foreach(Directionality; TypeTuple!(DirectedS, UndirectedS, BidirectionalS)) {
684                 alias Graph = AdjacencyList!(VertexStorage, EdgeStorage, Directionality, char, string);
685 
686                 Graph g;
687 
688                 // Graph layout
689                 //      B
690                 //    / |
691                 //   A  |  C
692                 //      | /
693                 //      D
694 
695                 auto vA = g.addVertex('a');
696                 auto vB = g.addVertex('b');
697                 auto vC = g.addVertex('c');
698                 auto vD = g.addVertex('d');
699 
700                 auto addUniqueEdge = delegate(Graph.VertexDescriptor s, Graph.VertexDescriptor d) {
701                     auto tmp = g.addEdge(s, d, to!string(g[s]) ~ " --> " ~ to!string(g[d]) );
702                     assert(tmp.addedNew, Graph.stringof ~ ": Edge must be unique.");
703                     return tmp.edge;
704                 };
705 
706                 auto eAB = addUniqueEdge(vA, vB);
707                 auto eBC = addUniqueEdge(vB, vC);
708                 auto eCD = addUniqueEdge(vC, vD);
709                 auto eBD = addUniqueEdge(vB, vD);
710 
711                 assert (g.edgeCount == 4, "edgeCount should be 4");
712 
713                 g.removeEdge(eBC);
714 
715                 assert (g.edgeCount == 3, "edgeCount should be 3");
716 
717                 checkEdges!Graph(g, "A", vA, [vB], []);
718                 checkEdges!Graph(g, "B", vB, g.IsUndirected ? [vA, vD] : [vD], [vA]);
719                 checkEdges!Graph(g, "C", vC, g.IsUndirected ? [vD] : [vD], []);
720                 checkEdges!Graph(g, "D", vD, g.IsUndirected ? [vB, vC] : [], [vB, vC]);
721 
722                 assert (g[eAB] == "a --> b");
723                 assert (g[eBD] == "b --> d");
724                 assert (g[eCD] == "c --> d");
725             }
726         }
727     }
728 }
729 
730 unittest {
731     writeln("AdjacencyList: Edge properties are mutable.");
732 
733         foreach(VertexStorage; TypeTuple!(VecS, ListS)) {
734         foreach(EdgeStorage; TypeTuple!(VecS, ListS)) {
735             foreach(Directionality; TypeTuple!(DirectedS, UndirectedS, BidirectionalS)) {
736                 alias Graph = AdjacencyList!(VertexStorage, EdgeStorage, Directionality, char, string);
737 
738                 Graph g;
739 
740                 // Graph layout
741                 //      B
742                 //    / |
743                 //   A  |  C
744                 //      | /
745                 //      D
746 
747                 auto vA = g.addVertex('a');
748                 auto vB = g.addVertex('b');
749                 auto vC = g.addVertex('c');
750                 auto vD = g.addVertex('d');
751 
752                 auto addUniqueEdge = delegate(Graph.VertexDescriptor s, Graph.VertexDescriptor d) {
753                     auto tmp = g.addEdge(s, d, to!string(g[s]) ~ " --> " ~ to!string(g[d]) );
754                     assert(tmp.addedNew, Graph.stringof ~ ": Edge must be unique.");
755                     return tmp.edge;
756                 };
757 
758                 auto eAB = addUniqueEdge(vA, vB);
759                 auto eBC = addUniqueEdge(vB, vC);
760                 auto eCD = addUniqueEdge(vC, vD);
761                 auto eBD = addUniqueEdge(vB, vD);
762 
763                 assert (g[eBC] == "b --> c", "Property should be readable");
764                 g[eBC] = "some value";
765                 assert (g[eBC] == "some value");
766             }
767         }
768     }
769 }