COIN-OR::LEMON - Graph Library

Changeset 171:02f4d5d9bfd7 in lemon


Ignore:
Timestamp:
06/15/08 22:05:23 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Children:
172:c94a80f38d7f, 173:b026e9779b28, 175:4eb8900a865c
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.