1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/test/connectivity_test.cc Thu May 07 12:19:41 2009 +0100
1.3 @@ -0,0 +1,297 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2009
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#include <lemon/connectivity.h>
1.23 +#include <lemon/list_graph.h>
1.24 +#include <lemon/adaptors.h>
1.25 +
1.26 +#include "test_tools.h"
1.27 +
1.28 +using namespace lemon;
1.29 +
1.30 +
1.31 +int main()
1.32 +{
1.33 + typedef ListDigraph Digraph;
1.34 + typedef Undirector<Digraph> Graph;
1.35 +
1.36 + {
1.37 + Digraph d;
1.38 + Digraph::NodeMap<int> order(d);
1.39 + Graph g(d);
1.40 +
1.41 + check(stronglyConnected(d), "The empty digraph is strongly connected");
1.42 + check(countStronglyConnectedComponents(d) == 0,
1.43 + "The empty digraph has 0 strongly connected component");
1.44 + check(connected(g), "The empty graph is connected");
1.45 + check(countConnectedComponents(g) == 0,
1.46 + "The empty graph has 0 connected component");
1.47 +
1.48 + check(biNodeConnected(g), "The empty graph is bi-node-connected");
1.49 + check(countBiNodeConnectedComponents(g) == 0,
1.50 + "The empty graph has 0 bi-node-connected component");
1.51 + check(biEdgeConnected(g), "The empty graph is bi-edge-connected");
1.52 + check(countBiEdgeConnectedComponents(g) == 0,
1.53 + "The empty graph has 0 bi-edge-connected component");
1.54 +
1.55 + check(dag(d), "The empty digraph is DAG.");
1.56 + check(checkedTopologicalSort(d, order), "The empty digraph is DAG.");
1.57 + check(loopFree(d), "The empty digraph is loop-free.");
1.58 + check(parallelFree(d), "The empty digraph is parallel-free.");
1.59 + check(simpleGraph(d), "The empty digraph is simple.");
1.60 +
1.61 + check(acyclic(g), "The empty graph is acyclic.");
1.62 + check(tree(g), "The empty graph is tree.");
1.63 + check(bipartite(g), "The empty graph is bipartite.");
1.64 + check(loopFree(g), "The empty graph is loop-free.");
1.65 + check(parallelFree(g), "The empty graph is parallel-free.");
1.66 + check(simpleGraph(g), "The empty graph is simple.");
1.67 + }
1.68 +
1.69 + {
1.70 + Digraph d;
1.71 + Digraph::NodeMap<int> order(d);
1.72 + Graph g(d);
1.73 + Digraph::Node n = d.addNode();
1.74 +
1.75 + check(stronglyConnected(d), "This digraph is strongly connected");
1.76 + check(countStronglyConnectedComponents(d) == 1,
1.77 + "This digraph has 1 strongly connected component");
1.78 + check(connected(g), "This graph is connected");
1.79 + check(countConnectedComponents(g) == 1,
1.80 + "This graph has 1 connected component");
1.81 +
1.82 + check(biNodeConnected(g), "This graph is bi-node-connected");
1.83 + check(countBiNodeConnectedComponents(g) == 0,
1.84 + "This graph has 0 bi-node-connected component");
1.85 + check(biEdgeConnected(g), "This graph is bi-edge-connected");
1.86 + check(countBiEdgeConnectedComponents(g) == 1,
1.87 + "This graph has 1 bi-edge-connected component");
1.88 +
1.89 + check(dag(d), "This digraph is DAG.");
1.90 + check(checkedTopologicalSort(d, order), "This digraph is DAG.");
1.91 + check(loopFree(d), "This digraph is loop-free.");
1.92 + check(parallelFree(d), "This digraph is parallel-free.");
1.93 + check(simpleGraph(d), "This digraph is simple.");
1.94 +
1.95 + check(acyclic(g), "This graph is acyclic.");
1.96 + check(tree(g), "This graph is tree.");
1.97 + check(bipartite(g), "This graph is bipartite.");
1.98 + check(loopFree(g), "This graph is loop-free.");
1.99 + check(parallelFree(g), "This graph is parallel-free.");
1.100 + check(simpleGraph(g), "This graph is simple.");
1.101 + }
1.102 +
1.103 + {
1.104 + Digraph d;
1.105 + Digraph::NodeMap<int> order(d);
1.106 + Graph g(d);
1.107 +
1.108 + Digraph::Node n1 = d.addNode();
1.109 + Digraph::Node n2 = d.addNode();
1.110 + Digraph::Node n3 = d.addNode();
1.111 + Digraph::Node n4 = d.addNode();
1.112 + Digraph::Node n5 = d.addNode();
1.113 + Digraph::Node n6 = d.addNode();
1.114 +
1.115 + d.addArc(n1, n3);
1.116 + d.addArc(n3, n2);
1.117 + d.addArc(n2, n1);
1.118 + d.addArc(n4, n2);
1.119 + d.addArc(n4, n3);
1.120 + d.addArc(n5, n6);
1.121 + d.addArc(n6, n5);
1.122 +
1.123 + check(!stronglyConnected(d), "This digraph is not strongly connected");
1.124 + check(countStronglyConnectedComponents(d) == 3,
1.125 + "This digraph has 3 strongly connected components");
1.126 + check(!connected(g), "This graph is not connected");
1.127 + check(countConnectedComponents(g) == 2,
1.128 + "This graph has 2 connected components");
1.129 +
1.130 + check(!dag(d), "This digraph is not DAG.");
1.131 + check(!checkedTopologicalSort(d, order), "This digraph is not DAG.");
1.132 + check(loopFree(d), "This digraph is loop-free.");
1.133 + check(parallelFree(d), "This digraph is parallel-free.");
1.134 + check(simpleGraph(d), "This digraph is simple.");
1.135 +
1.136 + check(!acyclic(g), "This graph is not acyclic.");
1.137 + check(!tree(g), "This graph is not tree.");
1.138 + check(!bipartite(g), "This graph is not bipartite.");
1.139 + check(loopFree(g), "This graph is loop-free.");
1.140 + check(!parallelFree(g), "This graph is not parallel-free.");
1.141 + check(!simpleGraph(g), "This graph is not simple.");
1.142 +
1.143 + d.addArc(n3, n3);
1.144 +
1.145 + check(!loopFree(d), "This digraph is not loop-free.");
1.146 + check(!loopFree(g), "This graph is not loop-free.");
1.147 + check(!simpleGraph(d), "This digraph is not simple.");
1.148 +
1.149 + d.addArc(n3, n2);
1.150 +
1.151 + check(!parallelFree(d), "This digraph is not parallel-free.");
1.152 + }
1.153 +
1.154 + {
1.155 + Digraph d;
1.156 + Digraph::ArcMap<bool> cutarcs(d, false);
1.157 + Graph g(d);
1.158 +
1.159 + Digraph::Node n1 = d.addNode();
1.160 + Digraph::Node n2 = d.addNode();
1.161 + Digraph::Node n3 = d.addNode();
1.162 + Digraph::Node n4 = d.addNode();
1.163 + Digraph::Node n5 = d.addNode();
1.164 + Digraph::Node n6 = d.addNode();
1.165 + Digraph::Node n7 = d.addNode();
1.166 + Digraph::Node n8 = d.addNode();
1.167 +
1.168 + d.addArc(n1, n2);
1.169 + d.addArc(n5, n1);
1.170 + d.addArc(n2, n8);
1.171 + d.addArc(n8, n5);
1.172 + d.addArc(n6, n4);
1.173 + d.addArc(n4, n6);
1.174 + d.addArc(n2, n5);
1.175 + d.addArc(n1, n8);
1.176 + d.addArc(n6, n7);
1.177 + d.addArc(n7, n6);
1.178 +
1.179 + check(!stronglyConnected(d), "This digraph is not strongly connected");
1.180 + check(countStronglyConnectedComponents(d) == 3,
1.181 + "This digraph has 3 strongly connected components");
1.182 + Digraph::NodeMap<int> scomp1(d);
1.183 + check(stronglyConnectedComponents(d, scomp1) == 3,
1.184 + "This digraph has 3 strongly connected components");
1.185 + check(scomp1[n1] != scomp1[n3] && scomp1[n1] != scomp1[n4] &&
1.186 + scomp1[n3] != scomp1[n4], "Wrong stronglyConnectedComponents()");
1.187 + check(scomp1[n1] == scomp1[n2] && scomp1[n1] == scomp1[n5] &&
1.188 + scomp1[n1] == scomp1[n8], "Wrong stronglyConnectedComponents()");
1.189 + check(scomp1[n4] == scomp1[n6] && scomp1[n4] == scomp1[n7],
1.190 + "Wrong stronglyConnectedComponents()");
1.191 + Digraph::ArcMap<bool> scut1(d, false);
1.192 + check(stronglyConnectedCutArcs(d, scut1) == 0,
1.193 + "This digraph has 0 strongly connected cut arc.");
1.194 + for (Digraph::ArcIt a(d); a != INVALID; ++a) {
1.195 + check(!scut1[a], "Wrong stronglyConnectedCutArcs()");
1.196 + }
1.197 +
1.198 + check(!connected(g), "This graph is not connected");
1.199 + check(countConnectedComponents(g) == 3,
1.200 + "This graph has 3 connected components");
1.201 + Graph::NodeMap<int> comp(g);
1.202 + check(connectedComponents(g, comp) == 3,
1.203 + "This graph has 3 connected components");
1.204 + check(comp[n1] != comp[n3] && comp[n1] != comp[n4] &&
1.205 + comp[n3] != comp[n4], "Wrong connectedComponents()");
1.206 + check(comp[n1] == comp[n2] && comp[n1] == comp[n5] &&
1.207 + comp[n1] == comp[n8], "Wrong connectedComponents()");
1.208 + check(comp[n4] == comp[n6] && comp[n4] == comp[n7],
1.209 + "Wrong connectedComponents()");
1.210 +
1.211 + cutarcs[d.addArc(n3, n1)] = true;
1.212 + cutarcs[d.addArc(n3, n5)] = true;
1.213 + cutarcs[d.addArc(n3, n8)] = true;
1.214 + cutarcs[d.addArc(n8, n6)] = true;
1.215 + cutarcs[d.addArc(n8, n7)] = true;
1.216 +
1.217 + check(!stronglyConnected(d), "This digraph is not strongly connected");
1.218 + check(countStronglyConnectedComponents(d) == 3,
1.219 + "This digraph has 3 strongly connected components");
1.220 + Digraph::NodeMap<int> scomp2(d);
1.221 + check(stronglyConnectedComponents(d, scomp2) == 3,
1.222 + "This digraph has 3 strongly connected components");
1.223 + check(scomp2[n3] == 0, "Wrong stronglyConnectedComponents()");
1.224 + check(scomp2[n1] == 1 && scomp2[n2] == 1 && scomp2[n5] == 1 &&
1.225 + scomp2[n8] == 1, "Wrong stronglyConnectedComponents()");
1.226 + check(scomp2[n4] == 2 && scomp2[n6] == 2 && scomp2[n7] == 2,
1.227 + "Wrong stronglyConnectedComponents()");
1.228 + Digraph::ArcMap<bool> scut2(d, false);
1.229 + check(stronglyConnectedCutArcs(d, scut2) == 5,
1.230 + "This digraph has 5 strongly connected cut arcs.");
1.231 + for (Digraph::ArcIt a(d); a != INVALID; ++a) {
1.232 + check(scut2[a] == cutarcs[a], "Wrong stronglyConnectedCutArcs()");
1.233 + }
1.234 + }
1.235 +
1.236 + {
1.237 + // DAG example for topological sort from the book New Algorithms
1.238 + // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein)
1.239 + Digraph d;
1.240 + Digraph::NodeMap<int> order(d);
1.241 +
1.242 + Digraph::Node belt = d.addNode();
1.243 + Digraph::Node trousers = d.addNode();
1.244 + Digraph::Node necktie = d.addNode();
1.245 + Digraph::Node coat = d.addNode();
1.246 + Digraph::Node socks = d.addNode();
1.247 + Digraph::Node shirt = d.addNode();
1.248 + Digraph::Node shoe = d.addNode();
1.249 + Digraph::Node watch = d.addNode();
1.250 + Digraph::Node pants = d.addNode();
1.251 +
1.252 + d.addArc(socks, shoe);
1.253 + d.addArc(pants, shoe);
1.254 + d.addArc(pants, trousers);
1.255 + d.addArc(trousers, shoe);
1.256 + d.addArc(trousers, belt);
1.257 + d.addArc(belt, coat);
1.258 + d.addArc(shirt, belt);
1.259 + d.addArc(shirt, necktie);
1.260 + d.addArc(necktie, coat);
1.261 +
1.262 + check(dag(d), "This digraph is DAG.");
1.263 + topologicalSort(d, order);
1.264 + for (Digraph::ArcIt a(d); a != INVALID; ++a) {
1.265 + check(order[d.source(a)] < order[d.target(a)],
1.266 + "Wrong topologicalSort()");
1.267 + }
1.268 + }
1.269 +
1.270 + {
1.271 + ListGraph g;
1.272 + ListGraph::NodeMap<bool> map(g);
1.273 +
1.274 + ListGraph::Node n1 = g.addNode();
1.275 + ListGraph::Node n2 = g.addNode();
1.276 + ListGraph::Node n3 = g.addNode();
1.277 + ListGraph::Node n4 = g.addNode();
1.278 + ListGraph::Node n5 = g.addNode();
1.279 + ListGraph::Node n6 = g.addNode();
1.280 + ListGraph::Node n7 = g.addNode();
1.281 +
1.282 + g.addEdge(n1, n3);
1.283 + g.addEdge(n1, n4);
1.284 + g.addEdge(n2, n5);
1.285 + g.addEdge(n3, n6);
1.286 + g.addEdge(n4, n6);
1.287 + g.addEdge(n4, n7);
1.288 + g.addEdge(n5, n7);
1.289 +
1.290 + check(bipartite(g), "This graph is bipartite");
1.291 + check(bipartitePartitions(g, map), "This graph is bipartite");
1.292 +
1.293 + check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],
1.294 + "Wrong bipartitePartitions()");
1.295 + check(map[n3] == map[n4] && map[n3] == map[n5],
1.296 + "Wrong bipartitePartitions()");
1.297 + }
1.298 +
1.299 + return 0;
1.300 +}