Changeset 1233:f3d856bf1ebf in lemon-0.x

Timestamp:

03/21/05 12:40:08 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

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

Message:

Several serious bugs fixed

Location:

src

Files:

• lemon/dfs.h (modified) (4 diffs)
• test/dfs_test.cc (modified) (1 diff)

src/lemon/dfs.h

@@ -526 +526 @@
         _reached->set(m,true);
         //        _pred_node->set(m,G->source(e));
-        _stack[++_stack_head] = OutEdgeIt(*G, m);
+        ++_stack_head;
+        _stack[_stack_head] = OutEdgeIt(*G, m);
         _dist->set(m,_stack_head);
       }
@@ -588 +589 @@
     void start(Node dest)
     {
-      while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextEdge();
+      while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest ) 
+        processNextEdge();
     }
     
@@ -598 +600 @@
     ///with addSource() before using this function.
     ///
-    ///\param nm must be a bool (or convertible) node map. The algorithm
-    ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
+    ///\param nm must be a bool (or convertible) edge map. The algorithm
+    ///will stop when it reaches a edge \c v with <tt>nm[v]==true</tt>.
+    ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c mn is an edge map,
+    ///not a node map.
     template<class NM>
       void start(const NM &nm)
       {
-        while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextEdge();
+        while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge();
       }
     
@@ -644 +648 @@
       addSource(s);
       start(t);
-      return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
+      return reached(t)?_stack_head+1:0;
     }
     

src/test/dfs_test.cc

@@ -110 +110 @@
       check(u==dfs_test.predNode(v),"Wrong tree.");
       check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
-            "Wrong distance." << dfs_test.dist(v) << " " <<dfs_test.dist(u) );
+            "Wrong distance. (" << dfs_test.dist(u) << "->" 
+            <<dfs_test.dist(v) << ')');
     }
   }