test/connectivity_test.cc
changeset 895 dca9eed2c375
parent 649 76cbcb3e9bbb
child 998 7fdaa05a69a1
equal deleted inserted replaced
0:b6ca28e27ead 1:3f048f474d89
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     4  *
     5  * Copyright (C) 2003-2009
     5  * Copyright (C) 2003-2010
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     8  *
     9  * Permission to use, modify and distribute this software is granted
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    10  * provided that this copyright notice appears in all copies. For
    27 
    27 
    28 int main()
    28 int main()
    29 {
    29 {
    30   typedef ListDigraph Digraph;
    30   typedef ListDigraph Digraph;
    31   typedef Undirector<Digraph> Graph;
    31   typedef Undirector<Digraph> Graph;
    32   
    32 
    33   {
    33   {
    34     Digraph d;
    34     Digraph d;
    35     Digraph::NodeMap<int> order(d);
    35     Digraph::NodeMap<int> order(d);
    36     Graph g(d);
    36     Graph g(d);
    37     
    37 
    38     check(stronglyConnected(d), "The empty digraph is strongly connected");
    38     check(stronglyConnected(d), "The empty digraph is strongly connected");
    39     check(countStronglyConnectedComponents(d) == 0,
    39     check(countStronglyConnectedComponents(d) == 0,
    40           "The empty digraph has 0 strongly connected component");
    40           "The empty digraph has 0 strongly connected component");
    41     check(connected(g), "The empty graph is connected");
    41     check(connected(g), "The empty graph is connected");
    42     check(countConnectedComponents(g) == 0,
    42     check(countConnectedComponents(g) == 0,
    46     check(countBiNodeConnectedComponents(g) == 0,
    46     check(countBiNodeConnectedComponents(g) == 0,
    47           "The empty graph has 0 bi-node-connected component");
    47           "The empty graph has 0 bi-node-connected component");
    48     check(biEdgeConnected(g), "The empty graph is bi-edge-connected");
    48     check(biEdgeConnected(g), "The empty graph is bi-edge-connected");
    49     check(countBiEdgeConnectedComponents(g) == 0,
    49     check(countBiEdgeConnectedComponents(g) == 0,
    50           "The empty graph has 0 bi-edge-connected component");
    50           "The empty graph has 0 bi-edge-connected component");
    51           
    51 
    52     check(dag(d), "The empty digraph is DAG.");
    52     check(dag(d), "The empty digraph is DAG.");
    53     check(checkedTopologicalSort(d, order), "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.");
    54     check(loopFree(d), "The empty digraph is loop-free.");
    55     check(parallelFree(d), "The empty digraph is parallel-free.");
    55     check(parallelFree(d), "The empty digraph is parallel-free.");
    56     check(simpleGraph(d), "The empty digraph is simple.");
    56     check(simpleGraph(d), "The empty digraph is simple.");
    80     check(countBiNodeConnectedComponents(g) == 0,
    80     check(countBiNodeConnectedComponents(g) == 0,
    81           "This graph has 0 bi-node-connected component");
    81           "This graph has 0 bi-node-connected component");
    82     check(biEdgeConnected(g), "This graph is bi-edge-connected");
    82     check(biEdgeConnected(g), "This graph is bi-edge-connected");
    83     check(countBiEdgeConnectedComponents(g) == 1,
    83     check(countBiEdgeConnectedComponents(g) == 1,
    84           "This graph has 1 bi-edge-connected component");
    84           "This graph has 1 bi-edge-connected component");
    85           
    85 
    86     check(dag(d), "This digraph is DAG.");
    86     check(dag(d), "This digraph is DAG.");
    87     check(checkedTopologicalSort(d, order), "This digraph is DAG.");
    87     check(checkedTopologicalSort(d, order), "This digraph is DAG.");
    88     check(loopFree(d), "This digraph is loop-free.");
    88     check(loopFree(d), "This digraph is loop-free.");
    89     check(parallelFree(d), "This digraph is parallel-free.");
    89     check(parallelFree(d), "This digraph is parallel-free.");
    90     check(simpleGraph(d), "This digraph is simple.");
    90     check(simpleGraph(d), "This digraph is simple.");
    99 
    99 
   100   {
   100   {
   101     Digraph d;
   101     Digraph d;
   102     Digraph::NodeMap<int> order(d);
   102     Digraph::NodeMap<int> order(d);
   103     Graph g(d);
   103     Graph g(d);
   104     
   104 
   105     Digraph::Node n1 = d.addNode();
   105     Digraph::Node n1 = d.addNode();
   106     Digraph::Node n2 = d.addNode();
   106     Digraph::Node n2 = d.addNode();
   107     Digraph::Node n3 = d.addNode();
   107     Digraph::Node n3 = d.addNode();
   108     Digraph::Node n4 = d.addNode();
   108     Digraph::Node n4 = d.addNode();
   109     Digraph::Node n5 = d.addNode();
   109     Digraph::Node n5 = d.addNode();
   110     Digraph::Node n6 = d.addNode();
   110     Digraph::Node n6 = d.addNode();
   111     
   111 
   112     d.addArc(n1, n3);
   112     d.addArc(n1, n3);
   113     d.addArc(n3, n2);
   113     d.addArc(n3, n2);
   114     d.addArc(n2, n1);
   114     d.addArc(n2, n1);
   115     d.addArc(n4, n2);
   115     d.addArc(n4, n2);
   116     d.addArc(n4, n3);
   116     d.addArc(n4, n3);
   134     check(!tree(g), "This graph is not tree.");
   134     check(!tree(g), "This graph is not tree.");
   135     check(!bipartite(g), "This graph is not bipartite.");
   135     check(!bipartite(g), "This graph is not bipartite.");
   136     check(loopFree(g), "This graph is loop-free.");
   136     check(loopFree(g), "This graph is loop-free.");
   137     check(!parallelFree(g), "This graph is not parallel-free.");
   137     check(!parallelFree(g), "This graph is not parallel-free.");
   138     check(!simpleGraph(g), "This graph is not simple.");
   138     check(!simpleGraph(g), "This graph is not simple.");
   139     
   139 
   140     d.addArc(n3, n3);
   140     d.addArc(n3, n3);
   141     
   141 
   142     check(!loopFree(d), "This digraph is not loop-free.");
   142     check(!loopFree(d), "This digraph is not loop-free.");
   143     check(!loopFree(g), "This graph is not loop-free.");
   143     check(!loopFree(g), "This graph is not loop-free.");
   144     check(!simpleGraph(d), "This digraph is not simple.");
   144     check(!simpleGraph(d), "This digraph is not simple.");
   145     
   145 
   146     d.addArc(n3, n2);
   146     d.addArc(n3, n2);
   147     
   147 
   148     check(!parallelFree(d), "This digraph is not parallel-free.");
   148     check(!parallelFree(d), "This digraph is not parallel-free.");
   149   }
   149   }
   150   
   150 
   151   {
   151   {
   152     Digraph d;
   152     Digraph d;
   153     Digraph::ArcMap<bool> cutarcs(d, false);
   153     Digraph::ArcMap<bool> cutarcs(d, false);
   154     Graph g(d);
   154     Graph g(d);
   155     
   155 
   156     Digraph::Node n1 = d.addNode();
   156     Digraph::Node n1 = d.addNode();
   157     Digraph::Node n2 = d.addNode();
   157     Digraph::Node n2 = d.addNode();
   158     Digraph::Node n3 = d.addNode();
   158     Digraph::Node n3 = d.addNode();
   159     Digraph::Node n4 = d.addNode();
   159     Digraph::Node n4 = d.addNode();
   160     Digraph::Node n5 = d.addNode();
   160     Digraph::Node n5 = d.addNode();
   170     d.addArc(n4, n6);
   170     d.addArc(n4, n6);
   171     d.addArc(n2, n5);
   171     d.addArc(n2, n5);
   172     d.addArc(n1, n8);
   172     d.addArc(n1, n8);
   173     d.addArc(n6, n7);
   173     d.addArc(n6, n7);
   174     d.addArc(n7, n6);
   174     d.addArc(n7, n6);
   175    
   175 
   176     check(!stronglyConnected(d), "This digraph is not strongly connected");
   176     check(!stronglyConnected(d), "This digraph is not strongly connected");
   177     check(countStronglyConnectedComponents(d) == 3,
   177     check(countStronglyConnectedComponents(d) == 3,
   178           "This digraph has 3 strongly connected components");
   178           "This digraph has 3 strongly connected components");
   179     Digraph::NodeMap<int> scomp1(d);
   179     Digraph::NodeMap<int> scomp1(d);
   180     check(stronglyConnectedComponents(d, scomp1) == 3,
   180     check(stronglyConnectedComponents(d, scomp1) == 3,
   233   {
   233   {
   234     // DAG example for topological sort from the book New Algorithms
   234     // DAG example for topological sort from the book New Algorithms
   235     // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein)
   235     // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein)
   236     Digraph d;
   236     Digraph d;
   237     Digraph::NodeMap<int> order(d);
   237     Digraph::NodeMap<int> order(d);
   238     
   238 
   239     Digraph::Node belt = d.addNode();
   239     Digraph::Node belt = d.addNode();
   240     Digraph::Node trousers = d.addNode();
   240     Digraph::Node trousers = d.addNode();
   241     Digraph::Node necktie = d.addNode();
   241     Digraph::Node necktie = d.addNode();
   242     Digraph::Node coat = d.addNode();
   242     Digraph::Node coat = d.addNode();
   243     Digraph::Node socks = d.addNode();
   243     Digraph::Node socks = d.addNode();
   253     d.addArc(trousers, belt);
   253     d.addArc(trousers, belt);
   254     d.addArc(belt, coat);
   254     d.addArc(belt, coat);
   255     d.addArc(shirt, belt);
   255     d.addArc(shirt, belt);
   256     d.addArc(shirt, necktie);
   256     d.addArc(shirt, necktie);
   257     d.addArc(necktie, coat);
   257     d.addArc(necktie, coat);
   258     
   258 
   259     check(dag(d), "This digraph is DAG.");
   259     check(dag(d), "This digraph is DAG.");
   260     topologicalSort(d, order);
   260     topologicalSort(d, order);
   261     for (Digraph::ArcIt a(d); a != INVALID; ++a) {
   261     for (Digraph::ArcIt a(d); a != INVALID; ++a) {
   262       check(order[d.source(a)] < order[d.target(a)],
   262       check(order[d.source(a)] < order[d.target(a)],
   263             "Wrong topologicalSort()");
   263             "Wrong topologicalSort()");
   265   }
   265   }
   266 
   266 
   267   {
   267   {
   268     ListGraph g;
   268     ListGraph g;
   269     ListGraph::NodeMap<bool> map(g);
   269     ListGraph::NodeMap<bool> map(g);
   270     
   270 
   271     ListGraph::Node n1 = g.addNode();
   271     ListGraph::Node n1 = g.addNode();
   272     ListGraph::Node n2 = g.addNode();
   272     ListGraph::Node n2 = g.addNode();
   273     ListGraph::Node n3 = g.addNode();
   273     ListGraph::Node n3 = g.addNode();
   274     ListGraph::Node n4 = g.addNode();
   274     ListGraph::Node n4 = g.addNode();
   275     ListGraph::Node n5 = g.addNode();
   275     ListGraph::Node n5 = g.addNode();
   281     g.addEdge(n2, n5);
   281     g.addEdge(n2, n5);
   282     g.addEdge(n3, n6);
   282     g.addEdge(n3, n6);
   283     g.addEdge(n4, n6);
   283     g.addEdge(n4, n6);
   284     g.addEdge(n4, n7);
   284     g.addEdge(n4, n7);
   285     g.addEdge(n5, n7);
   285     g.addEdge(n5, n7);
   286    
   286 
   287     check(bipartite(g), "This graph is bipartite");
   287     check(bipartite(g), "This graph is bipartite");
   288     check(bipartitePartitions(g, map), "This graph is bipartite");
   288     check(bipartitePartitions(g, map), "This graph is bipartite");
   289     
   289 
   290     check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],
   290     check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],
   291           "Wrong bipartitePartitions()");
   291           "Wrong bipartitePartitions()");
   292     check(map[n3] == map[n4] && map[n3] == map[n5],
   292     check(map[n3] == map[n4] && map[n3] == map[n5],
   293           "Wrong bipartitePartitions()");
   293           "Wrong bipartitePartitions()");
   294   }
   294   }