1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
2 * |
2 * |
3 * This file is a part of LEMON, a generic C++ optimization library. |
3 * This file is a part of LEMON, a generic C++ optimization library. |
4 * |
4 * |
5 * Copyright (C) 2003-2009 |
5 * Copyright (C) 2003-2010 |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
8 * |
8 * |
9 * Permission to use, modify and distribute this software is granted |
9 * Permission to use, modify and distribute this software is granted |
10 * provided that this copyright notice appears in all copies. For |
10 * provided that this copyright notice appears in all copies. For |
27 |
27 |
28 int main() |
28 int main() |
29 { |
29 { |
30 typedef ListDigraph Digraph; |
30 typedef ListDigraph Digraph; |
31 typedef Undirector<Digraph> Graph; |
31 typedef Undirector<Digraph> Graph; |
32 |
32 |
33 { |
33 { |
34 Digraph d; |
34 Digraph d; |
35 Digraph::NodeMap<int> order(d); |
35 Digraph::NodeMap<int> order(d); |
36 Graph g(d); |
36 Graph g(d); |
37 |
37 |
38 check(stronglyConnected(d), "The empty digraph is strongly connected"); |
38 check(stronglyConnected(d), "The empty digraph is strongly connected"); |
39 check(countStronglyConnectedComponents(d) == 0, |
39 check(countStronglyConnectedComponents(d) == 0, |
40 "The empty digraph has 0 strongly connected component"); |
40 "The empty digraph has 0 strongly connected component"); |
41 check(connected(g), "The empty graph is connected"); |
41 check(connected(g), "The empty graph is connected"); |
42 check(countConnectedComponents(g) == 0, |
42 check(countConnectedComponents(g) == 0, |
46 check(countBiNodeConnectedComponents(g) == 0, |
46 check(countBiNodeConnectedComponents(g) == 0, |
47 "The empty graph has 0 bi-node-connected component"); |
47 "The empty graph has 0 bi-node-connected component"); |
48 check(biEdgeConnected(g), "The empty graph is bi-edge-connected"); |
48 check(biEdgeConnected(g), "The empty graph is bi-edge-connected"); |
49 check(countBiEdgeConnectedComponents(g) == 0, |
49 check(countBiEdgeConnectedComponents(g) == 0, |
50 "The empty graph has 0 bi-edge-connected component"); |
50 "The empty graph has 0 bi-edge-connected component"); |
51 |
51 |
52 check(dag(d), "The empty digraph is DAG."); |
52 check(dag(d), "The empty digraph is DAG."); |
53 check(checkedTopologicalSort(d, order), "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."); |
54 check(loopFree(d), "The empty digraph is loop-free."); |
55 check(parallelFree(d), "The empty digraph is parallel-free."); |
55 check(parallelFree(d), "The empty digraph is parallel-free."); |
56 check(simpleGraph(d), "The empty digraph is simple."); |
56 check(simpleGraph(d), "The empty digraph is simple."); |
80 check(countBiNodeConnectedComponents(g) == 0, |
80 check(countBiNodeConnectedComponents(g) == 0, |
81 "This graph has 0 bi-node-connected component"); |
81 "This graph has 0 bi-node-connected component"); |
82 check(biEdgeConnected(g), "This graph is bi-edge-connected"); |
82 check(biEdgeConnected(g), "This graph is bi-edge-connected"); |
83 check(countBiEdgeConnectedComponents(g) == 1, |
83 check(countBiEdgeConnectedComponents(g) == 1, |
84 "This graph has 1 bi-edge-connected component"); |
84 "This graph has 1 bi-edge-connected component"); |
85 |
85 |
86 check(dag(d), "This digraph is DAG."); |
86 check(dag(d), "This digraph is DAG."); |
87 check(checkedTopologicalSort(d, order), "This digraph is DAG."); |
87 check(checkedTopologicalSort(d, order), "This digraph is DAG."); |
88 check(loopFree(d), "This digraph is loop-free."); |
88 check(loopFree(d), "This digraph is loop-free."); |
89 check(parallelFree(d), "This digraph is parallel-free."); |
89 check(parallelFree(d), "This digraph is parallel-free."); |
90 check(simpleGraph(d), "This digraph is simple."); |
90 check(simpleGraph(d), "This digraph is simple."); |
99 |
99 |
100 { |
100 { |
101 Digraph d; |
101 Digraph d; |
102 Digraph::NodeMap<int> order(d); |
102 Digraph::NodeMap<int> order(d); |
103 Graph g(d); |
103 Graph g(d); |
104 |
104 |
105 Digraph::Node n1 = d.addNode(); |
105 Digraph::Node n1 = d.addNode(); |
106 Digraph::Node n2 = d.addNode(); |
106 Digraph::Node n2 = d.addNode(); |
107 Digraph::Node n3 = d.addNode(); |
107 Digraph::Node n3 = d.addNode(); |
108 Digraph::Node n4 = d.addNode(); |
108 Digraph::Node n4 = d.addNode(); |
109 Digraph::Node n5 = d.addNode(); |
109 Digraph::Node n5 = d.addNode(); |
110 Digraph::Node n6 = d.addNode(); |
110 Digraph::Node n6 = d.addNode(); |
111 |
111 |
112 d.addArc(n1, n3); |
112 d.addArc(n1, n3); |
113 d.addArc(n3, n2); |
113 d.addArc(n3, n2); |
114 d.addArc(n2, n1); |
114 d.addArc(n2, n1); |
115 d.addArc(n4, n2); |
115 d.addArc(n4, n2); |
116 d.addArc(n4, n3); |
116 d.addArc(n4, n3); |
134 check(!tree(g), "This graph is not tree."); |
134 check(!tree(g), "This graph is not tree."); |
135 check(!bipartite(g), "This graph is not bipartite."); |
135 check(!bipartite(g), "This graph is not bipartite."); |
136 check(loopFree(g), "This graph is loop-free."); |
136 check(loopFree(g), "This graph is loop-free."); |
137 check(!parallelFree(g), "This graph is not parallel-free."); |
137 check(!parallelFree(g), "This graph is not parallel-free."); |
138 check(!simpleGraph(g), "This graph is not simple."); |
138 check(!simpleGraph(g), "This graph is not simple."); |
139 |
139 |
140 d.addArc(n3, n3); |
140 d.addArc(n3, n3); |
141 |
141 |
142 check(!loopFree(d), "This digraph is not loop-free."); |
142 check(!loopFree(d), "This digraph is not loop-free."); |
143 check(!loopFree(g), "This graph is not loop-free."); |
143 check(!loopFree(g), "This graph is not loop-free."); |
144 check(!simpleGraph(d), "This digraph is not simple."); |
144 check(!simpleGraph(d), "This digraph is not simple."); |
145 |
145 |
146 d.addArc(n3, n2); |
146 d.addArc(n3, n2); |
147 |
147 |
148 check(!parallelFree(d), "This digraph is not parallel-free."); |
148 check(!parallelFree(d), "This digraph is not parallel-free."); |
149 } |
149 } |
150 |
150 |
151 { |
151 { |
152 Digraph d; |
152 Digraph d; |
153 Digraph::ArcMap<bool> cutarcs(d, false); |
153 Digraph::ArcMap<bool> cutarcs(d, false); |
154 Graph g(d); |
154 Graph g(d); |
155 |
155 |
156 Digraph::Node n1 = d.addNode(); |
156 Digraph::Node n1 = d.addNode(); |
157 Digraph::Node n2 = d.addNode(); |
157 Digraph::Node n2 = d.addNode(); |
158 Digraph::Node n3 = d.addNode(); |
158 Digraph::Node n3 = d.addNode(); |
159 Digraph::Node n4 = d.addNode(); |
159 Digraph::Node n4 = d.addNode(); |
160 Digraph::Node n5 = d.addNode(); |
160 Digraph::Node n5 = d.addNode(); |
170 d.addArc(n4, n6); |
170 d.addArc(n4, n6); |
171 d.addArc(n2, n5); |
171 d.addArc(n2, n5); |
172 d.addArc(n1, n8); |
172 d.addArc(n1, n8); |
173 d.addArc(n6, n7); |
173 d.addArc(n6, n7); |
174 d.addArc(n7, n6); |
174 d.addArc(n7, n6); |
175 |
175 |
176 check(!stronglyConnected(d), "This digraph is not strongly connected"); |
176 check(!stronglyConnected(d), "This digraph is not strongly connected"); |
177 check(countStronglyConnectedComponents(d) == 3, |
177 check(countStronglyConnectedComponents(d) == 3, |
178 "This digraph has 3 strongly connected components"); |
178 "This digraph has 3 strongly connected components"); |
179 Digraph::NodeMap<int> scomp1(d); |
179 Digraph::NodeMap<int> scomp1(d); |
180 check(stronglyConnectedComponents(d, scomp1) == 3, |
180 check(stronglyConnectedComponents(d, scomp1) == 3, |
233 { |
233 { |
234 // DAG example for topological sort from the book New Algorithms |
234 // DAG example for topological sort from the book New Algorithms |
235 // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein) |
235 // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein) |
236 Digraph d; |
236 Digraph d; |
237 Digraph::NodeMap<int> order(d); |
237 Digraph::NodeMap<int> order(d); |
238 |
238 |
239 Digraph::Node belt = d.addNode(); |
239 Digraph::Node belt = d.addNode(); |
240 Digraph::Node trousers = d.addNode(); |
240 Digraph::Node trousers = d.addNode(); |
241 Digraph::Node necktie = d.addNode(); |
241 Digraph::Node necktie = d.addNode(); |
242 Digraph::Node coat = d.addNode(); |
242 Digraph::Node coat = d.addNode(); |
243 Digraph::Node socks = d.addNode(); |
243 Digraph::Node socks = d.addNode(); |
253 d.addArc(trousers, belt); |
253 d.addArc(trousers, belt); |
254 d.addArc(belt, coat); |
254 d.addArc(belt, coat); |
255 d.addArc(shirt, belt); |
255 d.addArc(shirt, belt); |
256 d.addArc(shirt, necktie); |
256 d.addArc(shirt, necktie); |
257 d.addArc(necktie, coat); |
257 d.addArc(necktie, coat); |
258 |
258 |
259 check(dag(d), "This digraph is DAG."); |
259 check(dag(d), "This digraph is DAG."); |
260 topologicalSort(d, order); |
260 topologicalSort(d, order); |
261 for (Digraph::ArcIt a(d); a != INVALID; ++a) { |
261 for (Digraph::ArcIt a(d); a != INVALID; ++a) { |
262 check(order[d.source(a)] < order[d.target(a)], |
262 check(order[d.source(a)] < order[d.target(a)], |
263 "Wrong topologicalSort()"); |
263 "Wrong topologicalSort()"); |
265 } |
265 } |
266 |
266 |
267 { |
267 { |
268 ListGraph g; |
268 ListGraph g; |
269 ListGraph::NodeMap<bool> map(g); |
269 ListGraph::NodeMap<bool> map(g); |
270 |
270 |
271 ListGraph::Node n1 = g.addNode(); |
271 ListGraph::Node n1 = g.addNode(); |
272 ListGraph::Node n2 = g.addNode(); |
272 ListGraph::Node n2 = g.addNode(); |
273 ListGraph::Node n3 = g.addNode(); |
273 ListGraph::Node n3 = g.addNode(); |
274 ListGraph::Node n4 = g.addNode(); |
274 ListGraph::Node n4 = g.addNode(); |
275 ListGraph::Node n5 = g.addNode(); |
275 ListGraph::Node n5 = g.addNode(); |
281 g.addEdge(n2, n5); |
281 g.addEdge(n2, n5); |
282 g.addEdge(n3, n6); |
282 g.addEdge(n3, n6); |
283 g.addEdge(n4, n6); |
283 g.addEdge(n4, n6); |
284 g.addEdge(n4, n7); |
284 g.addEdge(n4, n7); |
285 g.addEdge(n5, n7); |
285 g.addEdge(n5, n7); |
286 |
286 |
287 check(bipartite(g), "This graph is bipartite"); |
287 check(bipartite(g), "This graph is bipartite"); |
288 check(bipartitePartitions(g, map), "This graph is bipartite"); |
288 check(bipartitePartitions(g, map), "This graph is bipartite"); |
289 |
289 |
290 check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7], |
290 check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7], |
291 "Wrong bipartitePartitions()"); |
291 "Wrong bipartitePartitions()"); |
292 check(map[n3] == map[n4] && map[n3] == map[n5], |
292 check(map[n3] == map[n4] && map[n3] == map[n5], |
293 "Wrong bipartitePartitions()"); |
293 "Wrong bipartitePartitions()"); |
294 } |
294 } |