test/connectivity_test.cc
author Alpar Juttner <alpar@cs.elte.hu>
Sun, 11 Aug 2013 12:53:30 +0200
branch1.1
changeset 815 eaed91c09e0f
parent 808 bdfc038f364c
parent 809 552e3d1242c6
permissions -rw-r--r--
Release series 1.1.x has reached its end of life.
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2011
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #include <lemon/connectivity.h>
    20 #include <lemon/list_graph.h>
    21 #include <lemon/adaptors.h>
    22 
    23 #include "test_tools.h"
    24 
    25 using namespace lemon;
    26 
    27 
    28 int main()
    29 {
    30   typedef ListDigraph Digraph;
    31   typedef Undirector<Digraph> Graph;
    32 
    33   {
    34     Digraph d;
    35     Digraph::NodeMap<int> order(d);
    36     Graph g(d);
    37 
    38     check(stronglyConnected(d), "The empty digraph is strongly connected");
    39     check(countStronglyConnectedComponents(d) == 0,
    40           "The empty digraph has 0 strongly connected component");
    41     check(connected(g), "The empty graph is connected");
    42     check(countConnectedComponents(g) == 0,
    43           "The empty graph has 0 connected component");
    44 
    45     check(biNodeConnected(g), "The empty graph is bi-node-connected");
    46     check(countBiNodeConnectedComponents(g) == 0,
    47           "The empty graph has 0 bi-node-connected component");
    48     check(biEdgeConnected(g), "The empty graph is bi-edge-connected");
    49     check(countBiEdgeConnectedComponents(g) == 0,
    50           "The empty graph has 0 bi-edge-connected component");
    51 
    52     check(dag(d), "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.");
    55     check(parallelFree(d), "The empty digraph is parallel-free.");
    56     check(simpleGraph(d), "The empty digraph is simple.");
    57 
    58     check(acyclic(g), "The empty graph is acyclic.");
    59     check(tree(g), "The empty graph is tree.");
    60     check(bipartite(g), "The empty graph is bipartite.");
    61     check(loopFree(g), "The empty graph is loop-free.");
    62     check(parallelFree(g), "The empty graph is parallel-free.");
    63     check(simpleGraph(g), "The empty graph is simple.");
    64   }
    65 
    66   {
    67     Digraph d;
    68     Digraph::NodeMap<int> order(d);
    69     Graph g(d);
    70     Digraph::Node n = d.addNode();
    71     ::lemon::ignore_unused_variable_warning(n);
    72 
    73     check(stronglyConnected(d), "This digraph is strongly connected");
    74     check(countStronglyConnectedComponents(d) == 1,
    75           "This digraph has 1 strongly connected component");
    76     check(connected(g), "This graph is connected");
    77     check(countConnectedComponents(g) == 1,
    78           "This graph has 1 connected component");
    79 
    80     check(biNodeConnected(g), "This graph is bi-node-connected");
    81     check(countBiNodeConnectedComponents(g) == 0,
    82           "This graph has 0 bi-node-connected component");
    83     check(biEdgeConnected(g), "This graph is bi-edge-connected");
    84     check(countBiEdgeConnectedComponents(g) == 1,
    85           "This graph has 1 bi-edge-connected component");
    86 
    87     check(dag(d), "This digraph is DAG.");
    88     check(checkedTopologicalSort(d, order), "This digraph is DAG.");
    89     check(loopFree(d), "This digraph is loop-free.");
    90     check(parallelFree(d), "This digraph is parallel-free.");
    91     check(simpleGraph(d), "This digraph is simple.");
    92 
    93     check(acyclic(g), "This graph is acyclic.");
    94     check(tree(g), "This graph is tree.");
    95     check(bipartite(g), "This graph is bipartite.");
    96     check(loopFree(g), "This graph is loop-free.");
    97     check(parallelFree(g), "This graph is parallel-free.");
    98     check(simpleGraph(g), "This graph is simple.");
    99   }
   100 
   101   {
   102     ListGraph g;
   103     ListGraph::NodeMap<bool> map(g);
   104 
   105     ListGraph::Node n1 = g.addNode();
   106     ListGraph::Node n2 = g.addNode();
   107 
   108     ListGraph::Edge e1 = g.addEdge(n1, n2);
   109     ::lemon::ignore_unused_variable_warning(e1);
   110     check(biNodeConnected(g), "Graph is bi-node-connected");
   111 
   112     ListGraph::Node n3 = g.addNode();
   113     ::lemon::ignore_unused_variable_warning(n3);
   114     check(!biNodeConnected(g), "Graph is not bi-node-connected");
   115   }
   116 
   117 
   118   {
   119     Digraph d;
   120     Digraph::NodeMap<int> order(d);
   121     Graph g(d);
   122 
   123     Digraph::Node n1 = d.addNode();
   124     Digraph::Node n2 = d.addNode();
   125     Digraph::Node n3 = d.addNode();
   126     Digraph::Node n4 = d.addNode();
   127     Digraph::Node n5 = d.addNode();
   128     Digraph::Node n6 = d.addNode();
   129 
   130     d.addArc(n1, n3);
   131     d.addArc(n3, n2);
   132     d.addArc(n2, n1);
   133     d.addArc(n4, n2);
   134     d.addArc(n4, n3);
   135     d.addArc(n5, n6);
   136     d.addArc(n6, n5);
   137 
   138     check(!stronglyConnected(d), "This digraph is not strongly connected");
   139     check(countStronglyConnectedComponents(d) == 3,
   140           "This digraph has 3 strongly connected components");
   141     check(!connected(g), "This graph is not connected");
   142     check(countConnectedComponents(g) == 2,
   143           "This graph has 2 connected components");
   144 
   145     check(!dag(d), "This digraph is not DAG.");
   146     check(!checkedTopologicalSort(d, order), "This digraph is not DAG.");
   147     check(loopFree(d), "This digraph is loop-free.");
   148     check(parallelFree(d), "This digraph is parallel-free.");
   149     check(simpleGraph(d), "This digraph is simple.");
   150 
   151     check(!acyclic(g), "This graph is not acyclic.");
   152     check(!tree(g), "This graph is not tree.");
   153     check(!bipartite(g), "This graph is not bipartite.");
   154     check(loopFree(g), "This graph is loop-free.");
   155     check(!parallelFree(g), "This graph is not parallel-free.");
   156     check(!simpleGraph(g), "This graph is not simple.");
   157 
   158     d.addArc(n3, n3);
   159 
   160     check(!loopFree(d), "This digraph is not loop-free.");
   161     check(!loopFree(g), "This graph is not loop-free.");
   162     check(!simpleGraph(d), "This digraph is not simple.");
   163 
   164     d.addArc(n3, n2);
   165 
   166     check(!parallelFree(d), "This digraph is not parallel-free.");
   167   }
   168 
   169   {
   170     Digraph d;
   171     Digraph::ArcMap<bool> cutarcs(d, false);
   172     Graph g(d);
   173 
   174     Digraph::Node n1 = d.addNode();
   175     Digraph::Node n2 = d.addNode();
   176     Digraph::Node n3 = d.addNode();
   177     Digraph::Node n4 = d.addNode();
   178     Digraph::Node n5 = d.addNode();
   179     Digraph::Node n6 = d.addNode();
   180     Digraph::Node n7 = d.addNode();
   181     Digraph::Node n8 = d.addNode();
   182 
   183     d.addArc(n1, n2);
   184     d.addArc(n5, n1);
   185     d.addArc(n2, n8);
   186     d.addArc(n8, n5);
   187     d.addArc(n6, n4);
   188     d.addArc(n4, n6);
   189     d.addArc(n2, n5);
   190     d.addArc(n1, n8);
   191     d.addArc(n6, n7);
   192     d.addArc(n7, n6);
   193 
   194     check(!stronglyConnected(d), "This digraph is not strongly connected");
   195     check(countStronglyConnectedComponents(d) == 3,
   196           "This digraph has 3 strongly connected components");
   197     Digraph::NodeMap<int> scomp1(d);
   198     check(stronglyConnectedComponents(d, scomp1) == 3,
   199           "This digraph has 3 strongly connected components");
   200     check(scomp1[n1] != scomp1[n3] && scomp1[n1] != scomp1[n4] &&
   201           scomp1[n3] != scomp1[n4], "Wrong stronglyConnectedComponents()");
   202     check(scomp1[n1] == scomp1[n2] && scomp1[n1] == scomp1[n5] &&
   203           scomp1[n1] == scomp1[n8], "Wrong stronglyConnectedComponents()");
   204     check(scomp1[n4] == scomp1[n6] && scomp1[n4] == scomp1[n7],
   205           "Wrong stronglyConnectedComponents()");
   206     Digraph::ArcMap<bool> scut1(d, false);
   207     check(stronglyConnectedCutArcs(d, scut1) == 0,
   208           "This digraph has 0 strongly connected cut arc.");
   209     for (Digraph::ArcIt a(d); a != INVALID; ++a) {
   210       check(!scut1[a], "Wrong stronglyConnectedCutArcs()");
   211     }
   212 
   213     check(!connected(g), "This graph is not connected");
   214     check(countConnectedComponents(g) == 3,
   215           "This graph has 3 connected components");
   216     Graph::NodeMap<int> comp(g);
   217     check(connectedComponents(g, comp) == 3,
   218           "This graph has 3 connected components");
   219     check(comp[n1] != comp[n3] && comp[n1] != comp[n4] &&
   220           comp[n3] != comp[n4], "Wrong connectedComponents()");
   221     check(comp[n1] == comp[n2] && comp[n1] == comp[n5] &&
   222           comp[n1] == comp[n8], "Wrong connectedComponents()");
   223     check(comp[n4] == comp[n6] && comp[n4] == comp[n7],
   224           "Wrong connectedComponents()");
   225 
   226     cutarcs[d.addArc(n3, n1)] = true;
   227     cutarcs[d.addArc(n3, n5)] = true;
   228     cutarcs[d.addArc(n3, n8)] = true;
   229     cutarcs[d.addArc(n8, n6)] = true;
   230     cutarcs[d.addArc(n8, n7)] = true;
   231 
   232     check(!stronglyConnected(d), "This digraph is not strongly connected");
   233     check(countStronglyConnectedComponents(d) == 3,
   234           "This digraph has 3 strongly connected components");
   235     Digraph::NodeMap<int> scomp2(d);
   236     check(stronglyConnectedComponents(d, scomp2) == 3,
   237           "This digraph has 3 strongly connected components");
   238     check(scomp2[n3] == 0, "Wrong stronglyConnectedComponents()");
   239     check(scomp2[n1] == 1 && scomp2[n2] == 1 && scomp2[n5] == 1 &&
   240           scomp2[n8] == 1, "Wrong stronglyConnectedComponents()");
   241     check(scomp2[n4] == 2 && scomp2[n6] == 2 && scomp2[n7] == 2,
   242           "Wrong stronglyConnectedComponents()");
   243     Digraph::ArcMap<bool> scut2(d, false);
   244     check(stronglyConnectedCutArcs(d, scut2) == 5,
   245           "This digraph has 5 strongly connected cut arcs.");
   246     for (Digraph::ArcIt a(d); a != INVALID; ++a) {
   247       check(scut2[a] == cutarcs[a], "Wrong stronglyConnectedCutArcs()");
   248     }
   249   }
   250 
   251   {
   252     // DAG example for topological sort from the book New Algorithms
   253     // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein)
   254     Digraph d;
   255     Digraph::NodeMap<int> order(d);
   256 
   257     Digraph::Node belt = d.addNode();
   258     Digraph::Node trousers = d.addNode();
   259     Digraph::Node necktie = d.addNode();
   260     Digraph::Node coat = d.addNode();
   261     Digraph::Node socks = d.addNode();
   262     Digraph::Node shirt = d.addNode();
   263     Digraph::Node shoe = d.addNode();
   264     Digraph::Node watch = d.addNode();
   265     Digraph::Node pants = d.addNode();
   266     ::lemon::ignore_unused_variable_warning(watch);
   267 
   268     d.addArc(socks, shoe);
   269     d.addArc(pants, shoe);
   270     d.addArc(pants, trousers);
   271     d.addArc(trousers, shoe);
   272     d.addArc(trousers, belt);
   273     d.addArc(belt, coat);
   274     d.addArc(shirt, belt);
   275     d.addArc(shirt, necktie);
   276     d.addArc(necktie, coat);
   277 
   278     check(dag(d), "This digraph is DAG.");
   279     topologicalSort(d, order);
   280     for (Digraph::ArcIt a(d); a != INVALID; ++a) {
   281       check(order[d.source(a)] < order[d.target(a)],
   282             "Wrong topologicalSort()");
   283     }
   284   }
   285 
   286   {
   287     ListGraph g;
   288     ListGraph::NodeMap<bool> map(g);
   289 
   290     ListGraph::Node n1 = g.addNode();
   291     ListGraph::Node n2 = g.addNode();
   292     ListGraph::Node n3 = g.addNode();
   293     ListGraph::Node n4 = g.addNode();
   294     ListGraph::Node n5 = g.addNode();
   295     ListGraph::Node n6 = g.addNode();
   296     ListGraph::Node n7 = g.addNode();
   297 
   298     g.addEdge(n1, n3);
   299     g.addEdge(n1, n4);
   300     g.addEdge(n2, n5);
   301     g.addEdge(n3, n6);
   302     g.addEdge(n4, n6);
   303     g.addEdge(n4, n7);
   304     g.addEdge(n5, n7);
   305 
   306     check(bipartite(g), "This graph is bipartite");
   307     check(bipartitePartitions(g, map), "This graph is bipartite");
   308 
   309     check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],
   310           "Wrong bipartitePartitions()");
   311     check(map[n3] == map[n4] && map[n3] == map[n5],
   312           "Wrong bipartitePartitions()");
   313   }
   314 
   315   return 0;
   316 }