COIN-OR::LEMON - Graph Library

Changeset 1128:6a347310d4c2 in lemon-0.x


Ignore:
Timestamp:
02/06/05 15:44:41 (15 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1527
Message:

Several important changes:

  • Named parameters for setting ReachedMap?
  • run() is separated into initialization and processing phase
  • It is possible to run Dijkstra from multiple sources
  • It is possible to stop the execution when a destination is reached.
File:
1 edited

Legend:

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

    r1126 r1128  
    159159  ///
    160160  ///\author Jacint Szabo and Alpar Juttner
    161   ///\todo We need a typedef-names should be standardized. (-:
     161  ///\todo A compare object would be nice.
    162162
    163163#ifdef DOXYGEN
     
    238238    Node source;
    239239
    240     ///Initializes the maps.
     240    ///Creates the maps if necessary.
    241241   
    242242    ///\todo Error if \c G or are \c NULL. What about \c length?
    243243    ///\todo Better memory allocation (instead of new).
    244     void init_maps()
     244    void create_maps()
    245245    {
    246246      if(!_pred) {
     
    264264  public :
    265265 
     266    ///\name Named template parameters
     267
     268    ///@{
     269
    266270    template <class T>
    267271    struct DefPredMapTraits : public Traits {
    268272      typedef T PredMap;
    269       ///\todo An exception should be thrown.
    270       ///
    271273      static PredMap *createPredMap(const Graph &G)
    272274      {
     
    286288    struct DefPredNodeMapTraits : public Traits {
    287289      typedef T PredNodeMap;
    288       ///\todo An exception should be thrown.
    289       ///
    290290      static PredNodeMap *createPredNodeMap(const Graph &G)
    291291      {
     
    305305    struct DefDistMapTraits : public Traits {
    306306      typedef T DistMap;
    307       ///\todo An exception should be thrown.
    308       ///
    309307      static DistMap *createDistMap(const Graph &G)
    310308      {
     
    320318                                        LengthMap,
    321319                                        DefDistMapTraits<T> > { };
     320   
     321    template <class T>
     322    struct DefReachedMapTraits : public Traits {
     323      typedef T ReachedMap;
     324      static ReachedMap *createReachedMap(const Graph &G)
     325      {
     326        throw UninitializedParameter();
     327      }
     328    };
     329    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
     330
     331    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
     332    ///
     333    template <class T>
     334    class DefReachedMap : public Dijkstra< Graph,
     335                                        LengthMap,
     336                                        DefReachedMapTraits<T> > { };
     337   
     338    struct DefGraphReachedMapTraits : public Traits {
     339      typedef typename Graph::NodeMap<bool> ReachedMap;
     340      static ReachedMap *createReachedMap(const Graph &G)
     341      {
     342        return new ReachedMap(G);
     343      }
     344    };
     345    ///\brief \ref named-templ-param "Named parameter"
     346    ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
     347    ///
     348    ///\ref named-templ-param "Named parameter"
     349    ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
     350    ///If you don't set it explicitely, it will be automatically allocated.
     351    template <class T>
     352    class DefReachedMapToBeDefaultMap :
     353      public Dijkstra< Graph,
     354                       LengthMap,
     355                       DefGraphReachedMapTraits> { };
     356   
     357    ///@}
     358
     359
     360  private:
     361    typename Graph::template NodeMap<int> _heap_map;
     362    Heap _heap;
     363  public:     
    322364   
    323365    ///Constructor.
     
    330372      pred_node(NULL), local_pred_node(false),
    331373      distance(NULL), local_distance(false),
    332       _reached(NULL), local_reached(false)
     374      _reached(NULL), local_reached(false),
     375      _heap_map(*G,-1),_heap(_heap_map)
    333376    { }
    334377   
     
    402445      return *this;
    403446    }
    404    
    405   ///Runs %Dijkstra algorithm from node \c s.
    406 
    407   ///This method runs the %Dijkstra algorithm from a root node \c s
    408   ///in order to
    409   ///compute the
    410   ///shortest path to each node. The algorithm computes
    411   ///- The shortest path tree.
    412   ///- The distance of each node from the root.
    413   ///\todo heap_map's type could also be in the traits class.
    414     void run(Node s) {
    415      
    416       init_maps();
    417      
    418       source = s;
     447
     448    ///\name Excetution control
     449    ///The simplest way to execute the algorithm is to use
     450    ///\ref run().
     451    ///\n
     452    ///It you need more control on the execution,
     453    ///first you must call \ref init(), then you can add several source nodes
     454    ///with \ref addSource(). Finally \ref start() will perform the actual path
     455    ///computation.
     456
     457    ///@{
     458
     459    ///Initializes the internal data structures.
     460
     461    ///Initializes the internal data structures.
     462    ///
     463    ///\todo _heap_map's type could also be in the traits class.
     464    void init()
     465    {
     466      create_maps();
    419467     
    420468      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
     
    422470        pred_node->set(u,INVALID);
    423471        ///\todo *_reached is not set to false.
    424       }
     472        _heap_map.set(u,Heap::PRE_HEAP);
     473      }
     474    }
     475   
     476    ///Adds a new source node.
     477
     478    ///Adds a new source node the the priority heap.
     479    ///It checks if the node has already been added to the heap.
     480    ///
     481    ///The optional second parameter is the initial distance of the node.
     482    ///
     483    ///\todo Do we really want to check it?
     484    void addSource(Node s,Value dst=0)
     485    {
     486      source = s;
     487      if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
     488    }
     489   
     490    void processNode()
     491    {
     492      Node v=_heap.top();
     493      _reached->set(v,true);
     494      Value oldvalue=_heap[v];
     495      _heap.pop();
     496      distance->set(v, oldvalue);
    425497     
    426       typename Graph::template NodeMap<int> heap_map(*G,-1);
    427      
    428       Heap heap(heap_map);
    429      
    430       heap.push(s,0);
    431      
    432       while ( !heap.empty() ) {
    433        
    434         Node v=heap.top();
    435         _reached->set(v,true);
    436         Value oldvalue=heap[v];
    437         heap.pop();
    438         distance->set(v, oldvalue);
    439        
    440        
    441         for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
    442           Node w=G->target(e);
    443           switch(heap.state(w)) {
    444           case Heap::PRE_HEAP:
    445             heap.push(w,oldvalue+(*length)[e]);
     498      for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
     499        Node w=G->target(e);
     500        switch(_heap.state(w)) {
     501        case Heap::PRE_HEAP:
     502          _heap.push(w,oldvalue+(*length)[e]);
     503          _pred->set(w,e);
     504          pred_node->set(w,v);
     505          break;
     506        case Heap::IN_HEAP:
     507          if ( oldvalue+(*length)[e] < _heap[w] ) {
     508            _heap.decrease(w, oldvalue+(*length)[e]);
    446509            _pred->set(w,e);
    447510            pred_node->set(w,v);
    448             break;
    449           case Heap::IN_HEAP:
    450             if ( oldvalue+(*length)[e] < heap[w] ) {
    451               heap.decrease(w, oldvalue+(*length)[e]);
    452               _pred->set(w,e);
    453               pred_node->set(w,v);
    454             }
    455             break;
    456           case Heap::POST_HEAP:
    457             break;
    458511          }
     512          break;
     513        case Heap::POST_HEAP:
     514          break;
    459515        }
    460516      }
    461517    }
    462    
     518
     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().
     525    ///
     526    ///This method runs the %Dijkstra algorithm from the root node(s)
     527    ///in order to
     528    ///compute the
     529    ///shortest path to each node. The algorithm computes
     530    ///- The shortest path tree.
     531    ///- The distance of each node from the root(s).
     532    ///
     533    void start()
     534    {
     535      while ( !_heap.empty() ) processNode();
     536    }
     537   
     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().
     544    ///
     545    ///This method runs the %Dijkstra algorithm from the root node(s)
     546    ///in order to
     547    ///compute the
     548    ///shortest path to \c dest. The algorithm computes
     549    ///- The shortest path to \c  dest.
     550    ///- The distance of \c dest from the root(s).
     551    ///
     552    void start(Node dest)
     553    {
     554      while ( !_heap.empty() && _heap.top()!=dest) processNode();
     555    }
     556   
     557    ///Runs %Dijkstra algorithm from node \c s.
     558   
     559    ///This method runs the %Dijkstra algorithm from a root node \c s
     560    ///in order to
     561    ///compute the
     562    ///shortest path to each node. The algorithm computes
     563    ///- The shortest path tree.
     564    ///- The distance of each node from the root.
     565    ///
     566    ///\note d.run(s) is just a shortcut of the following code.
     567    ///\code
     568    ///  d.init();
     569    ///  d.addSource(s);
     570    ///  d.start();
     571    ///\endcode
     572    void run(Node s) {
     573      init();
     574      addSource(s);
     575      start();
     576    }
     577   
     578    ///@}
     579
     580    ///\name Query Functions
     581    ///The result of the %Dijkstra algorithm can be obtained using these
     582    ///functions.\n
     583    ///Before the use of these functions,
     584    ///either run() or start() must be called.
     585   
     586    ///@{
     587
    463588    ///The distance of a node from the root.
    464589
     
    514639
    515640    ///Returns \c true if \c v is reachable from the root.
    516     ///\note The root node is reported to be reached!
     641    ///\warning If the algorithm is started from multiple nodes,
     642    ///this function may give false result for the source nodes.
    517643    ///\pre \ref run() must be called before using this function.
    518644    ///
    519645    bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; }
    520646   
     647    ///@}
    521648  };
    522649
Note: See TracChangeset for help on using the changeset viewer.