COIN-OR::LEMON - Graph Library

source: lemon/test/connectivity_test.cc @ 1265:552e3d1242c6

Last change on this file since 1265:552e3d1242c6 was 1265:552e3d1242c6, checked in by Balazs Dezso <deba@…>, 11 years ago

Fix biNodeConnected() function (#439)

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