test/graph_utils_test.cc
changeset 175 4eb8900a865c
parent 139 701c529ba737
child 209 765619b7cbb2
equal deleted inserted replaced
0:e514dac31c31 1:5714295bdb46
    14  * express or implied, and with no claim as to its suitability for any
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    15  * purpose.
    16  *
    16  *
    17  */
    17  */
    18 
    18 
    19 #include <iostream>
    19 #include <cstdlib>
    20 #include <vector>
    20 #include <ctime>
    21 
    21 
       
    22 #include <lemon/random.h>
    22 #include <lemon/graph_utils.h>
    23 #include <lemon/graph_utils.h>
    23 
       
    24 #include <lemon/list_graph.h>
    24 #include <lemon/list_graph.h>
    25 #include <lemon/smart_graph.h>
    25 #include <lemon/smart_graph.h>
    26 
    26 
       
    27 #include "graph_test.h"
    27 #include "test_tools.h"
    28 #include "test_tools.h"
    28 #include "graph_utils_test.h"
       
    29 
       
    30 
    29 
    31 using namespace lemon;
    30 using namespace lemon;
    32 
    31 
    33 template <class Graph>
    32 template <typename Digraph>
    34 void checkSnapDeg() 
    33 void checkFindArcs() {
       
    34   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
       
    35 
       
    36   {
       
    37     Digraph digraph;
       
    38     for (int i = 0; i < 10; ++i) {
       
    39       digraph.addNode();
       
    40     }
       
    41     DescriptorMap<Digraph, Node> nodes(digraph);
       
    42     typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
       
    43     for (int i = 0; i < 100; ++i) {
       
    44       int src = rnd[invNodes.size()];
       
    45       int trg = rnd[invNodes.size()];
       
    46       digraph.addArc(invNodes[src], invNodes[trg]);
       
    47     }
       
    48     typename Digraph::template ArcMap<bool> found(digraph, false);
       
    49     DescriptorMap<Digraph, Arc> arcs(digraph);
       
    50     for (NodeIt src(digraph); src != INVALID; ++src) {
       
    51       for (NodeIt trg(digraph); trg != INVALID; ++trg) {
       
    52         for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {
       
    53           check(digraph.source(con) == src, "Wrong source.");
       
    54           check(digraph.target(con) == trg, "Wrong target.");
       
    55           check(found[con] == false, "The arc found already.");
       
    56           found[con] = true;
       
    57         }
       
    58       }
       
    59     }
       
    60     for (ArcIt it(digraph); it != INVALID; ++it) {
       
    61       check(found[it] == true, "The arc is not found.");
       
    62     }
       
    63   }
       
    64 
       
    65   {
       
    66     int num = 5;
       
    67     Digraph fg;
       
    68     std::vector<Node> nodes;
       
    69     for (int i = 0; i < num; ++i) {
       
    70       nodes.push_back(fg.addNode());
       
    71     }
       
    72     for (int i = 0; i < num * num; ++i) {
       
    73       fg.addArc(nodes[i / num], nodes[i % num]);
       
    74     }
       
    75     check(countNodes(fg) == num, "Wrong node number.");
       
    76     check(countArcs(fg) == num*num, "Wrong arc number.");
       
    77     for (NodeIt src(fg); src != INVALID; ++src) {
       
    78       for (NodeIt trg(fg); trg != INVALID; ++trg) {
       
    79         ConArcIt<Digraph> con(fg, src, trg);
       
    80         check(con != INVALID, "There is no connecting arc.");
       
    81         check(fg.source(con) == src, "Wrong source.");
       
    82         check(fg.target(con) == trg, "Wrong target.");
       
    83         check(++con == INVALID, "There is more connecting arc.");
       
    84       }
       
    85     }
       
    86     ArcLookUp<Digraph> al1(fg);
       
    87     DynArcLookUp<Digraph> al2(fg);
       
    88     AllArcLookUp<Digraph> al3(fg);
       
    89     for (NodeIt src(fg); src != INVALID; ++src) {
       
    90       for (NodeIt trg(fg); trg != INVALID; ++trg) {
       
    91         Arc con1 = al1(src, trg);
       
    92         Arc con2 = al2(src, trg);
       
    93         Arc con3 = al3(src, trg);
       
    94         Arc con4 = findArc(fg, src, trg);
       
    95         check(con1 == con2 && con2 == con3 && con3 == con4, "Different results.")
       
    96         check(con1 != INVALID, "There is no connecting arc.");
       
    97         check(fg.source(con1) == src, "Wrong source.");
       
    98         check(fg.target(con1) == trg, "Wrong target.");
       
    99         check(al3(src, trg, con3) == INVALID, "There is more connecting arc.");
       
   100         check(findArc(fg, src, trg, con4) == INVALID, "There is more connecting arc.");
       
   101       }
       
   102     }
       
   103   }
       
   104 }
       
   105 
       
   106 template <typename Graph>
       
   107 void checkFindEdges() {
       
   108   TEMPLATE_GRAPH_TYPEDEFS(Graph);
       
   109   Graph graph;
       
   110   for (int i = 0; i < 10; ++i) {
       
   111     graph.addNode();
       
   112   }
       
   113   DescriptorMap<Graph, Node> nodes(graph);
       
   114   typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes);
       
   115   for (int i = 0; i < 100; ++i) {
       
   116     int src = rnd[invNodes.size()];
       
   117     int trg = rnd[invNodes.size()];
       
   118     graph.addEdge(invNodes[src], invNodes[trg]);
       
   119   }
       
   120   typename Graph::template EdgeMap<int> found(graph, 0);
       
   121   DescriptorMap<Graph, Edge> edges(graph);
       
   122   for (NodeIt src(graph); src != INVALID; ++src) {
       
   123     for (NodeIt trg(graph); trg != INVALID; ++trg) {
       
   124       for (ConEdgeIt<Graph> con(graph, src, trg); con != INVALID; ++con) {
       
   125         check( (graph.u(con) == src && graph.v(con) == trg) ||
       
   126                (graph.v(con) == src && graph.u(con) == trg), "Wrong end nodes.");
       
   127         ++found[con];
       
   128         check(found[con] <= 2, "The edge found more than twice.");
       
   129       }
       
   130     }
       
   131   }
       
   132   for (EdgeIt it(graph); it != INVALID; ++it) {
       
   133     check( (graph.u(it) != graph.v(it) && found[it] == 2) ||
       
   134            (graph.u(it) == graph.v(it) && found[it] == 1),
       
   135            "The edge is not found correctly.");
       
   136   }
       
   137 }
       
   138 
       
   139 template <class Digraph>
       
   140 void checkDeg()
    35 {
   141 {
    36   Graph g;
   142   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    37   typename Graph::Node n1=g.addNode();
   143   
    38   typename Graph::Node n2=g.addNode();
   144   const int nodeNum = 10;
    39    
   145   const int arcNum = 100;
    40   InDegMap<Graph> ind(g);
   146   Digraph digraph;
    41  
   147   InDegMap<Digraph> inDeg(digraph);
       
   148   OutDegMap<Digraph> outDeg(digraph);
       
   149   std::vector<Node> nodes(nodeNum);
       
   150   for (int i = 0; i < nodeNum; ++i) {
       
   151     nodes[i] = digraph.addNode();
       
   152   }
       
   153   std::vector<Arc> arcs(arcNum);
       
   154   for (int i = 0; i < arcNum; ++i) {
       
   155     arcs[i] = digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
       
   156   }
       
   157   for (int i = 0; i < nodeNum; ++i) {
       
   158     check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]), 
       
   159           "Wrong in degree map");
       
   160   }
       
   161   for (int i = 0; i < nodeNum; ++i) {
       
   162     check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]), 
       
   163           "Wrong out degree map");
       
   164   }
       
   165 }
       
   166 
       
   167 template <class Digraph>
       
   168 void checkSnapDeg()
       
   169 {
       
   170   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
       
   171 
       
   172   Digraph g;
       
   173   Node n1=g.addNode();
       
   174   Node n2=g.addNode();
       
   175   
       
   176   InDegMap<Digraph> ind(g);
       
   177   
    42   g.addArc(n1,n2);
   178   g.addArc(n1,n2);
    43   
   179   
    44   typename Graph::Snapshot snap(g);
   180   typename Digraph::Snapshot snap(g);
    45   
   181   
    46   OutDegMap<Graph> outd(g);
   182   OutDegMap<Digraph> outd(g);
    47   
   183   
    48   check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
   184   check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
    49   check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
   185   check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
    50 
   186 
    51   g.addArc(n1,n2);
   187   g.addArc(n1,n2);
    52   g.addArc(n2,n1);
   188   g.addArc(n2,n1);
    53  
   189 
    54   check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
   190   check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
    55   check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
   191   check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
    56 
   192 
    57   snap.restore();
   193   snap.restore();
    58 
   194 
    59   check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
   195   check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
    60   check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
   196   check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
    61   
       
    62 }
   197 }
    63 
   198 
    64 int main() {
   199 int main() {
    65   ///\file
   200   // Checking ConArcIt, ConEdgeIt, ArcLookUp, AllArcLookUp, and DynArcLookUp
    66   { // checking list graph
   201   checkFindArcs<ListDigraph>();
    67     checkDigraphCounters<ListDigraph>();
   202   checkFindArcs<SmartDigraph>();
    68     checkFindArc<ListDigraph>();
   203   checkFindEdges<ListGraph>();
    69   }
   204   checkFindEdges<SmartGraph>();
    70   { // checking smart graph
   205 
    71     checkDigraphCounters<SmartDigraph>();
   206   // Checking In/OutDegMap (and Snapshot feature)
    72     checkFindArc<SmartDigraph>();
   207   checkDeg<ListDigraph>();
    73   }
   208   checkDeg<SmartDigraph>();
    74   {
       
    75     int num = 5;
       
    76     SmartDigraph fg;
       
    77     std::vector<SmartDigraph::Node> nodes;
       
    78     for (int i = 0; i < num; ++i) {
       
    79       nodes.push_back(fg.addNode());
       
    80     }
       
    81     for (int i = 0; i < num * num; ++i) {
       
    82       fg.addArc(nodes[i / num], nodes[i % num]);
       
    83     }
       
    84     check(countNodes(fg) == num, "FullGraph: wrong node number.");
       
    85     check(countArcs(fg) == num*num, "FullGraph: wrong arc number.");
       
    86     for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
       
    87       for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
       
    88 	ConArcIt<SmartDigraph> con(fg, src, trg);
       
    89 	check(con != INVALID, "There is no connecting arc.");
       
    90 	check(fg.source(con) == src, "Wrong source.");
       
    91 	check(fg.target(con) == trg, "Wrong target.");
       
    92 	check(++con == INVALID, "There is more connecting arc.");
       
    93       }
       
    94     }
       
    95     AllArcLookUp<SmartDigraph> el(fg);
       
    96     for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
       
    97       for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
       
    98 	SmartDigraph::Arc con = el(src, trg);
       
    99 	check(con != INVALID, "There is no connecting arc.");
       
   100 	check(fg.source(con) == src, "Wrong source.");
       
   101 	check(fg.target(con) == trg, "Wrong target.");
       
   102 	check(el(src,trg,con) == INVALID, "There is more connecting arc.");
       
   103       }
       
   104     }
       
   105   }
       
   106 
       
   107   //check In/OutDegMap (and Snapshot feature)
       
   108 
       
   109   checkSnapDeg<ListDigraph>();
   209   checkSnapDeg<ListDigraph>();
   110   checkSnapDeg<SmartDigraph>();
   210   checkSnapDeg<SmartDigraph>();
   111   
       
   112   {
       
   113     const int nodeNum = 10;
       
   114     const int arcNum = 100;
       
   115     ListDigraph digraph;
       
   116     InDegMap<ListDigraph> inDeg(digraph);
       
   117     OutDegMap<ListDigraph> outDeg(digraph);
       
   118     std::vector<ListDigraph::Node> nodes(nodeNum);
       
   119     for (int i = 0; i < nodeNum; ++i) {
       
   120       nodes[i] = digraph.addNode();
       
   121     }
       
   122     std::vector<ListDigraph::Arc> arcs(arcNum);
       
   123     for (int i = 0; i < arcNum; ++i) {
       
   124       arcs[i] = 
       
   125 	digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
       
   126     }
       
   127     for (int i = 0; i < nodeNum; ++i) {
       
   128       check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]), 
       
   129 	    "Wrong in degree map");
       
   130     }
       
   131     for (int i = 0; i < nodeNum; ++i) {
       
   132       check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]), 
       
   133 	    "Wrong in degree map");
       
   134     }
       
   135   }
       
   136 
       
   137   ///Everything is OK
       
   138   std::cout << __FILE__ ": All tests passed.\n";
       
   139 
   211 
   140   return 0;
   212   return 0;
   141 }
   213 }