COIN-OR::LEMON - Graph Library

Changeset 2443:14abfa02bf42 in lemon-0.x


Ignore:
Timestamp:
05/11/07 18:02:53 (13 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

Location:
lemon
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • lemon/bfs.h

    r2438 r2443  
    516516
    517517    ///Processes the next node. And checks that at least one of
    518     ///reached node has true value in the \c nm nodemap. If one node
     518    ///reached node has true value in the \c nm node map. If one node
    519519    ///with true value is reachable from the processed node then the
    520     ///reached parameter will be set true. The reached parameter
    521     ///should be initially false.
    522     ///
    523     ///\param nm The nodemaps of possible targets.
    524     ///\retval reach Indicates that one of the target nodes is reached.
     520    ///rnode parameter will be set to the first of such nodes.
     521    ///
     522    ///\param nm The node map of possible targets.
     523    ///\retval rnode The reached target node.
    525524    ///\return The processed node.
    526525    ///
    527526    ///\warning The queue must not be empty!
    528527    template<class NM>
    529     Node processNextNode(const NM& nm, bool& reach)
     528    Node processNextNode(const NM& nm, Node& rnode)
    530529    {
    531530      if(_queue_tail==_queue_next_dist) {
     
    542541          _pred->set(m,e);
    543542          _dist->set(m,_curr_dist);
    544           reach = reach || nm[m];
     543          if (nm[m] && rnode == INVALID) rnode = m;
    545544        }
    546545      return n;
     
    567566   
    568567    ///Returns the number of the nodes to be processed in the queue.
    569     ///
    570568    int queueSize() { return _queue_head-_queue_tail; }
    571569   
     
    583581    ///- The shortest path tree.
    584582    ///- The distance of each node from the root(s).
    585     ///
    586583    void start()
    587584    {
     
    602599    ///- The shortest path to \c  dest.
    603600    ///- The distance of \c dest from the root(s).
    604     ///
    605601    void start(Node dest)
    606602    {
     
    617613    ///
    618614    ///\param nm must be a bool (or convertible) node map. The
    619     ///algorithm will stop when it reached a node \c v with
     615    ///algorithm will stop when it reaches a node \c v with
    620616    /// <tt>nm[v]</tt> true.
    621     ///\todo query the reached target
     617    ///
     618    ///\return The reached node \c v with <tt>nm[v]<\tt> true or
     619    ///\c INVALID if no such node was found.
    622620    template<class NM>
    623     void start(const NM &nm)
    624     {
    625       bool reach = false;
    626       while ( !emptyQueue() && !reach ) processNextNode(nm, reach);
     621    Node start(const NM &nm)
     622    {
     623      Node rnode = INVALID;
     624      while ( !emptyQueue() && rnode == INVALID ) {
     625        processNextNode(nm, rnode);
     626      }
     627      return rnode;
    627628    }
    628629   
     
    14341435    ///
    14351436    /// Processes the next node. And checks that at least one of
    1436     /// reached node has true value in the \c nm nodemap. If one node
     1437    /// reached node has true value in the \c nm node map. If one node
    14371438    /// with true value is reachable from the processed node then the
    1438     /// reached parameter will be set true. The reached parameter
    1439     /// should be initially false.
    1440     ///
    1441     /// \param nm The nodemaps of possible targets.
    1442     /// \retval reached Indicates that one of the target nodes is reached.
     1439    /// rnode parameter will be set to the first of such nodes.
     1440    ///
     1441    /// \param nm The node map of possible targets.
     1442    /// \retval rnode The reached target node.
    14431443    /// \return The processed node.
    14441444    ///
    14451445    /// \warning The queue must not be empty!
    14461446    template <typename NM>
    1447     Node processNextNode(const NM& nm, bool& reach) {
     1447    Node processNextNode(const NM& nm, Node& rnode) {
    14481448      Node n = _list[++_list_front];
    14491449      _visitor->process(n);
     
    14561456          _reached->set(m, true);
    14571457          _list[++_list_back] = m;
    1458           reach = reach || nm[m];
     1458          if (nm[m] && rnode == INVALID) rnode = m;
    14591459        } else {
    14601460          _visitor->examine(e);
     
    15151515    ///
    15161516    ///\param nm must be a bool (or convertible) node map. The
    1517     ///algorithm will stop when it reached a node \c v with
     1517    ///algorithm will stop when it reaches a node \c v with
    15181518    /// <tt>nm[v]</tt> true.
     1519    ///
     1520    ///\return The reached node \c v with <tt>nm[v]<\tt> true or
     1521    ///\c INVALID if no such node was found.
    15191522    template <typename NM>
    1520     void start(const NM &nm) {
    1521       bool reach = false;
    1522       while ( !emptyQueue() && !reach ) processNextNode(nm, reach);
     1523    Node start(const NM &nm) {
     1524      Node rnode = INVALID;
     1525      while ( !emptyQueue() && rnode == INVALID ) {
     1526        processNextNode(nm, rnode);
     1527      }
     1528      return rnode;
    15231529    }
    15241530
  • lemon/dfs.h

    r2439 r2443  
    565565    ///
    566566    ///\param em must be a bool (or convertible) edge map. The algorithm
    567     ///will stop when it reaches an edge \c e with <tt>em[e]==true<\tt>.
    568     ///
    569     ///\return The reached edge \c e with <tt>em[e]==true<\tt> or
     567    ///will stop when it reaches an edge \c e with <tt>em[e]<\tt> true.
     568    ///
     569    ///\return The reached edge \c e with <tt>em[e]<\tt> true or
    570570    ///\c INVALID if no such edge was found.
    571571    ///
     
    14591459    ///
    14601460    /// \param em must be a bool (or convertible) edge map. The algorithm
    1461     /// will stop when it reaches an edge \c e with <tt>em[e]==true<\tt>.
    1462     ///
    1463     ///\return The reached edge \c e with <tt>em[e]==true<\tt> or
     1461    /// will stop when it reaches an edge \c e with <tt>em[e]<\tt> true.
     1462    ///
     1463    ///\return The reached edge \c e with <tt>em[e]<\tt> true or
    14641464    ///\c INVALID if no such edge was found.
    14651465    ///
  • lemon/dijkstra.h

    r2439 r2443  
    664664    ///
    665665    ///\param nm must be a bool (or convertible) node map. The algorithm
    666     ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
    667     ///
    668     ///\return The reached node \c v with <tt>nm[v]==true<\tt> or
     666    ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
     667    ///
     668    ///\return The reached node \c v with <tt>nm[v]<\tt> true or
    669669    ///\c INVALID if no such node was found.
    670670    template<class NodeBoolMap>
Note: See TracChangeset for help on using the changeset viewer.