test/connectivity_test.cc
changeset 956 141f9c0db4a3
parent 696 76cbcb3e9bbb
child 1159 7fdaa05a69a1
     1.1 --- a/test/connectivity_test.cc	Wed Mar 17 12:35:52 2010 +0100
     1.2 +++ b/test/connectivity_test.cc	Sat Mar 06 14:35:12 2010 +0000
     1.3 @@ -2,7 +2,7 @@
     1.4   *
     1.5   * This file is a part of LEMON, a generic C++ optimization library.
     1.6   *
     1.7 - * Copyright (C) 2003-2009
     1.8 + * Copyright (C) 2003-2010
     1.9   * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10   * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11   *
    1.12 @@ -29,12 +29,12 @@
    1.13  {
    1.14    typedef ListDigraph Digraph;
    1.15    typedef Undirector<Digraph> Graph;
    1.16 -  
    1.17 +
    1.18    {
    1.19      Digraph d;
    1.20      Digraph::NodeMap<int> order(d);
    1.21      Graph g(d);
    1.22 -    
    1.23 +
    1.24      check(stronglyConnected(d), "The empty digraph is strongly connected");
    1.25      check(countStronglyConnectedComponents(d) == 0,
    1.26            "The empty digraph has 0 strongly connected component");
    1.27 @@ -48,7 +48,7 @@
    1.28      check(biEdgeConnected(g), "The empty graph is bi-edge-connected");
    1.29      check(countBiEdgeConnectedComponents(g) == 0,
    1.30            "The empty graph has 0 bi-edge-connected component");
    1.31 -          
    1.32 +
    1.33      check(dag(d), "The empty digraph is DAG.");
    1.34      check(checkedTopologicalSort(d, order), "The empty digraph is DAG.");
    1.35      check(loopFree(d), "The empty digraph is loop-free.");
    1.36 @@ -82,7 +82,7 @@
    1.37      check(biEdgeConnected(g), "This graph is bi-edge-connected");
    1.38      check(countBiEdgeConnectedComponents(g) == 1,
    1.39            "This graph has 1 bi-edge-connected component");
    1.40 -          
    1.41 +
    1.42      check(dag(d), "This digraph is DAG.");
    1.43      check(checkedTopologicalSort(d, order), "This digraph is DAG.");
    1.44      check(loopFree(d), "This digraph is loop-free.");
    1.45 @@ -101,14 +101,14 @@
    1.46      Digraph d;
    1.47      Digraph::NodeMap<int> order(d);
    1.48      Graph g(d);
    1.49 -    
    1.50 +
    1.51      Digraph::Node n1 = d.addNode();
    1.52      Digraph::Node n2 = d.addNode();
    1.53      Digraph::Node n3 = d.addNode();
    1.54      Digraph::Node n4 = d.addNode();
    1.55      Digraph::Node n5 = d.addNode();
    1.56      Digraph::Node n6 = d.addNode();
    1.57 -    
    1.58 +
    1.59      d.addArc(n1, n3);
    1.60      d.addArc(n3, n2);
    1.61      d.addArc(n2, n1);
    1.62 @@ -136,23 +136,23 @@
    1.63      check(loopFree(g), "This graph is loop-free.");
    1.64      check(!parallelFree(g), "This graph is not parallel-free.");
    1.65      check(!simpleGraph(g), "This graph is not simple.");
    1.66 -    
    1.67 +
    1.68      d.addArc(n3, n3);
    1.69 -    
    1.70 +
    1.71      check(!loopFree(d), "This digraph is not loop-free.");
    1.72      check(!loopFree(g), "This graph is not loop-free.");
    1.73      check(!simpleGraph(d), "This digraph is not simple.");
    1.74 -    
    1.75 +
    1.76      d.addArc(n3, n2);
    1.77 -    
    1.78 +
    1.79      check(!parallelFree(d), "This digraph is not parallel-free.");
    1.80    }
    1.81 -  
    1.82 +
    1.83    {
    1.84      Digraph d;
    1.85      Digraph::ArcMap<bool> cutarcs(d, false);
    1.86      Graph g(d);
    1.87 -    
    1.88 +
    1.89      Digraph::Node n1 = d.addNode();
    1.90      Digraph::Node n2 = d.addNode();
    1.91      Digraph::Node n3 = d.addNode();
    1.92 @@ -172,7 +172,7 @@
    1.93      d.addArc(n1, n8);
    1.94      d.addArc(n6, n7);
    1.95      d.addArc(n7, n6);
    1.96 -   
    1.97 +
    1.98      check(!stronglyConnected(d), "This digraph is not strongly connected");
    1.99      check(countStronglyConnectedComponents(d) == 3,
   1.100            "This digraph has 3 strongly connected components");
   1.101 @@ -235,7 +235,7 @@
   1.102      // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein)
   1.103      Digraph d;
   1.104      Digraph::NodeMap<int> order(d);
   1.105 -    
   1.106 +
   1.107      Digraph::Node belt = d.addNode();
   1.108      Digraph::Node trousers = d.addNode();
   1.109      Digraph::Node necktie = d.addNode();
   1.110 @@ -255,7 +255,7 @@
   1.111      d.addArc(shirt, belt);
   1.112      d.addArc(shirt, necktie);
   1.113      d.addArc(necktie, coat);
   1.114 -    
   1.115 +
   1.116      check(dag(d), "This digraph is DAG.");
   1.117      topologicalSort(d, order);
   1.118      for (Digraph::ArcIt a(d); a != INVALID; ++a) {
   1.119 @@ -267,7 +267,7 @@
   1.120    {
   1.121      ListGraph g;
   1.122      ListGraph::NodeMap<bool> map(g);
   1.123 -    
   1.124 +
   1.125      ListGraph::Node n1 = g.addNode();
   1.126      ListGraph::Node n2 = g.addNode();
   1.127      ListGraph::Node n3 = g.addNode();
   1.128 @@ -283,10 +283,10 @@
   1.129      g.addEdge(n4, n6);
   1.130      g.addEdge(n4, n7);
   1.131      g.addEdge(n5, n7);
   1.132 -   
   1.133 +
   1.134      check(bipartite(g), "This graph is bipartite");
   1.135      check(bipartitePartitions(g, map), "This graph is bipartite");
   1.136 -    
   1.137 +
   1.138      check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],
   1.139            "Wrong bipartitePartitions()");
   1.140      check(map[n3] == map[n4] && map[n3] == map[n5],