lemon-0.x: comparison lemon/bfs.h

equal deleted inserted replaced

-:2723ffb700f9
+:f53a43d50388
 }
 ///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
+///rnode parameter will be set to the first of such nodes.
-///should be initially false.
+///
-///
+///\param nm The node map of possible targets.
-///\param nm The nodemaps of possible targets.
+///\retval rnode The reached target node.
-///\retval reach 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& reach)
+Node processNextNode(const NM& nm, Node& rnode)
 {
 if(_queue_tail==_queue_next_dist) {
 	_curr_dist++;
 	_queue_next_dist=_queue_head;
 }
 	if(!(*_reached)[m=G->target(e)]) {
 	  _queue[_queue_head++]=m;
 	  _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;
 }
 ///Next node to be processed.
 ///to be processed in the queue
 bool emptyQueue() { return _queue_tail==_queue_head; }
 ///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.
 ///Executes the algorithm.
 ///in order to
 ///compute the
 ///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();
 }
 ///in order to
 ///compute the
 ///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;
 while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
 }
 ///
 ///\pre init() must be called and at least one node should be added
 ///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;
+Node rnode = INVALID;
-while ( !emptyQueue() && !reach ) processNextNode(nm, reach);
+while ( !emptyQueue() && rnode == INVALID ) {
+	processNextNode(nm, rnode);
+}
+return rnode;
 }
 ///Runs %BFS algorithm from node \c s.
 ///This method runs the %BFS algorithm from a root node \c s
 }
 /// \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
+/// rnode parameter will be set to the first of such nodes.
-/// should be initially false.
+///
-///
+/// \param nm The node map of possible targets.
-/// \param nm The nodemaps of possible targets.
+/// \retval rnode The reached target node.
-/// \retval reached Indicates that one of the target nodes is reached.
 /// \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;
 for (_graph->firstOut(e, n); e != INVALID; _graph->nextOut(e)) {
 Node m = _graph->target(e);
 if (!(*_reached)[m]) {
 _visitor->discover(e);
 _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);
 }
 }
 return n;
 ///
 /// \pre init() must be called and at least one node should be added
 /// 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) {
+Node start(const NM &nm) {
-bool reach = false;
+Node rnode = INVALID;
-while ( !emptyQueue() && !reach ) processNextNode(nm, reach);
+while ( !emptyQueue() && rnode == INVALID ) {
+	processNextNode(nm, rnode);
+}
+return rnode;
 }
 /// \brief Runs %BFSVisit algorithm from node \c s.
 ///
 /// This method runs the %BFS algorithm from a root node \c s.

changeset 2446	dd20d76eed13
parent 2438	718479989797
child 2476	059dcdda37c5