Changeset 780:e06d0d16595f in lemon-0.x for src

Timestamp:

09/01/04 17:08:41 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

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

Message:

• DFS class (bfs.h and bfs_test.cc) added
• Bugfixes in Dijkstra and Bfs

Location:

src

Files:

• hugo/bfs.h (modified) (1 diff)
• hugo/dfs.h (added)
• hugo/dijkstra.h (modified) (2 diffs)
• test/Makefile.am (modified) (2 diffs)
• test/bfs_test.cc (modified) (1 diff)
• test/dfs_test.cc (added)
• test/dijkstra_test.cc (modified) (1 diff)

src/hugo/bfs.h

@@ -281 +281 @@
     ///\pre \ref run() must be called before using this function.
     ///
-    bool reached(Node v) { return v==source || (*predecessor)[v]==INVALID; }
+    bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
     
   };

src/hugo/dijkstra.h

@@ -280 +280 @@
     ///\ref predNode(Node v).  \pre \ref run() must be called before using
     ///this function.
+    ///\todo predEdge could be a better name.
     Edge pred(Node v) const { return (*predecessor)[v]; }
 
@@ -318 +319 @@
     ///\pre \ref run() must be called before using this function.
     ///
-    bool reached(Node v) { return v==source || (*predecessor)[v]==INVALID; }
+    bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
     
   };

src/test/Makefile.am

@@ -3 +3 @@
 noinst_HEADERS = test_tools.h
 
-check_PROGRAMS = graph_test dijkstra_test bfs_test time_measure_test \
+check_PROGRAMS = graph_test dijkstra_test bfs_test dfs_test time_measure_test \
         error_test xy_test \
         unionfind_test test_tools_pass test_tools_fail
@@ -13 +13 @@
 dijkstra_test_SOURCES = dijkstra_test.cc
 bfs_test_SOURCES = bfs_test.cc
+dfs_test_SOURCES = dfs_test.cc
 unionfind_test_SOURCES = unionfind_test.cc
 time_measure_test_SOURCES = time_measure_test.cc

src/test/bfs_test.cc

@@ -77 +77 @@
   }
 
-  ///\bug This works only for integer lengths
-  for(NodeIt v(G); v==INVALID; ++v)
-    if ( bfs_test.reached(v) ) {
+  for(NodeIt v(G); v==INVALID; ++v) {
+    check(bfs_test.reached(v),"Each node should be reached.");
+    if ( bfs_test.pred(v)!=INVALID ) {
       Edge e=bfs_test.pred(v);
       Node u=G.tail(e);
+      check(u==bfs_test.predNode(v),"Wrong tree.");
       check(bfs_test.dist(v) - bfs_test.dist(u) == 1,
-            "Bad shortest path tree edge! Difference: " 
+            "Wrong distance. Difference: " 
             << std::abs(bfs_test.dist(v) - bfs_test.dist(u) 
                         - 1));
     }
+  }
 }
+

src/test/dijkstra_test.cc

@@ -87 +87 @@
 
   ///\bug This works only for integer lengths
-  for(NodeIt v(G); v!=INVALID; ++v)
-    if ( dijkstra_test.reached(v) ) {
+  for(NodeIt v(G); v!=INVALID; ++v){
+    check(dijkstra_test.reached(v),"Each node should be reached.");
+    if ( dijkstra_test.pred(v)!=INVALID ) {
       Edge e=dijkstra_test.pred(v);
       Node u=G.tail(e);
+      check(u==dijkstra_test.predNode(v),"Wrong tree.");
       check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == cap[e],
-            "Bad shortest path tree edge! Difference: " 
+            "Wrong distance! Difference: " 
             << std::abs(dijkstra_test.dist(v) - dijkstra_test.dist(u) 
                             - cap[e]));
     }
+  }
 }
+