Several serious bugs fixed
authoralpar
Mon, 21 Mar 2005 11:40:08 +0000
changeset 1233f3d856bf1ebf
parent 1232 43fc017da4f8
child 1234 49d018060749
Several serious bugs fixed
src/lemon/dfs.h
src/test/dfs_test.cc
     1.1 --- a/src/lemon/dfs.h	Mon Mar 21 11:08:17 2005 +0000
     1.2 +++ b/src/lemon/dfs.h	Mon Mar 21 11:40:08 2005 +0000
     1.3 @@ -525,7 +525,8 @@
     1.4  	_pred->set(m,e);
     1.5  	_reached->set(m,true);
     1.6  	//	  _pred_node->set(m,G->source(e));
     1.7 -	_stack[++_stack_head] = OutEdgeIt(*G, m);
     1.8 +	++_stack_head;
     1.9 +	_stack[_stack_head] = OutEdgeIt(*G, m);
    1.10  	_dist->set(m,_stack_head);
    1.11        }
    1.12        else {
    1.13 @@ -587,7 +588,8 @@
    1.14      ///
    1.15      void start(Node dest)
    1.16      {
    1.17 -      while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextEdge();
    1.18 +      while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest ) 
    1.19 +	processNextEdge();
    1.20      }
    1.21      
    1.22      ///Executes the algorithm until a condition is met.
    1.23 @@ -597,12 +599,14 @@
    1.24      ///\pre init() must be called and at least one node should be added
    1.25      ///with addSource() before using this function.
    1.26      ///
    1.27 -    ///\param nm must be a bool (or convertible) node map. The algorithm
    1.28 -    ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
    1.29 +    ///\param nm must be a bool (or convertible) edge map. The algorithm
    1.30 +    ///will stop when it reaches a edge \c v with <tt>nm[v]==true</tt>.
    1.31 +    ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c mn is an edge map,
    1.32 +    ///not a node map.
    1.33      template<class NM>
    1.34        void start(const NM &nm)
    1.35        {
    1.36 -	while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextEdge();
    1.37 +	while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge();
    1.38        }
    1.39      
    1.40      ///Runs %DFS algorithm from node \c s.
    1.41 @@ -643,7 +647,7 @@
    1.42        init();
    1.43        addSource(s);
    1.44        start(t);
    1.45 -      return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
    1.46 +      return reached(t)?_stack_head+1:0;
    1.47      }
    1.48      
    1.49      ///@}
     2.1 --- a/src/test/dfs_test.cc	Mon Mar 21 11:08:17 2005 +0000
     2.2 +++ b/src/test/dfs_test.cc	Mon Mar 21 11:40:08 2005 +0000
     2.3 @@ -109,7 +109,8 @@
     2.4        Node u=G.source(e);
     2.5        check(u==dfs_test.predNode(v),"Wrong tree.");
     2.6        check(dfs_test.dist(v) - dfs_test.dist(u) == 1,
     2.7 -	    "Wrong distance." << dfs_test.dist(v) << " " <<dfs_test.dist(u) );
     2.8 +	    "Wrong distance. (" << dfs_test.dist(u) << "->" 
     2.9 +	    <<dfs_test.dist(v) << ')');
    2.10      }
    2.11    }
    2.12  }