COIN-OR::LEMON - Graph Library

source: lemon/test/connectivity_test.cc @ 1126:a30455cd0107

1.1 r1.1.4
Last change on this file since 1126:a30455cd0107 was 1081:f1398882a928, checked in by Alpar Juttner <alpar@…>, 13 years ago

Unify sources

File size: 10.4 KB
Line 
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-2011
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
25using namespace lemon;
26
27
28int 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}
Note: See TracBrowser for help on using the repository browser.