1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2010
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #include <lemon/connectivity.h>
20 #include <lemon/list_graph.h>
21 #include <lemon/adaptors.h>
23 #include "test_tools.h"
25 using namespace lemon;
30 typedef ListDigraph Digraph;
31 typedef Undirector<Digraph> Graph;
35 Digraph::NodeMap<int> order(d);
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");
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");
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.");
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.");
68 Digraph::NodeMap<int> order(d);
70 Digraph::Node n = d.addNode();
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");
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");
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.");
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.");
102 Digraph::NodeMap<int> order(d);
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();
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");
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.");
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.");
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.");
148 check(!parallelFree(d), "This digraph is not parallel-free.");
153 Digraph::ArcMap<bool> cutarcs(d, false);
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();
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()");
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()");
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;
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()");
234 // DAG example for topological sort from the book New Algorithms
235 // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein)
237 Digraph::NodeMap<int> order(d);
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();
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);
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()");
269 ListGraph::NodeMap<bool> map(g);
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();
287 check(bipartite(g), "This graph is bipartite");
288 check(bipartitePartitions(g, map), "This graph is bipartite");
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()");