Changeset 1128:6a347310d4c2 in lemon-0.x for src/work/alpar

Timestamp:

02/06/05 15:44:41 (19 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:

• src/work/alpar/dijkstra.h (modified) (10 diffs)

src/work/alpar/dijkstra.h

@@ -159 +159 @@
   ///
   ///\author Jacint Szabo and Alpar Juttner
-  ///\todo We need a typedef-names should be standardized. (-:
+  ///\todo A compare object would be nice.
 
 #ifdef DOXYGEN
@@ -238 +238 @@
     Node source;
 
-    ///Initializes the maps.
+    ///Creates the maps if necessary.
     
     ///\todo Error if \c G or are \c NULL. What about \c length?
     ///\todo Better memory allocation (instead of new).
-    void init_maps() 
+    void create_maps() 
     {
       if(!_pred) {
@@ -264 +264 @@
   public :
  
+    ///\name Named template parameters
+
+    ///@{
+
     template <class T>
     struct DefPredMapTraits : public Traits {
       typedef T PredMap;
-      ///\todo An exception should be thrown.
-      ///
       static PredMap *createPredMap(const Graph &G) 
       {
@@ -286 +288 @@
     struct DefPredNodeMapTraits : public Traits {
       typedef T PredNodeMap;
-      ///\todo An exception should be thrown.
-      ///
       static PredNodeMap *createPredNodeMap(const Graph &G) 
       {
@@ -305 +305 @@
     struct DefDistMapTraits : public Traits {
       typedef T DistMap;
-      ///\todo An exception should be thrown.
-      ///
       static DistMap *createDistMap(const Graph &G) 
       {
@@ -320 +318 @@
                                         LengthMap,
                                         DefDistMapTraits<T> > { };
+    
+    template <class T>
+    struct DefReachedMapTraits : public Traits {
+      typedef T ReachedMap;
+      static ReachedMap *createReachedMap(const Graph &G) 
+      {
+        throw UninitializedParameter();
+      }
+    };
+    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
+
+    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
+    ///
+    template <class T>
+    class DefReachedMap : public Dijkstra< Graph,
+                                        LengthMap,
+                                        DefReachedMapTraits<T> > { };
+    
+    struct DefGraphReachedMapTraits : public Traits {
+      typedef typename Graph::NodeMap<bool> ReachedMap;
+      static ReachedMap *createReachedMap(const Graph &G) 
+      {
+        return new ReachedMap(G);
+      }
+    };
+    ///\brief \ref named-templ-param "Named parameter"
+    ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
+    ///
+    ///\ref named-templ-param "Named parameter"
+    ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
+    ///If you don't set it explicitely, it will be automatically allocated.
+    template <class T>
+    class DefReachedMapToBeDefaultMap :
+      public Dijkstra< Graph,
+                       LengthMap,
+                       DefGraphReachedMapTraits> { };
+    
+    ///@}
+
+
+  private:
+    typename Graph::template NodeMap<int> _heap_map;
+    Heap _heap;
+  public:      
     
     ///Constructor.
@@ -330 +372 @@
       pred_node(NULL), local_pred_node(false),
       distance(NULL), local_distance(false),
-      _reached(NULL), local_reached(false)
+      _reached(NULL), local_reached(false),
+      _heap_map(*G,-1),_heap(_heap_map)
     { }
     
@@ -402 +445 @@
       return *this;
     }
-    
-  ///Runs %Dijkstra algorithm from node \c s.
-
-  ///This method runs the %Dijkstra algorithm from a root node \c s
-  ///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.
-  ///\todo heap_map's type could also be in the traits class.
-    void run(Node s) {
-      
-      init_maps();
-      
-      source = s;
+
+    ///\name Excetution control
+    ///The simplest way to execute the algorithm is to use
+    ///\ref run().
+    ///\n
+    ///It you need more control on the execution,
+    ///first you must call \ref init(), then you can add several source nodes
+    ///with \ref addSource(). Finally \ref start() will perform the actual path
+    ///computation.
+
+    ///@{
+
+    ///Initializes the internal data structures.
+
+    ///Initializes the internal data structures.
+    ///
+    ///\todo _heap_map's type could also be in the traits class.
+    void init()
+    {
+      create_maps();
       
       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
@@ -422 +470 @@
         pred_node->set(u,INVALID);
         ///\todo *_reached is not set to false.
-      }
+        _heap_map.set(u,Heap::PRE_HEAP);
+      }
+    }
+    
+    ///Adds a new source node.
+
+    ///Adds a new source node the the priority heap.
+    ///It checks if the node has already been added to the heap.
+    ///
+    ///The optional second parameter is the initial distance of the node.
+    ///
+    ///\todo Do we really want to check it?
+    void addSource(Node s,Value dst=0)
+    {
+      source = s;
+      if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
+    }
+    
+    void processNode()
+    {
+      Node v=_heap.top(); 
+      _reached->set(v,true);
+      Value oldvalue=_heap[v];
+      _heap.pop();
+      distance->set(v, oldvalue);
       
-      typename Graph::template NodeMap<int> heap_map(*G,-1);
-      
-      Heap heap(heap_map);
-      
-      heap.push(s,0); 
-      
-      while ( !heap.empty() ) {
-        
-        Node v=heap.top(); 
-        _reached->set(v,true);
-        Value oldvalue=heap[v];
-        heap.pop();
-        distance->set(v, oldvalue);
-        
-        
-        for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
-          Node w=G->target(e); 
-          switch(heap.state(w)) {
-          case Heap::PRE_HEAP:
-            heap.push(w,oldvalue+(*length)[e]); 
+      for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
+        Node w=G->target(e); 
+        switch(_heap.state(w)) {
+        case Heap::PRE_HEAP:
+          _heap.push(w,oldvalue+(*length)[e]); 
+          _pred->set(w,e);
+          pred_node->set(w,v);
+          break;
+        case Heap::IN_HEAP:
+          if ( oldvalue+(*length)[e] < _heap[w] ) {
+            _heap.decrease(w, oldvalue+(*length)[e]); 
             _pred->set(w,e);
             pred_node->set(w,v);
-            break;
-          case Heap::IN_HEAP:
-            if ( oldvalue+(*length)[e] < heap[w] ) {
-              heap.decrease(w, oldvalue+(*length)[e]); 
-              _pred->set(w,e);
-              pred_node->set(w,v);
-            }
-            break;
-          case Heap::POST_HEAP:
-            break;
           }
+          break;
+        case Heap::POST_HEAP:
+          break;
         }
       }
     }
-    
+
+    ///Starts the execution of the algorithm.
+
+    ///Starts the execution of the algorithm.
+    ///
+    ///\pre init() must be called before and at least one node should be added
+    ///with addSource().
+    ///
+    ///This method runs the %Dijkstra algorithm from the root node(s)
+    ///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 ( !_heap.empty() ) processNode();
+    }
+    
+    ///Starts the execution of the algorithm until \c dest is reached.
+
+    ///Starts the execution of the algorithm until \c dest is reached.
+    ///
+    ///\pre init() must be called before and at least one node should be added
+    ///with addSource().
+    ///
+    ///This method runs the %Dijkstra algorithm from the root node(s)
+    ///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)
+    {
+      while ( !_heap.empty() && _heap.top()!=dest) processNode();
+    }
+    
+    ///Runs %Dijkstra algorithm from node \c s.
+    
+    ///This method runs the %Dijkstra algorithm from a root node \c s
+    ///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.
+    ///
+    ///\note d.run(s) is just a shortcut of the following code.
+    ///\code
+    ///  d.init();
+    ///  d.addSource(s);
+    ///  d.start();
+    ///\endcode
+    void run(Node s) {
+      init();
+      addSource(s);
+      start();
+    }
+    
+    ///@}
+
+    ///\name Query Functions
+    ///The result of the %Dijkstra algorithm can be obtained using these
+    ///functions.\n
+    ///Before the use of these functions,
+    ///either run() or start() must be called.
+    
+    ///@{
+
     ///The distance of a node from the root.
 
@@ -514 +639 @@
 
     ///Returns \c true if \c v is reachable from the root.
-    ///\note The root node is reported to be reached!
+    ///\warning If the algorithm is started from multiple nodes,
+    ///this function may give false result for the source nodes.
     ///\pre \ref run() must be called before using this function.
     ///
     bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; }
     
+    ///@}
   };