Changeset 774:4297098d9677 in lemon-0.x for src/test

Timestamp:

08/30/04 14:01:47 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1066

Message:

Merge back the whole branches/hugo++ to trunk.

Location:

src/test

Files:

• Makefile.am (modified) (2 diffs)
• bfs_test.cc (added)
• dijkstra_test.cc (modified) (2 diffs)
• graph_test.cc (modified) (14 diffs)
• test_tools.h (modified) (1 diff)
• unionfind_test.cc (modified) (4 diffs)
• xy_test.cc (modified) (3 diffs)

src/test/Makefile.am

@@ -3 +3 @@
 noinst_HEADERS = test_tools.h
 
-check_PROGRAMS = graph_test dijkstra_test time_measure_test error_test xy_test \
-        test_tools_pass test_tools_fail
+check_PROGRAMS = graph_test dijkstra_test bfs_test time_measure_test \
+        error_test xy_test \
+        unionfind_test test_tools_pass test_tools_fail
 
 TESTS = $(check_PROGRAMS)
@@ -11 +12 @@
 graph_test_SOURCES = graph_test.cc
 dijkstra_test_SOURCES = dijkstra_test.cc
+bfs_test_SOURCES = bfs_test.cc
+unionfind_test_SOURCES = unionfind_test.cc
 time_measure_test_SOURCES = time_measure_test.cc
 error_test_SOURCES = error_test.cc

src/test/dijkstra_test.cc

@@ -76 +76 @@
 
 
-  for(EdgeIt e(G); G.valid(e); G.next(e)) {
+  for(EdgeIt e(G); e==INVALID; ++e) {
     Node u=G.tail(e);
     Node v=G.head(e);
@@ -87 +87 @@
 
   ///\bug This works only for integer lengths
-  for(NodeIt v(G); G.valid(v); G.next(v))
+  for(NodeIt v(G); v==INVALID; ++v)
     if ( dijkstra_test.reached(v) ) {
       Edge e=dijkstra_test.pred(v);

src/test/graph_test.cc

@@ -7 +7 @@
 #include"test_tools.h"
 
-/*
+/**
+\file
 This test makes consistency checks of list graph structures.
 
-G.addNode(), G.addEdge(), G.valid(), G.tail(), G.head()
+G.addNode(), G.addEdge(), G.tail(), G.head()
 
 \todo Checks for empty graphs and isolated points.
+\todo Checks for Node->NodeIt, Edge->{EdgeIt,InEdgeIt,OutEdgeIt}
+conversion.
 */
 
@@ -30 +33 @@
     Node i; Node j(i); Node k(INVALID);
     i=j;
-    bool b=G.valid(i); b=b;
+    //    bool b=G.valid(i); b=b;
+    bool b; b=b;
+    b=(i==INVALID); b=(i!=INVALID);
     b=(i==j); b=(i!=j); b=(i<j);
   }
@@ -37 +42 @@
     i=j;
     j=G.first(i);
-    j=G.next(i);
-    bool b=G.valid(i); b=b;
+    j=++i;
+    //    bool b=G.valid(i); b=b;
+    bool b; b=b;
+    b=(i==INVALID); b=(i!=INVALID);
     Node n(i);
     n=i;
     b=(i==j); b=(i!=j); b=(i<j);
+    //Node ->NodeIt conversion
+    NodeIt ni(G,n);
   }
   {
     Edge i; Edge j(i); Edge k(INVALID);
     i=j;
-    bool b=G.valid(i); b=b;
+    //    bool b=G.valid(i); b=b;
+    bool b; b=b;
+    b=(i==INVALID); b=(i!=INVALID);
     b=(i==j); b=(i!=j); b=(i<j);
   }
@@ -53 +64 @@
     i=j;
     j=G.first(i);
-    j=G.next(i);
-    bool b=G.valid(i); b=b;
+    j=++i;
+    //    bool b=G.valid(i); b=b;
+    bool b; b=b;
+    b=(i==INVALID); b=(i!=INVALID);
     Edge e(i);
     e=i;
     b=(i==j); b=(i!=j); b=(i<j);
+    //Edge ->EdgeIt conversion
+    EdgeIt ei(G,e);
   }
   {
@@ -64 +79 @@
     i=j;
     j=G.first(i,n);
-    j=G.next(i);
-    bool b=G.valid(i); b=b;
+    j=++i;
+    //    bool b=G.valid(i); b=b;
+    bool b; b=b;
+    b=(i==INVALID); b=(i!=INVALID);
     Edge e(i);
     e=i;
     b=(i==j); b=(i!=j); b=(i<j);
+    //Edge ->InEdgeIt conversion
+    InEdgeIt ei(G,e);
   }
   {
@@ -75 +94 @@
     i=j;
     j=G.first(i,n);
-    j=G.next(i);
-    bool b=G.valid(i); b=b;
+    j=++i;
+    //    bool b=G.valid(i); b=b;
+    bool b; b=b;
+    b=(i==INVALID); b=(i!=INVALID);
     Edge e(i);
     e=i;
     b=(i==j); b=(i!=j); b=(i<j);
-  }
-
-  Node n,m;
-  n=m=INVALID;
-  Edge e;
-  e=INVALID;
-  n=G.tail(e);
-  n=G.head(e);
-
-  //aNode, bNode ?
-
+    //Edge ->OutEdgeIt conversion
+    OutEdgeIt ei(G,e);
+  }
+  {
+    Node n,m;
+    n=m=INVALID;
+    Edge e;
+    e=INVALID;
+    n=G.tail(e);
+    n=G.head(e);
+  }
   // id tests
-  { int i=G.id(n); i=i; }
-  { int i=G.id(e); i=i; }
-  
-  //  G.clear();
-
+  { Node n; int i=G.id(n); i=i; }
+  { Edge e; int i=G.id(e); i=i; }
   //NodeMap tests
   {
     Node k;
     typename Graph::template NodeMap<int> m(G);
-    typename Graph::template NodeMap<int> const &cm = m;  //Const map
+    //Const map
+    typename Graph::template NodeMap<int> const &cm = m;
     //Inicialize with default value
     typename Graph::template NodeMap<int> mdef(G,12);
-    typename Graph::template NodeMap<int> mm(cm);   //Copy
-    typename Graph::template NodeMap<double> dm(cm); //Copy from another type
+    //Copy
+    typename Graph::template NodeMap<int> mm(cm);
+    //Copy from another type
+    typename Graph::template NodeMap<double> dm(cm);
     int v;
     v=m[k]; m[k]=v; m.set(k,v);
@@ -161 +182 @@
     m=dm; //Copy to another type
   }
-  
 }
 
@@ -178 +198 @@
   n=G.addNode();
   m=G.addNode();
-  
-  G.addEdge(n,m);
+  Edge e;
+  e=G.addEdge(n,m); 
+  
+  //  G.clear();
+}
+
+template<class Graph> void checkCompileErase(Graph &G) 
+{
+  typedef typename Graph::Node Node;
+  typedef typename Graph::Edge Edge;
+  Node n;
+  Edge e;
+  G.erase(n);
+  G.erase(e);
+}
+
+template<class Graph> void checkCompileEraseEdge(Graph &G) 
+{
+  typedef typename Graph::Edge Edge;
+  Edge e;
+  G.erase(e);
+}
+
+template<class Graph> void checkCompileFindEdge(Graph &G) 
+{
+  typedef typename Graph::NodeIt Node;
+  typedef typename Graph::NodeIt NodeIt;
+
+  G.findEdge(NodeIt(G),++NodeIt(G),G.findEdge(NodeIt(G),++NodeIt(G)));
+  G.findEdge(Node(),Node(),G.findEdge(Node(),Node()));  
 }
 
@@ -187 +235 @@
   typename Graph::NodeIt n(G);
   for(int i=0;i<nn;i++) {
-    check(G.valid(n),"Wrong Node list linking.");
-    G.next(n);
-  }
-  check(!G.valid(n),"Wrong Node list linking.");
+    check(n!=INVALID,"Wrong Node list linking.");
+    ++n;
+  }
+  check(n==INVALID,"Wrong Node list linking.");
 }
 
@@ -199 +247 @@
   EdgeIt e(G);
   for(int i=0;i<nn;i++) {
-    check(G.valid(e),"Wrong Edge list linking.");
-    G.next(e);
-  }
-  check(!G.valid(e),"Wrong Edge list linking.");
+    check(e!=INVALID,"Wrong Edge list linking.");
+    ++e;
+  }
+  check(e==INVALID,"Wrong Edge list linking.");
 }
 
@@ -211 +259 @@
   typename Graph::OutEdgeIt e(G,n);
   for(int i=0;i<nn;i++) {
-    check(G.valid(e),"Wrong OutEdge list linking.");
-    G.next(e);
-  }
-  check(!G.valid(e),"Wrong OutEdge list linking.");
+    check(e!=INVALID,"Wrong OutEdge list linking.");
+    ++e;
+  }
+  check(e==INVALID,"Wrong OutEdge list linking.");
 }
 
 template<class Graph> void checkInEdgeList(Graph &G,
-                                            typename Graph::Node n,
-                                            int nn)
+                                           typename Graph::Node n,
+                                           int nn)
 {
   typename Graph::InEdgeIt e(G,n);
   for(int i=0;i<nn;i++) {
-    check(G.valid(e),"Wrong InEdge list linking.");
-    G.next(e);
-  }
-  check(!G.valid(e),"Wrong InEdge list linking.");
-}
-
-//Checks head(), tail() as well;
+    check(e!=INVALID,"Wrong InEdge list linking.");
+    ++e;
+  }
+  check(e==INVALID,"Wrong InEdge list linking.");
+}
+
+///\file
+///\todo Checks head(), tail() as well;
+
 template<class Graph> void bidirPetersen(Graph &G)
 {
@@ -239 +289 @@
   std::vector<Edge> ee;
   
-  for(EdgeIt e(G);G.valid(e);G.next(e)) ee.push_back(e);
+  for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e);
 
   for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)
@@ -255 +305 @@
   checkEdgeList(G,30);
 
-  for(NodeIt n(G);G.valid(n);G.next(n)) {
+  for(NodeIt n(G);n!=INVALID;++n) {
     checkInEdgeList(G,n,3);
     checkOutEdgeList(G,n,3);
-    G.next(n);
+    ++n;
   }  
 }
 
-template
+//Compile GraphSkeleton
+template 
 void checkCompileStaticGraph<StaticGraphSkeleton>(StaticGraphSkeleton &);
 template void checkCompile<GraphSkeleton>(GraphSkeleton &);
-
+template
+void checkCompileErase<EraseableGraphSkeleton>(EraseableGraphSkeleton &);
+
+//Compile SmartGraph
 template void checkCompile<SmartGraph>(SmartGraph &);
+//Compile SymSmartGraph
 template void checkCompile<SymSmartGraph>(SymSmartGraph &);
+
+//Compile ListGraph
 template void checkCompile<ListGraph>(ListGraph &);
+template void checkCompileErase<ListGraph>(ListGraph &);
+template void checkCompileFindEdge<ListGraph>(ListGraph &);
+
+//Compile SymListGraph
 template void checkCompile<SymListGraph>(SymListGraph &);
+template void checkCompileErase<SymListGraph>(SymListGraph &);
+template void checkCompileFindEdge<SymListGraph>(SymListGraph &);
+
+//Compile FullGraph
 template void checkCompileStaticGraph<FullGraph>(FullGraph &);
-
+template void checkCompileFindEdge<FullGraph>(FullGraph &);
+
+//Compile EdgeSet <ListGraph>
 template void checkCompile<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
+template
+void checkCompileEraseEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
+template
+void checkCompileFindEdge<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
+
+//Compile EdgeSet <NodeSet>
 template void checkCompile<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
+template
+void checkCompileEraseEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
+template void checkCompileFindEdge<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
+
 
 int main() 
@@ -300 +377 @@
   }
 
-  //\todo map tests.
-  //\todo copy constr tests.
+  ///\file
+  ///\todo map tests.
+  ///\todo copy constr tests.
 
   std::cout << __FILE__ ": All tests passed.\n";

src/test/test_tools.h

@@ -21 +21 @@
 ///print this (and then exits).
 ///\verbatim graph_test.cc:123: error: This is obviously false. \endverbatim
+///
+///\todo It should be in \c error.h
 #define check(rc, msg) \
   if(!(rc)) { \

src/test/unionfind_test.cc

@@ -3 +3 @@
 #include <hugo/maps.h>
 #include <hugo/unionfind.h>
+#include "test_tools.h"
 
 using namespace hugo;
 using namespace std;
-
-bool passed = true;
-
-void check(bool rc) {
-  passed = passed && rc;
-  if(!rc) {
-    cout << "Test failed!" << endl;
-  }
-}
 
 template <typename T>
@@ -23 +15 @@
 void print(UFE const &ufe) {
   UFE::ClassIt cit;
-  cout << "printing the classes of the structure:" << endl;
+  cout << "Print the classes of the structure:" << endl;
   int i = 1;
   for (ufe.first(cit); ufe.valid(cit); ufe.next(cit)) {
@@ -42 +34 @@
   UFE U(base);
 
-  print(U);
+//   print(U);
 
-  cout << "Inserting 1..." << endl;
+  cout << "Insert 1..." << endl;
   U.insert(1);
-  print(U);
+//   print(U);
   
-  cout << "Inserting 2..." << endl;
+  cout << "Insert 2..." << endl;
   U.insert(2);
-  print(U);
+//   print(U);
   
-  cout << "Joining 1 and 2..." << endl;
-  check(U.join(1,2));
-  print(U);
+  cout << "Join 1 and 2..." << endl;
+  check(U.join(1,2),"Test failed.");
+//   print(U);
 
-  cout << "Inserting 3, 4, 5, 6, 7..." << endl;
+  cout << "Insert 3, 4, 5, 6, 7..." << endl;
   U.insert(3);
   U.insert(4);
@@ -62 +54 @@
   U.insert(6);
   U.insert(7);
-  print (U);
+//   print (U);
 
-  cout << "Joining 1 - 4, 2 - 4 and 3 - 5 ..." << endl;
-  check(U.join(1,4));
-  check(!U.join(2,4));
-  check(U.join(3,5));
-  print(U);
+  cout << "Join 1 - 4, 2 - 4 and 3 - 5 ..." << endl;
+  check(U.join(1,4),"Test failed.");
+  check(!U.join(2,4),"Test failed.");
+  check(U.join(3,5),"Test failed.");
+//   print(U);
 
-  cout << "Inserting 8 to the component of 5 ..." << endl;
+  cout << "Insert 8 to the component of 5 ..." << endl;
   U.insert(8,5);
-  print(U);
+//   print(U);
 
-  cout << "size of the class of 4: " << U.size(4) << endl;
-  check(U.size(4) == 3);
-  cout << "size of the class of 5: " << U.size(5) << endl;
-  check(U.size(5) == 3);
-  cout << "size of the class of 6: " << U.size(6) << endl;
-  check(U.size(6) == 1);
-  cout << "size of the class of 2: " << U.size(2) << endl;
-  check(U.size(2) == 3);
+  cout << "Size of the class of 4: " << U.size(4) << endl;
+  check(U.size(4) == 3,"Test failed.");
+  cout << "Size of the class of 5: " << U.size(5) << endl;
+  check(U.size(5) == 3,"Test failed.");
+  cout << "Size of the class of 6: " << U.size(6) << endl;
+  check(U.size(6) == 1,"Test failed.");
+  cout << "Size of the class of 2: " << U.size(2) << endl;
+  check(U.size(2) == 3,"Test failed.");
 
-  cout << "Inserting 9 ..." << endl;
+  cout << "Insert 9 ..." << endl;
   U.insert(9);
-  print(U);
-  cout << "Inserting 10 to the component of 9 ..." << endl;
+//   print(U);
+  cout << "Insert 10 to the component of 9 ..." << endl;
   U.insert(10,9);
-  print(U);
+//   print(U);
 
-  cout << "Joining 8 and 10..." << endl;
-  check(U.join(8,10));
-  print(U);
+  cout << "Join 8 and 10..." << endl;
+  check(U.join(8,10),"Test failed.");
+//   print(U);
 
   cout << "Move 9 to the class of 4 ..." << endl;
-  check(U.move(9,4));
-  print(U);
+  check(U.move(9,4),"Test failed.");
+//   print(U);
 
   cout << "Move 9 to the class of 2 ..." << endl;
-  check(!U.move(9,2));
-  print(U);
+  check(!U.move(9,2),"Test failed.");
+//   print(U);
 
-  cout << "size of the class of 4: " << U.size(4) << endl;
-  check(U.size(4) == 4);
-  cout << "size of the class of 9: " << U.size(9) << endl;
-  check(U.size(9) == 4);
+  cout << "Size of the class of 4: " << U.size(4) << endl;
+  check(U.size(4) == 4,"Test failed.");
+  cout << "Size of the class of 9: " << U.size(9) << endl;
+  check(U.size(9) == 4,"Test failed.");
   
   cout << "Move 5 to the class of 6 ..." << endl;
-  check(U.move(5,6));
-  print(U);
+  check(U.move(5,6),"Test failed.");
+//   print(U);
 
-  cout << "size of the class of 5: " << U.size(5) << endl;
-  check(U.size(5) == 2);
-  cout << "size of the class of 8: " << U.size(8) << endl;
-  check(U.size(8) == 3);
+  cout << "Size of the class of 5: " << U.size(5) << endl;
+  check(U.size(5) == 2,"Test failed.");
+  cout << "Size of the class of 8: " << U.size(8) << endl;
+  check(U.size(8) == 3,"Test failed.");
 
   cout << "Move 7 to the class of 10 ..." << endl;
-  check(U.move(7,10));
-  print(U);
+  check(U.move(7,10),"Test failed.");
+//   print(U);
 
-  cout << "size of the class of 7: " << U.size(7) << endl;
-  check(U.size(7) == 4);
+  cout << "Size of the class of 7: " << U.size(7) << endl;
+  check(U.size(7) == 4,"Test failed.");
 
-  cout <<"erase 9: " << endl;
+  cout <<"Erase 9... " << endl;
   U.erase(9);
-  print(U);
+//   print(U);
 
-  cout <<"erase 1: " << endl;
+  cout <<"Erase 1... " << endl;
   U.erase(1);
-  print(U);
+//   print(U);
 
-  cout << "size of the class of 4: " << U.size(4) << endl;
-  check(U.size(4) == 2);
-  cout << "size of the class of 2: " << U.size(2) << endl;
-  check(U.size(2) == 2);
+  cout << "Size of the class of 4: " << U.size(4) << endl;
+  check(U.size(4) == 2,"Test failed.");
+  cout << "Size of the class of 2: " << U.size(2) << endl;
+  check(U.size(2) == 2,"Test failed.");
 
 
-  cout <<"erase 1: " << endl;
+  cout <<"Erase 1... " << endl;
   U.erase(1);
-  print(U);
+//   print(U);
 
-  cout <<"erase 6: " << endl;
+  cout <<"Erase 6... " << endl;
   U.erase(6);
-  print(U);
+//   print(U);
 
-  cout << "split the class of 8: " << endl;
+  cout << "Split the class of 8... " << endl;
   U.split(8);
-  print(U);
+//   print(U);
 
 
-  cout << "size of the class of 4: " << U.size(4) << endl;
-  check(U.size(4) == 2);
-  cout << "size of the class of 3: " << U.size(3) << endl;
-  check(U.size(3) == 1);
-  cout << "size of the class of 2: " << U.size(2) << endl;
-  check(U.size(2) == 2);
+  cout << "Size of the class of 4: " << U.size(4) << endl;
+  check(U.size(4) == 2,"Test failed.");
+  cout << "Size of the class of 3: " << U.size(3) << endl;
+  check(U.size(3) == 1,"Test failed.");
+  cout << "Size of the class of 2: " << U.size(2) << endl;
+  check(U.size(2) == 2,"Test failed.");
 
 
-  cout << "Joining 3 - 4 and 2 - 4 ..." << endl;
-  check(U.join(3,4));
-  check(!U.join(2,4));
-  print(U);
+  cout << "Join 3 - 4 and 2 - 4 ..." << endl;
+  check(U.join(3,4),"Test failed.");
+  check(!U.join(2,4),"Test failed.");
+//   print(U);
 
 
-  cout << "size of the class of 4: " << U.size(4) << endl;
-  check(U.size(4) == 3);
-  cout << "size of the class of 3: " << U.size(3) << endl;
-  check(U.size(3) == 3);
-  cout << "size of the class of 2: " << U.size(2) << endl;
-  check(U.size(2) == 3);
+  cout << "Size of the class of 4: " << U.size(4) << endl;
+  check(U.size(4) == 3,"Test failed.");
+  cout << "Size of the class of 3: " << U.size(3) << endl;
+  check(U.size(3) == 3,"Test failed.");
+  cout << "Size of the class of 2: " << U.size(2) << endl;
+  check(U.size(2) == 3,"Test failed.");
 
-  cout << "makeRep(4)" << endl;
+  cout << "makeRep(4)..." << endl;
   U.makeRep(4);
-  print(U);
-  cout << "makeRep(3)" << endl;
+//   print(U);
+  cout << "makeRep(3)..." << endl;
   U.makeRep(3);
-  print(U);
-  cout << "makeRep(2)" << endl;
+//   print(U);
+  cout << "makeRep(2)..." << endl;
   U.makeRep(2);
-  print(U);
+//   print(U);
 
-  cout << "size of the class of 4: " << U.size(4) << endl;
-  check(U.size(4) == 3);
-  cout << "size of the class of 3: " << U.size(3) << endl;
-  check(U.size(3) == 3);
-  cout << "size of the class of 2: " << U.size(2) << endl;
-  check(U.size(2) == 3);
+  cout << "Size of the class of 4: " << U.size(4) << endl;
+  check(U.size(4) == 3,"Test failed.");
+  cout << "Size of the class of 3: " << U.size(3) << endl;
+  check(U.size(3) == 3,"Test failed.");
+  cout << "Size of the class of 2: " << U.size(2) << endl;
+  check(U.size(2) == 3,"Test failed.");
 
 
   cout << "eraseClass 4 ..." << endl;
   U.eraseClass(4);
-  print(U);
+//   print(U);
 
   cout << "eraseClass 7 ..." << endl;
   U.eraseClass(7);
-  print(U);
+//   print(U);
 
-  cout << "done" << endl;
-
-  cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
-       << endl;
-
-  return passed ? 0 : 1;
+  cout << "done." << endl;
 }

src/test/xy_test.cc

@@ -8 +8 @@
 {
 
-  cout << "Testing classes xy and boundingbox." << endl;
+  cout << "Testing classes `xy' and `boundingbox'." << endl;
 
         typedef xy<int> XY;
@@ -34 +34 @@
         typedef BoundingBox<int> BB;
         BB doboz1;
-        check(doboz1.empty(), "empty? Should be.");
+        check(doboz1.empty(), "It should be empty.");
         
         doboz1 += a;
-        check(!doboz1.empty(), "empty? Should not be.");
+        check(!doboz1.empty(), "It should not be empty.");
         doboz1 += b;
 
@@ -47 +47 @@
 
         seged.x=2;seged.y=3;
-        check(doboz1.inside(seged),"Inside? It should be.");
+        check(doboz1.inside(seged),"It should be inside.");
 
         seged.x=1;seged.y=3;
-        check(doboz1.inside(seged),"Inside? It should be.");
+        check(doboz1.inside(seged),"It should be inside.");
 
         seged.x=0;seged.y=3;
-        check(!doboz1.inside(seged),"Inside? It should not be.");
+        check(!doboz1.inside(seged),"It should not be inside.");
 
         BB doboz2(seged);
         check(!doboz2.empty(),
-              "empty? Should not be. Constructed from 1 point.");
+              "It should not be empty. Constructed from 1 point.");
 
         doboz2 += doboz1;
         check(doboz2.inside(seged),
-              "Not inside? It should be. Incremented a box with an other.");
+              "It should be inside. Incremented a box with an other.");
 }