Changeset 1119:d3504fc075dc in lemon-0.x for src/work/alpar

Timestamp:

02/03/05 17:08:56 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

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

Message:

Two incomplete additions:

• Exceptions
• bool map indication reached nodes (NullMap? by default)

File:

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

src/work/alpar/dijkstra.h

@@ -25 +25 @@
 #include <lemon/bin_heap.h>
 #include <lemon/invalid.h>
+#include <lemon/error.h>
+#include <lemon/maps.h>
 
 namespace lemon {
+
+
+  class UninitializedData : public LogicError {};
+
 
 /// \addtogroup flowalgs
@@ -68 +74 @@
  
     ///\todo Please document...
-    ///
+    ///\todo The graph alone may be insufficient for the initialization
     static PredMap *createPredMap(const GR &G) 
     {
@@ -86 +92 @@
     {
       return new PredNodeMap(G);
+    }
+
+    ///The type of the map that stores whether a nodes is reached.
+ 
+    ///It must meet the \ref concept::WriteMap "WriteMap" concept.
+    ///By default it is a NullMap.
+    ///\todo If it is set to a real map, Dijkstra::reached() should read this.
+    ///\todo named parameter to set this type, function to read and write.
+    typedef NullMap<typename Graph::Node,bool> ReachedMap;
+    ///Instantiates a ReachedMap.
+ 
+    ///\todo Please document...
+    ///
+    static ReachedMap *createReachedMap(const GR &G)
+    {
+      return new ReachedMap();
     }
     ///The type of the map that stores the dists of the nodes.
@@ -146 +168 @@
   class Dijkstra {
   public:
+    ///Exception thrown by dijkstra.
+    class UninitializedData : public lemon::UninitializedData {};
+
     typedef TR Traits;
     ///The type of the underlying graph.
@@ -168 +193 @@
     ///nodes of the shortest paths.
     typedef typename TR::PredNodeMap PredNodeMap;
+    ///The type of the map indicating if a node is reached.
+    typedef typename TR::ReachedMap ReachedMap;
     ///The type of the map that stores the dists of the nodes.
     typedef typename TR::DistMap DistMap;
@@ -178 +205 @@
     const LengthMap *length;
     ///Pointer to the map of predecessors edges.
-    PredMap *predecessor;
-    ///Indicates if \ref predecessor is locally allocated (\c true) or not.
-    bool local_predecessor;
+    PredMap *_pred;
+    ///Indicates if \ref _pred is locally allocated (\c true) or not.
+    bool local_pred;
     ///Pointer to the map of predecessors nodes.
     PredNodeMap *pred_node;
@@ -189 +216 @@
     ///Indicates if \ref distance is locally allocated (\c true) or not.
     bool local_distance;
+    ///Pointer to the map of reached status of the nodes.
+    ReachedMap *_reached;
+    ///Indicates if \ref _reached is locally allocated (\c true) or not.
+    bool local_reached;
 
     ///The source node of the last execution.
@@ -199 +230 @@
     void init_maps() 
     {
-      if(!predecessor) {
-        local_predecessor = true;
-        predecessor = Traits::createPredMap(*G);
+      if(!_pred) {
+        local_pred = true;
+        _pred = Traits::createPredMap(*G);
       }
       if(!pred_node) {
@@ -210 +241 @@
         local_distance = true;
         distance = Traits::createDistMap(*G);
+      }
+      if(!_reached) {
+        local_reached = true;
+        _reached = Traits::createReachedMap(*G);
       }
     }
@@ -222 +257 @@
       static PredMap *createPredMap(const Graph &G) 
       {
-        std::cerr << __FILE__ ":" << __LINE__ <<
-          ": error: Special maps should be manually created" << std::endl;
-        exit(1);
+        throw UninitializedData();
       }
     };
@@ -243 +276 @@
       static PredNodeMap *createPredNodeMap(const Graph &G) 
       {
-        std::cerr << __FILE__ ":" << __LINE__ <<
-          ": error: Special maps should be manually created" << std::endl;
-        exit(1);
+        throw UninitializedData();
       }
     };
@@ -264 +295 @@
       static DistMap *createDistMap(const Graph &G) 
       {
-        std::cerr << __FILE__ ":" << __LINE__ <<
-          ": error: Special maps should be manually created" << std::endl;
-        exit(1);
+        throw UninitializedData();
       }
     };
@@ -284 +313 @@
     Dijkstra(const Graph& _G, const LengthMap& _length) :
       G(&_G), length(&_length),
-      predecessor(NULL), local_predecessor(false),
+      _pred(NULL), local_pred(false),
       pred_node(NULL), local_pred_node(false),
-      distance(NULL), local_distance(false)
+      distance(NULL), local_distance(false),
+      _reached(NULL), local_reached(false)
     { }
     
@@ -292 +322 @@
     ~Dijkstra() 
     {
-      if(local_predecessor) delete predecessor;
+      if(local_pred) delete _pred;
       if(local_pred_node) delete pred_node;
       if(local_distance) delete distance;
+      if(local_reached) delete _reached;
     }
 
@@ -316 +347 @@
     Dijkstra &predMap(PredMap &m) 
     {
-      if(local_predecessor) {
-        delete predecessor;
-        local_predecessor=false;
-      }
-      predecessor = &m;
+      if(local_pred) {
+        delete _pred;
+        local_pred=false;
+      }
+      _pred = &m;
       return *this;
     }
@@ -374 +405 @@
       
       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
-        predecessor->set(u,INVALID);
+        _pred->set(u,INVALID);
         pred_node->set(u,INVALID);
+        ///\todo *_reached is not set to false.
       }
       
@@ -387 +419 @@
         
         Node v=heap.top(); 
+        _reached->set(v,true);
         Value oldvalue=heap[v];
         heap.pop();
@@ -397 +430 @@
           case Heap::PRE_HEAP:
             heap.push(w,oldvalue+(*length)[e]); 
-            predecessor->set(w,e);
+            _pred->set(w,e);
             pred_node->set(w,v);
             break;
@@ -403 +436 @@
             if ( oldvalue+(*length)[e] < heap[w] ) {
               heap.decrease(w, oldvalue+(*length)[e]); 
-              predecessor->set(w,e);
+              _pred->set(w,e);
               pred_node->set(w,v);
             }
@@ -432 +465 @@
     ///this function.
     ///\todo predEdge could be a better name.
-    Edge pred(Node v) const { return (*predecessor)[v]; }
+    Edge pred(Node v) const { return (*_pred)[v]; }
 
     ///Returns the 'previous node' of the shortest path tree.
@@ -455 +488 @@
     ///shortest path tree.
     ///\pre \ref run() must be called before using this function.
-    const PredMap &predMap() const { return *predecessor;}
+    const PredMap &predMap() const { return *_pred;}
  
     ///Returns a reference to the map of nodes of shortest paths.
@@ -470 +503 @@
     ///\pre \ref run() must be called before using this function.
     ///
-    bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
+    bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; }
     
   };
@@ -514 +547 @@
     typedef TR Base;
 
-    ///The type of the underlying graph.
+    //The type of the underlying graph.
     typedef typename TR::Graph Graph;
-    ///\e
+    //\e
     typedef typename Graph::Node Node;
-    ///\e
+    //\e
     typedef typename Graph::NodeIt NodeIt;
-    ///\e
+    //\e
     typedef typename Graph::Edge Edge;
-    ///\e
+    //\e
     typedef typename Graph::OutEdgeIt OutEdgeIt;
     
-    ///The type of the map that stores the edge lengths.
+    //The type of the map that stores the edge lengths.
     typedef typename TR::LengthMap LengthMap;
-    ///The type of the length of the edges.
+    //The type of the length of the edges.
     typedef typename LengthMap::Value Value;
-    ///\brief The type of the map that stores the last
-    ///edges of the shortest paths.
+    //\brief The type of the map that stores the last
+    //edges of the shortest paths.
     typedef typename TR::PredMap PredMap;
-    ///\brief The type of the map that stores the last but one
-    ///nodes of the shortest paths.
+    //\brief The type of the map that stores the last but one
+    //nodes of the shortest paths.
     typedef typename TR::PredNodeMap PredNodeMap;
-    ///The type of the map that stores the dists of the nodes.
+    //The type of the map that stores the dists of the nodes.
     typedef typename TR::DistMap DistMap;
 
-    ///The heap type used by the dijkstra algorithm.
+    //The heap type used by the dijkstra algorithm.
     typedef typename TR::Heap Heap;
 public:
@@ -553 +586 @@
     void run()
     {
+      if(_source==0) throw UninitializedData();
       Dijkstra<Graph,LengthMap,TR> Dij(*(Graph*)_g,*(LengthMap*)_length);
       if(_pred) Dij.predMap(*(PredMap*)_pred);