COIN-OR::LEMON - Graph Library

Changeset 1130:47ef467ccf70 in lemon-0.x for src


Ignore:
Timestamp:
02/06/05 21:00:56 (15 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1529
Message:
  • PredNodeMap? is a NullMap? by default
  • Execution with stop condition
  • Find shortest path between two nodes
File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/alpar/dijkstra.h

    r1128 r1130  
    8686    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
    8787    ///
    88     typedef typename Graph::template NodeMap<typename GR::Node> PredNodeMap;
     88    typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
    8989    ///Instantiates a PredNodeMap.
    9090   
     
    9393    static PredNodeMap *createPredNodeMap(const GR &G)
    9494    {
    95       return new PredNodeMap(G);
     95      return new PredNodeMap();
    9696    }
    9797
     
    223223    bool local_pred;
    224224    ///Pointer to the map of predecessors nodes.
    225     PredNodeMap *pred_node;
    226     ///Indicates if \ref pred_node is locally allocated (\c true) or not.
    227     bool local_pred_node;
     225    PredNodeMap *_predNode;
     226    ///Indicates if \ref _predNode is locally allocated (\c true) or not.
     227    bool local_predNode;
    228228    ///Pointer to the map of distances.
    229     DistMap *distance;
    230     ///Indicates if \ref distance is locally allocated (\c true) or not.
    231     bool local_distance;
     229    DistMap *_dist;
     230    ///Indicates if \ref _dist is locally allocated (\c true) or not.
     231    bool local_dist;
    232232    ///Pointer to the map of reached status of the nodes.
    233233    ReachedMap *_reached;
     
    248248        _pred = Traits::createPredMap(*G);
    249249      }
    250       if(!pred_node) {
    251         local_pred_node = true;
    252         pred_node = Traits::createPredNodeMap(*G);
    253       }
    254       if(!distance) {
    255         local_distance = true;
    256         distance = Traits::createDistMap(*G);
     250      if(!_predNode) {
     251        local_predNode = true;
     252        _predNode = Traits::createPredNodeMap(*G);
     253      }
     254      if(!_dist) {
     255        local_dist = true;
     256        _dist = Traits::createDistMap(*G);
    257257      }
    258258      if(!_reached) {
     
    370370      G(&_G), length(&_length),
    371371      _pred(NULL), local_pred(false),
    372       pred_node(NULL), local_pred_node(false),
    373       distance(NULL), local_distance(false),
     372      _predNode(NULL), local_predNode(false),
     373      _dist(NULL), local_dist(false),
    374374      _reached(NULL), local_reached(false),
    375375      _heap_map(*G,-1),_heap(_heap_map)
     
    380380    {
    381381      if(local_pred) delete _pred;
    382       if(local_pred_node) delete pred_node;
    383       if(local_distance) delete distance;
     382      if(local_predNode) delete _predNode;
     383      if(local_dist) delete _dist;
    384384      if(local_reached) delete _reached;
    385385    }
     
    421421    Dijkstra &predNodeMap(PredNodeMap &m)
    422422    {
    423       if(local_pred_node) {
    424         delete pred_node;
    425         local_pred_node=false;
    426       }
    427       pred_node = &m;
     423      if(local_predNode) {
     424        delete _predNode;
     425        local_predNode=false;
     426      }
     427      _predNode = &m;
    428428      return *this;
    429429    }
     
    438438    Dijkstra &distMap(DistMap &m)
    439439    {
    440       if(local_distance) {
    441         delete distance;
    442         local_distance=false;
    443       }
    444       distance = &m;
     440      if(local_dist) {
     441        delete _dist;
     442        local_dist=false;
     443      }
     444      _dist = &m;
    445445      return *this;
    446446    }
    447447
     448  private:
     449    void finalizeNodeData(Node v,Value dst)
     450    {
     451      _reached->set(v,true);
     452      _dist->set(v, dst);
     453      _predNode->set(v,G->source((*_pred)[v]));
     454    }
     455
     456  public:
    448457    ///\name Excetution control
    449458    ///The simplest way to execute the algorithm is to use
     
    468477      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
    469478        _pred->set(u,INVALID);
    470         pred_node->set(u,INVALID);
     479        _predNode->set(u,INVALID);
    471480        ///\todo *_reached is not set to false.
    472481        _heap_map.set(u,Heap::PRE_HEAP);
     
    491500    {
    492501      Node v=_heap.top();
    493       _reached->set(v,true);
    494502      Value oldvalue=_heap[v];
    495503      _heap.pop();
    496       distance->set(v, oldvalue);
     504      finalizeNodeData(v,oldvalue);
    497505     
    498506      for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
     
    502510          _heap.push(w,oldvalue+(*length)[e]);
    503511          _pred->set(w,e);
    504           pred_node->set(w,v);
     512//        _predNode->set(w,v);
    505513          break;
    506514        case Heap::IN_HEAP:
     
    508516            _heap.decrease(w, oldvalue+(*length)[e]);
    509517            _pred->set(w,e);
    510             pred_node->set(w,v);
     518//          _predNode->set(w,v);
    511519          }
    512520          break;
     
    517525    }
    518526
    519     ///Starts the execution of the algorithm.
    520 
    521     ///Starts the execution of the algorithm.
    522     ///
    523     ///\pre init() must be called before and at least one node should be added
    524     ///with addSource().
     527    ///Executes the algorithm.
     528
     529    ///Executes the algorithm.
     530    ///
     531    ///\pre init() must be called and at least one node should be added
     532    ///with addSource() before using this function.
    525533    ///
    526534    ///This method runs the %Dijkstra algorithm from the root node(s)
     
    536544    }
    537545   
    538     ///Starts the execution of the algorithm until \c dest is reached.
    539 
    540     ///Starts the execution of the algorithm until \c dest is reached.
    541     ///
    542     ///\pre init() must be called before and at least one node should be added
    543     ///with addSource().
     546    ///Executes the algorithm until \c dest is reached.
     547
     548    ///Executes the algorithm until \c dest is reached.
     549    ///
     550    ///\pre init() must be called and at least one node should be added
     551    ///with addSource() before using this function.
    544552    ///
    545553    ///This method runs the %Dijkstra algorithm from the root node(s)
     
    552560    void start(Node dest)
    553561    {
    554       while ( !_heap.empty() && _heap.top()!=dest) processNode();
     562      while ( !_heap.empty() && _heap.top()!=dest ) processNode();
     563      if ( _heap.top()==dest ) finalizeNodeData(_heap.top());
     564    }
     565   
     566    ///Executes the algorithm until a condition is met.
     567
     568    ///Executes the algorithm until a condition is met.
     569    ///
     570    ///\pre init() must be called and at least one node should be added
     571    ///with addSource() before using this function.
     572    ///
     573    ///\param nm must be a bool (or convertible) node map. The algorithm
     574    ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
     575    template<class NM>
     576    void start(const NM &nm)
     577    {
     578      while ( !_heap.empty() && !mn[_heap.top()] ) processNode();
     579      if ( !_heap.empty() ) finalizeNodeData(_heap.top());
    555580    }
    556581   
     
    576601    }
    577602   
     603    ///Finds the shortest path between \c s and \c t.
     604   
     605    ///Finds the shortest path between \c s and \c t.
     606    ///
     607    ///\return The length of the shortest s---t path if there exists one,
     608    ///0 otherwise.
     609    ///\note Apart from the return value, d.run(s) is
     610    ///just a shortcut of the following code.
     611    ///\code
     612    ///  d.init();
     613    ///  d.addSource(s);
     614    ///  d.start(t);
     615    ///\endcode
     616    Value run(Node s,Node t) {
     617      init();
     618      addSource(s);
     619      start(t);
     620      return (*_pred)[t]==INVALID?0:(*_dist)[t];
     621    }
     622   
    578623    ///@}
    579624
     
    592637    ///\warning If node \c v in unreachable from the root the return value
    593638    ///of this funcion is undefined.
    594     Value dist(Node v) const { return (*distance)[v]; }
     639    Value dist(Node v) const { return (*_dist)[v]; }
    595640
    596641    ///Returns the 'previous edge' of the shortest path tree.
     
    614659    ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
    615660    ///using this function.
    616     Node predNode(Node v) const { return (*pred_node)[v]; }
     661    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
     662                                  G->source((*_pred)[v]); }
    617663   
    618664    ///Returns a reference to the NodeMap of distances.
     
    620666    ///Returns a reference to the NodeMap of distances. \pre \ref run() must
    621667    ///be called before using this function.
    622     const DistMap &distMap() const { return *distance;}
     668    const DistMap &distMap() const { return *_dist;}
    623669 
    624670    ///Returns a reference to the shortest path tree map.
     
    634680    ///shortest path tree.
    635681    ///\pre \ref run() must be called before using this function.
    636     const PredNodeMap &predNodeMap() const { return *pred_node;}
     682    const PredNodeMap &predNodeMap() const { return *_predNode;}
    637683
    638684    ///Checks if a node is reachable from the root.
Note: See TracChangeset for help on using the changeset viewer.