523 Edge e=_stack[_stack_head]; |
523 Edge e=_stack[_stack_head]; |
524 if(!(*_reached)[m=G->target(e)]) { |
524 if(!(*_reached)[m=G->target(e)]) { |
525 _pred->set(m,e); |
525 _pred->set(m,e); |
526 _reached->set(m,true); |
526 _reached->set(m,true); |
527 // _pred_node->set(m,G->source(e)); |
527 // _pred_node->set(m,G->source(e)); |
528 _stack[++_stack_head] = OutEdgeIt(*G, m); |
528 ++_stack_head; |
|
529 _stack[_stack_head] = OutEdgeIt(*G, m); |
529 _dist->set(m,_stack_head); |
530 _dist->set(m,_stack_head); |
530 } |
531 } |
531 else { |
532 else { |
532 Node n; |
533 Node n; |
533 while(_stack_head>=0 && |
534 while(_stack_head>=0 && |
585 ///- The %DFS path to \c dest. |
586 ///- The %DFS path to \c dest. |
586 ///- The distance of \c dest from the root(s). |
587 ///- The distance of \c dest from the root(s). |
587 /// |
588 /// |
588 void start(Node dest) |
589 void start(Node dest) |
589 { |
590 { |
590 while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextEdge(); |
591 while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest ) |
|
592 processNextEdge(); |
591 } |
593 } |
592 |
594 |
593 ///Executes the algorithm until a condition is met. |
595 ///Executes the algorithm until a condition is met. |
594 |
596 |
595 ///Executes the algorithm until a condition is met. |
597 ///Executes the algorithm until a condition is met. |
596 /// |
598 /// |
597 ///\pre init() must be called and at least one node should be added |
599 ///\pre init() must be called and at least one node should be added |
598 ///with addSource() before using this function. |
600 ///with addSource() before using this function. |
599 /// |
601 /// |
600 ///\param nm must be a bool (or convertible) node map. The algorithm |
602 ///\param nm must be a bool (or convertible) edge map. The algorithm |
601 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>. |
603 ///will stop when it reaches a edge \c v with <tt>nm[v]==true</tt>. |
|
604 ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c mn is an edge map, |
|
605 ///not a node map. |
602 template<class NM> |
606 template<class NM> |
603 void start(const NM &nm) |
607 void start(const NM &nm) |
604 { |
608 { |
605 while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextEdge(); |
609 while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge(); |
606 } |
610 } |
607 |
611 |
608 ///Runs %DFS algorithm from node \c s. |
612 ///Runs %DFS algorithm from node \c s. |
609 |
613 |
610 ///This method runs the %DFS algorithm from a root node \c s |
614 ///This method runs the %DFS algorithm from a root node \c s |