Changeset 2335:27aa03cd3121 in lemon-0.x for test

Timestamp:

01/08/07 11:39:59 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

New path concept and path structures

TODO: BellmanFord::negativeCycle()

Location:

test

Files:

• all_pairs_shortest_path_test.cc (modified) (3 diffs)
• bfs_test.cc (modified) (2 diffs)
• dfs_test.cc (modified) (2 diffs)
• dijkstra_test.cc (modified) (2 diffs)
• path_test.cc (modified) (1 diff)

test/all_pairs_shortest_path_test.cc

@@ -29 +29 @@
 
 #include <lemon/fib_heap.h>
+
+#include <lemon/path.h>
 
 #include <lemon/time_measure.h>
@@ -91 +93 @@
   }    
 
+  bool checked_path = false;
+
   for (NodeIt it(graph); it != INVALID; ++it) {
     for (NodeIt jt(graph); jt != INVALID; ++jt) {
@@ -98 +102 @@
             "Wrong connection in all pairs shortest path");
       if (johnson.connected(it, jt)) {
+        if (it != jt && !checked_path) {
+          {
+            Path<Graph> path = johnson.path(it, jt);
+            check(checkPath(graph, path), "Wrong path.");
+            check(pathSource(graph, path) == it, "Wrong path.");
+            check(pathTarget(graph, path) == jt, "Wrong path.");
+          }
+          {
+            Path<Graph> path = floyd.path(it, jt);
+            check(checkPath(graph, path), "Wrong path.");
+            check(pathSource(graph, path) == it, "Wrong path.");
+            check(pathTarget(graph, path) == jt, "Wrong path.");
+          }
+          checked_path = true;
+          std::cout << "Path checked" << std::endl;
+        }
         check(johnson.dist(it, jt) == floyd.dist(it, jt),
               "Wrong distance in all pairs shortest path");

test/bfs_test.cc

@@ -60 +60 @@
   b  = bfs_test.reached(n);
 
-  Path<Graph> pp(G);
-  bfs_test.getPath(pp,n);
+  Path<Graph> pp = bfs_test.path(n);
 }
 
@@ -110 +109 @@
   check(bfs_test.dist(t)==3,"Bfs found a wrong path. " << bfs_test.dist(t));
 
-  Path<Graph> p(G);
-  check(bfs_test.getPath(p,t),"getPath() failed to set the path.");
+  Path<Graph> p = bfs_test.path(t);
   check(p.length()==3,"getPath() found a wrong path.");
+  check(checkPath(G, p),"path() found a wrong path.");
+  check(pathSource(G, p) == s,"path() found a wrong path.");
+  check(pathTarget(G, p) == t,"path() found a wrong path.");
   
 

test/dfs_test.cc

@@ -60 +60 @@
   b  = dfs_test.reached(n);
 
-  Path<Graph> pp(G);
-  dfs_test.getPath(pp,n);
+  Path<Graph> pp = dfs_test.path(n);
 }
 
@@ -109 +108 @@
   dfs_test.run(s);  
   
-  Path<Graph> p(G);
-  check(dfs_test.getPath(p,t),"getPath() failed to set the path.");
-  check(p.length()==dfs_test.dist(t),"getPath() found a wrong path.");
+  Path<Graph> p = dfs_test.path(t);
+  check(p.length()==dfs_test.dist(t),"path() found a wrong path.");
+  check(checkPath(G, p),"path() found a wrong path.");
+  check(pathSource(G, p) == s,"path() found a wrong path.");
+  check(pathTarget(G, p) == t,"path() found a wrong path.");
   
   for(NodeIt v(G); v!=INVALID; ++v) {

test/dijkstra_test.cc

@@ -64 +64 @@
   b  = dijkstra_test.reached(n);
 
-  Path<Graph> pp(G);
-  dijkstra_test.getPath(pp,n);
+  Path<Graph> pp = dijkstra_test.path(n);
 }
 
@@ -121 +120 @@
 
 
-  Path<Graph> p(G);
-  check(dijkstra_test.getPath(p,t),"getPath() failed to set the path.");
+  Path<Graph> p = dijkstra_test.path(t);
   check(p.length()==4,"getPath() found a wrong path.");
+  check(checkPath(G, p),"path() found a wrong path.");
+  check(pathSource(G, p) == s,"path() found a wrong path.");
+  check(pathTarget(G, p) == t,"path() found a wrong path.");
   
 

test/path_test.cc

@@ -32 +32 @@
 
 void check_concepts() {
-  checkConcept<concepts::Path<concepts::Graph>, 
-    concepts::Path<concepts::Graph> >();
-  checkConcept<concepts::Path<concepts::Graph>, 
-    Path<concepts::Graph> >();
+  checkConcept<concepts::Path<ListGraph>, concepts::Path<ListGraph> >();
   checkConcept<concepts::Path<ListGraph>, Path<ListGraph> >();
+  checkConcept<concepts::Path<ListGraph>, SimplePath<ListGraph> >();
+  checkConcept<concepts::Path<ListGraph>, StaticPath<ListGraph> >();
+  checkConcept<concepts::Path<ListGraph>, ListPath<ListGraph> >();
 }
 
 int main() {
-  check_concepts();
-  
-  ListGraph g;
-  
-  ListGraph::Node n1 = g.addNode();
-  ListGraph::Node n2 = g.addNode();
-  ListGraph::Node n3 = g.addNode();
-  ListGraph::Node n4 = g.addNode();
-  ListGraph::Node n5 = g.addNode();
- 
-  ListGraph::Edge e1 = g.addEdge(n1, n2);
-  ListGraph::Edge e2 = g.addEdge(n2, n3);
-  ListGraph::Edge e3 = g.addEdge(n3, n4);
-  ListGraph::Edge e4 = g.addEdge(n4, n5);
-  ListGraph::Edge e5 = g.addEdge(n5, n1);
-
-  {
-    Path<ListGraph> p(g);
-
-    check(p.empty(), "Wrong Path");
-    check(p.length() == 0, "Wrong Path");
-    
-    {
-      Path<ListGraph>::Builder b(p);
-      b.setStartNode(n3);
-      b.commit();
-    }
-
-    check(!p.empty(), "Wrong Path");
-    check(p.length() == 0, "Wrong Path");
-    check(p.source() == n3, "Wrong Path");
-    check(p.target() == n3, "Wrong Path");
-
-    {
-      Path<ListGraph>::Builder b(p);
-      b.pushBack(e3);
-      b.pushBack(e4);
-      b.pushFront(e2);
-      b.commit();
-    }
-
-    check(!p.empty(), "Wrong Path");
-    check(p.length() == 3, "Wrong Path");
-    check(p.source() == n2, "Wrong Path");
-    check(p.target() == n5, "Wrong Path");
-    
-    {
-      Path<ListGraph>::NodeIt it(p);
-      check((ListGraph::Node)it == n2, "Wrong Path"); ++it;
-      check((ListGraph::Node)it == n3, "Wrong Path"); ++it;
-      check((ListGraph::Node)it == n4, "Wrong Path"); ++it;
-      check((ListGraph::Node)it == n5, "Wrong Path"); ++it;
-      check((ListGraph::Node)it == INVALID, "Wrong Path");
-    }
-
-    {
-      Path<ListGraph>::EdgeIt it(p);
-      check((ListGraph::Edge)it == e2, "Wrong Path"); ++it;
-      check((ListGraph::Edge)it == e3, "Wrong Path"); ++it;
-      check((ListGraph::Edge)it == e4, "Wrong Path"); ++it;
-      check((ListGraph::Edge)it == INVALID, "Wrong Path");
-    }
-    
-  }
-  
+  check_concepts();  
   return 0;
 }