COIN-OR::LEMON - Graph Library

source: lemon-main/test/connectivity_test.cc @ 1059:08f2dc76e82e

Last change on this file since 1059:08f2dc76e82e was 998:7fdaa05a69a1, checked in by Alpar Juttner <alpar@…>, 12 years ago

Merge #449 to branches >=1.2

File size: 10.5 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-2010
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    ignore_unused_variable_warning(n);
72
73    check(stronglyConnected(d), "This digraph is strongly connected");
74    check(countStronglyConnectedComponents(d) == 1,
75          "This digraph has 1 strongly connected component");
76    check(connected(g), "This graph is connected");
77    check(countConnectedComponents(g) == 1,
78          "This graph has 1 connected component");
79
80    check(biNodeConnected(g), "This graph is bi-node-connected");
81    check(countBiNodeConnectedComponents(g) == 0,
82          "This graph has 0 bi-node-connected component");
83    check(biEdgeConnected(g), "This graph is bi-edge-connected");
84    check(countBiEdgeConnectedComponents(g) == 1,
85          "This graph has 1 bi-edge-connected component");
86
87    check(dag(d), "This digraph is DAG.");
88    check(checkedTopologicalSort(d, order), "This digraph is DAG.");
89    check(loopFree(d), "This digraph is loop-free.");
90    check(parallelFree(d), "This digraph is parallel-free.");
91    check(simpleGraph(d), "This digraph is simple.");
92
93    check(acyclic(g), "This graph is acyclic.");
94    check(tree(g), "This graph is tree.");
95    check(bipartite(g), "This graph is bipartite.");
96    check(loopFree(g), "This graph is loop-free.");
97    check(parallelFree(g), "This graph is parallel-free.");
98    check(simpleGraph(g), "This graph is simple.");
99  }
100
101  {
102    Digraph d;
103    Digraph::NodeMap<int> order(d);
104    Graph g(d);
105
106    Digraph::Node n1 = d.addNode();
107    Digraph::Node n2 = d.addNode();
108    Digraph::Node n3 = d.addNode();
109    Digraph::Node n4 = d.addNode();
110    Digraph::Node n5 = d.addNode();
111    Digraph::Node n6 = d.addNode();
112
113    d.addArc(n1, n3);
114    d.addArc(n3, n2);
115    d.addArc(n2, n1);
116    d.addArc(n4, n2);
117    d.addArc(n4, n3);
118    d.addArc(n5, n6);
119    d.addArc(n6, n5);
120
121    check(!stronglyConnected(d), "This digraph is not strongly connected");
122    check(countStronglyConnectedComponents(d) == 3,
123          "This digraph has 3 strongly connected components");
124    check(!connected(g), "This graph is not connected");
125    check(countConnectedComponents(g) == 2,
126          "This graph has 2 connected components");
127
128    check(!dag(d), "This digraph is not DAG.");
129    check(!checkedTopologicalSort(d, order), "This digraph is not DAG.");
130    check(loopFree(d), "This digraph is loop-free.");
131    check(parallelFree(d), "This digraph is parallel-free.");
132    check(simpleGraph(d), "This digraph is simple.");
133
134    check(!acyclic(g), "This graph is not acyclic.");
135    check(!tree(g), "This graph is not tree.");
136    check(!bipartite(g), "This graph is not bipartite.");
137    check(loopFree(g), "This graph is loop-free.");
138    check(!parallelFree(g), "This graph is not parallel-free.");
139    check(!simpleGraph(g), "This graph is not simple.");
140
141    d.addArc(n3, n3);
142
143    check(!loopFree(d), "This digraph is not loop-free.");
144    check(!loopFree(g), "This graph is not loop-free.");
145    check(!simpleGraph(d), "This digraph is not simple.");
146
147    d.addArc(n3, n2);
148
149    check(!parallelFree(d), "This digraph is not parallel-free.");
150  }
151
152  {
153    Digraph d;
154    Digraph::ArcMap<bool> cutarcs(d, false);
155    Graph g(d);
156
157    Digraph::Node n1 = d.addNode();
158    Digraph::Node n2 = d.addNode();
159    Digraph::Node n3 = d.addNode();
160    Digraph::Node n4 = d.addNode();
161    Digraph::Node n5 = d.addNode();
162    Digraph::Node n6 = d.addNode();
163    Digraph::Node n7 = d.addNode();
164    Digraph::Node n8 = d.addNode();
165
166    d.addArc(n1, n2);
167    d.addArc(n5, n1);
168    d.addArc(n2, n8);
169    d.addArc(n8, n5);
170    d.addArc(n6, n4);
171    d.addArc(n4, n6);
172    d.addArc(n2, n5);
173    d.addArc(n1, n8);
174    d.addArc(n6, n7);
175    d.addArc(n7, n6);
176
177    check(!stronglyConnected(d), "This digraph is not strongly connected");
178    check(countStronglyConnectedComponents(d) == 3,
179          "This digraph has 3 strongly connected components");
180    Digraph::NodeMap<int> scomp1(d);
181    check(stronglyConnectedComponents(d, scomp1) == 3,
182          "This digraph has 3 strongly connected components");
183    check(scomp1[n1] != scomp1[n3] && scomp1[n1] != scomp1[n4] &&
184          scomp1[n3] != scomp1[n4], "Wrong stronglyConnectedComponents()");
185    check(scomp1[n1] == scomp1[n2] && scomp1[n1] == scomp1[n5] &&
186          scomp1[n1] == scomp1[n8], "Wrong stronglyConnectedComponents()");
187    check(scomp1[n4] == scomp1[n6] && scomp1[n4] == scomp1[n7],
188          "Wrong stronglyConnectedComponents()");
189    Digraph::ArcMap<bool> scut1(d, false);
190    check(stronglyConnectedCutArcs(d, scut1) == 0,
191          "This digraph has 0 strongly connected cut arc.");
192    for (Digraph::ArcIt a(d); a != INVALID; ++a) {
193      check(!scut1[a], "Wrong stronglyConnectedCutArcs()");
194    }
195
196    check(!connected(g), "This graph is not connected");
197    check(countConnectedComponents(g) == 3,
198          "This graph has 3 connected components");
199    Graph::NodeMap<int> comp(g);
200    check(connectedComponents(g, comp) == 3,
201          "This graph has 3 connected components");
202    check(comp[n1] != comp[n3] && comp[n1] != comp[n4] &&
203          comp[n3] != comp[n4], "Wrong connectedComponents()");
204    check(comp[n1] == comp[n2] && comp[n1] == comp[n5] &&
205          comp[n1] == comp[n8], "Wrong connectedComponents()");
206    check(comp[n4] == comp[n6] && comp[n4] == comp[n7],
207          "Wrong connectedComponents()");
208
209    cutarcs[d.addArc(n3, n1)] = true;
210    cutarcs[d.addArc(n3, n5)] = true;
211    cutarcs[d.addArc(n3, n8)] = true;
212    cutarcs[d.addArc(n8, n6)] = true;
213    cutarcs[d.addArc(n8, n7)] = true;
214
215    check(!stronglyConnected(d), "This digraph is not strongly connected");
216    check(countStronglyConnectedComponents(d) == 3,
217          "This digraph has 3 strongly connected components");
218    Digraph::NodeMap<int> scomp2(d);
219    check(stronglyConnectedComponents(d, scomp2) == 3,
220          "This digraph has 3 strongly connected components");
221    check(scomp2[n3] == 0, "Wrong stronglyConnectedComponents()");
222    check(scomp2[n1] == 1 && scomp2[n2] == 1 && scomp2[n5] == 1 &&
223          scomp2[n8] == 1, "Wrong stronglyConnectedComponents()");
224    check(scomp2[n4] == 2 && scomp2[n6] == 2 && scomp2[n7] == 2,
225          "Wrong stronglyConnectedComponents()");
226    Digraph::ArcMap<bool> scut2(d, false);
227    check(stronglyConnectedCutArcs(d, scut2) == 5,
228          "This digraph has 5 strongly connected cut arcs.");
229    for (Digraph::ArcIt a(d); a != INVALID; ++a) {
230      check(scut2[a] == cutarcs[a], "Wrong stronglyConnectedCutArcs()");
231    }
232  }
233
234  {
235    // DAG example for topological sort from the book New Algorithms
236    // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein)
237    Digraph d;
238    Digraph::NodeMap<int> order(d);
239
240    Digraph::Node belt = d.addNode();
241    Digraph::Node trousers = d.addNode();
242    Digraph::Node necktie = d.addNode();
243    Digraph::Node coat = d.addNode();
244    Digraph::Node socks = d.addNode();
245    Digraph::Node shirt = d.addNode();
246    Digraph::Node shoe = d.addNode();
247    Digraph::Node watch = d.addNode();
248    Digraph::Node pants = d.addNode();
249    ignore_unused_variable_warning(watch);
250
251    d.addArc(socks, shoe);
252    d.addArc(pants, shoe);
253    d.addArc(pants, trousers);
254    d.addArc(trousers, shoe);
255    d.addArc(trousers, belt);
256    d.addArc(belt, coat);
257    d.addArc(shirt, belt);
258    d.addArc(shirt, necktie);
259    d.addArc(necktie, coat);
260
261    check(dag(d), "This digraph is DAG.");
262    topologicalSort(d, order);
263    for (Digraph::ArcIt a(d); a != INVALID; ++a) {
264      check(order[d.source(a)] < order[d.target(a)],
265            "Wrong topologicalSort()");
266    }
267  }
268
269  {
270    ListGraph g;
271    ListGraph::NodeMap<bool> map(g);
272
273    ListGraph::Node n1 = g.addNode();
274    ListGraph::Node n2 = g.addNode();
275    ListGraph::Node n3 = g.addNode();
276    ListGraph::Node n4 = g.addNode();
277    ListGraph::Node n5 = g.addNode();
278    ListGraph::Node n6 = g.addNode();
279    ListGraph::Node n7 = g.addNode();
280
281    g.addEdge(n1, n3);
282    g.addEdge(n1, n4);
283    g.addEdge(n2, n5);
284    g.addEdge(n3, n6);
285    g.addEdge(n4, n6);
286    g.addEdge(n4, n7);
287    g.addEdge(n5, n7);
288
289    check(bipartite(g), "This graph is bipartite");
290    check(bipartitePartitions(g, map), "This graph is bipartite");
291
292    check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],
293          "Wrong bipartitePartitions()");
294    check(map[n3] == map[n4] && map[n3] == map[n5],
295          "Wrong bipartitePartitions()");
296  }
297
298  return 0;
299}
Note: See TracBrowser for help on using the repository browser.