COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
06/15/08 22:05:23 (11 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Children:
172:c94a80f38d7f, 173:b026e9779b28, 175:4eb8900a865c
Phase:
public
Message:

Improve and redesign test programs + unify their output (ticket #25)

  • Move graph related utilities form test_tools.h to graph_test.h.
  • Move the contents of graph_utils_test.h to graph_utils_test.cc.
  • Rename map_test.h -> graph_maps_test.h.
  • Rename digraph_test.h -> graph_test.h.
  • Many improvements in the following files:
    • digraph_test.cc
    • graph_test.cc
    • graph_test.h
    • graph_maps_test.h
    • graph_utils_test.cc
    • bfs_test.cc
    • dfs_test.cc
    • counter_test.cc
  • Test programs print messages only if it really seems necessary.
  • Remove \file commands form .cc test files.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/graph_utils_test.cc

    r139 r171  
    1717 */
    1818
    19 #include <iostream>
    20 #include <vector>
    21 
     19#include <cstdlib>
     20#include <ctime>
     21
     22#include <lemon/random.h>
    2223#include <lemon/graph_utils.h>
    23 
    2424#include <lemon/list_graph.h>
    2525#include <lemon/smart_graph.h>
    2626
     27#include "graph_test.h"
    2728#include "test_tools.h"
    28 #include "graph_utils_test.h"
    29 
    3029
    3130using namespace lemon;
    3231
    33 template <class Graph>
    34 void checkSnapDeg()
     32template <typename Digraph>
     33void 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
     106template <typename Graph>
     107void 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
     139template <class Digraph>
     140void checkDeg()
    35141{
    36   Graph g;
    37   typename Graph::Node n1=g.addNode();
    38   typename Graph::Node n2=g.addNode();
    39    
    40   InDegMap<Graph> ind(g);
    41  
     142  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
     143 
     144  const int nodeNum = 10;
     145  const int arcNum = 100;
     146  Digraph digraph;
     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
     167template <class Digraph>
     168void 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 
    42178  g.addArc(n1,n2);
    43179 
    44   typename Graph::Snapshot snap(g);
    45  
    46   OutDegMap<Graph> outd(g);
     180  typename Digraph::Snapshot snap(g);
     181 
     182  OutDegMap<Digraph> outd(g);
    47183 
    48184  check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
     
    51187  g.addArc(n1,n2);
    52188  g.addArc(n2,n1);
    53  
     189
    54190  check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
    55191  check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
     
    59195  check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
    60196  check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
    61  
    62197}
    63198
    64199int main() {
    65   ///\file
    66   { // checking list graph
    67     checkDigraphCounters<ListDigraph>();
    68     checkFindArc<ListDigraph>();
    69   }
    70   { // checking smart graph
    71     checkDigraphCounters<SmartDigraph>();
    72     checkFindArc<SmartDigraph>();
    73   }
    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 
     200  // Checking ConArcIt, ConEdgeIt, ArcLookUp, AllArcLookUp, and DynArcLookUp
     201  checkFindArcs<ListDigraph>();
     202  checkFindArcs<SmartDigraph>();
     203  checkFindEdges<ListGraph>();
     204  checkFindEdges<SmartGraph>();
     205
     206  // Checking In/OutDegMap (and Snapshot feature)
     207  checkDeg<ListDigraph>();
     208  checkDeg<SmartDigraph>();
    109209  checkSnapDeg<ListDigraph>();
    110210  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";
    139211
    140212  return 0;
Note: See TracChangeset for help on using the changeset viewer.