COIN-OR::LEMON - Graph Library

Changeset 171:02f4d5d9bfd7 in lemon-1.2


Ignore:
Timestamp:
06/15/08 22:05:23 (16 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.
Location:
test
Files:
2 added
3 deleted
17 edited

Legend:

Unmodified
Added
Removed
  • test/CMakeLists.txt

    r170 r171  
    1212  error_test
    1313  graph_test
     14  graph_utils_test
    1415  kruskal_test
    1516  maps_test
     17  path_test
    1618  random_test
    17   path_test
    1819  time_measure_test
    1920  unionfind_test)
  • test/Makefile.am

    r170 r171  
    33
    44noinst_HEADERS += \
    5         test/digraph_test.h \
    6         test/graph_utils_test.h \
     5        test/graph_test.h \
    76        test/heap_test.h \
    8         test/map_test.h \
     7        test/graph_maps_test.h \
    98        test/test_tools.h
    109
  • test/bfs_test.cc

    r100 r171  
    1717 */
    1818
    19 #include "test_tools.h"
    20 //#include <lemon/smart_graph.h>
     19#include <lemon/concepts/digraph.h>
     20#include <lemon/smart_graph.h>
    2121#include <lemon/list_graph.h>
    2222#include <lemon/bfs.h>
    2323#include <lemon/path.h>
    24 #include<lemon/concepts/digraph.h>
     24
     25#include "graph_test.h"
     26#include "test_tools.h"
    2527
    2628using namespace lemon;
    2729
    28 const int PET_SIZE =5;
    29 
    30 
    31 void check_Bfs_Compile()
     30void checkBfsCompile()
    3231{
    3332  typedef concepts::Digraph Digraph;
    34 
    35   typedef Digraph::Arc Arc;
    36   typedef Digraph::Node Node;
    37   typedef Digraph::ArcIt ArcIt;
    38   typedef Digraph::NodeIt NodeIt;
    39  
    4033  typedef Bfs<Digraph> BType;
    4134 
    4235  Digraph G;
    43   Node n;
    44   Arc e;
     36  Digraph::Node n;
     37  Digraph::Arc e;
    4538  int l;
    4639  bool b;
     
    6457}
    6558
    66 void check_Bfs_Function_Compile()
     59void checkBfsFunctionCompile()
    6760{
    6861  typedef int VType;
    6962  typedef concepts::Digraph Digraph;
    70 
    7163  typedef Digraph::Arc Arc;
    7264  typedef Digraph::Node Node;
    73   typedef Digraph::ArcIt ArcIt;
    74   typedef Digraph::NodeIt NodeIt;
    75   typedef concepts::ReadMap<Arc,VType> LengthMap;
    7665   
    7766  Digraph g;
     
    8473    .processedMap(concepts::WriteMap<Node,bool>())
    8574    .run(Node());
    86  
    8775}
    8876
    89 int main()
    90 {
    91    
    92   // typedef SmartDigraph Digraph;
    93   typedef ListDigraph Digraph;
    94 
    95   typedef Digraph::Arc Arc;
    96   typedef Digraph::Node Node;
    97   typedef Digraph::ArcIt ArcIt;
    98   typedef Digraph::NodeIt NodeIt;
    99   typedef Digraph::ArcMap<int> LengthMap;
     77template <class Digraph>
     78void checkBfs() {
     79  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    10080
    10181  Digraph G;
    10282  Node s, t;
    103   PetStruct<Digraph> ps = addPetersen(G,PET_SIZE);
     83  PetStruct<Digraph> ps = addPetersen(G, 5);
    10484   
    10585  s=ps.outer[2];
     
    10989  bfs_test.run(s);
    11090 
    111   check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
     91  check(bfs_test.dist(t)==3,"Bfs found a wrong path." << bfs_test.dist(t));
    11292
    11393  Path<Digraph> p = bfs_test.path(t);
    114   check(p.length()==3,"getPath() found a wrong path.");
     94  check(p.length()==3,"path() found a wrong path.");
    11595  check(checkPath(G, p),"path() found a wrong path.");
    11696  check(pathSource(G, p) == s,"path() found a wrong path.");
     
    140120}
    141121
     122int main()
     123{
     124  checkBfs<ListDigraph>();
     125  checkBfs<SmartDigraph>();
     126  return 0;
     127}
  • test/counter_test.cc

    r119 r171  
    1818
    1919#include <lemon/counter.h>
     20#include <vector>
    2021
    21 ///\file \brief Test cases for time_measure.h
    22 ///
    23 ///\todo To be extended
     22using namespace lemon;
    2423
     24template <typename T>
     25void bubbleSort(std::vector<T>& v) {
     26  Counter op("Bubble Sort - Operations: ");
     27  Counter::NoSubCounter as(op, "Assignments: ");
     28  Counter::NoSubCounter co(op, "Comparisons: ");
     29  for (int i = v.size()-1; i > 0; --i) {
     30    for (int j = 0; j < i; ++j) {
     31      if (v[j] > v[j+1]) {
     32        T tmp = v[j];
     33        v[j] = v[j+1];
     34        v[j+1] = tmp;
     35        as += 3;
     36      }
     37      ++co;
     38    }
     39  }
     40}
    2541
    26 int fibonacci(int f)
    27 {
    28   static lemon::Counter count("Fibonacci steps: ");
    29   count++;
    30   if(f<1) return 0;
    31   else if(f==1) return 1;
    32   else return fibonacci(f-1)+fibonacci(f-2);
     42template <typename T>
     43void insertionSort(std::vector<T>& v) {
     44  Counter op("Insertion Sort - Operations: ");
     45  Counter::NoSubCounter as(op, "Assignments: ");
     46  Counter::NoSubCounter co(op, "Comparisons: ");
     47  for (int i = 1; i < int(v.size()); ++i) {
     48    T value = v[i];
     49    ++as;
     50    int j = i;
     51    while (j > 0 && v[j-1] > value) {
     52      v[j] = v[j-1];
     53      --j;
     54      ++co; ++as;
     55    }
     56    v[j] = value;
     57    ++as;
     58  }
     59}
     60
     61template <typename MyCounter>
     62void counterTest() {
     63  MyCounter c("Main Counter: ");
     64  c++;
     65  typename MyCounter::SubCounter d(c, "SubCounter: ");
     66  d++;
     67  typename MyCounter::SubCounter::NoSubCounter e(d, "SubSubCounter: ");
     68  e++;
     69  d+=3;
     70  c-=4;
     71  e-=2;
     72  c.reset(2);
     73  c.reset();
     74}
     75
     76void init(std::vector<int>& v) {
     77  v[0] = 10; v[1] = 60; v[2] = 20; v[3] = 90; v[4] = 100;
     78  v[5] = 80; v[6] = 40; v[7] = 30; v[8] = 50; v[9] = 70;
    3379}
    3480
    3581int main()
    3682{
    37   fibonacci(10);
     83  counterTest<Counter>();
     84  counterTest<NoCounter>();
    3885 
    39   { 
    40     typedef lemon::Counter MyCounter;
    41     MyCounter c("Main counter: ");
    42     c++;
    43     c++;
    44     MyCounter::SubCounter d(c,"Subcounter: ");
    45     d++;
    46     d++;
    47     MyCounter::SubCounter::SubCounter e(d,"SubSubCounter: ");
    48     e++;
    49     e++;
    50   }
    51  
    52   {
    53     typedef lemon::NoCounter MyCounter;
    54     MyCounter c("Main counter: ");
    55     c++;
    56     c++;
    57     MyCounter::SubCounter d(c,"Subcounter: ");
    58     d++;
    59     d++;
    60     MyCounter::SubCounter::SubCounter e(d,"SubSubCounter: ");
    61     e++;
    62     e++;
    63   }
     86  std::vector<int> x(10);
     87  init(x); bubbleSort(x);
     88  init(x); insertionSort(x);
    6489
    6590  return 0;
  • test/dfs_test.cc

    r100 r171  
    1717 */
    1818
    19 #include "test_tools.h"
    20 // #include <lemon/smart_graph.h>
     19#include <lemon/concepts/digraph.h>
     20#include <lemon/smart_graph.h>
    2121#include <lemon/list_graph.h>
    2222#include <lemon/dfs.h>
    2323#include <lemon/path.h>
    24 #include <lemon/concepts/digraph.h>
     24
     25#include "graph_test.h"
     26#include "test_tools.h"
    2527
    2628using namespace lemon;
    2729
    28 const int PET_SIZE =5;
    29 
    30 
    31 void check_Dfs_SmartDigraph_Compile()
     30void checkDfsCompile()
    3231{
    3332  typedef concepts::Digraph Digraph;
    34 
    35   typedef Digraph::Arc Arc;
    36   typedef Digraph::Node Node;
    37   typedef Digraph::ArcIt ArcIt;
    38   typedef Digraph::NodeIt NodeIt;
    39  
    4033  typedef Dfs<Digraph> DType;
    4134 
    4235  Digraph G;
    43   Node n;
    44   Arc e;
     36  Digraph::Node n;
     37  Digraph::Arc e;
    4538  int l;
    4639  bool b;
     
    6457}
    6558
    66 
    67 void check_Dfs_Function_Compile()
     59void checkDfsFunctionCompile()
    6860{
    6961  typedef int VType;
    7062  typedef concepts::Digraph Digraph;
    71 
    7263  typedef Digraph::Arc Arc;
    7364  typedef Digraph::Node Node;
    74   typedef Digraph::ArcIt ArcIt;
    75   typedef Digraph::NodeIt NodeIt;
    76   typedef concepts::ReadMap<Arc,VType> LengthMap;
    7765   
    7866  Digraph g;
     
    8472    .reachedMap(concepts::ReadWriteMap<Node,bool>())
    8573    .processedMap(concepts::WriteMap<Node,bool>())
    86     .run(Node());
    87  
     74    .run(Node());
    8875}
    8976
    90 int main()
    91 {
    92    
    93   // typedef SmartDigraph Digraph;
    94   typedef ListDigraph Digraph;
    95 
    96   typedef Digraph::Arc Arc;
    97   typedef Digraph::Node Node;
    98   typedef Digraph::ArcIt ArcIt;
    99   typedef Digraph::NodeIt NodeIt;
    100   typedef Digraph::ArcMap<int> LengthMap;
     77template <class Digraph>
     78void checkDfs() {
     79  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    10180
    10281  Digraph G;
    10382  Node s, t;
    104   PetStruct<Digraph> ps = addPetersen(G,PET_SIZE);
     83  PetStruct<Digraph> ps = addPetersen(G, 5);
    10584   
    10685  s=ps.outer[2];
     
    11190 
    11291  Path<Digraph> p = dfs_test.path(t);
    113   check(p.length()==dfs_test.dist(t),"path() found a wrong path.");
     92  check(p.length() == dfs_test.dist(t),"path() found a wrong path.");
    11493  check(checkPath(G, p),"path() found a wrong path.");
    11594  check(pathSource(G, p) == s,"path() found a wrong path.");
     
    129108}
    130109
     110int main()
     111{
     112  checkDfs<ListDigraph>();
     113  checkDfs<SmartDigraph>();
     114  return 0;
     115}
  • test/digraph_test.cc

    r107 r171  
    1717 */
    1818
    19 #include <iostream>
    20 #include <vector>
    21 
    2219#include <lemon/concepts/digraph.h>
    2320#include <lemon/list_graph.h>
    24 //#include <lemon/smart_graph.h>
     21#include <lemon/smart_graph.h>
    2522//#include <lemon/full_graph.h>
    2623//#include <lemon/hypercube_graph.h>
    2724
    2825#include "test_tools.h"
    29 #include "digraph_test.h"
    30 #include "map_test.h"
    31 
     26#include "graph_test.h"
     27#include "graph_maps_test.h"
    3228
    3329using namespace lemon;
    3430using namespace lemon::concepts;
    3531
    36 
    37 int main() {
    38   { // checking digraph components
     32void check_concepts() {
     33  { // Checking digraph components
    3934    checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
    4035
     
    4742    checkConcept<MappableDigraphComponent<>,
    4843      MappableDigraphComponent<> >();
    49 
    5044  }
    51   { // checking skeleton digraphs
     45  { // Checking skeleton digraph
    5246    checkConcept<Digraph, Digraph>();
    5347  }
    54   { // checking list digraph
    55     checkConcept<Digraph, ListDigraph >();
     48  { // Checking ListDigraph
     49    checkConcept<Digraph, ListDigraph>();
    5650    checkConcept<AlterableDigraphComponent<>, ListDigraph>();
    5751    checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
    5852    checkConcept<ClearableDigraphComponent<>, ListDigraph>();
    5953    checkConcept<ErasableDigraphComponent<>, ListDigraph>();
     54    checkDigraphIterators<ListDigraph>();
     55  }
     56  { // Checking SmartDigraph
     57    checkConcept<Digraph, SmartDigraph>();
     58    checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
     59    checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
     60    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
     61    checkDigraphIterators<SmartDigraph>();
     62  }
     63//  { // Checking FullDigraph
     64//    checkConcept<Digraph, FullDigraph>();
     65//    checkDigraphIterators<FullDigraph>();
     66//  }
     67//  { // Checking HyperCubeDigraph
     68//    checkConcept<Digraph, HyperCubeDigraph>();
     69//    checkDigraphIterators<HyperCubeDigraph>();
     70//  }
     71}
    6072
     73template <typename Digraph>
     74void check_graph_validity() {
     75  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
     76  Digraph g;
     77
     78  Node
     79    n1 = g.addNode(),
     80    n2 = g.addNode(),
     81    n3 = g.addNode();
     82
     83  Arc
     84    e1 = g.addArc(n1, n2),
     85    e2 = g.addArc(n2, n3);
     86
     87  check(g.valid(n1), "Wrong validity check");
     88  check(g.valid(e1), "Wrong validity check");
     89
     90  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
     91  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
     92}
     93
     94template <typename Digraph>
     95void check_graph_validity_erase() {
     96  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
     97  Digraph g;
     98
     99  Node
     100    n1 = g.addNode(),
     101    n2 = g.addNode(),
     102    n3 = g.addNode();
     103
     104  Arc
     105    e1 = g.addArc(n1, n2),
     106    e2 = g.addArc(n2, n3);
     107
     108  check(g.valid(n1), "Wrong validity check");
     109  check(g.valid(e1), "Wrong validity check");
     110
     111  g.erase(n1);
     112
     113  check(!g.valid(n1), "Wrong validity check");
     114  check(g.valid(n2), "Wrong validity check");
     115  check(g.valid(n3), "Wrong validity check");
     116  check(!g.valid(e1), "Wrong validity check");
     117  check(g.valid(e2), "Wrong validity check");
     118
     119  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
     120  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
     121}
     122
     123void check_digraphs() {
     124  { // Checking ListDigraph
    61125    checkDigraph<ListDigraph>();
    62126    checkGraphNodeMap<ListDigraph>();
    63127    checkGraphArcMap<ListDigraph>();
     128
     129    check_graph_validity_erase<ListDigraph>();
    64130  }
    65 //   { // checking smart digraph
    66 //     checkConcept<Digraph, SmartDigraph >();
     131  { // Checking SmartDigraph
     132    checkDigraph<SmartDigraph>();
     133    checkGraphNodeMap<SmartDigraph>();
     134    checkGraphArcMap<SmartDigraph>();
    67135
    68 //     checkDigraph<SmartDigraph>();
    69 //     checkDigraphNodeMap<SmartDigraph>();
    70 //     checkDigraphArcMap<SmartDigraph>();
    71 //   }
    72 //   { // checking full digraph
    73 //     checkConcept<Digraph, FullDigraph >();
    74 //   }
    75 //   { // checking full digraph
    76 //     checkConcept<Digraph, HyperCubeDigraph >();
    77 //   }
     136    check_graph_validity<SmartDigraph>();
     137  }
     138}
    78139
    79   std::cout << __FILE__ ": All tests passed.\n";
    80 
     140int main() {
     141  check_concepts();
     142  check_digraphs();
    81143  return 0;
    82144}
  • test/dijkstra_test.cc

    r170 r171  
    1717 */
    1818
    19 ///\file
    20 ///\brief Test cases for Dijkstra algorithm.
    21 
    2219#include <lemon/concepts/digraph.h>
    2320#include <lemon/smart_graph.h>
     
    2724#include <lemon/path.h>
    2825
     26#include "graph_test.h"
    2927#include "test_tools.h"
    3028
  • test/dim_test.cc

    r39 r171  
    2626int main()
    2727{
    28   cout << "Testing classes 'dim2::Point' and 'dim2::BoundingBox'." << endl;
    29 
    3028  typedef dim2::Point<int> Point;
    3129
    3230  Point p;
    33   check(p.size()==2, "Wrong vector initialization.");
     31  check(p.size()==2, "Wrong dim2::Point initialization.");
    3432
    3533  Point a(1,2);
    3634  Point b(3,4);
    37   check(a[0]==1 && a[1]==2, "Wrong vector initialization.");
     35  check(a[0]==1 && a[1]==2, "Wrong dim2::Point initialization.");
    3836
    3937  p = a+b;
    40   check(p.x==4 && p.y==6, "Wrong vector addition.");
     38  check(p.x==4 && p.y==6, "Wrong dim2::Point addition.");
    4139
    4240  p = a-b;
    43   check(p.x==-2 && p.y==-2, "Wrong vector subtraction.");
     41  check(p.x==-2 && p.y==-2, "Wrong dim2::Point subtraction.");
    4442
    45   check(a.normSquare()==5,"Wrong vector norm calculation.");
    46   check(a*b==11, "Wrong vector scalar product.");
     43  check(a.normSquare()==5,"Wrong dim2::Point norm calculation.");
     44  check(a*b==11, "Wrong dim2::Point scalar product.");
    4745
    4846  int l=2;
    4947  p = a*l;
    50   check(p.x==2 && p.y==4, "Wrong vector multiplication by a scalar.");
     48  check(p.x==2 && p.y==4, "Wrong dim2::Point multiplication by a scalar.");
    5149
    5250  p = b/l;
    53   check(p.x==1 && p.y==2, "Wrong vector division by a scalar.");
     51  check(p.x==1 && p.y==2, "Wrong dim2::Point division by a scalar.");
    5452
    5553  typedef dim2::BoundingBox<int> BB;
    5654  BB box1;
    57   check(box1.empty(), "It should be empty.");
     55  check(box1.empty(), "Wrong empty() in dim2::BoundingBox.");
    5856
    5957  box1.add(a);
    60   check(!box1.empty(), "It should not be empty.");
     58  check(!box1.empty(), "Wrong empty() in dim2::BoundingBox.");
    6159  box1.add(b);
    6260
     
    6563        box1.topRight().x==3 &&
    6664        box1.topRight().y==4,
    67         "Wrong addition of points to box.");
     65        "Wrong addition of points to dim2::BoundingBox.");
    6866
    6967  p.x=2; p.y=3;
    70   check(box1.inside(p), "It should be inside.");
     68  check(box1.inside(p), "Wrong inside() in dim2::BoundingBox.");
    7169
    7270  p.x=1; p.y=3;
    73   check(box1.inside(p), "It should be inside.");
     71  check(box1.inside(p), "Wrong inside() in dim2::BoundingBox.");
    7472
    7573  p.x=0; p.y=3;
    76   check(!box1.inside(p), "It should not be inside.");
     74  check(!box1.inside(p), "Wrong inside() in dim2::BoundingBox.");
    7775
    7876  BB box2(p);
    79   check(!box2.empty(),
    80         "It should not be empty. Constructed from 1 point.");
     77  check(!box2.empty(), "Wrong empty() in dim2::BoundingBox.");
    8178
    8279  box2.add(box1);
    83   check(box2.inside(p),
    84         "It should be inside. Incremented a box with another one.");
     80  check(box2.inside(p), "Wrong inside() in dim2::BoundingBox.");
    8581
    8682  return 0;
  • test/error_test.cc

    r118 r171  
    5555#undef LEMON_DISABLE_ASSERTS
    5656
     57//checking custom assert handler
    5758#define LEMON_ASSERT_CUSTOM
    5859
  • test/graph_test.cc

    r149 r171  
    2323// #include <lemon/grid_graph.h>
    2424
    25 #include <lemon/graph_utils.h>
    26 
    2725#include "test_tools.h"
    28 
     26#include "graph_test.h"
     27#include "graph_maps_test.h"
    2928
    3029using namespace lemon;
     
    3231
    3332void check_concepts() {
    34 
    35   { // checking digraph components
     33  { // Checking graph components
    3634    checkConcept<BaseGraphComponent, BaseGraphComponent >();
    3735
     
    4442    checkConcept<MappableGraphComponent<>,
    4543      MappableGraphComponent<> >();
    46 
    47   }
    48   {
    49     checkConcept<Graph, ListGraph>();   
    50     checkConcept<Graph, SmartGraph>();   
    51 //     checkConcept<Graph, FullGraph>();   
    52 //     checkConcept<Graph, Graph>();   
    53 //     checkConcept<Graph, GridGraph>();
    54   }
     44  }
     45  { // Checking skeleton graph
     46    checkConcept<Graph, Graph>();
     47  }
     48  { // Checking ListGraph
     49    checkConcept<Graph, ListGraph>();
     50    checkConcept<AlterableGraphComponent<>, ListGraph>();
     51    checkConcept<ExtendableGraphComponent<>, ListGraph>();
     52    checkConcept<ClearableGraphComponent<>, ListGraph>();
     53    checkConcept<ErasableGraphComponent<>, ListGraph>();
     54    checkGraphIterators<ListGraph>();
     55  }
     56  { // Checking SmartGraph
     57    checkConcept<Graph, SmartGraph>();
     58    checkConcept<AlterableGraphComponent<>, SmartGraph>();
     59    checkConcept<ExtendableGraphComponent<>, SmartGraph>();
     60    checkConcept<ClearableGraphComponent<>, SmartGraph>();
     61    checkGraphIterators<SmartGraph>();
     62  }
     63//  { // Checking FullGraph
     64//    checkConcept<Graph, FullGraph>();
     65//    checkGraphIterators<FullGraph>();
     66//  }
     67//  { // Checking GridGraph
     68//    checkConcept<Graph, GridGraph>();
     69//    checkGraphIterators<GridGraph>();
     70//  }
    5571}
    5672
    5773template <typename Graph>
    58 void check_item_counts(Graph &g, int n, int e) {
    59   int nn = 0;
    60   for (typename Graph::NodeIt it(g); it != INVALID; ++it) {
    61     ++nn;
    62   }
    63 
    64   check(nn == n, "Wrong node number.");
    65   //  check(countNodes(g) == n, "Wrong node number.");
    66 
    67   int ee = 0;
    68   for (typename Graph::ArcIt it(g); it != INVALID; ++it) {
    69     ++ee;
    70   }
    71 
    72   check(ee == 2*e, "Wrong arc number.");
    73   //  check(countArcs(g) == 2*e, "Wrong arc number.");
    74 
    75   int uee = 0;
    76   for (typename Graph::EdgeIt it(g); it != INVALID; ++it) {
    77     ++uee;
    78   }
    79 
    80   check(uee == e, "Wrong edge number.");
    81   //  check(countEdges(g) == e, "Wrong edge number.");
    82 }
    83 
    84 template <typename Graph>
    85 void check_graph_counts() {
    86 
     74void check_graph_validity() {
    8775  TEMPLATE_GRAPH_TYPEDEFS(Graph);
    8876  Graph g;
    89 
    90   check_item_counts(g,0,0);
    9177
    9278  Node
     
    9985    e2 = g.addEdge(n2, n3);
    10086
    101   check_item_counts(g,3,2);
     87  check(g.valid(n1), "Wrong validity check");
     88  check(g.valid(e1), "Wrong validity check");
     89  check(g.valid(g.direct(e1, true)), "Wrong validity check");
     90
     91  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
     92  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
     93  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
    10294}
    10395
    10496template <typename Graph>
    105 void check_graph_validity() {
    106 
     97void check_graph_validity_erase() {
    10798  TEMPLATE_GRAPH_TYPEDEFS(Graph);
    10899  Graph g;
    109 
    110   check_item_counts(g,0,0);
    111100
    112101  Node
     
    119108    e2 = g.addEdge(n2, n3);
    120109
    121   check(g.valid(n1), "Validity check");
    122   check(g.valid(e1), "Validity check");
    123   check(g.valid(g.direct(e1, true)), "Validity check");
    124 
    125   check(!g.valid(g.nodeFromId(-1)), "Validity check");
    126   check(!g.valid(g.edgeFromId(-1)), "Validity check");
    127   check(!g.valid(g.arcFromId(-1)), "Validity check");
    128    
    129 }
    130 
    131 template <typename Graph>
    132 void check_graph_validity_erase() {
    133 
    134   TEMPLATE_GRAPH_TYPEDEFS(Graph);
    135   Graph g;
    136 
    137   check_item_counts(g,0,0);
    138 
    139   Node
    140     n1 = g.addNode(),
    141     n2 = g.addNode(),
    142     n3 = g.addNode();
    143 
    144   Edge
    145     e1 = g.addEdge(n1, n2),
    146     e2 = g.addEdge(n2, n3);
    147 
    148   check(g.valid(n1), "Validity check");
    149   check(g.valid(e1), "Validity check");
    150   check(g.valid(g.direct(e1, true)), "Validity check");
     110  check(g.valid(n1), "Wrong validity check");
     111  check(g.valid(e1), "Wrong validity check");
     112  check(g.valid(g.direct(e1, true)), "Wrong validity check");
    151113
    152114  g.erase(n1);
    153115
    154   check(!g.valid(n1), "Validity check");
    155   check(g.valid(n2), "Validity check");
    156   check(g.valid(n3), "Validity check");
    157   check(!g.valid(e1), "Validity check");
    158   check(g.valid(e2), "Validity check");
    159 
    160   check(!g.valid(g.nodeFromId(-1)), "Validity check");
    161   check(!g.valid(g.edgeFromId(-1)), "Validity check");
    162   check(!g.valid(g.arcFromId(-1)), "Validity check");
    163    
    164 }
    165 
    166 
     116  check(!g.valid(n1), "Wrong validity check");
     117  check(g.valid(n2), "Wrong validity check");
     118  check(g.valid(n3), "Wrong validity check");
     119  check(!g.valid(e1), "Wrong validity check");
     120  check(g.valid(e2), "Wrong validity check");
     121
     122  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
     123  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
     124  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
     125}
    167126
    168127// void checkGridGraph(const GridGraph& g, int w, int h) {
     
    210169// }
    211170
     171void check_graphs() {
     172  { // Checking ListGraph
     173    checkGraph<ListGraph>();
     174    checkGraphNodeMap<ListGraph>();
     175    checkGraphEdgeMap<ListGraph>();
     176
     177    check_graph_validity_erase<ListGraph>();
     178  }
     179  { // Checking SmartGraph
     180    checkGraph<SmartGraph>();
     181    checkGraphNodeMap<SmartGraph>();
     182    checkGraphEdgeMap<SmartGraph>();
     183
     184    check_graph_validity<SmartGraph>();
     185  }
     186//   { // Checking FullGraph
     187//     FullGraph g(5);
     188//     checkGraphNodeList(g, 5);
     189//     checkGraphEdgeList(g, 10);
     190//   }
     191//   { // Checking GridGraph
     192//     GridGraph g(5, 6);
     193//     checkGraphNodeList(g, 30);
     194//     checkGraphEdgeList(g, 49);
     195//     checkGridGraph(g, 5, 6);
     196//   }
     197}
     198
    212199int main() {
    213200  check_concepts();
    214 
    215   check_graph_counts<ListGraph>();
    216   check_graph_counts<SmartGraph>();
    217 
    218   check_graph_validity_erase<ListGraph>();
    219   check_graph_validity<SmartGraph>();
    220 
    221 //   {
    222 //     FullGraph g(5);
    223 //     check_item_counts(g, 5, 10);
    224 //   }
    225 
    226 //   {
    227 //     GridGraph g(5, 6);
    228 //     check_item_counts(g, 30, 49);
    229 //     checkGridGraph(g, 5, 6);
    230 //   }
    231 
    232   std::cout << __FILE__ ": All tests passed.\n";
    233 
     201  check_graphs();
    234202  return 0;
    235203}
  • 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;
  • test/heap_test.cc

    r100 r171  
    4343using namespace lemon::concepts;
    4444
    45 
    4645int main() {
    4746
     
    7877 
    7978  {
    80     std::cerr << "Checking Bin Heap" << std::endl;
     79    std::cout << "Checking Bin Heap" << std::endl;
    8180
    8281    typedef BinHeap<Prio, ItemIntMap> IntHeap;
     
    9291  }
    9392  {
    94     std::cerr << "Checking Fib Heap" << std::endl;
     93    std::cout << "Checking Fib Heap" << std::endl;
    9594
    9695    typedef FibHeap<Prio, ItemIntMap> IntHeap;
     
    106105  }
    107106  {
    108     std::cerr << "Checking Radix Heap" << std::endl;
     107    std::cout << "Checking Radix Heap" << std::endl;
    109108
    110109    typedef RadixHeap<ItemIntMap> IntHeap;
     
    121120
    122121  {
    123     std::cerr << "Checking Bucket Heap" << std::endl;
     122    std::cout << "Checking Bucket Heap" << std::endl;
    124123
    125124    typedef BucketHeap<ItemIntMap> IntHeap;
     
    135134  }
    136135
    137   std::cout << __FILE__ ": All tests passed.\n";
    138 
    139136  return 0;
    140137}
  • test/kruskal_test.cc

    r103 r171  
    2929#include <lemon/concepts/graph.h>
    3030
    31 
    3231using namespace std;
    3332using namespace lemon;
     
    5857  kruskal(g, r, ws.begin());
    5958  kruskal(ug, ur, uws.begin());
    60 
    6159}
    6260
     
    9896  check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
    9997        "Total cost should be 10");
    100   //Test with a edge map (filled with uniform costs).
     98  //Test with an edge map (filled with uniform costs).
    10199  check(kruskal(G, edge_cost_map, tree_map)==10,
    102100        "Total cost should be 10");
  • test/random_test.cc

    r102 r171  
    2020#include "test_tools.h"
    2121
    22 ///\file \brief Test cases for random.h
    23 ///
    24 ///\todo To be extended
    25 ///
    26 
    2722int seed_array[] = {1, 2};
    2823
  • test/test_tools.h

    r100 r171  
    2020#define LEMON_TEST_TEST_TOOLS_H
    2121
     22///\ingroup misc
     23///\file
     24///\brief Some utilities to write test programs.
     25
    2226#include <iostream>
    23 #include <vector>
    2427
    25 #include <cstdlib>
    26 #include <ctime>
     28///If \c rc is fail, writes an error message and exits.
    2729
    28 #include <lemon/concept_check.h>
    29 #include <lemon/concepts/digraph.h>
    30 
    31 #include <lemon/random.h>
    32 
    33 using namespace lemon;
    34 
    35 //! \ingroup misc
    36 //! \file
    37 //! \brief Some utilities to write test programs.
    38 
    39 
    40 ///If \c rc is fail, writes an error message end exit.
    41 
    42 ///If \c rc is fail, writes an error message end exit.
     30///If \c rc is fail, writes an error message and exits.
    4331///The error message contains the file name and the line number of the
    4432///source code in a standard from, which makes it possible to go there
     
    4735///For example
    4836///\code check(0==1,"This is obviously false.");\endcode will
    49 ///print this (and then exits).
    50 ///\verbatim digraph_test.cc:123: error: This is obviously false. \endverbatim
     37///print something like this (and then exits).
     38///\verbatim file_name.cc:123: error: This is obviously false. \endverbatim
    5139///
    52 ///\todo It should be in \c error.h
     40///\todo It should be in \c assert.h
    5341#define check(rc, msg) \
    5442  if(!(rc)) { \
     
    5745  } else { } \
    5846
    59 ///Structure returned by \ref addPetersen().
    60 
    61 ///Structure returned by \ref addPetersen().
    62 ///
    63 template<class Digraph> struct PetStruct
    64 {
    65   ///Vector containing the outer nodes.
    66   std::vector<typename Digraph::Node> outer;
    67   ///Vector containing the inner nodes.
    68   std::vector<typename Digraph::Node> inner;
    69   ///Vector containing the arcs of the inner circle.
    70   std::vector<typename Digraph::Arc> incir;
    71   ///Vector containing the arcs of the outer circle.
    72   std::vector<typename Digraph::Arc> outcir;
    73   ///Vector containing the chord arcs.
    74   std::vector<typename Digraph::Arc> chords;
    75 };
    76 
    77 
    78 
    79 ///Adds a Petersen digraph to \c G.
    80 
    81 ///Adds a Petersen digraph to \c G.
    82 ///\return The nodes and arcs of the generated digraph.
    83 
    84 template<typename Digraph>
    85 PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
    86 {
    87   PetStruct<Digraph> n;
    88 
    89   for(int i=0;i<num;i++) {
    90     n.outer.push_back(G.addNode());
    91     n.inner.push_back(G.addNode());
    92   }
    93 
    94  for(int i=0;i<num;i++) {
    95    n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
    96    n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));
    97    n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));
    98   }
    99  return n;
    100 }
    101 
    102 /// \brief Adds to the digraph the reverse pair of all arcs.
    103 ///
    104 /// Adds to the digraph the reverse pair of all arcs.
    105 ///
    106 template<class Digraph> void bidirDigraph(Digraph &G)
    107 {
    108   typedef typename Digraph::Arc Arc;
    109   typedef typename Digraph::ArcIt ArcIt;
    110  
    111   std::vector<Arc> ee;
    112  
    113   for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
    114 
    115   for(typename std::vector<Arc>::iterator p=ee.begin();p!=ee.end();p++)
    116     G.addArc(G.target(*p),G.source(*p));
    117 }
    118 
    119 
    120 /// \brief Checks the bidirectioned Petersen digraph.
    121 ///
    122 ///  Checks the bidirectioned Petersen digraph.
    123 ///
    124 template<class Digraph> void checkBidirPetersen(Digraph &G, int num = 5)
    125 {
    126   typedef typename Digraph::Node Node;
    127 
    128   typedef typename Digraph::ArcIt ArcIt;
    129   typedef typename Digraph::NodeIt NodeIt;
    130 
    131   checkDigraphNodeList(G, 2 * num);
    132   checkDigraphArcList(G, 6 * num);
    133 
    134   for(NodeIt n(G);n!=INVALID;++n) {
    135     checkDigraphInArcList(G, n, 3);
    136     checkDigraphOutArcList(G, n, 3);
    137   } 
    138 }
    139 
    140 ///Structure returned by \ref addUPetersen().
    141 
    142 ///Structure returned by \ref addUPetersen().
    143 ///
    144 template<class Digraph> struct UPetStruct
    145 {
    146   ///Vector containing the outer nodes.
    147   std::vector<typename Digraph::Node> outer;
    148   ///Vector containing the inner nodes.
    149   std::vector<typename Digraph::Node> inner;
    150   ///Vector containing the arcs of the inner circle.
    151   std::vector<typename Digraph::Edge> incir;
    152   ///Vector containing the arcs of the outer circle.
    153   std::vector<typename Digraph::Edge> outcir;
    154   ///Vector containing the chord arcs.
    155   std::vector<typename Digraph::Edge> chords;
    156 };
    157 
    158 ///Adds a Petersen digraph to the undirected \c G.
    159 
    160 ///Adds a Petersen digraph to the undirected \c G.
    161 ///\return The nodes and arcs of the generated digraph.
    162 
    163 template<typename Digraph>
    164 UPetStruct<Digraph> addUPetersen(Digraph &G,int num=5)
    165 {
    166   UPetStruct<Digraph> n;
    167 
    168   for(int i=0;i<num;i++) {
    169     n.outer.push_back(G.addNode());
    170     n.inner.push_back(G.addNode());
    171   }
    172 
    173  for(int i=0;i<num;i++) {
    174    n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
    175    n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1)%5]));
    176    n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2)%5]));
    177  }
    178  return n;
    179 }
    180 
    18147#endif
  • test/time_measure_test.cc

    r119 r171  
    1818
    1919#include <lemon/time_measure.h>
    20 
    21 ///\file \brief Test cases for time_measure.h
    22 ///
    23 ///\todo To be extended
    24 
    2520
    2621using namespace lemon;
  • test/unionfind_test.cc

    r105 r171  
    1616 *
    1717 */
    18 
    19 #include <iostream>
    2018
    2119#include <lemon/list_graph.h>
     
    4038  U.insert(n[2]);
    4139
    42   check(U.join(n[1],n[2]) != -1,"Test failed.");
     40  check(U.join(n[1],n[2]) != -1, "Something is wrong with UnionFindEnum");
    4341
    4442  U.insert(n[3]);
     
    4947
    5048
    51   check(U.join(n[1],n[4]) != -1,"Test failed.");
    52   check(U.join(n[2],n[4]) == -1,"Test failed.");
    53   check(U.join(n[3],n[5]) != -1,"Test failed.");
     49  check(U.join(n[1],n[4]) != -1, "Something is wrong with UnionFindEnum");
     50  check(U.join(n[2],n[4]) == -1, "Something is wrong with UnionFindEnum");
     51  check(U.join(n[3],n[5]) != -1, "Something is wrong with UnionFindEnum");
    5452
    5553
     
    5755
    5856
    59   check(U.size(U.find(n[4])) == 3,"Test failed.");
    60   check(U.size(U.find(n[5])) == 3,"Test failed.");
    61   check(U.size(U.find(n[6])) == 1,"Test failed.");
    62   check(U.size(U.find(n[2])) == 3,"Test failed.");
     57  check(U.size(U.find(n[4])) == 3, "Something is wrong with UnionFindEnum");
     58  check(U.size(U.find(n[5])) == 3, "Something is wrong with UnionFindEnum");
     59  check(U.size(U.find(n[6])) == 1, "Something is wrong with UnionFindEnum");
     60  check(U.size(U.find(n[2])) == 3, "Something is wrong with UnionFindEnum");
    6361
    6462
     
    6765
    6866
    69   check(U.join(n[8],n[10]) != -1,"Test failed.");
     67  check(U.join(n[8],n[10])  != -1, "Something is wrong with UnionFindEnum");
    7068
    7169
    72   check(U.size(U.find(n[4])) == 3,"Test failed.");
    73   check(U.size(U.find(n[9])) == 5,"Test failed.");
     70  check(U.size(U.find(n[4])) == 3, "Something is wrong with UnionFindEnum");
     71  check(U.size(U.find(n[9])) == 5, "Something is wrong with UnionFindEnum");
    7472
    75   check(U.size(U.find(n[8])) == 5,"Test failed.");
     73  check(U.size(U.find(n[8])) == 5, "Something is wrong with UnionFindEnum");
    7674
    7775  U.erase(n[9]);
    7876  U.erase(n[1]);
    7977
    80   check(U.size(U.find(n[10])) == 4,"Test failed.");
    81   check(U.size(U.find(n[2])) == 2,"Test failed.");
     78  check(U.size(U.find(n[10])) == 4, "Something is wrong with UnionFindEnum");
     79  check(U.size(U.find(n[2]))  == 2, "Something is wrong with UnionFindEnum");
    8280
    8381  U.erase(n[6]);
     
    8583
    8684
    87   check(U.size(U.find(n[4])) == 2,"Test failed.");
    88   check(U.size(U.find(n[3])) == 1,"Test failed.");
    89   check(U.size(U.find(n[2])) == 2,"Test failed.");
     85  check(U.size(U.find(n[4])) == 2, "Something is wrong with UnionFindEnum");
     86  check(U.size(U.find(n[3])) == 1, "Something is wrong with UnionFindEnum");
     87  check(U.size(U.find(n[2])) == 2, "Something is wrong with UnionFindEnum");
    9088
    9189
    92   check(U.join(n[3],n[4]) != -1,"Test failed.");
    93   check(U.join(n[2],n[4]) == -1,"Test failed.");
     90  check(U.join(n[3],n[4]) != -1, "Something is wrong with UnionFindEnum");
     91  check(U.join(n[2],n[4]) == -1, "Something is wrong with UnionFindEnum");
    9492
    9593
    96   check(U.size(U.find(n[4])) == 3,"Test failed.");
    97   check(U.size(U.find(n[3])) == 3,"Test failed.");
    98   check(U.size(U.find(n[2])) == 3,"Test failed.");
     94  check(U.size(U.find(n[4])) == 3, "Something is wrong with UnionFindEnum");
     95  check(U.size(U.find(n[3])) == 3, "Something is wrong with UnionFindEnum");
     96  check(U.size(U.find(n[2])) == 3, "Something is wrong with UnionFindEnum");
    9997
    10098  U.eraseClass(U.find(n[4]));
Note: See TracChangeset for help on using the changeset viewer.