Changeset 2443:14abfa02bf42 in lemon-0.x for lemon/bfs.h

Timestamp:

05/11/07 18:02:53 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

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

Message:

Patch for retrieving reached/processed node in dijkstra, bfs and dfs

Patch from Peter Kovacs

File:

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

lemon/bfs.h

@@ -516 +516 @@
 
     ///Processes the next node. And checks that at least one of
-    ///reached node has true value in the \c nm nodemap. If one node
+    ///reached node has true value in the \c nm node map. 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 nm The nodemaps of possible targets.
-    ///\retval reach Indicates that one of the target nodes is reached.
+    ///rnode parameter will be set to the first of such nodes.
+    ///
+    ///\param nm The node map of possible targets.
+    ///\retval rnode The reached target node.
     ///\return The processed node.
     ///
     ///\warning The queue must not be empty!
     template<class NM>
-    Node processNextNode(const NM& nm, bool& reach)
+    Node processNextNode(const NM& nm, Node& rnode)
     {
       if(_queue_tail==_queue_next_dist) {
@@ -542 +541 @@
           _pred->set(m,e);
           _dist->set(m,_curr_dist);
-          reach = reach || nm[m];
+          if (nm[m] && rnode == INVALID) rnode = m;
         }
       return n;
@@ -567 +566 @@
     
     ///Returns the number of the nodes to be processed in the queue.
-    ///
     int queueSize() { return _queue_head-_queue_tail; }
     
@@ -583 +581 @@
     ///- The shortest path tree.
     ///- The distance of each node from the root(s).
-    ///
     void start()
     {
@@ -602 +599 @@
     ///- The shortest path to \c  dest.
     ///- The distance of \c dest from the root(s).
-    ///
     void start(Node dest)
     {
@@ -617 +613 @@
     ///
     ///\param nm must be a bool (or convertible) node map. The
-    ///algorithm will stop when it reached a node \c v with
+    ///algorithm will stop when it reaches a node \c v with
     /// <tt>nm[v]</tt> true.
-    ///\todo query the reached target
+    ///
+    ///\return The reached node \c v with <tt>nm[v]<\tt> true or
+    ///\c INVALID if no such node was found.
     template<class NM>
-    void start(const NM &nm)
-    {
-      bool reach = false;
-      while ( !emptyQueue() && !reach ) processNextNode(nm, reach);
+    Node start(const NM &nm)
+    {
+      Node rnode = INVALID;
+      while ( !emptyQueue() && rnode == INVALID ) {
+        processNextNode(nm, rnode);
+      }
+      return rnode;
     }
     
@@ -1434 +1435 @@
     ///
     /// Processes the next node. And checks that at least one of
-    /// reached node has true value in the \c nm nodemap. If one node
+    /// reached node has true value in the \c nm node map. 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 nm The nodemaps of possible targets.
-    /// \retval reached Indicates that one of the target nodes is reached.
+    /// rnode parameter will be set to the first of such nodes.
+    ///
+    /// \param nm The node map of possible targets.
+    /// \retval rnode The reached target node.
     /// \return The processed node.
     ///
     /// \warning The queue must not be empty!
     template <typename NM>
-    Node processNextNode(const NM& nm, bool& reach) {
+    Node processNextNode(const NM& nm, Node& rnode) {
       Node n = _list[++_list_front];
       _visitor->process(n);
@@ -1456 +1456 @@
           _reached->set(m, true);
           _list[++_list_back] = m;
-          reach = reach || nm[m];
+          if (nm[m] && rnode == INVALID) rnode = m;
         } else {
           _visitor->examine(e);
@@ -1515 +1515 @@
     ///
     ///\param nm must be a bool (or convertible) node map. The
-    ///algorithm will stop when it reached a node \c v with
+    ///algorithm will stop when it reaches a node \c v with
     /// <tt>nm[v]</tt> true.
+    ///
+    ///\return The reached node \c v with <tt>nm[v]<\tt> true or
+    ///\c INVALID if no such node was found.
     template <typename NM>
-    void start(const NM &nm) {
-      bool reach = false;
-      while ( !emptyQueue() && !reach ) processNextNode(nm, reach);
+    Node start(const NM &nm) {
+      Node rnode = INVALID;
+      while ( !emptyQueue() && rnode == INVALID ) {
+        processNextNode(nm, rnode);
+      }
+      return rnode;
     }