1.1 --- a/test/CMakeLists.txt Wed May 06 14:44:05 2009 +0200
1.2 +++ b/test/CMakeLists.txt Wed May 06 14:46:05 2009 +0200
1.3 @@ -9,6 +9,7 @@
1.4 adaptors_test
1.5 bfs_test
1.6 circulation_test
1.7 + connectivity_test
1.8 counter_test
1.9 dfs_test
1.10 digraph_test
2.1 --- a/test/Makefile.am Wed May 06 14:44:05 2009 +0200
2.2 +++ b/test/Makefile.am Wed May 06 14:46:05 2009 +0200
2.3 @@ -9,6 +9,7 @@
2.4 test/adaptors_test \
2.5 test/bfs_test \
2.6 test/circulation_test \
2.7 + test/connectivity_test \
2.8 test/counter_test \
2.9 test/dfs_test \
2.10 test/digraph_test \
2.11 @@ -54,6 +55,7 @@
2.12 test_bfs_test_SOURCES = test/bfs_test.cc
2.13 test_circulation_test_SOURCES = test/circulation_test.cc
2.14 test_counter_test_SOURCES = test/counter_test.cc
2.15 +test_connectivity_test_SOURCES = test/connectivity_test.cc
2.16 test_dfs_test_SOURCES = test/dfs_test.cc
2.17 test_digraph_test_SOURCES = test/digraph_test.cc
2.18 test_dijkstra_test_SOURCES = test/dijkstra_test.cc
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/test/connectivity_test.cc Wed May 06 14:46:05 2009 +0200
3.3 @@ -0,0 +1,297 @@
3.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
3.5 + *
3.6 + * This file is a part of LEMON, a generic C++ optimization library.
3.7 + *
3.8 + * Copyright (C) 2003-2009
3.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
3.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
3.11 + *
3.12 + * Permission to use, modify and distribute this software is granted
3.13 + * provided that this copyright notice appears in all copies. For
3.14 + * precise terms see the accompanying LICENSE file.
3.15 + *
3.16 + * This software is provided "AS IS" with no warranty of any kind,
3.17 + * express or implied, and with no claim as to its suitability for any
3.18 + * purpose.
3.19 + *
3.20 + */
3.21 +
3.22 +#include <lemon/connectivity.h>
3.23 +#include <lemon/list_graph.h>
3.24 +#include <lemon/adaptors.h>
3.25 +
3.26 +#include "test_tools.h"
3.27 +
3.28 +using namespace lemon;
3.29 +
3.30 +
3.31 +int main()
3.32 +{
3.33 + typedef ListDigraph Digraph;
3.34 + typedef Undirector<Digraph> Graph;
3.35 +
3.36 + {
3.37 + Digraph d;
3.38 + Digraph::NodeMap<int> order(d);
3.39 + Graph g(d);
3.40 +
3.41 + check(stronglyConnected(d), "The empty digraph is strongly connected");
3.42 + check(countStronglyConnectedComponents(d) == 0,
3.43 + "The empty digraph has 0 strongly connected component");
3.44 + check(connected(g), "The empty graph is connected");
3.45 + check(countConnectedComponents(g) == 0,
3.46 + "The empty graph has 0 connected component");
3.47 +
3.48 + check(biNodeConnected(g), "The empty graph is bi-node-connected");
3.49 + check(countBiNodeConnectedComponents(g) == 0,
3.50 + "The empty graph has 0 bi-node-connected component");
3.51 + check(biEdgeConnected(g), "The empty graph is bi-edge-connected");
3.52 + check(countBiEdgeConnectedComponents(g) == 0,
3.53 + "The empty graph has 0 bi-edge-connected component");
3.54 +
3.55 + check(dag(d), "The empty digraph is DAG.");
3.56 + check(checkedTopologicalSort(d, order), "The empty digraph is DAG.");
3.57 + check(loopFree(d), "The empty digraph is loop-free.");
3.58 + check(parallelFree(d), "The empty digraph is parallel-free.");
3.59 + check(simpleGraph(d), "The empty digraph is simple.");
3.60 +
3.61 + check(acyclic(g), "The empty graph is acyclic.");
3.62 + check(tree(g), "The empty graph is tree.");
3.63 + check(bipartite(g), "The empty graph is bipartite.");
3.64 + check(loopFree(g), "The empty graph is loop-free.");
3.65 + check(parallelFree(g), "The empty graph is parallel-free.");
3.66 + check(simpleGraph(g), "The empty graph is simple.");
3.67 + }
3.68 +
3.69 + {
3.70 + Digraph d;
3.71 + Digraph::NodeMap<int> order(d);
3.72 + Graph g(d);
3.73 + Digraph::Node n = d.addNode();
3.74 +
3.75 + check(stronglyConnected(d), "This digraph is strongly connected");
3.76 + check(countStronglyConnectedComponents(d) == 1,
3.77 + "This digraph has 1 strongly connected component");
3.78 + check(connected(g), "This graph is connected");
3.79 + check(countConnectedComponents(g) == 1,
3.80 + "This graph has 1 connected component");
3.81 +
3.82 + check(biNodeConnected(g), "This graph is bi-node-connected");
3.83 + check(countBiNodeConnectedComponents(g) == 0,
3.84 + "This graph has 0 bi-node-connected component");
3.85 + check(biEdgeConnected(g), "This graph is bi-edge-connected");
3.86 + check(countBiEdgeConnectedComponents(g) == 1,
3.87 + "This graph has 1 bi-edge-connected component");
3.88 +
3.89 + check(dag(d), "This digraph is DAG.");
3.90 + check(checkedTopologicalSort(d, order), "This digraph is DAG.");
3.91 + check(loopFree(d), "This digraph is loop-free.");
3.92 + check(parallelFree(d), "This digraph is parallel-free.");
3.93 + check(simpleGraph(d), "This digraph is simple.");
3.94 +
3.95 + check(acyclic(g), "This graph is acyclic.");
3.96 + check(tree(g), "This graph is tree.");
3.97 + check(bipartite(g), "This graph is bipartite.");
3.98 + check(loopFree(g), "This graph is loop-free.");
3.99 + check(parallelFree(g), "This graph is parallel-free.");
3.100 + check(simpleGraph(g), "This graph is simple.");
3.101 + }
3.102 +
3.103 + {
3.104 + Digraph d;
3.105 + Digraph::NodeMap<int> order(d);
3.106 + Graph g(d);
3.107 +
3.108 + Digraph::Node n1 = d.addNode();
3.109 + Digraph::Node n2 = d.addNode();
3.110 + Digraph::Node n3 = d.addNode();
3.111 + Digraph::Node n4 = d.addNode();
3.112 + Digraph::Node n5 = d.addNode();
3.113 + Digraph::Node n6 = d.addNode();
3.114 +
3.115 + d.addArc(n1, n3);
3.116 + d.addArc(n3, n2);
3.117 + d.addArc(n2, n1);
3.118 + d.addArc(n4, n2);
3.119 + d.addArc(n4, n3);
3.120 + d.addArc(n5, n6);
3.121 + d.addArc(n6, n5);
3.122 +
3.123 + check(!stronglyConnected(d), "This digraph is not strongly connected");
3.124 + check(countStronglyConnectedComponents(d) == 3,
3.125 + "This digraph has 3 strongly connected components");
3.126 + check(!connected(g), "This graph is not connected");
3.127 + check(countConnectedComponents(g) == 2,
3.128 + "This graph has 2 connected components");
3.129 +
3.130 + check(!dag(d), "This digraph is not DAG.");
3.131 + check(!checkedTopologicalSort(d, order), "This digraph is not DAG.");
3.132 + check(loopFree(d), "This digraph is loop-free.");
3.133 + check(parallelFree(d), "This digraph is parallel-free.");
3.134 + check(simpleGraph(d), "This digraph is simple.");
3.135 +
3.136 + check(!acyclic(g), "This graph is not acyclic.");
3.137 + check(!tree(g), "This graph is not tree.");
3.138 + check(!bipartite(g), "This graph is not bipartite.");
3.139 + check(loopFree(g), "This graph is loop-free.");
3.140 + check(!parallelFree(g), "This graph is not parallel-free.");
3.141 + check(!simpleGraph(g), "This graph is not simple.");
3.142 +
3.143 + d.addArc(n3, n3);
3.144 +
3.145 + check(!loopFree(d), "This digraph is not loop-free.");
3.146 + check(!loopFree(g), "This graph is not loop-free.");
3.147 + check(!simpleGraph(d), "This digraph is not simple.");
3.148 +
3.149 + d.addArc(n3, n2);
3.150 +
3.151 + check(!parallelFree(d), "This digraph is not parallel-free.");
3.152 + }
3.153 +
3.154 + {
3.155 + Digraph d;
3.156 + Digraph::ArcMap<bool> cutarcs(d, false);
3.157 + Graph g(d);
3.158 +
3.159 + Digraph::Node n1 = d.addNode();
3.160 + Digraph::Node n2 = d.addNode();
3.161 + Digraph::Node n3 = d.addNode();
3.162 + Digraph::Node n4 = d.addNode();
3.163 + Digraph::Node n5 = d.addNode();
3.164 + Digraph::Node n6 = d.addNode();
3.165 + Digraph::Node n7 = d.addNode();
3.166 + Digraph::Node n8 = d.addNode();
3.167 +
3.168 + d.addArc(n1, n2);
3.169 + d.addArc(n5, n1);
3.170 + d.addArc(n2, n8);
3.171 + d.addArc(n8, n5);
3.172 + d.addArc(n6, n4);
3.173 + d.addArc(n4, n6);
3.174 + d.addArc(n2, n5);
3.175 + d.addArc(n1, n8);
3.176 + d.addArc(n6, n7);
3.177 + d.addArc(n7, n6);
3.178 +
3.179 + check(!stronglyConnected(d), "This digraph is not strongly connected");
3.180 + check(countStronglyConnectedComponents(d) == 3,
3.181 + "This digraph has 3 strongly connected components");
3.182 + Digraph::NodeMap<int> scomp1(d);
3.183 + check(stronglyConnectedComponents(d, scomp1) == 3,
3.184 + "This digraph has 3 strongly connected components");
3.185 + check(scomp1[n1] != scomp1[n3] && scomp1[n1] != scomp1[n4] &&
3.186 + scomp1[n3] != scomp1[n4], "Wrong stronglyConnectedComponents()");
3.187 + check(scomp1[n1] == scomp1[n2] && scomp1[n1] == scomp1[n5] &&
3.188 + scomp1[n1] == scomp1[n8], "Wrong stronglyConnectedComponents()");
3.189 + check(scomp1[n4] == scomp1[n6] && scomp1[n4] == scomp1[n7],
3.190 + "Wrong stronglyConnectedComponents()");
3.191 + Digraph::ArcMap<bool> scut1(d, false);
3.192 + check(stronglyConnectedCutArcs(d, scut1) == 0,
3.193 + "This digraph has 0 strongly connected cut arc.");
3.194 + for (Digraph::ArcIt a(d); a != INVALID; ++a) {
3.195 + check(!scut1[a], "Wrong stronglyConnectedCutArcs()");
3.196 + }
3.197 +
3.198 + check(!connected(g), "This graph is not connected");
3.199 + check(countConnectedComponents(g) == 3,
3.200 + "This graph has 3 connected components");
3.201 + Graph::NodeMap<int> comp(g);
3.202 + check(connectedComponents(g, comp) == 3,
3.203 + "This graph has 3 connected components");
3.204 + check(comp[n1] != comp[n3] && comp[n1] != comp[n4] &&
3.205 + comp[n3] != comp[n4], "Wrong connectedComponents()");
3.206 + check(comp[n1] == comp[n2] && comp[n1] == comp[n5] &&
3.207 + comp[n1] == comp[n8], "Wrong connectedComponents()");
3.208 + check(comp[n4] == comp[n6] && comp[n4] == comp[n7],
3.209 + "Wrong connectedComponents()");
3.210 +
3.211 + cutarcs[d.addArc(n3, n1)] = true;
3.212 + cutarcs[d.addArc(n3, n5)] = true;
3.213 + cutarcs[d.addArc(n3, n8)] = true;
3.214 + cutarcs[d.addArc(n8, n6)] = true;
3.215 + cutarcs[d.addArc(n8, n7)] = true;
3.216 +
3.217 + check(!stronglyConnected(d), "This digraph is not strongly connected");
3.218 + check(countStronglyConnectedComponents(d) == 3,
3.219 + "This digraph has 3 strongly connected components");
3.220 + Digraph::NodeMap<int> scomp2(d);
3.221 + check(stronglyConnectedComponents(d, scomp2) == 3,
3.222 + "This digraph has 3 strongly connected components");
3.223 + check(scomp2[n3] == 0, "Wrong stronglyConnectedComponents()");
3.224 + check(scomp2[n1] == 1 && scomp2[n2] == 1 && scomp2[n5] == 1 &&
3.225 + scomp2[n8] == 1, "Wrong stronglyConnectedComponents()");
3.226 + check(scomp2[n4] == 2 && scomp2[n6] == 2 && scomp2[n7] == 2,
3.227 + "Wrong stronglyConnectedComponents()");
3.228 + Digraph::ArcMap<bool> scut2(d, false);
3.229 + check(stronglyConnectedCutArcs(d, scut2) == 5,
3.230 + "This digraph has 5 strongly connected cut arcs.");
3.231 + for (Digraph::ArcIt a(d); a != INVALID; ++a) {
3.232 + check(scut2[a] == cutarcs[a], "Wrong stronglyConnectedCutArcs()");
3.233 + }
3.234 + }
3.235 +
3.236 + {
3.237 + // DAG example for topological sort from the book New Algorithms
3.238 + // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein)
3.239 + Digraph d;
3.240 + Digraph::NodeMap<int> order(d);
3.241 +
3.242 + Digraph::Node belt = d.addNode();
3.243 + Digraph::Node trousers = d.addNode();
3.244 + Digraph::Node necktie = d.addNode();
3.245 + Digraph::Node coat = d.addNode();
3.246 + Digraph::Node socks = d.addNode();
3.247 + Digraph::Node shirt = d.addNode();
3.248 + Digraph::Node shoe = d.addNode();
3.249 + Digraph::Node watch = d.addNode();
3.250 + Digraph::Node pants = d.addNode();
3.251 +
3.252 + d.addArc(socks, shoe);
3.253 + d.addArc(pants, shoe);
3.254 + d.addArc(pants, trousers);
3.255 + d.addArc(trousers, shoe);
3.256 + d.addArc(trousers, belt);
3.257 + d.addArc(belt, coat);
3.258 + d.addArc(shirt, belt);
3.259 + d.addArc(shirt, necktie);
3.260 + d.addArc(necktie, coat);
3.261 +
3.262 + check(dag(d), "This digraph is DAG.");
3.263 + topologicalSort(d, order);
3.264 + for (Digraph::ArcIt a(d); a != INVALID; ++a) {
3.265 + check(order[d.source(a)] < order[d.target(a)],
3.266 + "Wrong topologicalSort()");
3.267 + }
3.268 + }
3.269 +
3.270 + {
3.271 + ListGraph g;
3.272 + ListGraph::NodeMap<bool> map(g);
3.273 +
3.274 + ListGraph::Node n1 = g.addNode();
3.275 + ListGraph::Node n2 = g.addNode();
3.276 + ListGraph::Node n3 = g.addNode();
3.277 + ListGraph::Node n4 = g.addNode();
3.278 + ListGraph::Node n5 = g.addNode();
3.279 + ListGraph::Node n6 = g.addNode();
3.280 + ListGraph::Node n7 = g.addNode();
3.281 +
3.282 + g.addEdge(n1, n3);
3.283 + g.addEdge(n1, n4);
3.284 + g.addEdge(n2, n5);
3.285 + g.addEdge(n3, n6);
3.286 + g.addEdge(n4, n6);
3.287 + g.addEdge(n4, n7);
3.288 + g.addEdge(n5, n7);
3.289 +
3.290 + check(bipartite(g), "This graph is bipartite");
3.291 + check(bipartitePartitions(g, map), "This graph is bipartite");
3.292 +
3.293 + check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],
3.294 + "Wrong bipartitePartitions()");
3.295 + check(map[n3] == map[n4] && map[n3] == map[n5],
3.296 + "Wrong bipartitePartitions()");
3.297 + }
3.298 +
3.299 + return 0;
3.300 +}