Add a test file for the connectivity functions (#285)
authorPeter Kovacs <kpeter@inf.elte.hu>
Wed, 06 May 2009 14:46:05 +0200
changeset 64776cbcb3e9bbb
parent 646 4ff8041e9c2e
child 650 e2f99a473998
Add a test file for the connectivity functions (#285)
The Euler tools have a separate test file.
test/CMakeLists.txt
test/Makefile.am
test/connectivity_test.cc
     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 +}