# HG changeset patch
# User deba
# Date 1178899373 0
# Node ID 14abfa02bf4283aae53fd378a53388058da37110
# Parent  27b7c7de9cac83116530a942e83d593477597df6
Patch for retrieving reached/processed node in dijkstra, bfs and dfs

Patch from Peter Kovacs

diff -r 27b7c7de9cac -r 14abfa02bf42 lemon/bfs.h
--- a/lemon/bfs.h	Thu May 10 14:56:05 2007 +0000
+++ b/lemon/bfs.h	Fri May 11 16:02:53 2007 +0000
@@ -515,18 +515,17 @@
     ///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
+    ///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.
+    ///rnode parameter will be set to the first of such nodes.
     ///
-    ///\param nm The nodemaps of possible targets.
-    ///\retval reach Indicates that one of the target nodes is reached.
+    ///\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) {
 	_curr_dist++;
@@ -541,7 +540,7 @@
 	  _reached->set(m,true);
 	  _pred->set(m,e);
 	  _dist->set(m,_curr_dist);
-          reach = reach || nm[m];
+	  if (nm[m] && rnode == INVALID) rnode = m;
 	}
       return n;
     }
@@ -566,7 +565,6 @@
     ///Returns the number of the nodes to be processed.
     
     ///Returns the number of the nodes to be processed in the queue.
-    ///
     int queueSize() { return _queue_head-_queue_tail; }
     
     ///Executes the algorithm.
@@ -582,7 +580,6 @@
     ///shortest path to each node. The algorithm computes
     ///- The shortest path tree.
     ///- The distance of each node from the root(s).
-    ///
     void start()
     {
       while ( !emptyQueue() ) processNextNode();
@@ -601,7 +598,6 @@
     ///shortest path to \c dest. The algorithm computes
     ///- The shortest path to \c  dest.
     ///- The distance of \c dest from the root(s).
-    ///
     void start(Node dest)
     {
       bool reach = false;
@@ -616,14 +612,19 @@
     ///with addSource() before using this function.
     ///
     ///\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)
+    Node start(const NM &nm)
     {
-      bool reach = false;
-      while ( !emptyQueue() && !reach ) processNextNode(nm, reach);
+      Node rnode = INVALID;
+      while ( !emptyQueue() && rnode == INVALID ) {
+	processNextNode(nm, rnode);
+      }
+      return rnode;
     }
     
     ///Runs %BFS algorithm from node \c s.
@@ -1433,18 +1434,17 @@
     /// \brief 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
+    /// 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.
+    /// rnode parameter will be set to the first of such nodes.
     ///
-    /// \param nm The nodemaps of possible targets.
-    /// \retval reached Indicates that one of the target nodes is reached.
+    /// \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);
       Edge e;
@@ -1455,7 +1455,7 @@
           _visitor->reach(m);
           _reached->set(m, true);
           _list[++_list_back] = m;
-          reach = reach || nm[m];
+          if (nm[m] && rnode == INVALID) rnode = m;
         } else {
           _visitor->examine(e);
         }
@@ -1514,12 +1514,18 @@
     /// with addSource() before using this function.
     ///
     ///\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;
     }
 
     /// \brief Runs %BFSVisit algorithm from node \c s.
diff -r 27b7c7de9cac -r 14abfa02bf42 lemon/dfs.h
--- a/lemon/dfs.h	Thu May 10 14:56:05 2007 +0000
+++ b/lemon/dfs.h	Fri May 11 16:02:53 2007 +0000
@@ -564,9 +564,9 @@
     ///with addSource() before using this function.
     ///
     ///\param em must be a bool (or convertible) edge map. The algorithm
-    ///will stop when it reaches an edge \c e with <tt>em[e]==true<\tt>.
+    ///will stop when it reaches an edge \c e with <tt>em[e]<\tt> true.
     ///
-    ///\return The reached edge \c e with <tt>em[e]==true<\tt> or
+    ///\return The reached edge \c e with <tt>em[e]<\tt> true or
     ///\c INVALID if no such edge was found.
     ///
     ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an edge map,
@@ -1458,9 +1458,9 @@
     /// with addSource() before using this function.
     ///
     /// \param em must be a bool (or convertible) edge map. The algorithm
-    /// will stop when it reaches an edge \c e with <tt>em[e]==true<\tt>.
+    /// will stop when it reaches an edge \c e with <tt>em[e]<\tt> true.
     ///
-    ///\return The reached edge \c e with <tt>em[e]==true<\tt> or
+    ///\return The reached edge \c e with <tt>em[e]<\tt> true or
     ///\c INVALID if no such edge was found.
     ///
     /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an edge map,
diff -r 27b7c7de9cac -r 14abfa02bf42 lemon/dijkstra.h
--- a/lemon/dijkstra.h	Thu May 10 14:56:05 2007 +0000
+++ b/lemon/dijkstra.h	Fri May 11 16:02:53 2007 +0000
@@ -663,9 +663,9 @@
     ///with addSource() before using this function.
     ///
     ///\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>.
+    ///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]==true<\tt> or
+    ///\return The reached node \c v with <tt>nm[v]<\tt> true or
     ///\c INVALID if no such node was found.
     template<class NodeBoolMap>
     Node start(const NodeBoolMap &nm)