# HG changeset patch
# User alpar
# Date 1107446936 0
# Node ID d3504fc075dc6a31e3083a1ef177fa82aac3f5b8
# Parent  62296604afb495ad7bbe5d534d996a1dfe564e2b
Two incomplete additions:
- Exceptions
- bool map indication reached nodes (NullMap by default)

diff -r 62296604afb4 -r d3504fc075dc src/work/alpar/dijkstra.h
--- a/src/work/alpar/dijkstra.h	Wed Feb 02 16:23:41 2005 +0000
+++ b/src/work/alpar/dijkstra.h	Thu Feb 03 16:08:56 2005 +0000
@@ -24,9 +24,15 @@
 #include <lemon/list_graph.h>
 #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
 /// @{
 
@@ -67,7 +73,7 @@
     ///Instantiates a PredMap.
  
     ///\todo Please document...
-    ///
+    ///\todo The graph alone may be insufficient for the initialization
     static PredMap *createPredMap(const GR &G) 
     {
       return new PredMap(G);
@@ -86,6 +92,22 @@
     {
       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.
  
     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
@@ -145,6 +167,9 @@
 #endif
   class Dijkstra {
   public:
+    ///Exception thrown by dijkstra.
+    class UninitializedData : public lemon::UninitializedData {};
+
     typedef TR Traits;
     ///The type of the underlying graph.
     typedef typename TR::Graph Graph;
@@ -167,6 +192,8 @@
     ///\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 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;
     ///The heap type used by the dijkstra algorithm.
@@ -177,9 +204,9 @@
     /// Pointer to the length map
     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;
     ///Indicates if \ref pred_node is locally allocated (\c true) or not.
@@ -188,6 +215,10 @@
     DistMap *distance;
     ///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.
     Node source;
@@ -198,9 +229,9 @@
     ///\todo Better memory allocation (instead of new).
     void init_maps() 
     {
-      if(!predecessor) {
-	local_predecessor = true;
-	predecessor = Traits::createPredMap(*G);
+      if(!_pred) {
+	local_pred = true;
+	_pred = Traits::createPredMap(*G);
       }
       if(!pred_node) {
 	local_pred_node = true;
@@ -210,6 +241,10 @@
 	local_distance = true;
 	distance = Traits::createDistMap(*G);
       }
+      if(!_reached) {
+	local_reached = true;
+	_reached = Traits::createReachedMap(*G);
+      }
     }
     
   public :
@@ -221,9 +256,7 @@
       ///
       static PredMap *createPredMap(const Graph &G) 
       {
-	std::cerr << __FILE__ ":" << __LINE__ <<
-	  ": error: Special maps should be manually created" << std::endl;
-	exit(1);
+	throw UninitializedData();
       }
     };
     ///\ref named-templ-param "Named parameter" for setting PredMap type
@@ -242,9 +275,7 @@
       ///
       static PredNodeMap *createPredNodeMap(const Graph &G) 
       {
-	std::cerr << __FILE__ ":" << __LINE__ <<
-	  ": error: Special maps should be manually created" << std::endl;
-	exit(1);
+	throw UninitializedData();
       }
     };
     ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
@@ -263,9 +294,7 @@
       ///
       static DistMap *createDistMap(const Graph &G) 
       {
-	std::cerr << __FILE__ ":" << __LINE__ <<
-	  ": error: Special maps should be manually created" << std::endl;
-	exit(1);
+	throw UninitializedData();
       }
     };
     ///\ref named-templ-param "Named parameter" for setting DistMap type
@@ -283,17 +312,19 @@
     ///\param _length the length map used by the algorithm.
     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)
     { }
     
     ///Destructor.
     ~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;
     }
 
     ///Sets the length map.
@@ -315,11 +346,11 @@
     ///\return <tt> (*this) </tt>
     Dijkstra &predMap(PredMap &m) 
     {
-      if(local_predecessor) {
-	delete predecessor;
-	local_predecessor=false;
+      if(local_pred) {
+	delete _pred;
+	local_pred=false;
       }
-      predecessor = &m;
+      _pred = &m;
       return *this;
     }
 
@@ -373,8 +404,9 @@
       source = s;
       
       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.
       }
       
       typename Graph::template NodeMap<int> heap_map(*G,-1);
@@ -386,6 +418,7 @@
       while ( !heap.empty() ) {
 	
 	Node v=heap.top(); 
+	_reached->set(v,true);
 	Value oldvalue=heap[v];
 	heap.pop();
 	distance->set(v, oldvalue);
@@ -396,13 +429,13 @@
 	  switch(heap.state(w)) {
 	  case Heap::PRE_HEAP:
 	    heap.push(w,oldvalue+(*length)[e]); 
-	    predecessor->set(w,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]); 
-	      predecessor->set(w,e);
+	      _pred->set(w,e);
 	      pred_node->set(w,v);
 	    }
 	    break;
@@ -431,7 +464,7 @@
     ///\ref predNode(Node v).  \pre \ref run() must be called before using
     ///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.
 
@@ -454,7 +487,7 @@
     ///Returns a reference to the NodeMap of the edges of the
     ///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.
 
@@ -469,7 +502,7 @@
     ///\note The root node is reported to be reached!
     ///\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; }
     
   };
 
@@ -513,31 +546,31 @@
   {
     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:
     DijkstraWizard() : TR() {}
@@ -552,6 +585,7 @@
     ///\e
     void run()
     {
+      if(_source==0) throw UninitializedData();
       Dijkstra<Graph,LengthMap,TR> Dij(*(Graph*)_g,*(LengthMap*)_length);
       if(_pred) Dij.predMap(*(PredMap*)_pred);
       if(_predNode) Dij.predNodeMap(*(PredNodeMap*)_predNode);