Changeset 2300:69330d717235 in lemon-0.x for lemon/bfs.h

Timestamp:

11/13/06 13:30:59 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Conditional execution until the target is reached
/previous implementation: until the target is the next to process/

todo: query the target when we give nodemap as condition

File:

• lemon/bfs.h (modified) (4 diffs)

lemon/bfs.h

@@ -479 +479 @@
       return n;
     }
+
+    ///Processes the next node.
+
+    ///Processes the next node. And checks that the given target node
+    ///is reached. If the target node is reachable from the processed
+    ///node then the reached parameter will be set true. The reached
+    ///parameter should be initially false.
+    ///
+    ///\param target The target node.
+    ///\retval reached Indicates that the target node is reached.
+    ///\return The processed node.
+    ///
+    ///\warning The queue must not be empty!
+    Node processNextNode(Node target, bool& reached)
+    {
+      if(_queue_tail==_queue_next_dist) {
+        _curr_dist++;
+        _queue_next_dist=_queue_head;
+      }
+      Node n=_queue[_queue_tail++];
+      _processed->set(n,true);
+      Node m;
+      for(OutEdgeIt e(*G,n);e!=INVALID;++e)
+        if(!(*_reached)[m=G->target(e)]) {
+          _queue[_queue_head++]=m;
+          _reached->set(m,true);
+          _pred->set(m,e);
+          _dist->set(m,_curr_dist);
+          reached = reached || (target == m);
+        }
+      return n;
+    }
+
+    ///Processes the next node.
+
+    ///Processes the next node. And checks that at least one of
+    ///reached node has true value in the \c nm nodemap. If one node
+    ///with true value is reachable from the processed node then the
+    ///reached parameter will be set true. The reached parameter
+    ///should be initially false.
+    ///
+    ///\param target The nodemaps of possible targets.
+    ///\retval reached Indicates that one of the target nodes is reached.
+    ///\return The processed node.
+    ///
+    ///\warning The queue must not be empty!
+    template<class NM>
+    Node processNextNode(const NM& nm, bool& reached)
+    {
+      if(_queue_tail==_queue_next_dist) {
+        _curr_dist++;
+        _queue_next_dist=_queue_head;
+      }
+      Node n=_queue[_queue_tail++];
+      _processed->set(n,true);
+      Node m;
+      for(OutEdgeIt e(*G,n);e!=INVALID;++e)
+        if(!(*_reached)[m=G->target(e)]) {
+          _queue[_queue_head++]=m;
+          _reached->set(m,true);
+          _pred->set(m,e);
+          _dist->set(m,_curr_dist);
+          reached = reached || nm[m];
+        }
+      return n;
+    }
       
     ///Next node to be processed.
@@ -538 +604 @@
     void start(Node dest)
     {
-      while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextNode();
+      bool reached = false;
+      while ( !emptyQueue() && !reached) processNextNode(dest, reached);
     }
     
@@ -550 +617 @@
     ///\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>.
+    ///\todo query the reached target
     template<class NM>
     void start(const NM &nm)
     {
-      while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextNode();
+      bool reached = false;
+      while ( !emptyQueue() && !reached) processNextNode(nm, reached);
     }
     
@@ -594 +663 @@
       addSource(s);
       start(t);
-      return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
+      return reached(t)? _curr_dist : 0;
     }