COIN-OR::LEMON - Graph Library

Changeset 2300:69330d717235 in lemon-0.x


Ignore:
Timestamp:
11/13/06 13:30:59 (14 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3073
Message:

Conditional execution until the target is reached
/previous implementation: until the target is the next to process/

todo: query the target when we give nodemap as condition

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bfs.h

    r2260 r2300  
    479479      return n;
    480480    }
     481
     482    ///Processes the next node.
     483
     484    ///Processes the next node. And checks that the given target node
     485    ///is reached. If the target node is reachable from the processed
     486    ///node then the reached parameter will be set true. The reached
     487    ///parameter should be initially false.
     488    ///
     489    ///\param target The target node.
     490    ///\retval reached Indicates that the target node is reached.
     491    ///\return The processed node.
     492    ///
     493    ///\warning The queue must not be empty!
     494    Node processNextNode(Node target, bool& reached)
     495    {
     496      if(_queue_tail==_queue_next_dist) {
     497        _curr_dist++;
     498        _queue_next_dist=_queue_head;
     499      }
     500      Node n=_queue[_queue_tail++];
     501      _processed->set(n,true);
     502      Node m;
     503      for(OutEdgeIt e(*G,n);e!=INVALID;++e)
     504        if(!(*_reached)[m=G->target(e)]) {
     505          _queue[_queue_head++]=m;
     506          _reached->set(m,true);
     507          _pred->set(m,e);
     508          _dist->set(m,_curr_dist);
     509          reached = reached || (target == m);
     510        }
     511      return n;
     512    }
     513
     514    ///Processes the next node.
     515
     516    ///Processes the next node. And checks that at least one of
     517    ///reached node has true value in the \c nm nodemap. If one node
     518    ///with true value is reachable from the processed node then the
     519    ///reached parameter will be set true. The reached parameter
     520    ///should be initially false.
     521    ///
     522    ///\param target The nodemaps of possible targets.
     523    ///\retval reached Indicates that one of the target nodes is reached.
     524    ///\return The processed node.
     525    ///
     526    ///\warning The queue must not be empty!
     527    template<class NM>
     528    Node processNextNode(const NM& nm, bool& reached)
     529    {
     530      if(_queue_tail==_queue_next_dist) {
     531        _curr_dist++;
     532        _queue_next_dist=_queue_head;
     533      }
     534      Node n=_queue[_queue_tail++];
     535      _processed->set(n,true);
     536      Node m;
     537      for(OutEdgeIt e(*G,n);e!=INVALID;++e)
     538        if(!(*_reached)[m=G->target(e)]) {
     539          _queue[_queue_head++]=m;
     540          _reached->set(m,true);
     541          _pred->set(m,e);
     542          _dist->set(m,_curr_dist);
     543          reached = reached || nm[m];
     544        }
     545      return n;
     546    }
    481547     
    482548    ///Next node to be processed.
     
    538604    void start(Node dest)
    539605    {
    540       while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextNode();
     606      bool reached = false;
     607      while ( !emptyQueue() && !reached) processNextNode(dest, reached);
    541608    }
    542609   
     
    550617    ///\param nm must be a bool (or convertible) node map. The algorithm
    551618    ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
     619    ///\todo query the reached target
    552620    template<class NM>
    553621    void start(const NM &nm)
    554622    {
    555       while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextNode();
     623      bool reached = false;
     624      while ( !emptyQueue() && !reached) processNextNode(nm, reached);
    556625    }
    557626   
     
    594663      addSource(s);
    595664      start(t);
    596       return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
     665      return reached(t)? _curr_dist : 0;
    597666    }
    598667   
Note: See TracChangeset for help on using the changeset viewer.