1.1 --- a/lemon/bfs.h Thu May 10 14:56:05 2007 +0000
1.2 +++ b/lemon/bfs.h Fri May 11 16:02:53 2007 +0000
1.3 @@ -515,18 +515,17 @@
1.4 ///Processes the next node.
1.5
1.6 ///Processes the next node. And checks that at least one of
1.7 - ///reached node has true value in the \c nm nodemap. If one node
1.8 + ///reached node has true value in the \c nm node map. If one node
1.9 ///with true value is reachable from the processed node then the
1.10 - ///reached parameter will be set true. The reached parameter
1.11 - ///should be initially false.
1.12 + ///rnode parameter will be set to the first of such nodes.
1.13 ///
1.14 - ///\param nm The nodemaps of possible targets.
1.15 - ///\retval reach Indicates that one of the target nodes is reached.
1.16 + ///\param nm The node map of possible targets.
1.17 + ///\retval rnode The reached target node.
1.18 ///\return The processed node.
1.19 ///
1.20 ///\warning The queue must not be empty!
1.21 template<class NM>
1.22 - Node processNextNode(const NM& nm, bool& reach)
1.23 + Node processNextNode(const NM& nm, Node& rnode)
1.24 {
1.25 if(_queue_tail==_queue_next_dist) {
1.26 _curr_dist++;
1.27 @@ -541,7 +540,7 @@
1.28 _reached->set(m,true);
1.29 _pred->set(m,e);
1.30 _dist->set(m,_curr_dist);
1.31 - reach = reach || nm[m];
1.32 + if (nm[m] && rnode == INVALID) rnode = m;
1.33 }
1.34 return n;
1.35 }
1.36 @@ -566,7 +565,6 @@
1.37 ///Returns the number of the nodes to be processed.
1.38
1.39 ///Returns the number of the nodes to be processed in the queue.
1.40 - ///
1.41 int queueSize() { return _queue_head-_queue_tail; }
1.42
1.43 ///Executes the algorithm.
1.44 @@ -582,7 +580,6 @@
1.45 ///shortest path to each node. The algorithm computes
1.46 ///- The shortest path tree.
1.47 ///- The distance of each node from the root(s).
1.48 - ///
1.49 void start()
1.50 {
1.51 while ( !emptyQueue() ) processNextNode();
1.52 @@ -601,7 +598,6 @@
1.53 ///shortest path to \c dest. The algorithm computes
1.54 ///- The shortest path to \c dest.
1.55 ///- The distance of \c dest from the root(s).
1.56 - ///
1.57 void start(Node dest)
1.58 {
1.59 bool reach = false;
1.60 @@ -616,14 +612,19 @@
1.61 ///with addSource() before using this function.
1.62 ///
1.63 ///\param nm must be a bool (or convertible) node map. The
1.64 - ///algorithm will stop when it reached a node \c v with
1.65 + ///algorithm will stop when it reaches a node \c v with
1.66 /// <tt>nm[v]</tt> true.
1.67 - ///\todo query the reached target
1.68 + ///
1.69 + ///\return The reached node \c v with <tt>nm[v]<\tt> true or
1.70 + ///\c INVALID if no such node was found.
1.71 template<class NM>
1.72 - void start(const NM &nm)
1.73 + Node start(const NM &nm)
1.74 {
1.75 - bool reach = false;
1.76 - while ( !emptyQueue() && !reach ) processNextNode(nm, reach);
1.77 + Node rnode = INVALID;
1.78 + while ( !emptyQueue() && rnode == INVALID ) {
1.79 + processNextNode(nm, rnode);
1.80 + }
1.81 + return rnode;
1.82 }
1.83
1.84 ///Runs %BFS algorithm from node \c s.
1.85 @@ -1433,18 +1434,17 @@
1.86 /// \brief Processes the next node.
1.87 ///
1.88 /// Processes the next node. And checks that at least one of
1.89 - /// reached node has true value in the \c nm nodemap. If one node
1.90 + /// reached node has true value in the \c nm node map. If one node
1.91 /// with true value is reachable from the processed node then the
1.92 - /// reached parameter will be set true. The reached parameter
1.93 - /// should be initially false.
1.94 + /// rnode parameter will be set to the first of such nodes.
1.95 ///
1.96 - /// \param nm The nodemaps of possible targets.
1.97 - /// \retval reached Indicates that one of the target nodes is reached.
1.98 + /// \param nm The node map of possible targets.
1.99 + /// \retval rnode The reached target node.
1.100 /// \return The processed node.
1.101 ///
1.102 /// \warning The queue must not be empty!
1.103 template <typename NM>
1.104 - Node processNextNode(const NM& nm, bool& reach) {
1.105 + Node processNextNode(const NM& nm, Node& rnode) {
1.106 Node n = _list[++_list_front];
1.107 _visitor->process(n);
1.108 Edge e;
1.109 @@ -1455,7 +1455,7 @@
1.110 _visitor->reach(m);
1.111 _reached->set(m, true);
1.112 _list[++_list_back] = m;
1.113 - reach = reach || nm[m];
1.114 + if (nm[m] && rnode == INVALID) rnode = m;
1.115 } else {
1.116 _visitor->examine(e);
1.117 }
1.118 @@ -1514,12 +1514,18 @@
1.119 /// with addSource() before using this function.
1.120 ///
1.121 ///\param nm must be a bool (or convertible) node map. The
1.122 - ///algorithm will stop when it reached a node \c v with
1.123 + ///algorithm will stop when it reaches a node \c v with
1.124 /// <tt>nm[v]</tt> true.
1.125 + ///
1.126 + ///\return The reached node \c v with <tt>nm[v]<\tt> true or
1.127 + ///\c INVALID if no such node was found.
1.128 template <typename NM>
1.129 - void start(const NM &nm) {
1.130 - bool reach = false;
1.131 - while ( !emptyQueue() && !reach ) processNextNode(nm, reach);
1.132 + Node start(const NM &nm) {
1.133 + Node rnode = INVALID;
1.134 + while ( !emptyQueue() && rnode == INVALID ) {
1.135 + processNextNode(nm, rnode);
1.136 + }
1.137 + return rnode;
1.138 }
1.139
1.140 /// \brief Runs %BFSVisit algorithm from node \c s.
2.1 --- a/lemon/dfs.h Thu May 10 14:56:05 2007 +0000
2.2 +++ b/lemon/dfs.h Fri May 11 16:02:53 2007 +0000
2.3 @@ -564,9 +564,9 @@
2.4 ///with addSource() before using this function.
2.5 ///
2.6 ///\param em must be a bool (or convertible) edge map. The algorithm
2.7 - ///will stop when it reaches an edge \c e with <tt>em[e]==true<\tt>.
2.8 + ///will stop when it reaches an edge \c e with <tt>em[e]<\tt> true.
2.9 ///
2.10 - ///\return The reached edge \c e with <tt>em[e]==true<\tt> or
2.11 + ///\return The reached edge \c e with <tt>em[e]<\tt> true or
2.12 ///\c INVALID if no such edge was found.
2.13 ///
2.14 ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an edge map,
2.15 @@ -1458,9 +1458,9 @@
2.16 /// with addSource() before using this function.
2.17 ///
2.18 /// \param em must be a bool (or convertible) edge map. The algorithm
2.19 - /// will stop when it reaches an edge \c e with <tt>em[e]==true<\tt>.
2.20 + /// will stop when it reaches an edge \c e with <tt>em[e]<\tt> true.
2.21 ///
2.22 - ///\return The reached edge \c e with <tt>em[e]==true<\tt> or
2.23 + ///\return The reached edge \c e with <tt>em[e]<\tt> true or
2.24 ///\c INVALID if no such edge was found.
2.25 ///
2.26 /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an edge map,
3.1 --- a/lemon/dijkstra.h Thu May 10 14:56:05 2007 +0000
3.2 +++ b/lemon/dijkstra.h Fri May 11 16:02:53 2007 +0000
3.3 @@ -663,9 +663,9 @@
3.4 ///with addSource() before using this function.
3.5 ///
3.6 ///\param nm must be a bool (or convertible) node map. The algorithm
3.7 - ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
3.8 + ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
3.9 ///
3.10 - ///\return The reached node \c v with <tt>nm[v]==true<\tt> or
3.11 + ///\return The reached node \c v with <tt>nm[v]<\tt> true or
3.12 ///\c INVALID if no such node was found.
3.13 template<class NodeBoolMap>
3.14 Node start(const NodeBoolMap &nm)