anansi.algorithms.components source code

1 module anansi.algorithms.components;
2 
3 import std.stdio, std.meta;
4 
5 import anansi.algorithms.dfs,
6        anansi.traits,
7        anansi.types;
8 
9 /**
10  * Lists the connected components (a.k.a "islands") of an undirected graph.
11  *
12  * Params:
13  *   GraphT = The type of the graph object to examine. Must model the
14  *            incidence graph concept and be undirected.
15  *   ComponentMapT = The type of the component map to use. Must model a 
16  *                   property map of ints keyed by GraphT vertex 
17  *                   descriptor. 
18  */
19 template connectedComponents(GraphT, ComponentMapT) {
20     static assert (isGraph!GraphT);
21     static assert (GraphT.IsUndirected);
22     static assert (isPropertyMap!(ComponentMapT, GraphT.VertexDescriptor, size_t));
23 
24     /**
25      * Params:
26      *   g = The graph to examine.
27      *   components = The component map to populate.
28      *
29      * Returns: 
30      *   Returns the number of components in the graph.
31      */
32     size_t connectedComponents(ref const(GraphT) g, ref ComponentMapT components) {
33         alias Vertex = GraphT.VertexDescriptor;
34         alias Edge = GraphT.EdgeDescriptor;
35 
36         static struct ComponentRecorder {
37             this(ref size_t count, ref ComponentMapT componentMap) {
38                 _group = &count;
39                 _components = &componentMap;
40             }
41 
42             void startVertex(ref const(GraphT), Vertex v) {
43                 if( (*_group) == size_t.max )
44                     (*_group) = 0;
45                 else
46                     (*_group)++;
47             }
48 
49             void discoverVertex(ref const(GraphT), Vertex v) {
50                 (*_components)[v] = (*_group);
51             }
52 
53             private size_t* _group; 
54             private ComponentMapT* _components;
55 
56             NullVisitor!GraphT impl;
57             alias impl this;
58         } 
59 
60         if( g.vertices.empty )
61             return 0;
62 
63         // Let's try and represent the colour map as an array if we can; it'll
64         // make map access stupidly fast. 
65         static if (is(Vertex == size_t)) {
66             auto colourMap = new Colour[g.vertexCount];
67         }
68         else {
69             Colour[Vertex] colourMap;
70         }
71 
72         size_t count = size_t.max;
73         depthFirstSearch(g, g.vertices.front, colourMap, 
74                          ComponentRecorder(count, components));
75         return count+1;
76     }
77 }
78 
79 // ----------------------------------------------------------------------------
80 //
81 // ----------------------------------------------------------------------------
82 
83 version (unittest) {
84     import std.algorithm, std.conv, std.stdio;
85     import anansi.adjacencylist, anansi.traits;
86 
87     void makeDisconnectedCycles(G)(ref G g, int cycles, int cycleSize) {
88         alias Vertex = G.VertexDescriptor;
89         foreach(i; 0 .. cycles) {
90             Vertex firstVertex = g.addVertex();
91             Vertex prevVertex;
92             Vertex currentVertex = firstVertex;
93             foreach(j; 1 .. cycleSize) {
94                 prevVertex = currentVertex;
95                 currentVertex = g.addVertex();
96                 g.addEdge(prevVertex, currentVertex);
97             }
98             g.addEdge(currentVertex, firstVertex);
99         }
100     }
101 }
102 
103 unittest {
104     writeln("Connected Components: Empty graph should return 0.");
105     alias G = AdjacencyList!(VecS, VecS, UndirectedS);
106     G g;
107     size_t[G.VertexDescriptor] components;
108     auto rval = connectedComponents(g, components);
109 
110     assert (rval == 0, 
111         "connectedComponents() should return 0 for an empty graph.");
112 
113     assert (components.length == 0,
114         "connected components array should be 0 length.");
115 }
116 
117 
118 unittest {
119     writeln("Connected Components: Components should be identified.");
120     // check each supported configuration of storage selectors 
121     foreach(VertexStorage; AliasSeq!(VecS, ListS)) {
122         foreach(EdgeStorage; AliasSeq!(VecS, ListS)) {
123             alias G = AdjacencyList!(VertexStorage, EdgeStorage, UndirectedS);
124             G g;
125             size_t[G.VertexDescriptor] components;
126             makeDisconnectedCycles(g, 5, 10);
127             auto rval = connectedComponents(g, components);
128 
129             assert (rval == 5, 
130                 "connectedComponents should return the number of components discovered.");
131 
132             int[size_t] tally;
133             foreach(k, v; components) { tally[v]++; }
134 
135             assert( all!("a == 10")(tally.values), 
136                 "All components should have size 10." );
137         }
138     }
139 }