|
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library. |
|
4 * |
|
5 * Copyright (C) 2003-2009 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #include <lemon/connectivity.h> |
|
20 #include <lemon/list_graph.h> |
|
21 #include <lemon/adaptors.h> |
|
22 |
|
23 #include "test_tools.h" |
|
24 |
|
25 using namespace lemon; |
|
26 |
|
27 |
|
28 int main() |
|
29 { |
|
30 typedef ListDigraph Digraph; |
|
31 typedef Undirector<Digraph> Graph; |
|
32 |
|
33 { |
|
34 Digraph d; |
|
35 Digraph::NodeMap<int> order(d); |
|
36 Graph g(d); |
|
37 |
|
38 check(stronglyConnected(d), "The empty digraph is strongly connected"); |
|
39 check(countStronglyConnectedComponents(d) == 0, |
|
40 "The empty digraph has 0 strongly connected component"); |
|
41 check(connected(g), "The empty graph is connected"); |
|
42 check(countConnectedComponents(g) == 0, |
|
43 "The empty graph has 0 connected component"); |
|
44 |
|
45 check(biNodeConnected(g), "The empty graph is bi-node-connected"); |
|
46 check(countBiNodeConnectedComponents(g) == 0, |
|
47 "The empty graph has 0 bi-node-connected component"); |
|
48 check(biEdgeConnected(g), "The empty graph is bi-edge-connected"); |
|
49 check(countBiEdgeConnectedComponents(g) == 0, |
|
50 "The empty graph has 0 bi-edge-connected component"); |
|
51 |
|
52 check(dag(d), "The empty digraph is DAG."); |
|
53 check(checkedTopologicalSort(d, order), "The empty digraph is DAG."); |
|
54 check(loopFree(d), "The empty digraph is loop-free."); |
|
55 check(parallelFree(d), "The empty digraph is parallel-free."); |
|
56 check(simpleGraph(d), "The empty digraph is simple."); |
|
57 |
|
58 check(acyclic(g), "The empty graph is acyclic."); |
|
59 check(tree(g), "The empty graph is tree."); |
|
60 check(bipartite(g), "The empty graph is bipartite."); |
|
61 check(loopFree(g), "The empty graph is loop-free."); |
|
62 check(parallelFree(g), "The empty graph is parallel-free."); |
|
63 check(simpleGraph(g), "The empty graph is simple."); |
|
64 } |
|
65 |
|
66 { |
|
67 Digraph d; |
|
68 Digraph::NodeMap<int> order(d); |
|
69 Graph g(d); |
|
70 Digraph::Node n = d.addNode(); |
|
71 |
|
72 check(stronglyConnected(d), "This digraph is strongly connected"); |
|
73 check(countStronglyConnectedComponents(d) == 1, |
|
74 "This digraph has 1 strongly connected component"); |
|
75 check(connected(g), "This graph is connected"); |
|
76 check(countConnectedComponents(g) == 1, |
|
77 "This graph has 1 connected component"); |
|
78 |
|
79 check(biNodeConnected(g), "This graph is bi-node-connected"); |
|
80 check(countBiNodeConnectedComponents(g) == 0, |
|
81 "This graph has 0 bi-node-connected component"); |
|
82 check(biEdgeConnected(g), "This graph is bi-edge-connected"); |
|
83 check(countBiEdgeConnectedComponents(g) == 1, |
|
84 "This graph has 1 bi-edge-connected component"); |
|
85 |
|
86 check(dag(d), "This digraph is DAG."); |
|
87 check(checkedTopologicalSort(d, order), "This digraph is DAG."); |
|
88 check(loopFree(d), "This digraph is loop-free."); |
|
89 check(parallelFree(d), "This digraph is parallel-free."); |
|
90 check(simpleGraph(d), "This digraph is simple."); |
|
91 |
|
92 check(acyclic(g), "This graph is acyclic."); |
|
93 check(tree(g), "This graph is tree."); |
|
94 check(bipartite(g), "This graph is bipartite."); |
|
95 check(loopFree(g), "This graph is loop-free."); |
|
96 check(parallelFree(g), "This graph is parallel-free."); |
|
97 check(simpleGraph(g), "This graph is simple."); |
|
98 } |
|
99 |
|
100 { |
|
101 Digraph d; |
|
102 Digraph::NodeMap<int> order(d); |
|
103 Graph g(d); |
|
104 |
|
105 Digraph::Node n1 = d.addNode(); |
|
106 Digraph::Node n2 = d.addNode(); |
|
107 Digraph::Node n3 = d.addNode(); |
|
108 Digraph::Node n4 = d.addNode(); |
|
109 Digraph::Node n5 = d.addNode(); |
|
110 Digraph::Node n6 = d.addNode(); |
|
111 |
|
112 d.addArc(n1, n3); |
|
113 d.addArc(n3, n2); |
|
114 d.addArc(n2, n1); |
|
115 d.addArc(n4, n2); |
|
116 d.addArc(n4, n3); |
|
117 d.addArc(n5, n6); |
|
118 d.addArc(n6, n5); |
|
119 |
|
120 check(!stronglyConnected(d), "This digraph is not strongly connected"); |
|
121 check(countStronglyConnectedComponents(d) == 3, |
|
122 "This digraph has 3 strongly connected components"); |
|
123 check(!connected(g), "This graph is not connected"); |
|
124 check(countConnectedComponents(g) == 2, |
|
125 "This graph has 2 connected components"); |
|
126 |
|
127 check(!dag(d), "This digraph is not DAG."); |
|
128 check(!checkedTopologicalSort(d, order), "This digraph is not DAG."); |
|
129 check(loopFree(d), "This digraph is loop-free."); |
|
130 check(parallelFree(d), "This digraph is parallel-free."); |
|
131 check(simpleGraph(d), "This digraph is simple."); |
|
132 |
|
133 check(!acyclic(g), "This graph is not acyclic."); |
|
134 check(!tree(g), "This graph is not tree."); |
|
135 check(!bipartite(g), "This graph is not bipartite."); |
|
136 check(loopFree(g), "This graph is loop-free."); |
|
137 check(!parallelFree(g), "This graph is not parallel-free."); |
|
138 check(!simpleGraph(g), "This graph is not simple."); |
|
139 |
|
140 d.addArc(n3, n3); |
|
141 |
|
142 check(!loopFree(d), "This digraph is not loop-free."); |
|
143 check(!loopFree(g), "This graph is not loop-free."); |
|
144 check(!simpleGraph(d), "This digraph is not simple."); |
|
145 |
|
146 d.addArc(n3, n2); |
|
147 |
|
148 check(!parallelFree(d), "This digraph is not parallel-free."); |
|
149 } |
|
150 |
|
151 { |
|
152 Digraph d; |
|
153 Digraph::ArcMap<bool> cutarcs(d, false); |
|
154 Graph g(d); |
|
155 |
|
156 Digraph::Node n1 = d.addNode(); |
|
157 Digraph::Node n2 = d.addNode(); |
|
158 Digraph::Node n3 = d.addNode(); |
|
159 Digraph::Node n4 = d.addNode(); |
|
160 Digraph::Node n5 = d.addNode(); |
|
161 Digraph::Node n6 = d.addNode(); |
|
162 Digraph::Node n7 = d.addNode(); |
|
163 Digraph::Node n8 = d.addNode(); |
|
164 |
|
165 d.addArc(n1, n2); |
|
166 d.addArc(n5, n1); |
|
167 d.addArc(n2, n8); |
|
168 d.addArc(n8, n5); |
|
169 d.addArc(n6, n4); |
|
170 d.addArc(n4, n6); |
|
171 d.addArc(n2, n5); |
|
172 d.addArc(n1, n8); |
|
173 d.addArc(n6, n7); |
|
174 d.addArc(n7, n6); |
|
175 |
|
176 check(!stronglyConnected(d), "This digraph is not strongly connected"); |
|
177 check(countStronglyConnectedComponents(d) == 3, |
|
178 "This digraph has 3 strongly connected components"); |
|
179 Digraph::NodeMap<int> scomp1(d); |
|
180 check(stronglyConnectedComponents(d, scomp1) == 3, |
|
181 "This digraph has 3 strongly connected components"); |
|
182 check(scomp1[n1] != scomp1[n3] && scomp1[n1] != scomp1[n4] && |
|
183 scomp1[n3] != scomp1[n4], "Wrong stronglyConnectedComponents()"); |
|
184 check(scomp1[n1] == scomp1[n2] && scomp1[n1] == scomp1[n5] && |
|
185 scomp1[n1] == scomp1[n8], "Wrong stronglyConnectedComponents()"); |
|
186 check(scomp1[n4] == scomp1[n6] && scomp1[n4] == scomp1[n7], |
|
187 "Wrong stronglyConnectedComponents()"); |
|
188 Digraph::ArcMap<bool> scut1(d, false); |
|
189 check(stronglyConnectedCutArcs(d, scut1) == 0, |
|
190 "This digraph has 0 strongly connected cut arc."); |
|
191 for (Digraph::ArcIt a(d); a != INVALID; ++a) { |
|
192 check(!scut1[a], "Wrong stronglyConnectedCutArcs()"); |
|
193 } |
|
194 |
|
195 check(!connected(g), "This graph is not connected"); |
|
196 check(countConnectedComponents(g) == 3, |
|
197 "This graph has 3 connected components"); |
|
198 Graph::NodeMap<int> comp(g); |
|
199 check(connectedComponents(g, comp) == 3, |
|
200 "This graph has 3 connected components"); |
|
201 check(comp[n1] != comp[n3] && comp[n1] != comp[n4] && |
|
202 comp[n3] != comp[n4], "Wrong connectedComponents()"); |
|
203 check(comp[n1] == comp[n2] && comp[n1] == comp[n5] && |
|
204 comp[n1] == comp[n8], "Wrong connectedComponents()"); |
|
205 check(comp[n4] == comp[n6] && comp[n4] == comp[n7], |
|
206 "Wrong connectedComponents()"); |
|
207 |
|
208 cutarcs[d.addArc(n3, n1)] = true; |
|
209 cutarcs[d.addArc(n3, n5)] = true; |
|
210 cutarcs[d.addArc(n3, n8)] = true; |
|
211 cutarcs[d.addArc(n8, n6)] = true; |
|
212 cutarcs[d.addArc(n8, n7)] = true; |
|
213 |
|
214 check(!stronglyConnected(d), "This digraph is not strongly connected"); |
|
215 check(countStronglyConnectedComponents(d) == 3, |
|
216 "This digraph has 3 strongly connected components"); |
|
217 Digraph::NodeMap<int> scomp2(d); |
|
218 check(stronglyConnectedComponents(d, scomp2) == 3, |
|
219 "This digraph has 3 strongly connected components"); |
|
220 check(scomp2[n3] == 0, "Wrong stronglyConnectedComponents()"); |
|
221 check(scomp2[n1] == 1 && scomp2[n2] == 1 && scomp2[n5] == 1 && |
|
222 scomp2[n8] == 1, "Wrong stronglyConnectedComponents()"); |
|
223 check(scomp2[n4] == 2 && scomp2[n6] == 2 && scomp2[n7] == 2, |
|
224 "Wrong stronglyConnectedComponents()"); |
|
225 Digraph::ArcMap<bool> scut2(d, false); |
|
226 check(stronglyConnectedCutArcs(d, scut2) == 5, |
|
227 "This digraph has 5 strongly connected cut arcs."); |
|
228 for (Digraph::ArcIt a(d); a != INVALID; ++a) { |
|
229 check(scut2[a] == cutarcs[a], "Wrong stronglyConnectedCutArcs()"); |
|
230 } |
|
231 } |
|
232 |
|
233 { |
|
234 // DAG example for topological sort from the book New Algorithms |
|
235 // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein) |
|
236 Digraph d; |
|
237 Digraph::NodeMap<int> order(d); |
|
238 |
|
239 Digraph::Node belt = d.addNode(); |
|
240 Digraph::Node trousers = d.addNode(); |
|
241 Digraph::Node necktie = d.addNode(); |
|
242 Digraph::Node coat = d.addNode(); |
|
243 Digraph::Node socks = d.addNode(); |
|
244 Digraph::Node shirt = d.addNode(); |
|
245 Digraph::Node shoe = d.addNode(); |
|
246 Digraph::Node watch = d.addNode(); |
|
247 Digraph::Node pants = d.addNode(); |
|
248 |
|
249 d.addArc(socks, shoe); |
|
250 d.addArc(pants, shoe); |
|
251 d.addArc(pants, trousers); |
|
252 d.addArc(trousers, shoe); |
|
253 d.addArc(trousers, belt); |
|
254 d.addArc(belt, coat); |
|
255 d.addArc(shirt, belt); |
|
256 d.addArc(shirt, necktie); |
|
257 d.addArc(necktie, coat); |
|
258 |
|
259 check(dag(d), "This digraph is DAG."); |
|
260 topologicalSort(d, order); |
|
261 for (Digraph::ArcIt a(d); a != INVALID; ++a) { |
|
262 check(order[d.source(a)] < order[d.target(a)], |
|
263 "Wrong topologicalSort()"); |
|
264 } |
|
265 } |
|
266 |
|
267 { |
|
268 ListGraph g; |
|
269 ListGraph::NodeMap<bool> map(g); |
|
270 |
|
271 ListGraph::Node n1 = g.addNode(); |
|
272 ListGraph::Node n2 = g.addNode(); |
|
273 ListGraph::Node n3 = g.addNode(); |
|
274 ListGraph::Node n4 = g.addNode(); |
|
275 ListGraph::Node n5 = g.addNode(); |
|
276 ListGraph::Node n6 = g.addNode(); |
|
277 ListGraph::Node n7 = g.addNode(); |
|
278 |
|
279 g.addEdge(n1, n3); |
|
280 g.addEdge(n1, n4); |
|
281 g.addEdge(n2, n5); |
|
282 g.addEdge(n3, n6); |
|
283 g.addEdge(n4, n6); |
|
284 g.addEdge(n4, n7); |
|
285 g.addEdge(n5, n7); |
|
286 |
|
287 check(bipartite(g), "This graph is bipartite"); |
|
288 check(bipartitePartitions(g, map), "This graph is bipartite"); |
|
289 |
|
290 check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7], |
|
291 "Wrong bipartitePartitions()"); |
|
292 check(map[n3] == map[n4] && map[n3] == map[n5], |
|
293 "Wrong bipartitePartitions()"); |
|
294 } |
|
295 |
|
296 return 0; |
|
297 } |