1.1 --- a/lemon/bfs.h	Thu Nov 09 00:50:07 2006 +0000
     1.2 +++ b/lemon/bfs.h	Mon Nov 13 12:30:59 2006 +0000
     1.3 @@ -478,6 +478,72 @@
     1.4  	}
     1.5        return n;
     1.6      }
     1.7 +
     1.8 +    ///Processes the next node.
     1.9 +
    1.10 +    ///Processes the next node. And checks that the given target node
    1.11 +    ///is reached. If the target node is reachable from the processed
    1.12 +    ///node then the reached parameter will be set true. The reached
    1.13 +    ///parameter should be initially false.
    1.14 +    ///
    1.15 +    ///\param target The target node.
    1.16 +    ///\retval reached Indicates that the target node is reached.
    1.17 +    ///\return The processed node.
    1.18 +    ///
    1.19 +    ///\warning The queue must not be empty!
    1.20 +    Node processNextNode(Node target, bool& reached)
    1.21 +    {
    1.22 +      if(_queue_tail==_queue_next_dist) {
    1.23 +	_curr_dist++;
    1.24 +	_queue_next_dist=_queue_head;
    1.25 +      }
    1.26 +      Node n=_queue[_queue_tail++];
    1.27 +      _processed->set(n,true);
    1.28 +      Node m;
    1.29 +      for(OutEdgeIt e(*G,n);e!=INVALID;++e)
    1.30 +	if(!(*_reached)[m=G->target(e)]) {
    1.31 +	  _queue[_queue_head++]=m;
    1.32 +	  _reached->set(m,true);
    1.33 +	  _pred->set(m,e);
    1.34 +	  _dist->set(m,_curr_dist);
    1.35 +          reached = reached || (target == m);
    1.36 +	}
    1.37 +      return n;
    1.38 +    }
    1.39 +
    1.40 +    ///Processes the next node.
    1.41 +
    1.42 +    ///Processes the next node. And checks that at least one of
    1.43 +    ///reached node has true value in the \c nm nodemap. If one node
    1.44 +    ///with true value is reachable from the processed node then the
    1.45 +    ///reached parameter will be set true. The reached parameter
    1.46 +    ///should be initially false.
    1.47 +    ///
    1.48 +    ///\param target The nodemaps of possible targets.
    1.49 +    ///\retval reached Indicates that one of the target nodes is reached.
    1.50 +    ///\return The processed node.
    1.51 +    ///
    1.52 +    ///\warning The queue must not be empty!
    1.53 +    template<class NM>
    1.54 +    Node processNextNode(const NM& nm, bool& reached)
    1.55 +    {
    1.56 +      if(_queue_tail==_queue_next_dist) {
    1.57 +	_curr_dist++;
    1.58 +	_queue_next_dist=_queue_head;
    1.59 +      }
    1.60 +      Node n=_queue[_queue_tail++];
    1.61 +      _processed->set(n,true);
    1.62 +      Node m;
    1.63 +      for(OutEdgeIt e(*G,n);e!=INVALID;++e)
    1.64 +	if(!(*_reached)[m=G->target(e)]) {
    1.65 +	  _queue[_queue_head++]=m;
    1.66 +	  _reached->set(m,true);
    1.67 +	  _pred->set(m,e);
    1.68 +	  _dist->set(m,_curr_dist);
    1.69 +          reached = reached || nm[m];
    1.70 +	}
    1.71 +      return n;
    1.72 +    }
    1.73        
    1.74      ///Next node to be processed.
    1.75  
    1.76 @@ -537,7 +603,8 @@
    1.77      ///
    1.78      void start(Node dest)
    1.79      {
    1.80 -      while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextNode();
    1.81 +      bool reached = false;
    1.82 +      while ( !emptyQueue() && !reached) processNextNode(dest, reached);
    1.83      }
    1.84      
    1.85      ///Executes the algorithm until a condition is met.
    1.86 @@ -549,10 +616,12 @@
    1.87      ///
    1.88      ///\param nm must be a bool (or convertible) node map. The algorithm
    1.89      ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
    1.90 +    ///\todo query the reached target
    1.91      template<class NM>
    1.92      void start(const NM &nm)
    1.93      {
    1.94 -      while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextNode();
    1.95 +      bool reached = false;
    1.96 +      while ( !emptyQueue() && !reached) processNextNode(nm, reached);
    1.97      }
    1.98      
    1.99      ///Runs %BFS algorithm from node \c s.
   1.100 @@ -593,7 +662,7 @@
   1.101        init();
   1.102        addSource(s);
   1.103        start(t);
   1.104 -      return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
   1.105 +      return reached(t)? _curr_dist : 0;
   1.106      }
   1.107      
   1.108      ///@}