Improve and redesign test programs + unify their output (ticket #25)
authorPeter Kovacs <kpeter@inf.elte.hu>
Sun, 15 Jun 2008 22:05:23 +0200
changeset 17102f4d5d9bfd7
parent 170 91fb4372688f
child 172 c94a80f38d7f
child 173 b026e9779b28
child 175 4eb8900a865c
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.
test/CMakeLists.txt
test/Makefile.am
test/bfs_test.cc
test/counter_test.cc
test/dfs_test.cc
test/digraph_test.cc
test/digraph_test.h
test/dijkstra_test.cc
test/dim_test.cc
test/error_test.cc
test/graph_maps_test.h
test/graph_test.cc
test/graph_test.h
test/graph_utils_test.cc
test/graph_utils_test.h
test/heap_test.cc
test/kruskal_test.cc
test/map_test.h
test/random_test.cc
test/test_tools.h
test/time_measure_test.cc
test/unionfind_test.cc
     1.1 --- a/test/CMakeLists.txt	Sun Jun 15 22:03:33 2008 +0200
     1.2 +++ b/test/CMakeLists.txt	Sun Jun 15 22:05:23 2008 +0200
     1.3 @@ -11,10 +11,11 @@
     1.4    dim_test
     1.5    error_test
     1.6    graph_test
     1.7 +  graph_utils_test
     1.8    kruskal_test
     1.9    maps_test
    1.10 +  path_test
    1.11    random_test
    1.12 -  path_test
    1.13    time_measure_test
    1.14    unionfind_test)
    1.15  
     2.1 --- a/test/Makefile.am	Sun Jun 15 22:03:33 2008 +0200
     2.2 +++ b/test/Makefile.am	Sun Jun 15 22:05:23 2008 +0200
     2.3 @@ -2,10 +2,9 @@
     2.4  	test/CMakeLists.txt
     2.5  
     2.6  noinst_HEADERS += \
     2.7 -	test/digraph_test.h \
     2.8 -	test/graph_utils_test.h \
     2.9 +	test/graph_test.h \
    2.10  	test/heap_test.h \
    2.11 -	test/map_test.h \
    2.12 +	test/graph_maps_test.h \
    2.13          test/test_tools.h
    2.14  
    2.15  check_PROGRAMS += \
     3.1 --- a/test/bfs_test.cc	Sun Jun 15 22:03:33 2008 +0200
     3.2 +++ b/test/bfs_test.cc	Sun Jun 15 22:05:23 2008 +0200
     3.3 @@ -16,32 +16,25 @@
     3.4   *
     3.5   */
     3.6  
     3.7 -#include "test_tools.h"
     3.8 -//#include <lemon/smart_graph.h>
     3.9 +#include <lemon/concepts/digraph.h>
    3.10 +#include <lemon/smart_graph.h>
    3.11  #include <lemon/list_graph.h>
    3.12  #include <lemon/bfs.h>
    3.13  #include <lemon/path.h>
    3.14 -#include<lemon/concepts/digraph.h>
    3.15 +
    3.16 +#include "graph_test.h"
    3.17 +#include "test_tools.h"
    3.18  
    3.19  using namespace lemon;
    3.20  
    3.21 -const int PET_SIZE =5;
    3.22 -
    3.23 -
    3.24 -void check_Bfs_Compile() 
    3.25 +void checkBfsCompile() 
    3.26  {
    3.27    typedef concepts::Digraph Digraph;
    3.28 -
    3.29 -  typedef Digraph::Arc Arc;
    3.30 -  typedef Digraph::Node Node;
    3.31 -  typedef Digraph::ArcIt ArcIt;
    3.32 -  typedef Digraph::NodeIt NodeIt;
    3.33 - 
    3.34    typedef Bfs<Digraph> BType;
    3.35    
    3.36    Digraph G;
    3.37 -  Node n;
    3.38 -  Arc e;
    3.39 +  Digraph::Node n;
    3.40 +  Digraph::Arc e;
    3.41    int l;
    3.42    bool b;
    3.43    BType::DistMap d(G);
    3.44 @@ -63,16 +56,12 @@
    3.45    Path<Digraph> pp = bfs_test.path(n);
    3.46  }
    3.47  
    3.48 -void check_Bfs_Function_Compile() 
    3.49 +void checkBfsFunctionCompile() 
    3.50  {
    3.51    typedef int VType;
    3.52    typedef concepts::Digraph Digraph;
    3.53 -
    3.54    typedef Digraph::Arc Arc;
    3.55    typedef Digraph::Node Node;
    3.56 -  typedef Digraph::ArcIt ArcIt;
    3.57 -  typedef Digraph::NodeIt NodeIt;
    3.58 -  typedef concepts::ReadMap<Arc,VType> LengthMap;
    3.59     
    3.60    Digraph g;
    3.61    bfs(g,Node()).run();
    3.62 @@ -83,24 +72,15 @@
    3.63      .reachedMap(concepts::ReadWriteMap<Node,bool>())
    3.64      .processedMap(concepts::WriteMap<Node,bool>())
    3.65      .run(Node());
    3.66 -  
    3.67  }
    3.68  
    3.69 -int main()
    3.70 -{
    3.71 -    
    3.72 -  // typedef SmartDigraph Digraph;
    3.73 -  typedef ListDigraph Digraph;
    3.74 -
    3.75 -  typedef Digraph::Arc Arc;
    3.76 -  typedef Digraph::Node Node;
    3.77 -  typedef Digraph::ArcIt ArcIt;
    3.78 -  typedef Digraph::NodeIt NodeIt;
    3.79 -  typedef Digraph::ArcMap<int> LengthMap;
    3.80 +template <class Digraph>
    3.81 +void checkBfs() {
    3.82 +  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    3.83  
    3.84    Digraph G;
    3.85    Node s, t;
    3.86 -  PetStruct<Digraph> ps = addPetersen(G,PET_SIZE);
    3.87 +  PetStruct<Digraph> ps = addPetersen(G, 5);
    3.88     
    3.89    s=ps.outer[2];
    3.90    t=ps.inner[0];
    3.91 @@ -108,10 +88,10 @@
    3.92    Bfs<Digraph> bfs_test(G);
    3.93    bfs_test.run(s);
    3.94    
    3.95 -  check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
    3.96 +  check(bfs_test.dist(t)==3,"Bfs found a wrong path." << bfs_test.dist(t));
    3.97  
    3.98    Path<Digraph> p = bfs_test.path(t);
    3.99 -  check(p.length()==3,"getPath() found a wrong path.");
   3.100 +  check(p.length()==3,"path() found a wrong path.");
   3.101    check(checkPath(G, p),"path() found a wrong path.");
   3.102    check(pathSource(G, p) == s,"path() found a wrong path.");
   3.103    check(pathTarget(G, p) == t,"path() found a wrong path.");
   3.104 @@ -139,3 +119,9 @@
   3.105    }
   3.106  }
   3.107  
   3.108 +int main()
   3.109 +{
   3.110 +  checkBfs<ListDigraph>();
   3.111 +  checkBfs<SmartDigraph>();
   3.112 +  return 0;
   3.113 +}
     4.1 --- a/test/counter_test.cc	Sun Jun 15 22:03:33 2008 +0200
     4.2 +++ b/test/counter_test.cc	Sun Jun 15 22:05:23 2008 +0200
     4.3 @@ -17,50 +17,75 @@
     4.4   */
     4.5  
     4.6  #include <lemon/counter.h>
     4.7 +#include <vector>
     4.8  
     4.9 -///\file \brief Test cases for time_measure.h
    4.10 -///
    4.11 -///\todo To be extended
    4.12 +using namespace lemon;
    4.13  
    4.14 +template <typename T>
    4.15 +void bubbleSort(std::vector<T>& v) {
    4.16 +  Counter op("Bubble Sort - Operations: ");
    4.17 +  Counter::NoSubCounter as(op, "Assignments: ");
    4.18 +  Counter::NoSubCounter co(op, "Comparisons: ");
    4.19 +  for (int i = v.size()-1; i > 0; --i) {
    4.20 +    for (int j = 0; j < i; ++j) {
    4.21 +      if (v[j] > v[j+1]) {
    4.22 +        T tmp = v[j];
    4.23 +        v[j] = v[j+1];
    4.24 +        v[j+1] = tmp;
    4.25 +        as += 3;
    4.26 +      }
    4.27 +      ++co;
    4.28 +    }
    4.29 +  }
    4.30 +}
    4.31  
    4.32 -int fibonacci(int f) 
    4.33 -{
    4.34 -  static lemon::Counter count("Fibonacci steps: ");
    4.35 -  count++;
    4.36 -  if(f<1) return 0;
    4.37 -  else if(f==1) return 1;
    4.38 -  else return fibonacci(f-1)+fibonacci(f-2);
    4.39 +template <typename T>
    4.40 +void insertionSort(std::vector<T>& v) {
    4.41 +  Counter op("Insertion Sort - Operations: ");
    4.42 +  Counter::NoSubCounter as(op, "Assignments: ");
    4.43 +  Counter::NoSubCounter co(op, "Comparisons: ");
    4.44 +  for (int i = 1; i < int(v.size()); ++i) {
    4.45 +    T value = v[i];
    4.46 +    ++as;
    4.47 +    int j = i;
    4.48 +    while (j > 0 && v[j-1] > value) {
    4.49 +      v[j] = v[j-1];
    4.50 +      --j;
    4.51 +      ++co; ++as;
    4.52 +    }
    4.53 +    v[j] = value;
    4.54 +    ++as;
    4.55 +  }
    4.56 +}
    4.57 +
    4.58 +template <typename MyCounter>
    4.59 +void counterTest() {
    4.60 +  MyCounter c("Main Counter: ");
    4.61 +  c++;
    4.62 +  typename MyCounter::SubCounter d(c, "SubCounter: ");
    4.63 +  d++;
    4.64 +  typename MyCounter::SubCounter::NoSubCounter e(d, "SubSubCounter: ");
    4.65 +  e++;
    4.66 +  d+=3;
    4.67 +  c-=4;
    4.68 +  e-=2;
    4.69 +  c.reset(2);
    4.70 +  c.reset();
    4.71 +}
    4.72 +
    4.73 +void init(std::vector<int>& v) {
    4.74 +  v[0] = 10; v[1] = 60; v[2] = 20; v[3] = 90; v[4] = 100;
    4.75 +  v[5] = 80; v[6] = 40; v[7] = 30; v[8] = 50; v[9] = 70; 
    4.76  }
    4.77  
    4.78  int main()
    4.79  {
    4.80 -  fibonacci(10);
    4.81 +  counterTest<Counter>();
    4.82 +  counterTest<NoCounter>();
    4.83    
    4.84 -  {  
    4.85 -    typedef lemon::Counter MyCounter;
    4.86 -    MyCounter c("Main counter: ");
    4.87 -    c++;
    4.88 -    c++;
    4.89 -    MyCounter::SubCounter d(c,"Subcounter: ");
    4.90 -    d++;
    4.91 -    d++;
    4.92 -    MyCounter::SubCounter::SubCounter e(d,"SubSubCounter: ");
    4.93 -    e++;
    4.94 -    e++;
    4.95 -  }
    4.96 -  
    4.97 -  {
    4.98 -    typedef lemon::NoCounter MyCounter;
    4.99 -    MyCounter c("Main counter: ");
   4.100 -    c++;
   4.101 -    c++;
   4.102 -    MyCounter::SubCounter d(c,"Subcounter: ");
   4.103 -    d++;
   4.104 -    d++;
   4.105 -    MyCounter::SubCounter::SubCounter e(d,"SubSubCounter: ");
   4.106 -    e++;
   4.107 -    e++;
   4.108 -  }
   4.109 +  std::vector<int> x(10);
   4.110 +  init(x); bubbleSort(x);
   4.111 +  init(x); insertionSort(x);
   4.112  
   4.113    return 0;
   4.114  }
     5.1 --- a/test/dfs_test.cc	Sun Jun 15 22:03:33 2008 +0200
     5.2 +++ b/test/dfs_test.cc	Sun Jun 15 22:05:23 2008 +0200
     5.3 @@ -16,32 +16,25 @@
     5.4   *
     5.5   */
     5.6  
     5.7 -#include "test_tools.h"
     5.8 -// #include <lemon/smart_graph.h>
     5.9 +#include <lemon/concepts/digraph.h>
    5.10 +#include <lemon/smart_graph.h>
    5.11  #include <lemon/list_graph.h>
    5.12  #include <lemon/dfs.h>
    5.13  #include <lemon/path.h>
    5.14 -#include <lemon/concepts/digraph.h>
    5.15 +
    5.16 +#include "graph_test.h"
    5.17 +#include "test_tools.h"
    5.18  
    5.19  using namespace lemon;
    5.20  
    5.21 -const int PET_SIZE =5;
    5.22 -
    5.23 -
    5.24 -void check_Dfs_SmartDigraph_Compile() 
    5.25 +void checkDfsCompile() 
    5.26  {
    5.27    typedef concepts::Digraph Digraph;
    5.28 -
    5.29 -  typedef Digraph::Arc Arc;
    5.30 -  typedef Digraph::Node Node;
    5.31 -  typedef Digraph::ArcIt ArcIt;
    5.32 -  typedef Digraph::NodeIt NodeIt;
    5.33 - 
    5.34    typedef Dfs<Digraph> DType;
    5.35    
    5.36    Digraph G;
    5.37 -  Node n;
    5.38 -  Arc e;
    5.39 +  Digraph::Node n;
    5.40 +  Digraph::Arc e;
    5.41    int l;
    5.42    bool b;
    5.43    DType::DistMap d(G);
    5.44 @@ -63,17 +56,12 @@
    5.45    Path<Digraph> pp = dfs_test.path(n);
    5.46  }
    5.47  
    5.48 -
    5.49 -void check_Dfs_Function_Compile() 
    5.50 +void checkDfsFunctionCompile() 
    5.51  {
    5.52    typedef int VType;
    5.53    typedef concepts::Digraph Digraph;
    5.54 -
    5.55    typedef Digraph::Arc Arc;
    5.56    typedef Digraph::Node Node;
    5.57 -  typedef Digraph::ArcIt ArcIt;
    5.58 -  typedef Digraph::NodeIt NodeIt;
    5.59 -  typedef concepts::ReadMap<Arc,VType> LengthMap;
    5.60     
    5.61    Digraph g;
    5.62    dfs(g,Node()).run();
    5.63 @@ -83,25 +71,16 @@
    5.64      .distMap(concepts::WriteMap<Node,VType>())
    5.65      .reachedMap(concepts::ReadWriteMap<Node,bool>())
    5.66      .processedMap(concepts::WriteMap<Node,bool>())
    5.67 -    .run(Node());
    5.68 -  
    5.69 +    .run(Node()); 
    5.70  }
    5.71  
    5.72 -int main()
    5.73 -{
    5.74 -    
    5.75 -  // typedef SmartDigraph Digraph;
    5.76 -  typedef ListDigraph Digraph;
    5.77 -
    5.78 -  typedef Digraph::Arc Arc;
    5.79 -  typedef Digraph::Node Node;
    5.80 -  typedef Digraph::ArcIt ArcIt;
    5.81 -  typedef Digraph::NodeIt NodeIt;
    5.82 -  typedef Digraph::ArcMap<int> LengthMap;
    5.83 +template <class Digraph>
    5.84 +void checkDfs() {
    5.85 +  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    5.86  
    5.87    Digraph G;
    5.88    Node s, t;
    5.89 -  PetStruct<Digraph> ps = addPetersen(G,PET_SIZE);
    5.90 +  PetStruct<Digraph> ps = addPetersen(G, 5);
    5.91     
    5.92    s=ps.outer[2];
    5.93    t=ps.inner[0];
    5.94 @@ -110,7 +89,7 @@
    5.95    dfs_test.run(s);  
    5.96    
    5.97    Path<Digraph> p = dfs_test.path(t);
    5.98 -  check(p.length()==dfs_test.dist(t),"path() found a wrong path.");
    5.99 +  check(p.length() == dfs_test.dist(t),"path() found a wrong path.");
   5.100    check(checkPath(G, p),"path() found a wrong path.");
   5.101    check(pathSource(G, p) == s,"path() found a wrong path.");
   5.102    check(pathTarget(G, p) == t,"path() found a wrong path.");
   5.103 @@ -128,3 +107,9 @@
   5.104    }
   5.105  }
   5.106  
   5.107 +int main()
   5.108 +{
   5.109 +  checkDfs<ListDigraph>();
   5.110 +  checkDfs<SmartDigraph>();
   5.111 +  return 0;
   5.112 +}
     6.1 --- a/test/digraph_test.cc	Sun Jun 15 22:03:33 2008 +0200
     6.2 +++ b/test/digraph_test.cc	Sun Jun 15 22:05:23 2008 +0200
     6.3 @@ -16,26 +16,21 @@
     6.4   *
     6.5   */
     6.6  
     6.7 -#include <iostream>
     6.8 -#include <vector>
     6.9 -
    6.10  #include <lemon/concepts/digraph.h>
    6.11  #include <lemon/list_graph.h>
    6.12 -//#include <lemon/smart_graph.h>
    6.13 +#include <lemon/smart_graph.h>
    6.14  //#include <lemon/full_graph.h>
    6.15  //#include <lemon/hypercube_graph.h>
    6.16  
    6.17  #include "test_tools.h"
    6.18 -#include "digraph_test.h"
    6.19 -#include "map_test.h"
    6.20 -
    6.21 +#include "graph_test.h"
    6.22 +#include "graph_maps_test.h"
    6.23  
    6.24  using namespace lemon;
    6.25  using namespace lemon::concepts;
    6.26  
    6.27 -
    6.28 -int main() {
    6.29 -  { // checking digraph components
    6.30 +void check_concepts() {
    6.31 +  { // Checking digraph components
    6.32      checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
    6.33  
    6.34      checkConcept<IDableDigraphComponent<>, 
    6.35 @@ -46,37 +41,104 @@
    6.36  
    6.37      checkConcept<MappableDigraphComponent<>, 
    6.38        MappableDigraphComponent<> >();
    6.39 -
    6.40    }
    6.41 -  { // checking skeleton digraphs
    6.42 +  { // Checking skeleton digraph
    6.43      checkConcept<Digraph, Digraph>();
    6.44    }
    6.45 -  { // checking list digraph
    6.46 -    checkConcept<Digraph, ListDigraph >();
    6.47 +  { // Checking ListDigraph
    6.48 +    checkConcept<Digraph, ListDigraph>();
    6.49      checkConcept<AlterableDigraphComponent<>, ListDigraph>();
    6.50      checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
    6.51      checkConcept<ClearableDigraphComponent<>, ListDigraph>();
    6.52      checkConcept<ErasableDigraphComponent<>, ListDigraph>();
    6.53 +    checkDigraphIterators<ListDigraph>();
    6.54 +  }
    6.55 +  { // Checking SmartDigraph
    6.56 +    checkConcept<Digraph, SmartDigraph>();
    6.57 +    checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
    6.58 +    checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
    6.59 +    checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
    6.60 +    checkDigraphIterators<SmartDigraph>();
    6.61 +  }
    6.62 +//  { // Checking FullDigraph
    6.63 +//    checkConcept<Digraph, FullDigraph>();
    6.64 +//    checkDigraphIterators<FullDigraph>();
    6.65 +//  }
    6.66 +//  { // Checking HyperCubeDigraph
    6.67 +//    checkConcept<Digraph, HyperCubeDigraph>();
    6.68 +//    checkDigraphIterators<HyperCubeDigraph>();
    6.69 +//  }
    6.70 +}
    6.71  
    6.72 +template <typename Digraph>
    6.73 +void check_graph_validity() {
    6.74 +  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    6.75 +  Digraph g;
    6.76 +
    6.77 +  Node
    6.78 +    n1 = g.addNode(),
    6.79 +    n2 = g.addNode(),
    6.80 +    n3 = g.addNode();
    6.81 +
    6.82 +  Arc
    6.83 +    e1 = g.addArc(n1, n2),
    6.84 +    e2 = g.addArc(n2, n3);
    6.85 +
    6.86 +  check(g.valid(n1), "Wrong validity check");
    6.87 +  check(g.valid(e1), "Wrong validity check");
    6.88 +
    6.89 +  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
    6.90 +  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
    6.91 +}
    6.92 +
    6.93 +template <typename Digraph>
    6.94 +void check_graph_validity_erase() {
    6.95 +  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    6.96 +  Digraph g;
    6.97 +
    6.98 +  Node
    6.99 +    n1 = g.addNode(),
   6.100 +    n2 = g.addNode(),
   6.101 +    n3 = g.addNode();
   6.102 +
   6.103 +  Arc
   6.104 +    e1 = g.addArc(n1, n2),
   6.105 +    e2 = g.addArc(n2, n3);
   6.106 +
   6.107 +  check(g.valid(n1), "Wrong validity check");
   6.108 +  check(g.valid(e1), "Wrong validity check");
   6.109 +
   6.110 +  g.erase(n1);
   6.111 +
   6.112 +  check(!g.valid(n1), "Wrong validity check");
   6.113 +  check(g.valid(n2), "Wrong validity check");
   6.114 +  check(g.valid(n3), "Wrong validity check");
   6.115 +  check(!g.valid(e1), "Wrong validity check");
   6.116 +  check(g.valid(e2), "Wrong validity check");
   6.117 +
   6.118 +  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   6.119 +  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   6.120 +}
   6.121 +
   6.122 +void check_digraphs() {
   6.123 +  { // Checking ListDigraph
   6.124      checkDigraph<ListDigraph>();
   6.125      checkGraphNodeMap<ListDigraph>();
   6.126      checkGraphArcMap<ListDigraph>();
   6.127 +
   6.128 +    check_graph_validity_erase<ListDigraph>();
   6.129    }
   6.130 -//   { // checking smart digraph
   6.131 -//     checkConcept<Digraph, SmartDigraph >();
   6.132 +  { // Checking SmartDigraph
   6.133 +    checkDigraph<SmartDigraph>();
   6.134 +    checkGraphNodeMap<SmartDigraph>();
   6.135 +    checkGraphArcMap<SmartDigraph>();
   6.136  
   6.137 -//     checkDigraph<SmartDigraph>();
   6.138 -//     checkDigraphNodeMap<SmartDigraph>();
   6.139 -//     checkDigraphArcMap<SmartDigraph>();
   6.140 -//   }
   6.141 -//   { // checking full digraph
   6.142 -//     checkConcept<Digraph, FullDigraph >();
   6.143 -//   }
   6.144 -//   { // checking full digraph
   6.145 -//     checkConcept<Digraph, HyperCubeDigraph >();
   6.146 -//   }
   6.147 +    check_graph_validity<SmartDigraph>();
   6.148 +  }
   6.149 +}
   6.150  
   6.151 -  std::cout << __FILE__ ": All tests passed.\n";
   6.152 -
   6.153 +int main() {
   6.154 +  check_concepts();
   6.155 +  check_digraphs();
   6.156    return 0;
   6.157  }
     7.1 --- a/test/digraph_test.h	Sun Jun 15 22:03:33 2008 +0200
     7.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     7.3 @@ -1,188 +0,0 @@
     7.4 -/* -*- C++ -*-
     7.5 - *
     7.6 - * This file is a part of LEMON, a generic C++ optimization library
     7.7 - *
     7.8 - * Copyright (C) 2003-2008
     7.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    7.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
    7.11 - *
    7.12 - * Permission to use, modify and distribute this software is granted
    7.13 - * provided that this copyright notice appears in all copies. For
    7.14 - * precise terms see the accompanying LICENSE file.
    7.15 - *
    7.16 - * This software is provided "AS IS" with no warranty of any kind,
    7.17 - * express or implied, and with no claim as to its suitability for any
    7.18 - * purpose.
    7.19 - *
    7.20 - */
    7.21 -
    7.22 -#ifndef LEMON_TEST_GRAPH_TEST_H
    7.23 -#define LEMON_TEST_GRAPH_TEST_H
    7.24 -
    7.25 -//#include <lemon/graph_utils.h>
    7.26 -#include "test_tools.h"
    7.27 -
    7.28 -//! \ingroup misc
    7.29 -//! \file
    7.30 -//! \brief Some utility and test cases to test digraph classes.
    7.31 -namespace lemon {
    7.32 -
    7.33 -  ///Structure returned by \ref addPetersen().
    7.34 -
    7.35 -  ///Structure returned by \ref addPetersen().
    7.36 -  ///
    7.37 -  template<class Digraph> 
    7.38 -  struct PetStruct
    7.39 -  {
    7.40 -    ///Vector containing the outer nodes.
    7.41 -    std::vector<typename Digraph::Node> outer;
    7.42 -    ///Vector containing the inner nodes.
    7.43 -    std::vector<typename Digraph::Node> inner;
    7.44 -    ///Vector containing the edges of the inner circle.
    7.45 -    std::vector<typename Digraph::Arc> incir;
    7.46 -    ///Vector containing the edges of the outer circle.
    7.47 -    std::vector<typename Digraph::Arc> outcir;
    7.48 -    ///Vector containing the chord edges.
    7.49 -    std::vector<typename Digraph::Arc> chords;
    7.50 -  };
    7.51 -
    7.52 -
    7.53 -
    7.54 -  ///Adds a Petersen graph to \c G.
    7.55 -
    7.56 -  ///Adds a Petersen graph to \c G.
    7.57 -  ///\return The nodes and edges of the generated graph.
    7.58 -
    7.59 -  template<typename Digraph>
    7.60 -  PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
    7.61 -  {
    7.62 -    PetStruct<Digraph> n;
    7.63 -
    7.64 -    for(int i=0;i<num;i++) {
    7.65 -      n.outer.push_back(G.addNode());
    7.66 -      n.inner.push_back(G.addNode());
    7.67 -    }
    7.68 -
    7.69 -    for(int i=0;i<num;i++) {
    7.70 -      n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
    7.71 -      n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));
    7.72 -      n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));
    7.73 -    }
    7.74 -    return n;
    7.75 -  }
    7.76 -
    7.77 -  /// \brief Adds to the digraph the reverse pair of all edges.
    7.78 -  ///
    7.79 -  /// Adds to the digraph the reverse pair of all edges.
    7.80 -  ///
    7.81 -  template<class Digraph> 
    7.82 -  void bidirDigraph(Digraph &G)
    7.83 -  {
    7.84 -    typedef typename Digraph::Arc Arc;
    7.85 -    typedef typename Digraph::ArcIt ArcIt;
    7.86 -  
    7.87 -    std::vector<Arc> ee;
    7.88 -  
    7.89 -    for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
    7.90 -
    7.91 -    for(typename std::vector<Arc>::iterator p=ee.begin();p!=ee.end();p++)
    7.92 -      G.addArc(G.target(*p),G.source(*p));
    7.93 -  }
    7.94 -
    7.95 -
    7.96 -  /// \brief Checks the bidirectioned Petersen graph.
    7.97 -  ///
    7.98 -  ///  Checks the bidirectioned Petersen graph.
    7.99 -  ///
   7.100 -  template<class Digraph> 
   7.101 -  void checkBidirPetersen(Digraph &G, int num = 5)
   7.102 -  {
   7.103 -    typedef typename Digraph::Node Node;
   7.104 -
   7.105 -    typedef typename Digraph::ArcIt ArcIt;
   7.106 -    typedef typename Digraph::NodeIt NodeIt;
   7.107 -
   7.108 -    checkDigraphNodeList(G, 2 * num);
   7.109 -    checkDigraphArcList(G, 6 * num);
   7.110 -
   7.111 -    for(NodeIt n(G);n!=INVALID;++n) {
   7.112 -      checkDigraphInArcList(G, n, 3);
   7.113 -      checkDigraphOutArcList(G, n, 3);
   7.114 -    }  
   7.115 -  }
   7.116 -
   7.117 -  template<class Digraph> void checkDigraphNodeList(Digraph &G, int nn)
   7.118 -  {
   7.119 -    typename Digraph::NodeIt n(G);
   7.120 -    for(int i=0;i<nn;i++) {
   7.121 -      check(n!=INVALID,"Wrong Node list linking.");
   7.122 -      ++n;
   7.123 -    }
   7.124 -    check(n==INVALID,"Wrong Node list linking.");
   7.125 -  }
   7.126 -
   7.127 -  template<class Digraph>
   7.128 -  void checkDigraphArcList(Digraph &G, int nn)
   7.129 -  {
   7.130 -    typedef typename Digraph::ArcIt ArcIt;
   7.131 -
   7.132 -    ArcIt e(G);
   7.133 -    for(int i=0;i<nn;i++) {
   7.134 -      check(e!=INVALID,"Wrong Arc list linking.");
   7.135 -      ++e;
   7.136 -    }
   7.137 -    check(e==INVALID,"Wrong Arc list linking.");
   7.138 -  }
   7.139 -
   7.140 -  template<class Digraph> 
   7.141 -  void checkDigraphOutArcList(Digraph &G, typename Digraph::Node n, int nn)
   7.142 -  {
   7.143 -    typename Digraph::OutArcIt e(G,n);
   7.144 -    for(int i=0;i<nn;i++) {
   7.145 -      check(e!=INVALID,"Wrong OutArc list linking.");
   7.146 -      check(n==G.source(e), "Wrong OutArc list linking.");
   7.147 -      ++e;
   7.148 -    }
   7.149 -    check(e==INVALID,"Wrong OutArc list linking.");
   7.150 -  }
   7.151 -
   7.152 -  template<class Digraph> void 
   7.153 -  checkDigraphInArcList(Digraph &G, typename Digraph::Node n, int nn)
   7.154 -  {
   7.155 -    typename Digraph::InArcIt e(G,n);
   7.156 -    for(int i=0;i<nn;i++) {
   7.157 -      check(e!=INVALID,"Wrong InArc list linking.");
   7.158 -      check(n==G.target(e), "Wrong InArc list linking.");
   7.159 -      ++e;
   7.160 -    }
   7.161 -    check(e==INVALID,"Wrong InArc list linking.");
   7.162 -  }
   7.163 -
   7.164 -  template <class Digraph> 
   7.165 -  void checkDigraph() {
   7.166 -    const int num = 5;
   7.167 -    Digraph G;
   7.168 -    addPetersen(G, num);
   7.169 -    bidirDigraph(G);
   7.170 -    checkBidirPetersen(G, num);
   7.171 -  }
   7.172 -
   7.173 -  template <class Digraph> 
   7.174 -  void checkDigraphIterators(const Digraph& digraph) {
   7.175 -    typedef typename Digraph::Node Node;
   7.176 -    typedef typename Digraph::NodeIt NodeIt;
   7.177 -    typedef typename Digraph::Arc Arc;
   7.178 -    typedef typename Digraph::ArcIt ArcIt;
   7.179 -    typedef typename Digraph::InArcIt InArcIt;
   7.180 -    typedef typename Digraph::OutArcIt OutArcIt;
   7.181 -    //    typedef ConArcIt<Digraph> ConArcIt;
   7.182 -  }
   7.183 -
   7.184 -  ///\file
   7.185 -  ///\todo Check target(), source() as well;
   7.186 -
   7.187 -  
   7.188 -} //namespace lemon
   7.189 -
   7.190 -
   7.191 -#endif
     8.1 --- a/test/dijkstra_test.cc	Sun Jun 15 22:03:33 2008 +0200
     8.2 +++ b/test/dijkstra_test.cc	Sun Jun 15 22:05:23 2008 +0200
     8.3 @@ -16,9 +16,6 @@
     8.4   *
     8.5   */
     8.6  
     8.7 -///\file
     8.8 -///\brief Test cases for Dijkstra algorithm.
     8.9 -
    8.10  #include <lemon/concepts/digraph.h>
    8.11  #include <lemon/smart_graph.h>
    8.12  #include <lemon/list_graph.h>
    8.13 @@ -26,6 +23,7 @@
    8.14  #include <lemon/dijkstra.h>
    8.15  #include <lemon/path.h>
    8.16  
    8.17 +#include "graph_test.h"
    8.18  #include "test_tools.h"
    8.19  
    8.20  using namespace lemon;
     9.1 --- a/test/dim_test.cc	Sun Jun 15 22:03:33 2008 +0200
     9.2 +++ b/test/dim_test.cc	Sun Jun 15 22:05:23 2008 +0200
     9.3 @@ -25,63 +25,59 @@
     9.4  
     9.5  int main()
     9.6  {
     9.7 -  cout << "Testing classes 'dim2::Point' and 'dim2::BoundingBox'." << endl;
     9.8 -
     9.9    typedef dim2::Point<int> Point;
    9.10  
    9.11    Point p;
    9.12 -  check(p.size()==2, "Wrong vector initialization.");
    9.13 +  check(p.size()==2, "Wrong dim2::Point initialization.");
    9.14  
    9.15    Point a(1,2);
    9.16    Point b(3,4);
    9.17 -  check(a[0]==1 && a[1]==2, "Wrong vector initialization.");
    9.18 +  check(a[0]==1 && a[1]==2, "Wrong dim2::Point initialization.");
    9.19  
    9.20    p = a+b;
    9.21 -  check(p.x==4 && p.y==6, "Wrong vector addition.");
    9.22 +  check(p.x==4 && p.y==6, "Wrong dim2::Point addition.");
    9.23  
    9.24    p = a-b;
    9.25 -  check(p.x==-2 && p.y==-2, "Wrong vector subtraction.");
    9.26 +  check(p.x==-2 && p.y==-2, "Wrong dim2::Point subtraction.");
    9.27  
    9.28 -  check(a.normSquare()==5,"Wrong vector norm calculation.");
    9.29 -  check(a*b==11, "Wrong vector scalar product.");
    9.30 +  check(a.normSquare()==5,"Wrong dim2::Point norm calculation.");
    9.31 +  check(a*b==11, "Wrong dim2::Point scalar product.");
    9.32  
    9.33    int l=2;
    9.34    p = a*l;
    9.35 -  check(p.x==2 && p.y==4, "Wrong vector multiplication by a scalar.");
    9.36 +  check(p.x==2 && p.y==4, "Wrong dim2::Point multiplication by a scalar.");
    9.37  
    9.38    p = b/l;
    9.39 -  check(p.x==1 && p.y==2, "Wrong vector division by a scalar.");
    9.40 +  check(p.x==1 && p.y==2, "Wrong dim2::Point division by a scalar.");
    9.41  
    9.42    typedef dim2::BoundingBox<int> BB;
    9.43    BB box1;
    9.44 -  check(box1.empty(), "It should be empty.");
    9.45 +  check(box1.empty(), "Wrong empty() in dim2::BoundingBox.");
    9.46  
    9.47    box1.add(a);
    9.48 -  check(!box1.empty(), "It should not be empty.");
    9.49 +  check(!box1.empty(), "Wrong empty() in dim2::BoundingBox.");
    9.50    box1.add(b);
    9.51  
    9.52    check(box1.bottomLeft().x==1 &&
    9.53          box1.bottomLeft().y==2 &&
    9.54          box1.topRight().x==3 &&
    9.55          box1.topRight().y==4,
    9.56 -        "Wrong addition of points to box.");
    9.57 +        "Wrong addition of points to dim2::BoundingBox.");
    9.58  
    9.59    p.x=2; p.y=3;
    9.60 -  check(box1.inside(p), "It should be inside.");
    9.61 +  check(box1.inside(p), "Wrong inside() in dim2::BoundingBox.");
    9.62  
    9.63    p.x=1; p.y=3;
    9.64 -  check(box1.inside(p), "It should be inside.");
    9.65 +  check(box1.inside(p), "Wrong inside() in dim2::BoundingBox.");
    9.66  
    9.67    p.x=0; p.y=3;
    9.68 -  check(!box1.inside(p), "It should not be inside.");
    9.69 +  check(!box1.inside(p), "Wrong inside() in dim2::BoundingBox.");
    9.70  
    9.71    BB box2(p);
    9.72 -  check(!box2.empty(),
    9.73 -        "It should not be empty. Constructed from 1 point.");
    9.74 +  check(!box2.empty(), "Wrong empty() in dim2::BoundingBox.");
    9.75  
    9.76    box2.add(box1);
    9.77 -  check(box2.inside(p),
    9.78 -        "It should be inside. Incremented a box with another one.");
    9.79 +  check(box2.inside(p), "Wrong inside() in dim2::BoundingBox.");
    9.80  
    9.81    return 0;
    9.82  }
    10.1 --- a/test/error_test.cc	Sun Jun 15 22:03:33 2008 +0200
    10.2 +++ b/test/error_test.cc	Sun Jun 15 22:05:23 2008 +0200
    10.3 @@ -54,6 +54,7 @@
    10.4  }
    10.5  #undef LEMON_DISABLE_ASSERTS
    10.6  
    10.7 +//checking custom assert handler
    10.8  #define LEMON_ASSERT_CUSTOM
    10.9  
   10.10  static int cnt = 0;
    11.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    11.2 +++ b/test/graph_maps_test.h	Sun Jun 15 22:05:23 2008 +0200
    11.3 @@ -0,0 +1,144 @@
    11.4 +/* -*- C++ -*-
    11.5 + *
    11.6 + * This file is a part of LEMON, a generic C++ optimization library
    11.7 + *
    11.8 + * Copyright (C) 2003-2008
    11.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
   11.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
   11.11 + *
   11.12 + * Permission to use, modify and distribute this software is granted
   11.13 + * provided that this copyright notice appears in all copies. For
   11.14 + * precise terms see the accompanying LICENSE file.
   11.15 + *
   11.16 + * This software is provided "AS IS" with no warranty of any kind,
   11.17 + * express or implied, and with no claim as to its suitability for any
   11.18 + * purpose.
   11.19 + *
   11.20 + */
   11.21 +
   11.22 +#ifndef LEMON_TEST_MAP_TEST_H
   11.23 +#define LEMON_TEST_MAP_TEST_H
   11.24 +
   11.25 +#include <vector>
   11.26 +#include <lemon/maps.h>
   11.27 +
   11.28 +#include "test_tools.h"
   11.29 +
   11.30 +namespace lemon {
   11.31 +
   11.32 +  template <typename Graph>
   11.33 +  void checkGraphNodeMap() {
   11.34 +    Graph graph;
   11.35 +    const int num = 16;
   11.36 +
   11.37 +    typedef typename Graph::Node Node;
   11.38 +
   11.39 +    std::vector<Node> nodes;
   11.40 +    for (int i = 0; i < num; ++i) {
   11.41 +      nodes.push_back(graph.addNode());
   11.42 +    }
   11.43 +    typedef typename Graph::template NodeMap<int> IntNodeMap;
   11.44 +    IntNodeMap map(graph, 42);
   11.45 +    for (int i = 0; i < int(nodes.size()); ++i) {
   11.46 +      check(map[nodes[i]] == 42, "Wrong map constructor.");
   11.47 +    }
   11.48 +    for (int i = 0; i < num; ++i) {
   11.49 +      nodes.push_back(graph.addNode());
   11.50 +      map[nodes.back()] = 23;
   11.51 +      check(map[nodes.back()] == 23, "Wrong operator[].");
   11.52 +    }
   11.53 +    map = constMap<Node>(12);
   11.54 +    for (int i = 0; i < int(nodes.size()); ++i) {
   11.55 +      check(map[nodes[i]] == 12, "Wrong map constructor.");
   11.56 +    }
   11.57 +    graph.clear();
   11.58 +    nodes.clear();
   11.59 +  }
   11.60 +
   11.61 +  template <typename Graph>
   11.62 +  void checkGraphArcMap() {
   11.63 +    Graph graph;
   11.64 +    const int num = 16;
   11.65 +
   11.66 +    typedef typename Graph::Node Node;
   11.67 +    typedef typename Graph::Arc Arc;
   11.68 +
   11.69 +    std::vector<Node> nodes;
   11.70 +    for (int i = 0; i < num; ++i) {
   11.71 +      nodes.push_back(graph.addNode());
   11.72 +    }
   11.73 +
   11.74 +    std::vector<Arc> arcs;
   11.75 +    for (int i = 0; i < num; ++i) {
   11.76 +      for (int j = 0; j < i; ++j) {
   11.77 +	arcs.push_back(graph.addArc(nodes[i], nodes[j]));
   11.78 +      }
   11.79 +    }
   11.80 +
   11.81 +    typedef typename Graph::template ArcMap<int> IntArcMap;
   11.82 +    IntArcMap map(graph, 42);
   11.83 +
   11.84 +    for (int i = 0; i < int(arcs.size()); ++i) {
   11.85 +      check(map[arcs[i]] == 42, "Wrong map constructor.");
   11.86 +    }
   11.87 +
   11.88 +    for (int i = 0; i < num; ++i) {
   11.89 +      for (int j = i + 1; j < num; ++j) {
   11.90 +	arcs.push_back(graph.addArc(nodes[i], nodes[j]));
   11.91 +	map[arcs.back()] = 23;
   11.92 +        check(map[arcs.back()] == 23, "Wrong operator[].");
   11.93 +      }
   11.94 +    }
   11.95 +    map = constMap<Arc>(12);
   11.96 +    for (int i = 0; i < int(arcs.size()); ++i) {
   11.97 +      check(map[arcs[i]] == 12, "Wrong map constructor.");
   11.98 +    }
   11.99 +    graph.clear();
  11.100 +    arcs.clear();
  11.101 +  }
  11.102 +
  11.103 +  template <typename Graph>
  11.104 +  void checkGraphEdgeMap() {
  11.105 +    Graph graph;
  11.106 +    const int num = 16;
  11.107 +
  11.108 +    typedef typename Graph::Node Node;
  11.109 +    typedef typename Graph::Edge Edge;
  11.110 +
  11.111 +    std::vector<Node> nodes;
  11.112 +    for (int i = 0; i < num; ++i) {
  11.113 +      nodes.push_back(graph.addNode());
  11.114 +    }
  11.115 +
  11.116 +    std::vector<Edge> edges;
  11.117 +    for (int i = 0; i < num; ++i) {
  11.118 +      for (int j = 0; j < i; ++j) {
  11.119 +	edges.push_back(graph.addEdge(nodes[i], nodes[j]));
  11.120 +      }
  11.121 +    }
  11.122 +
  11.123 +    typedef typename Graph::template EdgeMap<int> IntEdgeMap;
  11.124 +    IntEdgeMap map(graph, 42);
  11.125 +
  11.126 +    for (int i = 0; i < int(edges.size()); ++i) {
  11.127 +      check(map[edges[i]] == 42, "Wrong map constructor.");
  11.128 +    }
  11.129 +
  11.130 +    for (int i = 0; i < num; ++i) {
  11.131 +      for (int j = i + 1; j < num; ++j) {
  11.132 +	edges.push_back(graph.addEdge(nodes[i], nodes[j]));
  11.133 +	map[edges.back()] = 23;
  11.134 +        check(map[edges.back()] == 23, "Wrong operator[].");
  11.135 +      }
  11.136 +    }
  11.137 +    map = constMap<Edge>(12);
  11.138 +    for (int i = 0; i < int(edges.size()); ++i) {
  11.139 +      check(map[edges[i]] == 12, "Wrong map constructor.");
  11.140 +    }
  11.141 +    graph.clear();
  11.142 +    edges.clear();
  11.143 +  }
  11.144 +
  11.145 +}
  11.146 +
  11.147 +#endif
    12.1 --- a/test/graph_test.cc	Sun Jun 15 22:03:33 2008 +0200
    12.2 +++ b/test/graph_test.cc	Sun Jun 15 22:05:23 2008 +0200
    12.3 @@ -22,17 +22,15 @@
    12.4  // #include <lemon/full_graph.h>
    12.5  // #include <lemon/grid_graph.h>
    12.6  
    12.7 -#include <lemon/graph_utils.h>
    12.8 -
    12.9  #include "test_tools.h"
   12.10 -
   12.11 +#include "graph_test.h"
   12.12 +#include "graph_maps_test.h"
   12.13  
   12.14  using namespace lemon;
   12.15  using namespace lemon::concepts;
   12.16  
   12.17  void check_concepts() {
   12.18 -
   12.19 -  { // checking digraph components
   12.20 +  { // Checking graph components
   12.21      checkConcept<BaseGraphComponent, BaseGraphComponent >();
   12.22  
   12.23      checkConcept<IDableGraphComponent<>, 
   12.24 @@ -43,52 +41,40 @@
   12.25  
   12.26      checkConcept<MappableGraphComponent<>, 
   12.27        MappableGraphComponent<> >();
   12.28 -
   12.29    }
   12.30 -  {
   12.31 -    checkConcept<Graph, ListGraph>();    
   12.32 -    checkConcept<Graph, SmartGraph>();    
   12.33 -//     checkConcept<Graph, FullGraph>();    
   12.34 -//     checkConcept<Graph, Graph>();    
   12.35 -//     checkConcept<Graph, GridGraph>();
   12.36 +  { // Checking skeleton graph
   12.37 +    checkConcept<Graph, Graph>();
   12.38    }
   12.39 +  { // Checking ListGraph
   12.40 +    checkConcept<Graph, ListGraph>();
   12.41 +    checkConcept<AlterableGraphComponent<>, ListGraph>();
   12.42 +    checkConcept<ExtendableGraphComponent<>, ListGraph>();
   12.43 +    checkConcept<ClearableGraphComponent<>, ListGraph>();
   12.44 +    checkConcept<ErasableGraphComponent<>, ListGraph>();
   12.45 +    checkGraphIterators<ListGraph>();
   12.46 +  }
   12.47 +  { // Checking SmartGraph
   12.48 +    checkConcept<Graph, SmartGraph>();
   12.49 +    checkConcept<AlterableGraphComponent<>, SmartGraph>();
   12.50 +    checkConcept<ExtendableGraphComponent<>, SmartGraph>();
   12.51 +    checkConcept<ClearableGraphComponent<>, SmartGraph>();
   12.52 +    checkGraphIterators<SmartGraph>();
   12.53 +  }
   12.54 +//  { // Checking FullGraph
   12.55 +//    checkConcept<Graph, FullGraph>();
   12.56 +//    checkGraphIterators<FullGraph>();
   12.57 +//  }
   12.58 +//  { // Checking GridGraph
   12.59 +//    checkConcept<Graph, GridGraph>();
   12.60 +//    checkGraphIterators<GridGraph>();
   12.61 +//  }
   12.62  }
   12.63  
   12.64  template <typename Graph>
   12.65 -void check_item_counts(Graph &g, int n, int e) {
   12.66 -  int nn = 0;
   12.67 -  for (typename Graph::NodeIt it(g); it != INVALID; ++it) {
   12.68 -    ++nn;
   12.69 -  }
   12.70 -
   12.71 -  check(nn == n, "Wrong node number.");
   12.72 -  //  check(countNodes(g) == n, "Wrong node number.");
   12.73 -
   12.74 -  int ee = 0;
   12.75 -  for (typename Graph::ArcIt it(g); it != INVALID; ++it) {
   12.76 -    ++ee;
   12.77 -  }
   12.78 -
   12.79 -  check(ee == 2*e, "Wrong arc number.");
   12.80 -  //  check(countArcs(g) == 2*e, "Wrong arc number.");
   12.81 -
   12.82 -  int uee = 0;
   12.83 -  for (typename Graph::EdgeIt it(g); it != INVALID; ++it) {
   12.84 -    ++uee;
   12.85 -  }
   12.86 -
   12.87 -  check(uee == e, "Wrong edge number.");
   12.88 -  //  check(countEdges(g) == e, "Wrong edge number.");
   12.89 -}
   12.90 -
   12.91 -template <typename Graph>
   12.92 -void check_graph_counts() {
   12.93 -
   12.94 +void check_graph_validity() {
   12.95    TEMPLATE_GRAPH_TYPEDEFS(Graph);
   12.96    Graph g;
   12.97  
   12.98 -  check_item_counts(g,0,0);
   12.99 -
  12.100    Node
  12.101      n1 = g.addNode(),
  12.102      n2 = g.addNode(),
  12.103 @@ -98,17 +84,20 @@
  12.104      e1 = g.addEdge(n1, n2),
  12.105      e2 = g.addEdge(n2, n3);
  12.106  
  12.107 -  check_item_counts(g,3,2);
  12.108 +  check(g.valid(n1), "Wrong validity check");
  12.109 +  check(g.valid(e1), "Wrong validity check");
  12.110 +  check(g.valid(g.direct(e1, true)), "Wrong validity check");
  12.111 +
  12.112 +  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
  12.113 +  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
  12.114 +  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
  12.115  }
  12.116  
  12.117  template <typename Graph>
  12.118 -void check_graph_validity() {
  12.119 -
  12.120 +void check_graph_validity_erase() {
  12.121    TEMPLATE_GRAPH_TYPEDEFS(Graph);
  12.122    Graph g;
  12.123  
  12.124 -  check_item_counts(g,0,0);
  12.125 -
  12.126    Node
  12.127      n1 = g.addNode(),
  12.128      n2 = g.addNode(),
  12.129 @@ -118,53 +107,23 @@
  12.130      e1 = g.addEdge(n1, n2),
  12.131      e2 = g.addEdge(n2, n3);
  12.132  
  12.133 -  check(g.valid(n1), "Validity check");
  12.134 -  check(g.valid(e1), "Validity check");
  12.135 -  check(g.valid(g.direct(e1, true)), "Validity check");
  12.136 -
  12.137 -  check(!g.valid(g.nodeFromId(-1)), "Validity check");
  12.138 -  check(!g.valid(g.edgeFromId(-1)), "Validity check");
  12.139 -  check(!g.valid(g.arcFromId(-1)), "Validity check");
  12.140 -    
  12.141 -}
  12.142 -
  12.143 -template <typename Graph>
  12.144 -void check_graph_validity_erase() {
  12.145 -
  12.146 -  TEMPLATE_GRAPH_TYPEDEFS(Graph);
  12.147 -  Graph g;
  12.148 -
  12.149 -  check_item_counts(g,0,0);
  12.150 -
  12.151 -  Node
  12.152 -    n1 = g.addNode(),
  12.153 -    n2 = g.addNode(),
  12.154 -    n3 = g.addNode();
  12.155 -
  12.156 -  Edge
  12.157 -    e1 = g.addEdge(n1, n2),
  12.158 -    e2 = g.addEdge(n2, n3);
  12.159 -
  12.160 -  check(g.valid(n1), "Validity check");
  12.161 -  check(g.valid(e1), "Validity check");
  12.162 -  check(g.valid(g.direct(e1, true)), "Validity check");
  12.163 +  check(g.valid(n1), "Wrong validity check");
  12.164 +  check(g.valid(e1), "Wrong validity check");
  12.165 +  check(g.valid(g.direct(e1, true)), "Wrong validity check");
  12.166  
  12.167    g.erase(n1);
  12.168  
  12.169 -  check(!g.valid(n1), "Validity check");
  12.170 -  check(g.valid(n2), "Validity check");
  12.171 -  check(g.valid(n3), "Validity check");
  12.172 -  check(!g.valid(e1), "Validity check");
  12.173 -  check(g.valid(e2), "Validity check");
  12.174 +  check(!g.valid(n1), "Wrong validity check");
  12.175 +  check(g.valid(n2), "Wrong validity check");
  12.176 +  check(g.valid(n3), "Wrong validity check");
  12.177 +  check(!g.valid(e1), "Wrong validity check");
  12.178 +  check(g.valid(e2), "Wrong validity check");
  12.179  
  12.180 -  check(!g.valid(g.nodeFromId(-1)), "Validity check");
  12.181 -  check(!g.valid(g.edgeFromId(-1)), "Validity check");
  12.182 -  check(!g.valid(g.arcFromId(-1)), "Validity check");
  12.183 -    
  12.184 +  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
  12.185 +  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
  12.186 +  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
  12.187  }
  12.188  
  12.189 -
  12.190 -
  12.191  // void checkGridGraph(const GridGraph& g, int w, int h) {
  12.192  //   check(g.width() == w, "Wrong width");
  12.193  //   check(g.height() == h, "Wrong height");
  12.194 @@ -209,27 +168,36 @@
  12.195  //   }
  12.196  // }
  12.197  
  12.198 +void check_graphs() {
  12.199 +  { // Checking ListGraph
  12.200 +    checkGraph<ListGraph>();
  12.201 +    checkGraphNodeMap<ListGraph>();
  12.202 +    checkGraphEdgeMap<ListGraph>();
  12.203 +
  12.204 +    check_graph_validity_erase<ListGraph>();
  12.205 +  }
  12.206 +  { // Checking SmartGraph
  12.207 +    checkGraph<SmartGraph>();
  12.208 +    checkGraphNodeMap<SmartGraph>();
  12.209 +    checkGraphEdgeMap<SmartGraph>();
  12.210 +
  12.211 +    check_graph_validity<SmartGraph>();
  12.212 +  }
  12.213 +//   { // Checking FullGraph
  12.214 +//     FullGraph g(5);
  12.215 +//     checkGraphNodeList(g, 5);
  12.216 +//     checkGraphEdgeList(g, 10);
  12.217 +//   }
  12.218 +//   { // Checking GridGraph
  12.219 +//     GridGraph g(5, 6);
  12.220 +//     checkGraphNodeList(g, 30);
  12.221 +//     checkGraphEdgeList(g, 49);
  12.222 +//     checkGridGraph(g, 5, 6);
  12.223 +//   }
  12.224 +}
  12.225 +
  12.226  int main() {
  12.227    check_concepts();
  12.228 -
  12.229 -  check_graph_counts<ListGraph>();
  12.230 -  check_graph_counts<SmartGraph>();
  12.231 -
  12.232 -  check_graph_validity_erase<ListGraph>();
  12.233 -  check_graph_validity<SmartGraph>();
  12.234 -
  12.235 -//   {
  12.236 -//     FullGraph g(5);
  12.237 -//     check_item_counts(g, 5, 10);
  12.238 -//   }
  12.239 -
  12.240 -//   {
  12.241 -//     GridGraph g(5, 6);
  12.242 -//     check_item_counts(g, 30, 49);
  12.243 -//     checkGridGraph(g, 5, 6);
  12.244 -//   }
  12.245 -
  12.246 -  std::cout << __FILE__ ": All tests passed.\n";
  12.247 -
  12.248 +  check_graphs();
  12.249    return 0;
  12.250  }
    13.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    13.2 +++ b/test/graph_test.h	Sun Jun 15 22:05:23 2008 +0200
    13.3 @@ -0,0 +1,262 @@
    13.4 +/* -*- C++ -*-
    13.5 + *
    13.6 + * This file is a part of LEMON, a generic C++ optimization library
    13.7 + *
    13.8 + * Copyright (C) 2003-2008
    13.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
   13.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
   13.11 + *
   13.12 + * Permission to use, modify and distribute this software is granted
   13.13 + * provided that this copyright notice appears in all copies. For
   13.14 + * precise terms see the accompanying LICENSE file.
   13.15 + *
   13.16 + * This software is provided "AS IS" with no warranty of any kind,
   13.17 + * express or implied, and with no claim as to its suitability for any
   13.18 + * purpose.
   13.19 + *
   13.20 + */
   13.21 +
   13.22 +#ifndef LEMON_TEST_GRAPH_TEST_H
   13.23 +#define LEMON_TEST_GRAPH_TEST_H
   13.24 +
   13.25 +#include <lemon/graph_utils.h>
   13.26 +#include "test_tools.h"
   13.27 +
   13.28 +namespace lemon {
   13.29 +
   13.30 +  template<class Graph>
   13.31 +  void checkGraphNodeList(const Graph &G, int cnt)
   13.32 +  {
   13.33 +    typename Graph::NodeIt n(G);
   13.34 +    for(int i=0;i<cnt;i++) {
   13.35 +      check(n!=INVALID,"Wrong Node list linking.");
   13.36 +      ++n;
   13.37 +    }
   13.38 +    check(n==INVALID,"Wrong Node list linking.");
   13.39 +    check(countNodes(G)==cnt,"Wrong Node number.");
   13.40 +  }
   13.41 +
   13.42 +  template<class Graph>
   13.43 +  void checkGraphArcList(const Graph &G, int cnt)
   13.44 +  {
   13.45 +    typename Graph::ArcIt e(G);
   13.46 +    for(int i=0;i<cnt;i++) {
   13.47 +      check(e!=INVALID,"Wrong Arc list linking.");
   13.48 +      ++e;
   13.49 +    }
   13.50 +    check(e==INVALID,"Wrong Arc list linking.");
   13.51 +    check(countArcs(G)==cnt,"Wrong Arc number.");
   13.52 +  }
   13.53 +
   13.54 +  template<class Graph>
   13.55 +  void checkGraphOutArcList(const Graph &G, typename Graph::Node n, int cnt)
   13.56 +  {
   13.57 +    typename Graph::OutArcIt e(G,n);
   13.58 +    for(int i=0;i<cnt;i++) {
   13.59 +      check(e!=INVALID,"Wrong OutArc list linking.");
   13.60 +      check(n==G.source(e),"Wrong OutArc list linking.");
   13.61 +      ++e;
   13.62 +    }
   13.63 +    check(e==INVALID,"Wrong OutArc list linking.");
   13.64 +    check(countOutArcs(G,n)==cnt,"Wrong OutArc number.");
   13.65 +  }
   13.66 +
   13.67 +  template<class Graph>
   13.68 +  void checkGraphInArcList(const Graph &G, typename Graph::Node n, int cnt)
   13.69 +  {
   13.70 +    typename Graph::InArcIt e(G,n);
   13.71 +    for(int i=0;i<cnt;i++) {
   13.72 +      check(e!=INVALID,"Wrong InArc list linking.");
   13.73 +      check(n==G.target(e),"Wrong InArc list linking.");
   13.74 +      ++e;
   13.75 +    }
   13.76 +    check(e==INVALID,"Wrong InArc list linking.");
   13.77 +    check(countInArcs(G,n)==cnt,"Wrong InArc number.");
   13.78 +  }
   13.79 +
   13.80 +  template<class Graph>
   13.81 +  void checkGraphEdgeList(const Graph &G, int cnt)
   13.82 +  {
   13.83 +    typename Graph::EdgeIt e(G);
   13.84 +    for(int i=0;i<cnt;i++) {
   13.85 +      check(e!=INVALID,"Wrong Edge list linking.");
   13.86 +      ++e;
   13.87 +    }
   13.88 +    check(e==INVALID,"Wrong Edge list linking.");
   13.89 +    check(countEdges(G)==cnt,"Wrong Edge number.");
   13.90 +  }
   13.91 +
   13.92 +  template<class Graph>
   13.93 +  void checkGraphIncEdgeList(const Graph &G, typename Graph::Node n, int cnt)
   13.94 +  {
   13.95 +    typename Graph::IncEdgeIt e(G,n);
   13.96 +    for(int i=0;i<cnt;i++) {
   13.97 +      check(e!=INVALID,"Wrong IncEdge list linking.");
   13.98 +      check(n==G.u(e) || n==G.v(e),"Wrong IncEdge list linking.");
   13.99 +      ++e;
  13.100 +    }
  13.101 +    check(e==INVALID,"Wrong IncEdge list linking.");
  13.102 +    check(countIncEdges(G,n)==cnt,"Wrong IncEdge number.");
  13.103 +  }
  13.104 +
  13.105 +  template <class Digraph>
  13.106 +  void checkDigraphIterators() {
  13.107 +    typedef typename Digraph::Node Node;
  13.108 +    typedef typename Digraph::NodeIt NodeIt;
  13.109 +    typedef typename Digraph::Arc Arc;
  13.110 +    typedef typename Digraph::ArcIt ArcIt;
  13.111 +    typedef typename Digraph::InArcIt InArcIt;
  13.112 +    typedef typename Digraph::OutArcIt OutArcIt;
  13.113 +  }
  13.114 +
  13.115 +  template <class Graph>
  13.116 +  void checkGraphIterators() {
  13.117 +    checkDigraphIterators<Graph>();
  13.118 +    typedef typename Graph::Edge Edge;
  13.119 +    typedef typename Graph::EdgeIt EdgeIt;
  13.120 +    typedef typename Graph::IncEdgeIt IncEdgeIt;
  13.121 +  }
  13.122 +
  13.123 +  // Structure returned by addPetersen()
  13.124 +  template<class Digraph>
  13.125 +  struct PetStruct
  13.126 +  {
  13.127 +    // Vector containing the outer nodes
  13.128 +    std::vector<typename Digraph::Node> outer;
  13.129 +    // Vector containing the inner nodes
  13.130 +    std::vector<typename Digraph::Node> inner;
  13.131 +    // Vector containing the arcs of the inner circle
  13.132 +    std::vector<typename Digraph::Arc> incir;
  13.133 +    // Vector containing the arcs of the outer circle
  13.134 +    std::vector<typename Digraph::Arc> outcir;
  13.135 +    // Vector containing the chord arcs
  13.136 +    std::vector<typename Digraph::Arc> chords;
  13.137 +  };
  13.138 +
  13.139 +  // Adds the reverse pair of all arcs to a digraph
  13.140 +  template<class Digraph>
  13.141 +  void bidirDigraph(Digraph &G)
  13.142 +  {
  13.143 +    typedef typename Digraph::Arc Arc;
  13.144 +    typedef typename Digraph::ArcIt ArcIt;
  13.145 +
  13.146 +    std::vector<Arc> ee;
  13.147 +
  13.148 +    for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
  13.149 +
  13.150 +    for(int i=0;i<int(ee.size());++i)
  13.151 +      G.addArc(G.target(ee[i]),G.source(ee[i]));
  13.152 +  }
  13.153 +
  13.154 +  // Adds a Petersen digraph to G.
  13.155 +  // Returns the nodes and arcs of the generated digraph.
  13.156 +  template<typename Digraph>
  13.157 +  PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
  13.158 +  {
  13.159 +    PetStruct<Digraph> n;
  13.160 +
  13.161 +    for(int i=0;i<num;i++) {
  13.162 +      n.outer.push_back(G.addNode());
  13.163 +      n.inner.push_back(G.addNode());
  13.164 +    }
  13.165 +
  13.166 +    for(int i=0;i<num;i++) {
  13.167 +      n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
  13.168 +      n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));
  13.169 +      n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));
  13.170 +    }
  13.171 +
  13.172 +    return n;
  13.173 +  }
  13.174 +
  13.175 +  // Checks the bidirectioned Petersen digraph
  13.176 +  template<class Digraph>
  13.177 +  void checkBidirPetersen(const Digraph &G, int num = 5)
  13.178 +  {
  13.179 +    typedef typename Digraph::NodeIt NodeIt;
  13.180 +
  13.181 +    checkGraphNodeList(G, 2 * num);
  13.182 +    checkGraphArcList(G, 6 * num);
  13.183 +
  13.184 +    for(NodeIt n(G);n!=INVALID;++n) {
  13.185 +      checkGraphInArcList(G, n, 3);
  13.186 +      checkGraphOutArcList(G, n, 3);
  13.187 +    }
  13.188 +  }
  13.189 +
  13.190 +  // Structure returned by addUPetersen()
  13.191 +  template<class Graph>
  13.192 +  struct UPetStruct
  13.193 +  {
  13.194 +    // Vector containing the outer nodes
  13.195 +    std::vector<typename Graph::Node> outer;
  13.196 +    // Vector containing the inner nodes
  13.197 +    std::vector<typename Graph::Node> inner;
  13.198 +    // Vector containing the edges of the inner circle
  13.199 +    std::vector<typename Graph::Edge> incir;
  13.200 +    // Vector containing the edges of the outer circle
  13.201 +    std::vector<typename Graph::Edge> outcir;
  13.202 +    // Vector containing the chord edges
  13.203 +    std::vector<typename Graph::Edge> chords;
  13.204 +  };
  13.205 +
  13.206 +  // Adds a Petersen graph to \c G.
  13.207 +  // Returns the nodes and edges of the generated graph.
  13.208 +  template<typename Graph>
  13.209 +  UPetStruct<Graph> addUPetersen(Graph &G,int num=5)
  13.210 +  {
  13.211 +    UPetStruct<Graph> n;
  13.212 +
  13.213 +    for(int i=0;i<num;i++) {
  13.214 +      n.outer.push_back(G.addNode());
  13.215 +      n.inner.push_back(G.addNode());
  13.216 +    }
  13.217 +
  13.218 +    for(int i=0;i<num;i++) {
  13.219 +      n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
  13.220 +      n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%num]));
  13.221 +      n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%num]));
  13.222 +    }
  13.223 +    
  13.224 +    return n;
  13.225 +  }
  13.226 +
  13.227 +  // Checks the undirected Petersen graph
  13.228 +  template<class Graph>
  13.229 +  void checkUndirPetersen(const Graph &G, int num = 5)
  13.230 +  {
  13.231 +    typedef typename Graph::NodeIt NodeIt;
  13.232 +
  13.233 +    checkGraphNodeList(G, 2 * num);
  13.234 +    checkGraphEdgeList(G, 3 * num);
  13.235 +    checkGraphArcList(G, 6 * num);
  13.236 +
  13.237 +    for(NodeIt n(G);n!=INVALID;++n) {
  13.238 +      checkGraphIncEdgeList(G, n, 3);
  13.239 +    }
  13.240 +  }
  13.241 +
  13.242 +  template <class Digraph>
  13.243 +  void checkDigraph() {
  13.244 +    const int num = 5;
  13.245 +    Digraph G;
  13.246 +    checkGraphNodeList(G, 0);
  13.247 +    checkGraphArcList(G, 0);
  13.248 +    addPetersen(G, num);
  13.249 +    bidirDigraph(G);
  13.250 +    checkBidirPetersen(G, num);
  13.251 +  }
  13.252 +  
  13.253 +  template <class Graph>
  13.254 +  void checkGraph() {
  13.255 +    const int num = 5;
  13.256 +    Graph G;
  13.257 +    checkGraphNodeList(G, 0);
  13.258 +    checkGraphEdgeList(G, 0);
  13.259 +    addUPetersen(G, num);
  13.260 +    checkUndirPetersen(G, num);
  13.261 +  }
  13.262 +
  13.263 +} //namespace lemon
  13.264 +
  13.265 +#endif
    14.1 --- a/test/graph_utils_test.cc	Sun Jun 15 22:03:33 2008 +0200
    14.2 +++ b/test/graph_utils_test.cc	Sun Jun 15 22:05:23 2008 +0200
    14.3 @@ -16,41 +16,177 @@
    14.4   *
    14.5   */
    14.6  
    14.7 -#include <iostream>
    14.8 -#include <vector>
    14.9 +#include <cstdlib>
   14.10 +#include <ctime>
   14.11  
   14.12 +#include <lemon/random.h>
   14.13  #include <lemon/graph_utils.h>
   14.14 -
   14.15  #include <lemon/list_graph.h>
   14.16  #include <lemon/smart_graph.h>
   14.17  
   14.18 +#include "graph_test.h"
   14.19  #include "test_tools.h"
   14.20 -#include "graph_utils_test.h"
   14.21 -
   14.22  
   14.23  using namespace lemon;
   14.24  
   14.25 -template <class Graph>
   14.26 -void checkSnapDeg() 
   14.27 +template <typename Digraph>
   14.28 +void checkFindArcs() {
   14.29 +  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
   14.30 +
   14.31 +  {
   14.32 +    Digraph digraph;
   14.33 +    for (int i = 0; i < 10; ++i) {
   14.34 +      digraph.addNode();
   14.35 +    }
   14.36 +    DescriptorMap<Digraph, Node> nodes(digraph);
   14.37 +    typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
   14.38 +    for (int i = 0; i < 100; ++i) {
   14.39 +      int src = rnd[invNodes.size()];
   14.40 +      int trg = rnd[invNodes.size()];
   14.41 +      digraph.addArc(invNodes[src], invNodes[trg]);
   14.42 +    }
   14.43 +    typename Digraph::template ArcMap<bool> found(digraph, false);
   14.44 +    DescriptorMap<Digraph, Arc> arcs(digraph);
   14.45 +    for (NodeIt src(digraph); src != INVALID; ++src) {
   14.46 +      for (NodeIt trg(digraph); trg != INVALID; ++trg) {
   14.47 +        for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {
   14.48 +          check(digraph.source(con) == src, "Wrong source.");
   14.49 +          check(digraph.target(con) == trg, "Wrong target.");
   14.50 +          check(found[con] == false, "The arc found already.");
   14.51 +          found[con] = true;
   14.52 +        }
   14.53 +      }
   14.54 +    }
   14.55 +    for (ArcIt it(digraph); it != INVALID; ++it) {
   14.56 +      check(found[it] == true, "The arc is not found.");
   14.57 +    }
   14.58 +  }
   14.59 +
   14.60 +  {
   14.61 +    int num = 5;
   14.62 +    Digraph fg;
   14.63 +    std::vector<Node> nodes;
   14.64 +    for (int i = 0; i < num; ++i) {
   14.65 +      nodes.push_back(fg.addNode());
   14.66 +    }
   14.67 +    for (int i = 0; i < num * num; ++i) {
   14.68 +      fg.addArc(nodes[i / num], nodes[i % num]);
   14.69 +    }
   14.70 +    check(countNodes(fg) == num, "Wrong node number.");
   14.71 +    check(countArcs(fg) == num*num, "Wrong arc number.");
   14.72 +    for (NodeIt src(fg); src != INVALID; ++src) {
   14.73 +      for (NodeIt trg(fg); trg != INVALID; ++trg) {
   14.74 +        ConArcIt<Digraph> con(fg, src, trg);
   14.75 +        check(con != INVALID, "There is no connecting arc.");
   14.76 +        check(fg.source(con) == src, "Wrong source.");
   14.77 +        check(fg.target(con) == trg, "Wrong target.");
   14.78 +        check(++con == INVALID, "There is more connecting arc.");
   14.79 +      }
   14.80 +    }
   14.81 +    ArcLookUp<Digraph> al1(fg);
   14.82 +    DynArcLookUp<Digraph> al2(fg);
   14.83 +    AllArcLookUp<Digraph> al3(fg);
   14.84 +    for (NodeIt src(fg); src != INVALID; ++src) {
   14.85 +      for (NodeIt trg(fg); trg != INVALID; ++trg) {
   14.86 +        Arc con1 = al1(src, trg);
   14.87 +        Arc con2 = al2(src, trg);
   14.88 +        Arc con3 = al3(src, trg);
   14.89 +        Arc con4 = findArc(fg, src, trg);
   14.90 +        check(con1 == con2 && con2 == con3 && con3 == con4, "Different results.")
   14.91 +        check(con1 != INVALID, "There is no connecting arc.");
   14.92 +        check(fg.source(con1) == src, "Wrong source.");
   14.93 +        check(fg.target(con1) == trg, "Wrong target.");
   14.94 +        check(al3(src, trg, con3) == INVALID, "There is more connecting arc.");
   14.95 +        check(findArc(fg, src, trg, con4) == INVALID, "There is more connecting arc.");
   14.96 +      }
   14.97 +    }
   14.98 +  }
   14.99 +}
  14.100 +
  14.101 +template <typename Graph>
  14.102 +void checkFindEdges() {
  14.103 +  TEMPLATE_GRAPH_TYPEDEFS(Graph);
  14.104 +  Graph graph;
  14.105 +  for (int i = 0; i < 10; ++i) {
  14.106 +    graph.addNode();
  14.107 +  }
  14.108 +  DescriptorMap<Graph, Node> nodes(graph);
  14.109 +  typename DescriptorMap<Graph, Node>::InverseMap invNodes(nodes);
  14.110 +  for (int i = 0; i < 100; ++i) {
  14.111 +    int src = rnd[invNodes.size()];
  14.112 +    int trg = rnd[invNodes.size()];
  14.113 +    graph.addEdge(invNodes[src], invNodes[trg]);
  14.114 +  }
  14.115 +  typename Graph::template EdgeMap<int> found(graph, 0);
  14.116 +  DescriptorMap<Graph, Edge> edges(graph);
  14.117 +  for (NodeIt src(graph); src != INVALID; ++src) {
  14.118 +    for (NodeIt trg(graph); trg != INVALID; ++trg) {
  14.119 +      for (ConEdgeIt<Graph> con(graph, src, trg); con != INVALID; ++con) {
  14.120 +        check( (graph.u(con) == src && graph.v(con) == trg) ||
  14.121 +               (graph.v(con) == src && graph.u(con) == trg), "Wrong end nodes.");
  14.122 +        ++found[con];
  14.123 +        check(found[con] <= 2, "The edge found more than twice.");
  14.124 +      }
  14.125 +    }
  14.126 +  }
  14.127 +  for (EdgeIt it(graph); it != INVALID; ++it) {
  14.128 +    check( (graph.u(it) != graph.v(it) && found[it] == 2) ||
  14.129 +           (graph.u(it) == graph.v(it) && found[it] == 1),
  14.130 +           "The edge is not found correctly.");
  14.131 +  }
  14.132 +}
  14.133 +
  14.134 +template <class Digraph>
  14.135 +void checkDeg()
  14.136  {
  14.137 -  Graph g;
  14.138 -  typename Graph::Node n1=g.addNode();
  14.139 -  typename Graph::Node n2=g.addNode();
  14.140 -   
  14.141 -  InDegMap<Graph> ind(g);
  14.142 - 
  14.143 +  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
  14.144 +  
  14.145 +  const int nodeNum = 10;
  14.146 +  const int arcNum = 100;
  14.147 +  Digraph digraph;
  14.148 +  InDegMap<Digraph> inDeg(digraph);
  14.149 +  OutDegMap<Digraph> outDeg(digraph);
  14.150 +  std::vector<Node> nodes(nodeNum);
  14.151 +  for (int i = 0; i < nodeNum; ++i) {
  14.152 +    nodes[i] = digraph.addNode();
  14.153 +  }
  14.154 +  std::vector<Arc> arcs(arcNum);
  14.155 +  for (int i = 0; i < arcNum; ++i) {
  14.156 +    arcs[i] = digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
  14.157 +  }
  14.158 +  for (int i = 0; i < nodeNum; ++i) {
  14.159 +    check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]), 
  14.160 +          "Wrong in degree map");
  14.161 +  }
  14.162 +  for (int i = 0; i < nodeNum; ++i) {
  14.163 +    check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]), 
  14.164 +          "Wrong out degree map");
  14.165 +  }
  14.166 +}
  14.167 +
  14.168 +template <class Digraph>
  14.169 +void checkSnapDeg()
  14.170 +{
  14.171 +  TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
  14.172 +
  14.173 +  Digraph g;
  14.174 +  Node n1=g.addNode();
  14.175 +  Node n2=g.addNode();
  14.176 +  
  14.177 +  InDegMap<Digraph> ind(g);
  14.178 +  
  14.179    g.addArc(n1,n2);
  14.180    
  14.181 -  typename Graph::Snapshot snap(g);
  14.182 +  typename Digraph::Snapshot snap(g);
  14.183    
  14.184 -  OutDegMap<Graph> outd(g);
  14.185 +  OutDegMap<Digraph> outd(g);
  14.186    
  14.187    check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
  14.188    check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
  14.189  
  14.190    g.addArc(n1,n2);
  14.191    g.addArc(n2,n1);
  14.192 - 
  14.193 +
  14.194    check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
  14.195    check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
  14.196  
  14.197 @@ -58,84 +194,20 @@
  14.198  
  14.199    check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
  14.200    check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
  14.201 -  
  14.202  }
  14.203  
  14.204  int main() {
  14.205 -  ///\file
  14.206 -  { // checking list graph
  14.207 -    checkDigraphCounters<ListDigraph>();
  14.208 -    checkFindArc<ListDigraph>();
  14.209 -  }
  14.210 -  { // checking smart graph
  14.211 -    checkDigraphCounters<SmartDigraph>();
  14.212 -    checkFindArc<SmartDigraph>();
  14.213 -  }
  14.214 -  {
  14.215 -    int num = 5;
  14.216 -    SmartDigraph fg;
  14.217 -    std::vector<SmartDigraph::Node> nodes;
  14.218 -    for (int i = 0; i < num; ++i) {
  14.219 -      nodes.push_back(fg.addNode());
  14.220 -    }
  14.221 -    for (int i = 0; i < num * num; ++i) {
  14.222 -      fg.addArc(nodes[i / num], nodes[i % num]);
  14.223 -    }
  14.224 -    check(countNodes(fg) == num, "FullGraph: wrong node number.");
  14.225 -    check(countArcs(fg) == num*num, "FullGraph: wrong arc number.");
  14.226 -    for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
  14.227 -      for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
  14.228 -	ConArcIt<SmartDigraph> con(fg, src, trg);
  14.229 -	check(con != INVALID, "There is no connecting arc.");
  14.230 -	check(fg.source(con) == src, "Wrong source.");
  14.231 -	check(fg.target(con) == trg, "Wrong target.");
  14.232 -	check(++con == INVALID, "There is more connecting arc.");
  14.233 -      }
  14.234 -    }
  14.235 -    AllArcLookUp<SmartDigraph> el(fg);
  14.236 -    for (SmartDigraph::NodeIt src(fg); src != INVALID; ++src) {
  14.237 -      for (SmartDigraph::NodeIt trg(fg); trg != INVALID; ++trg) {
  14.238 -	SmartDigraph::Arc con = el(src, trg);
  14.239 -	check(con != INVALID, "There is no connecting arc.");
  14.240 -	check(fg.source(con) == src, "Wrong source.");
  14.241 -	check(fg.target(con) == trg, "Wrong target.");
  14.242 -	check(el(src,trg,con) == INVALID, "There is more connecting arc.");
  14.243 -      }
  14.244 -    }
  14.245 -  }
  14.246 +  // Checking ConArcIt, ConEdgeIt, ArcLookUp, AllArcLookUp, and DynArcLookUp
  14.247 +  checkFindArcs<ListDigraph>();
  14.248 +  checkFindArcs<SmartDigraph>();
  14.249 +  checkFindEdges<ListGraph>();
  14.250 +  checkFindEdges<SmartGraph>();
  14.251  
  14.252 -  //check In/OutDegMap (and Snapshot feature)
  14.253 -
  14.254 +  // Checking In/OutDegMap (and Snapshot feature)
  14.255 +  checkDeg<ListDigraph>();
  14.256 +  checkDeg<SmartDigraph>();
  14.257    checkSnapDeg<ListDigraph>();
  14.258    checkSnapDeg<SmartDigraph>();
  14.259 -  
  14.260 -  {
  14.261 -    const int nodeNum = 10;
  14.262 -    const int arcNum = 100;
  14.263 -    ListDigraph digraph;
  14.264 -    InDegMap<ListDigraph> inDeg(digraph);
  14.265 -    OutDegMap<ListDigraph> outDeg(digraph);
  14.266 -    std::vector<ListDigraph::Node> nodes(nodeNum);
  14.267 -    for (int i = 0; i < nodeNum; ++i) {
  14.268 -      nodes[i] = digraph.addNode();
  14.269 -    }
  14.270 -    std::vector<ListDigraph::Arc> arcs(arcNum);
  14.271 -    for (int i = 0; i < arcNum; ++i) {
  14.272 -      arcs[i] = 
  14.273 -	digraph.addArc(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
  14.274 -    }
  14.275 -    for (int i = 0; i < nodeNum; ++i) {
  14.276 -      check(inDeg[nodes[i]] == countInArcs(digraph, nodes[i]), 
  14.277 -	    "Wrong in degree map");
  14.278 -    }
  14.279 -    for (int i = 0; i < nodeNum; ++i) {
  14.280 -      check(outDeg[nodes[i]] == countOutArcs(digraph, nodes[i]), 
  14.281 -	    "Wrong in degree map");
  14.282 -    }
  14.283 -  }
  14.284 -
  14.285 -  ///Everything is OK
  14.286 -  std::cout << __FILE__ ": All tests passed.\n";
  14.287  
  14.288    return 0;
  14.289  }
    15.1 --- a/test/graph_utils_test.h	Sun Jun 15 22:03:33 2008 +0200
    15.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
    15.3 @@ -1,83 +0,0 @@
    15.4 -/* -*- C++ -*-
    15.5 - *
    15.6 - * This file is a part of LEMON, a generic C++ optimization library
    15.7 - *
    15.8 - * Copyright (C) 2003-2008
    15.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
   15.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
   15.11 - *
   15.12 - * Permission to use, modify and distribute this software is granted
   15.13 - * provided that this copyright notice appears in all copies. For
   15.14 - * precise terms see the accompanying LICENSE file.
   15.15 - *
   15.16 - * This software is provided "AS IS" with no warranty of any kind,
   15.17 - * express or implied, and with no claim as to its suitability for any
   15.18 - * purpose.
   15.19 - *
   15.20 - */
   15.21 -
   15.22 -#ifndef LEMON_TEST_GRAPH_UTILS_TEST_H
   15.23 -#define LEMON_TEST_GRAPH_UTILS_TEST_H
   15.24 -
   15.25 -
   15.26 -#include "test_tools.h"
   15.27 -#include <cstdlib>
   15.28 -#include <ctime>
   15.29 -
   15.30 -//! \ingroup misc
   15.31 -//! \file
   15.32 -//! \brief Test cases for graph utils.
   15.33 -namespace lemon {
   15.34 -  
   15.35 -  template <typename Digraph>
   15.36 -  void checkDigraphCounters() {
   15.37 -    const int num = 5;
   15.38 -    Digraph digraph;
   15.39 -    addPetersen(digraph, num);
   15.40 -    bidirDigraph(digraph);
   15.41 -    check(countNodes(digraph) == 2*num, "Wrong node number.");
   15.42 -    check(countArcs(digraph) == 6*num, "Wrong arc number.");    
   15.43 -    for (typename Digraph::NodeIt it(digraph); it != INVALID; ++it) {
   15.44 -      check(countOutArcs(digraph, it) == 3, "Wrong out degree number.");
   15.45 -      check(countInArcs(digraph, it) == 3, "Wrong in degree number.");
   15.46 -    }
   15.47 -  }
   15.48 -
   15.49 -  template <typename Digraph>
   15.50 -  void checkFindArc() {
   15.51 -    typedef typename Digraph::Node Node;
   15.52 -    typedef typename Digraph::Arc Arc;
   15.53 -    typedef typename Digraph::NodeIt NodeIt;
   15.54 -    typedef typename Digraph::ArcIt ArcIt;
   15.55 -    Digraph digraph;
   15.56 -    for (int i = 0; i < 10; ++i) {
   15.57 -      digraph.addNode();
   15.58 -    }
   15.59 -    DescriptorMap<Digraph, Node> nodes(digraph);
   15.60 -    typename DescriptorMap<Digraph, Node>::InverseMap invNodes(nodes);
   15.61 -    for (int i = 0; i < 100; ++i) {
   15.62 -      int src = rnd[invNodes.size()];
   15.63 -      int trg = rnd[invNodes.size()];
   15.64 -      digraph.addArc(invNodes[src], invNodes[trg]);
   15.65 -    }
   15.66 -    typename Digraph::template ArcMap<bool> found(digraph, false);
   15.67 -    DescriptorMap<Digraph, Arc> arcs(digraph);
   15.68 -    for (NodeIt src(digraph); src != INVALID; ++src) {
   15.69 -      for (NodeIt trg(digraph); trg != INVALID; ++trg) {
   15.70 -	for (ConArcIt<Digraph> con(digraph, src, trg); con != INVALID; ++con) {
   15.71 -	  check(digraph.source(con) == src, "Wrong source.");
   15.72 -	  check(digraph.target(con) == trg, "Wrong target.");
   15.73 -	  check(found[con] == false, "The arc found already.");
   15.74 -	  found[con] = true;
   15.75 -	}
   15.76 -      }
   15.77 -    }
   15.78 -    for (ArcIt it(digraph); it != INVALID; ++it) {
   15.79 -      check(found[it] == true, "The arc is not found.");
   15.80 -    }
   15.81 -  }
   15.82 -  
   15.83 -} //namespace lemon
   15.84 -
   15.85 -
   15.86 -#endif
    16.1 --- a/test/heap_test.cc	Sun Jun 15 22:03:33 2008 +0200
    16.2 +++ b/test/heap_test.cc	Sun Jun 15 22:05:23 2008 +0200
    16.3 @@ -42,7 +42,6 @@
    16.4  using namespace lemon;
    16.5  using namespace lemon::concepts;
    16.6  
    16.7 -
    16.8  int main() {
    16.9  
   16.10    typedef int Item;
   16.11 @@ -77,7 +76,7 @@
   16.12      run();  
   16.13   
   16.14    {
   16.15 -    std::cerr << "Checking Bin Heap" << std::endl;
   16.16 +    std::cout << "Checking Bin Heap" << std::endl;
   16.17  
   16.18      typedef BinHeap<Prio, ItemIntMap> IntHeap;
   16.19      checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   16.20 @@ -91,7 +90,7 @@
   16.21      std::cout << timer << std::endl;
   16.22    }
   16.23    {
   16.24 -    std::cerr << "Checking Fib Heap" << std::endl;
   16.25 +    std::cout << "Checking Fib Heap" << std::endl;
   16.26  
   16.27      typedef FibHeap<Prio, ItemIntMap> IntHeap;
   16.28      checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   16.29 @@ -105,7 +104,7 @@
   16.30      std::cout << timer << std::endl;
   16.31    }
   16.32    {
   16.33 -    std::cerr << "Checking Radix Heap" << std::endl;
   16.34 +    std::cout << "Checking Radix Heap" << std::endl;
   16.35  
   16.36      typedef RadixHeap<ItemIntMap> IntHeap;
   16.37      checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   16.38 @@ -120,7 +119,7 @@
   16.39    }
   16.40  
   16.41    {
   16.42 -    std::cerr << "Checking Bucket Heap" << std::endl;
   16.43 +    std::cout << "Checking Bucket Heap" << std::endl;
   16.44  
   16.45      typedef BucketHeap<ItemIntMap> IntHeap;
   16.46      checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
   16.47 @@ -134,7 +133,5 @@
   16.48      std::cout << timer << std::endl;
   16.49    }
   16.50  
   16.51 -  std::cout << __FILE__ ": All tests passed.\n";
   16.52 -
   16.53    return 0;
   16.54  }
    17.1 --- a/test/kruskal_test.cc	Sun Jun 15 22:03:33 2008 +0200
    17.2 +++ b/test/kruskal_test.cc	Sun Jun 15 22:05:23 2008 +0200
    17.3 @@ -28,7 +28,6 @@
    17.4  #include <lemon/concepts/digraph.h>
    17.5  #include <lemon/concepts/graph.h>
    17.6  
    17.7 -
    17.8  using namespace std;
    17.9  using namespace lemon;
   17.10  
   17.11 @@ -57,7 +56,6 @@
   17.12  
   17.13    kruskal(g, r, ws.begin());
   17.14    kruskal(ug, ur, uws.begin());
   17.15 -
   17.16  }
   17.17  
   17.18  int main() {
   17.19 @@ -97,7 +95,7 @@
   17.20    //Test with const map.
   17.21    check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
   17.22  	"Total cost should be 10");
   17.23 -  //Test with a edge map (filled with uniform costs).
   17.24 +  //Test with an edge map (filled with uniform costs).
   17.25    check(kruskal(G, edge_cost_map, tree_map)==10,
   17.26  	"Total cost should be 10");
   17.27  
    18.1 --- a/test/map_test.h	Sun Jun 15 22:03:33 2008 +0200
    18.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
    18.3 @@ -1,149 +0,0 @@
    18.4 -/* -*- C++ -*-
    18.5 - *
    18.6 - * This file is a part of LEMON, a generic C++ optimization library
    18.7 - *
    18.8 - * Copyright (C) 2003-2008
    18.9 - * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
   18.10 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
   18.11 - *
   18.12 - * Permission to use, modify and distribute this software is granted
   18.13 - * provided that this copyright notice appears in all copies. For
   18.14 - * precise terms see the accompanying LICENSE file.
   18.15 - *
   18.16 - * This software is provided "AS IS" with no warranty of any kind,
   18.17 - * express or implied, and with no claim as to its suitability for any
   18.18 - * purpose.
   18.19 - *
   18.20 - */
   18.21 -
   18.22 -#ifndef LEMON_TEST_MAP_TEST_H
   18.23 -#define LEMON_TEST_MAP_TEST_H
   18.24 -
   18.25 -
   18.26 -#include <vector>
   18.27 -#include <lemon/maps.h>
   18.28 -
   18.29 -#include "test_tools.h"
   18.30 -
   18.31 -
   18.32 -//! \ingroup misc
   18.33 -//! \file
   18.34 -//! \brief Some utilities to test map classes.
   18.35 -
   18.36 -namespace lemon {
   18.37 -
   18.38 -
   18.39 -
   18.40 -  template <typename Graph>
   18.41 -  void checkGraphNodeMap() {
   18.42 -    Graph graph;
   18.43 -    const int num = 16;
   18.44 -    
   18.45 -    typedef typename Graph::Node Node;
   18.46 -
   18.47 -    std::vector<Node> nodes;
   18.48 -    for (int i = 0; i < num; ++i) {
   18.49 -      nodes.push_back(graph.addNode());      
   18.50 -    }
   18.51 -    typedef typename Graph::template NodeMap<int> IntNodeMap;
   18.52 -    IntNodeMap map(graph, 42);
   18.53 -    for (int i = 0; i < int(nodes.size()); ++i) {
   18.54 -      check(map[nodes[i]] == 42, "Wrong map constructor.");      
   18.55 -    }
   18.56 -    for (int i = 0; i < num; ++i) {
   18.57 -      nodes.push_back(graph.addNode());
   18.58 -      map[nodes.back()] = 23;
   18.59 -    }
   18.60 -    map = constMap<Node>(12);
   18.61 -    for (int i = 0; i < int(nodes.size()); ++i) {
   18.62 -      check(map[nodes[i]] == 12, "Wrong map constructor.");      
   18.63 -    }    
   18.64 -    graph.clear();
   18.65 -    nodes.clear();
   18.66 -  }
   18.67 -
   18.68 -  template <typename Graph>
   18.69 -  void checkGraphArcMap() {
   18.70 -    Graph graph;
   18.71 -    const int num = 16;
   18.72 -    
   18.73 -    typedef typename Graph::Node Node;
   18.74 -    typedef typename Graph::Arc Arc;
   18.75 -    
   18.76 -    std::vector<Node> nodes;
   18.77 -    for (int i = 0; i < num; ++i) {
   18.78 -      nodes.push_back(graph.addNode());
   18.79 -    }
   18.80 -    
   18.81 -    std::vector<Arc> edges;
   18.82 -    for (int i = 0; i < num; ++i) {
   18.83 -      for (int j = 0; j < i; ++j) {
   18.84 -	edges.push_back(graph.addArc(nodes[i], nodes[j]));
   18.85 -      }
   18.86 -    }
   18.87 -    
   18.88 -    typedef typename Graph::template ArcMap<int> IntArcMap;
   18.89 -    IntArcMap map(graph, 42);
   18.90 -    
   18.91 -    for (int i = 0; i < int(edges.size()); ++i) {
   18.92 -      check(map[edges[i]] == 42, "Wrong map constructor.");      
   18.93 -    }
   18.94 -    
   18.95 -    for (int i = 0; i < num; ++i) {
   18.96 -      for (int j = i + 1; j < num; ++j) {
   18.97 -	edges.push_back(graph.addArc(nodes[i], nodes[j]));
   18.98 -	map[edges.back()] = 23;
   18.99 -      }
  18.100 -    }
  18.101 -    map = constMap<Arc>(12);
  18.102 -    for (int i = 0; i < int(edges.size()); ++i) {
  18.103 -      check(map[edges[i]] == 12, "Wrong map constructor.");      
  18.104 -    }    
  18.105 -    graph.clear();
  18.106 -    edges.clear();    
  18.107 -  }
  18.108 -
  18.109 -  template <typename Graph>
  18.110 -  void checkGraphEdgeMap() {
  18.111 -    Graph graph;
  18.112 -    const int num = 16;
  18.113 -    
  18.114 -    typedef typename Graph::Node Node;
  18.115 -    typedef typename Graph::Edge Edge;
  18.116 -    
  18.117 -    std::vector<Node> nodes;
  18.118 -    for (int i = 0; i < num; ++i) {
  18.119 -      nodes.push_back(graph.addNode());
  18.120 -    }
  18.121 -    
  18.122 -    std::vector<Edge> edges;
  18.123 -    for (int i = 0; i < num; ++i) {
  18.124 -      for (int j = 0; j < i; ++j) {
  18.125 -	edges.push_back(graph.addEdge(nodes[i], nodes[j]));
  18.126 -      }
  18.127 -    }
  18.128 -    
  18.129 -    typedef typename Graph::template EdgeMap<int> IntEdgeMap;
  18.130 -    IntEdgeMap map(graph, 42);
  18.131 -    
  18.132 -    for (int i = 0; i < int(edges.size()); ++i) {
  18.133 -      check(map[edges[i]] == 42, "Wrong map constructor.");      
  18.134 -    }
  18.135 -    
  18.136 -    for (int i = 0; i < num; ++i) {
  18.137 -      for (int j = i + 1; j < num; ++j) {
  18.138 -	edges.push_back(graph.addEdge(nodes[i], nodes[j]));
  18.139 -	map[edges.back()] = 23;
  18.140 -      }
  18.141 -    }
  18.142 -    map = constMap<Edge>(12);
  18.143 -    for (int i = 0; i < int(edges.size()); ++i) {
  18.144 -      check(map[edges[i]] == 12, "Wrong map constructor.");      
  18.145 -    }    
  18.146 -    graph.clear();
  18.147 -    edges.clear();    
  18.148 -  }
  18.149 -
  18.150 -}
  18.151 -
  18.152 -#endif
    19.1 --- a/test/random_test.cc	Sun Jun 15 22:03:33 2008 +0200
    19.2 +++ b/test/random_test.cc	Sun Jun 15 22:05:23 2008 +0200
    19.3 @@ -19,11 +19,6 @@
    19.4  #include <lemon/random.h>
    19.5  #include "test_tools.h"
    19.6  
    19.7 -///\file \brief Test cases for random.h
    19.8 -///
    19.9 -///\todo To be extended
   19.10 -///
   19.11 -
   19.12  int seed_array[] = {1, 2};
   19.13  
   19.14  int main()
    20.1 --- a/test/test_tools.h	Sun Jun 15 22:03:33 2008 +0200
    20.2 +++ b/test/test_tools.h	Sun Jun 15 22:05:23 2008 +0200
    20.3 @@ -19,163 +19,29 @@
    20.4  #ifndef LEMON_TEST_TEST_TOOLS_H
    20.5  #define LEMON_TEST_TEST_TOOLS_H
    20.6  
    20.7 +///\ingroup misc
    20.8 +///\file
    20.9 +///\brief Some utilities to write test programs.
   20.10 +
   20.11  #include <iostream>
   20.12 -#include <vector>
   20.13  
   20.14 -#include <cstdlib>
   20.15 -#include <ctime>
   20.16 +///If \c rc is fail, writes an error message and exits.
   20.17  
   20.18 -#include <lemon/concept_check.h>
   20.19 -#include <lemon/concepts/digraph.h>
   20.20 -
   20.21 -#include <lemon/random.h>
   20.22 -
   20.23 -using namespace lemon;
   20.24 -
   20.25 -//! \ingroup misc
   20.26 -//! \file
   20.27 -//! \brief Some utilities to write test programs.
   20.28 -
   20.29 -
   20.30 -///If \c rc is fail, writes an error message end exit.
   20.31 -
   20.32 -///If \c rc is fail, writes an error message end exit.
   20.33 +///If \c rc is fail, writes an error message and exits.
   20.34  ///The error message contains the file name and the line number of the
   20.35  ///source code in a standard from, which makes it possible to go there
   20.36  ///using good source browsers like e.g. \c emacs.
   20.37  ///
   20.38  ///For example
   20.39  ///\code check(0==1,"This is obviously false.");\endcode will
   20.40 -///print this (and then exits).
   20.41 -///\verbatim digraph_test.cc:123: error: This is obviously false. \endverbatim
   20.42 +///print something like this (and then exits).
   20.43 +///\verbatim file_name.cc:123: error: This is obviously false. \endverbatim
   20.44  ///
   20.45 -///\todo It should be in \c error.h
   20.46 +///\todo It should be in \c assert.h
   20.47  #define check(rc, msg) \
   20.48    if(!(rc)) { \
   20.49      std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \
   20.50      abort(); \
   20.51    } else { } \
   20.52  
   20.53 -///Structure returned by \ref addPetersen().
   20.54 -
   20.55 -///Structure returned by \ref addPetersen().
   20.56 -///
   20.57 -template<class Digraph> struct PetStruct
   20.58 -{
   20.59 -  ///Vector containing the outer nodes.
   20.60 -  std::vector<typename Digraph::Node> outer;
   20.61 -  ///Vector containing the inner nodes.
   20.62 -  std::vector<typename Digraph::Node> inner;
   20.63 -  ///Vector containing the arcs of the inner circle.
   20.64 -  std::vector<typename Digraph::Arc> incir;
   20.65 -  ///Vector containing the arcs of the outer circle.
   20.66 -  std::vector<typename Digraph::Arc> outcir;
   20.67 -  ///Vector containing the chord arcs.
   20.68 -  std::vector<typename Digraph::Arc> chords;
   20.69 -};
   20.70 -
   20.71 -
   20.72 -
   20.73 -///Adds a Petersen digraph to \c G.
   20.74 -
   20.75 -///Adds a Petersen digraph to \c G.
   20.76 -///\return The nodes and arcs of the generated digraph.
   20.77 -
   20.78 -template<typename Digraph>
   20.79 -PetStruct<Digraph> addPetersen(Digraph &G,int num = 5)
   20.80 -{
   20.81 -  PetStruct<Digraph> n;
   20.82 -
   20.83 -  for(int i=0;i<num;i++) {
   20.84 -    n.outer.push_back(G.addNode());
   20.85 -    n.inner.push_back(G.addNode());
   20.86 -  }
   20.87 -
   20.88 - for(int i=0;i<num;i++) {
   20.89 -   n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
   20.90 -   n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num]));
   20.91 -   n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num]));
   20.92 -  }
   20.93 - return n;
   20.94 -}
   20.95 -
   20.96 -/// \brief Adds to the digraph the reverse pair of all arcs.
   20.97 -///
   20.98 -/// Adds to the digraph the reverse pair of all arcs.
   20.99 -///
  20.100 -template<class Digraph> void bidirDigraph(Digraph &G)
  20.101 -{
  20.102 -  typedef typename Digraph::Arc Arc;
  20.103 -  typedef typename Digraph::ArcIt ArcIt;
  20.104 -  
  20.105 -  std::vector<Arc> ee;
  20.106 -  
  20.107 -  for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e);
  20.108 -
  20.109 -  for(typename std::vector<Arc>::iterator p=ee.begin();p!=ee.end();p++)
  20.110 -    G.addArc(G.target(*p),G.source(*p));
  20.111 -}
  20.112 -
  20.113 -
  20.114 -/// \brief Checks the bidirectioned Petersen digraph.
  20.115 -///
  20.116 -///  Checks the bidirectioned Petersen digraph.
  20.117 -///
  20.118 -template<class Digraph> void checkBidirPetersen(Digraph &G, int num = 5)
  20.119 -{
  20.120 -  typedef typename Digraph::Node Node;
  20.121 -
  20.122 -  typedef typename Digraph::ArcIt ArcIt;
  20.123 -  typedef typename Digraph::NodeIt NodeIt;
  20.124 -
  20.125 -  checkDigraphNodeList(G, 2 * num);
  20.126 -  checkDigraphArcList(G, 6 * num);
  20.127 -
  20.128 -  for(NodeIt n(G);n!=INVALID;++n) {
  20.129 -    checkDigraphInArcList(G, n, 3);
  20.130 -    checkDigraphOutArcList(G, n, 3);
  20.131 -  }  
  20.132 -}
  20.133 -
  20.134 -///Structure returned by \ref addUPetersen().
  20.135 -
  20.136 -///Structure returned by \ref addUPetersen().
  20.137 -///
  20.138 -template<class Digraph> struct UPetStruct
  20.139 -{
  20.140 -  ///Vector containing the outer nodes.
  20.141 -  std::vector<typename Digraph::Node> outer;
  20.142 -  ///Vector containing the inner nodes.
  20.143 -  std::vector<typename Digraph::Node> inner;
  20.144 -  ///Vector containing the arcs of the inner circle.
  20.145 -  std::vector<typename Digraph::Edge> incir;
  20.146 -  ///Vector containing the arcs of the outer circle.
  20.147 -  std::vector<typename Digraph::Edge> outcir;
  20.148 -  ///Vector containing the chord arcs.
  20.149 -  std::vector<typename Digraph::Edge> chords;
  20.150 -};
  20.151 -
  20.152 -///Adds a Petersen digraph to the undirected \c G.
  20.153 -
  20.154 -///Adds a Petersen digraph to the undirected \c G.
  20.155 -///\return The nodes and arcs of the generated digraph.
  20.156 -
  20.157 -template<typename Digraph>
  20.158 -UPetStruct<Digraph> addUPetersen(Digraph &G,int num=5)
  20.159 -{
  20.160 -  UPetStruct<Digraph> n;
  20.161 -
  20.162 -  for(int i=0;i<num;i++) {
  20.163 -    n.outer.push_back(G.addNode());
  20.164 -    n.inner.push_back(G.addNode());
  20.165 -  }
  20.166 -
  20.167 - for(int i=0;i<num;i++) {
  20.168 -   n.chords.push_back(G.addArc(n.outer[i],n.inner[i]));
  20.169 -   n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1)%5]));
  20.170 -   n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2)%5]));
  20.171 - }
  20.172 - return n;
  20.173 -}
  20.174 -
  20.175  #endif
    21.1 --- a/test/time_measure_test.cc	Sun Jun 15 22:03:33 2008 +0200
    21.2 +++ b/test/time_measure_test.cc	Sun Jun 15 22:05:23 2008 +0200
    21.3 @@ -18,11 +18,6 @@
    21.4  
    21.5  #include <lemon/time_measure.h>
    21.6  
    21.7 -///\file \brief Test cases for time_measure.h
    21.8 -///
    21.9 -///\todo To be extended
   21.10 -
   21.11 -
   21.12  using namespace lemon;
   21.13  
   21.14  void f() 
    22.1 --- a/test/unionfind_test.cc	Sun Jun 15 22:03:33 2008 +0200
    22.2 +++ b/test/unionfind_test.cc	Sun Jun 15 22:05:23 2008 +0200
    22.3 @@ -16,8 +16,6 @@
    22.4   *
    22.5   */
    22.6  
    22.7 -#include <iostream>
    22.8 -
    22.9  #include <lemon/list_graph.h>
   22.10  #include <lemon/maps.h>
   22.11  #include <lemon/unionfind.h>
   22.12 @@ -39,7 +37,7 @@
   22.13    U.insert(n[1]);
   22.14    U.insert(n[2]);
   22.15  
   22.16 -  check(U.join(n[1],n[2]) != -1,"Test failed.");
   22.17 +  check(U.join(n[1],n[2]) != -1, "Something is wrong with UnionFindEnum");
   22.18  
   22.19    U.insert(n[3]);
   22.20    U.insert(n[4]);
   22.21 @@ -48,54 +46,54 @@
   22.22    U.insert(n[7]);
   22.23  
   22.24  
   22.25 -  check(U.join(n[1],n[4]) != -1,"Test failed.");
   22.26 -  check(U.join(n[2],n[4]) == -1,"Test failed.");
   22.27 -  check(U.join(n[3],n[5]) != -1,"Test failed.");
   22.28 +  check(U.join(n[1],n[4]) != -1, "Something is wrong with UnionFindEnum");
   22.29 +  check(U.join(n[2],n[4]) == -1, "Something is wrong with UnionFindEnum");
   22.30 +  check(U.join(n[3],n[5]) != -1, "Something is wrong with UnionFindEnum");
   22.31  
   22.32  
   22.33    U.insert(n[8],U.find(n[5]));
   22.34  
   22.35  
   22.36 -  check(U.size(U.find(n[4])) == 3,"Test failed.");
   22.37 -  check(U.size(U.find(n[5])) == 3,"Test failed.");
   22.38 -  check(U.size(U.find(n[6])) == 1,"Test failed.");
   22.39 -  check(U.size(U.find(n[2])) == 3,"Test failed.");
   22.40 +  check(U.size(U.find(n[4])) == 3, "Something is wrong with UnionFindEnum");
   22.41 +  check(U.size(U.find(n[5])) == 3, "Something is wrong with UnionFindEnum");
   22.42 +  check(U.size(U.find(n[6])) == 1, "Something is wrong with UnionFindEnum");
   22.43 +  check(U.size(U.find(n[2])) == 3, "Something is wrong with UnionFindEnum");
   22.44  
   22.45  
   22.46    U.insert(n[9]);
   22.47    U.insert(n[10],U.find(n[9]));
   22.48  
   22.49  
   22.50 -  check(U.join(n[8],n[10]) != -1,"Test failed.");
   22.51 +  check(U.join(n[8],n[10])  != -1, "Something is wrong with UnionFindEnum");
   22.52  
   22.53  
   22.54 -  check(U.size(U.find(n[4])) == 3,"Test failed.");
   22.55 -  check(U.size(U.find(n[9])) == 5,"Test failed.");
   22.56 +  check(U.size(U.find(n[4])) == 3, "Something is wrong with UnionFindEnum");
   22.57 +  check(U.size(U.find(n[9])) == 5, "Something is wrong with UnionFindEnum");
   22.58  
   22.59 -  check(U.size(U.find(n[8])) == 5,"Test failed.");
   22.60 +  check(U.size(U.find(n[8])) == 5, "Something is wrong with UnionFindEnum");
   22.61  
   22.62    U.erase(n[9]);
   22.63    U.erase(n[1]);
   22.64  
   22.65 -  check(U.size(U.find(n[10])) == 4,"Test failed.");
   22.66 -  check(U.size(U.find(n[2])) == 2,"Test failed.");
   22.67 +  check(U.size(U.find(n[10])) == 4, "Something is wrong with UnionFindEnum");
   22.68 +  check(U.size(U.find(n[2]))  == 2, "Something is wrong with UnionFindEnum");
   22.69  
   22.70    U.erase(n[6]);
   22.71    U.split(U.find(n[8]));
   22.72  
   22.73  
   22.74 -  check(U.size(U.find(n[4])) == 2,"Test failed.");
   22.75 -  check(U.size(U.find(n[3])) == 1,"Test failed.");
   22.76 -  check(U.size(U.find(n[2])) == 2,"Test failed.");
   22.77 +  check(U.size(U.find(n[4])) == 2, "Something is wrong with UnionFindEnum");
   22.78 +  check(U.size(U.find(n[3])) == 1, "Something is wrong with UnionFindEnum");
   22.79 +  check(U.size(U.find(n[2])) == 2, "Something is wrong with UnionFindEnum");
   22.80  
   22.81  
   22.82 -  check(U.join(n[3],n[4]) != -1,"Test failed.");
   22.83 -  check(U.join(n[2],n[4]) == -1,"Test failed.");
   22.84 +  check(U.join(n[3],n[4]) != -1, "Something is wrong with UnionFindEnum");
   22.85 +  check(U.join(n[2],n[4]) == -1, "Something is wrong with UnionFindEnum");
   22.86  
   22.87  
   22.88 -  check(U.size(U.find(n[4])) == 3,"Test failed.");
   22.89 -  check(U.size(U.find(n[3])) == 3,"Test failed.");
   22.90 -  check(U.size(U.find(n[2])) == 3,"Test failed.");
   22.91 +  check(U.size(U.find(n[4])) == 3, "Something is wrong with UnionFindEnum");
   22.92 +  check(U.size(U.find(n[3])) == 3, "Something is wrong with UnionFindEnum");
   22.93 +  check(U.size(U.find(n[2])) == 3, "Something is wrong with UnionFindEnum");
   22.94  
   22.95    U.eraseClass(U.find(n[4]));
   22.96    U.eraseClass(U.find(n[7]));