Changeset 688:bdc429a557f2 in lemon-0.x for src/hugo/dijkstra.h

Timestamp:

06/30/04 16:50:31 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@938

Message:

• Now, it is possible to have Dijkstra store its result directly in given maps.
• More docs.

File:

• src/hugo/dijkstra.h (modified) (11 diffs)

src/hugo/dijkstra.h

@@ -73 +73 @@
 
   private:
-    const Graph& G;
-    const LM& length;
-    PredMap predecessor;
-    PredNodeMap pred_node;
-    DistMap distance;
+    const Graph *G;
+    const LM *length;
+    //    bool local_length;
+    PredMap *predecessor;
+    bool local_predecessor;
+    PredNodeMap *pred_node;
+    bool local_pred_node;
+    DistMap *distance;
+    bool local_distance;
+
+    ///Initialize maps
+    
+    ///\todo Error if \c G or are \c NULL. What about \c length
+    ///\todo Better memory allocation (instead of new).
+    void init_maps() 
+    {
+//       if(!length) {
+//      local_length = true;
+//      length = new LM(G);
+//       }
+      if(!predecessor) {
+        local_predecessor = true;
+        predecessor = new PredMap(*G);
+      }
+      if(!pred_node) {
+        local_pred_node = true;
+        pred_node = new PredNodeMap(*G);
+      }
+      if(!distance) {
+        local_distance = true;
+        distance = new DistMap(*G);
+      }
+    }
     
   public :
     
     Dijkstra(const Graph& _G, const LM& _length) :
-      G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { }
+      G(&_G), length(&_length),
+      predecessor(NULL), pred_node(NULL), distance(NULL),
+      local_predecessor(false), local_pred_node(false), local_distance(false)
+    { }
+    
+    ~Dijkstra() 
+    {
+      //      if(local_length) delete length;
+      if(local_predecessor) delete predecessor;
+      if(local_pred_node) delete pred_node;
+      if(local_distance) delete distance;
+    }
+
+    ///Sets the graph the algorithm will run on.
+
+    ///Sets the graph the algorithm will run on.
+    ///\return <tt> (*this) </tt>
+    Dijkstra &setGraph(const Graph &_G) 
+    {
+      G = &_G;
+      return *this;
+    }
+    ///Sets the length map.
+
+    ///Sets the length map.
+    ///\return <tt> (*this) </tt>
+    Dijkstra &setLengthMap(const LM &m) 
+    {
+//       if(local_length) {
+//      delete length;
+//      local_length=false;
+//       }
+      length = &m;
+      return *this;
+    }
+
+    ///Sets the map storing the predecessor edges.
+
+    ///Sets the map storing the predecessor edges.
+    ///If you don't use this function before calling \ref run(),
+    ///it will allocate one. The destuctor deallocates this
+    ///automatically allocated map, of course.
+    ///\return <tt> (*this) </tt>
+    Dijkstra &setPredMap(PredMap &m) 
+    {
+      if(local_predecessor) {
+        delete predecessor;
+        local_predecessor=false;
+      }
+      predecessor = &m;
+      return *this;
+    }
+
+    ///Sets the map storing the predecessor nodes.
+
+    ///Sets the map storing the predecessor nodes.
+    ///If you don't use this function before calling \ref run(),
+    ///it will allocate one. The destuctor deallocates this
+    ///automatically allocated map, of course.
+    ///\return <tt> (*this) </tt>
+    Dijkstra &setPredNodeMap(PredNodeMap &m) 
+    {
+      if(local_pred_node) {
+        delete pred_node;
+        local_pred_node=false;
+      }
+      pred_node = &m;
+      return *this;
+    }
+
+    ///Sets the map storing the distances calculated by the algorithm.
+
+    ///Sets the map storing the distances calculated by the algorithm.
+    ///If you don't use this function before calling \ref run(),
+    ///it will allocate one. The destuctor deallocates this
+    ///automatically allocated map, of course.
+    ///\return <tt> (*this) </tt>
+    Dijkstra &setDistMap(DistMap &m) 
+    {
+      if(local_distance) {
+        delete distance;
+        local_distance=false;
+      }
+      distance = &m;
+      return *this;
+    }
     
     void run(Node s);
@@ -92 +205 @@
     ///\warning If node \c v in unreachable from the root the return value
     ///of this funcion is undefined.
-    ValueType dist(Node v) const { return distance[v]; }
+    ValueType dist(Node v) const { return (*distance)[v]; }
 
     ///Returns the 'previous edge' of the shortest path tree.
@@ -98 +211 @@
     ///For a node \c v it returns the 'previous edge' of the shortest path tree,
     ///i.e. it returns the last edge from a shortest path from the root to \c
-    ///v. It is INVALID if \c v is unreachable from the root or if \c v=s. The
+    ///v. It is \ref INVALID
+    ///if \c v is unreachable from the root or if \c v=s. The
     ///shortest path tree used here is equal to the shortest path tree used in
     ///\ref predNode(Node v).  \pre \ref run() must be called before using
     ///this function.
-    Edge pred(Node v) const { return predecessor[v]; }
+    Edge pred(Node v) const { return (*predecessor)[v]; }
 
     ///Returns the 'previous node' of the shortest path tree.
@@ -112 +226 @@
     ///tree used in \ref pred(Node v).  \pre \ref run() must be called before
     ///using this function.
-    Node predNode(Node v) const { return pred_node[v]; }
+    Node predNode(Node v) const { return (*pred_node)[v]; }
     
     ///Returns a reference to the NodeMap of distances.
@@ -118 +232 @@
     ///Returns a reference to the NodeMap of distances. \pre \ref run() must
     ///be called before using this function.
-    const DistMap &distMap() const { return distance;}
+    const DistMap &distMap() const { return *distance;}
  
     ///Returns a reference to the shortest path tree map.
@@ -125 +239 @@
     ///shortest path tree.
     ///\pre \ref run() must be called before using this function.
-    const PredMap &predMap() const { return predecessor;}
+    const PredMap &predMap() const { return *predecessor;}
  
     ///Returns a reference to the map of nodes of shortest paths.
@@ -132 +246 @@
     ///shortest path tree.
     ///\pre \ref run() must be called before using this function.
-    const PredNodeMap &predNodeMap() const { return pred_node;}
+    const PredNodeMap &predNodeMap() const { return *pred_node;}
 
     ///Checks if a node is reachable from the root.
@@ -141 +255 @@
     ///\pre \ref run() must be called before using this function.
     ///
-    bool reached(Node v) { return G.valid(predecessor[v]); }
+    bool reached(Node v) { return G->valid((*predecessor)[v]); }
     
   };
@@ -161 +275 @@
             template<class,class,class,class> class Heap >
   void Dijkstra<GR,LM,Heap>::run(Node s) {
-    
-    NodeIt u;
-    for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
-      predecessor.set(u,INVALID);
-      pred_node.set(u,INVALID);
-    }
-    
-    typename GR::template NodeMap<int> heap_map(G,-1);
+
+    init_maps();
+
+    for ( NodeIt u(*G) ; G->valid(u) ; G->next(u) ) {
+      predecessor->set(u,INVALID);
+      pred_node->set(u,INVALID);
+    }
+    
+    typename GR::template NodeMap<int> heap_map(*G,-1);
     
     typedef Heap<Node, ValueType, typename GR::template NodeMap<int>,
@@ -183 +298 @@
         ValueType oldvalue=heap[v];
         heap.pop();
-        distance.set(v, oldvalue);
+        distance->set(v, oldvalue);
         
-        { //FIXME this bracket is for e to be local
-          OutEdgeIt e;
-        for(G.first(e, v);
-            G.valid(e); G.next(e)) {
-          Node w=G.bNode(e); 
+          
+        for(OutEdgeIt e(*G,v); G->valid(e); G->next(e)) {
+          Node w=G->bNode(e); 
           
           switch(heap.state(w)) {
           case HeapType::PRE_HEAP:
-            heap.push(w,oldvalue+length[e]); 
-            predecessor.set(w,e);
-            pred_node.set(w,v);
+            heap.push(w,oldvalue+(*length)[e]); 
+            predecessor->set(w,e);
+            pred_node->set(w,v);
             break;
           case HeapType::IN_HEAP:
-            if ( oldvalue+length[e] < heap[w] ) {
-              heap.decrease(w, oldvalue+length[e]); 
-              predecessor.set(w,e);
-              pred_node.set(w,v);
+            if ( oldvalue+(*length)[e] < heap[w] ) {
+              heap.decrease(w, oldvalue+(*length)[e]); 
+              predecessor->set(w,e);
+              pred_node->set(w,v);
             }
             break;
@@ -208 +321 @@
           }
         }
-      } //FIXME tis bracket
       }
   }