1.1 --- a/src/work/alpar/dijkstra.h Wed Feb 02 16:23:41 2005 +0000
1.2 +++ b/src/work/alpar/dijkstra.h Thu Feb 03 16:08:56 2005 +0000
1.3 @@ -24,9 +24,15 @@
1.4 #include <lemon/list_graph.h>
1.5 #include <lemon/bin_heap.h>
1.6 #include <lemon/invalid.h>
1.7 +#include <lemon/error.h>
1.8 +#include <lemon/maps.h>
1.9
1.10 namespace lemon {
1.11
1.12 +
1.13 + class UninitializedData : public LogicError {};
1.14 +
1.15 +
1.16 /// \addtogroup flowalgs
1.17 /// @{
1.18
1.19 @@ -67,7 +73,7 @@
1.20 ///Instantiates a PredMap.
1.21
1.22 ///\todo Please document...
1.23 - ///
1.24 + ///\todo The graph alone may be insufficient for the initialization
1.25 static PredMap *createPredMap(const GR &G)
1.26 {
1.27 return new PredMap(G);
1.28 @@ -86,6 +92,22 @@
1.29 {
1.30 return new PredNodeMap(G);
1.31 }
1.32 +
1.33 + ///The type of the map that stores whether a nodes is reached.
1.34 +
1.35 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.36 + ///By default it is a NullMap.
1.37 + ///\todo If it is set to a real map, Dijkstra::reached() should read this.
1.38 + ///\todo named parameter to set this type, function to read and write.
1.39 + typedef NullMap<typename Graph::Node,bool> ReachedMap;
1.40 + ///Instantiates a ReachedMap.
1.41 +
1.42 + ///\todo Please document...
1.43 + ///
1.44 + static ReachedMap *createReachedMap(const GR &G)
1.45 + {
1.46 + return new ReachedMap();
1.47 + }
1.48 ///The type of the map that stores the dists of the nodes.
1.49
1.50 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.51 @@ -145,6 +167,9 @@
1.52 #endif
1.53 class Dijkstra {
1.54 public:
1.55 + ///Exception thrown by dijkstra.
1.56 + class UninitializedData : public lemon::UninitializedData {};
1.57 +
1.58 typedef TR Traits;
1.59 ///The type of the underlying graph.
1.60 typedef typename TR::Graph Graph;
1.61 @@ -167,6 +192,8 @@
1.62 ///\brief The type of the map that stores the last but one
1.63 ///nodes of the shortest paths.
1.64 typedef typename TR::PredNodeMap PredNodeMap;
1.65 + ///The type of the map indicating if a node is reached.
1.66 + typedef typename TR::ReachedMap ReachedMap;
1.67 ///The type of the map that stores the dists of the nodes.
1.68 typedef typename TR::DistMap DistMap;
1.69 ///The heap type used by the dijkstra algorithm.
1.70 @@ -177,9 +204,9 @@
1.71 /// Pointer to the length map
1.72 const LengthMap *length;
1.73 ///Pointer to the map of predecessors edges.
1.74 - PredMap *predecessor;
1.75 - ///Indicates if \ref predecessor is locally allocated (\c true) or not.
1.76 - bool local_predecessor;
1.77 + PredMap *_pred;
1.78 + ///Indicates if \ref _pred is locally allocated (\c true) or not.
1.79 + bool local_pred;
1.80 ///Pointer to the map of predecessors nodes.
1.81 PredNodeMap *pred_node;
1.82 ///Indicates if \ref pred_node is locally allocated (\c true) or not.
1.83 @@ -188,6 +215,10 @@
1.84 DistMap *distance;
1.85 ///Indicates if \ref distance is locally allocated (\c true) or not.
1.86 bool local_distance;
1.87 + ///Pointer to the map of reached status of the nodes.
1.88 + ReachedMap *_reached;
1.89 + ///Indicates if \ref _reached is locally allocated (\c true) or not.
1.90 + bool local_reached;
1.91
1.92 ///The source node of the last execution.
1.93 Node source;
1.94 @@ -198,9 +229,9 @@
1.95 ///\todo Better memory allocation (instead of new).
1.96 void init_maps()
1.97 {
1.98 - if(!predecessor) {
1.99 - local_predecessor = true;
1.100 - predecessor = Traits::createPredMap(*G);
1.101 + if(!_pred) {
1.102 + local_pred = true;
1.103 + _pred = Traits::createPredMap(*G);
1.104 }
1.105 if(!pred_node) {
1.106 local_pred_node = true;
1.107 @@ -210,6 +241,10 @@
1.108 local_distance = true;
1.109 distance = Traits::createDistMap(*G);
1.110 }
1.111 + if(!_reached) {
1.112 + local_reached = true;
1.113 + _reached = Traits::createReachedMap(*G);
1.114 + }
1.115 }
1.116
1.117 public :
1.118 @@ -221,9 +256,7 @@
1.119 ///
1.120 static PredMap *createPredMap(const Graph &G)
1.121 {
1.122 - std::cerr << __FILE__ ":" << __LINE__ <<
1.123 - ": error: Special maps should be manually created" << std::endl;
1.124 - exit(1);
1.125 + throw UninitializedData();
1.126 }
1.127 };
1.128 ///\ref named-templ-param "Named parameter" for setting PredMap type
1.129 @@ -242,9 +275,7 @@
1.130 ///
1.131 static PredNodeMap *createPredNodeMap(const Graph &G)
1.132 {
1.133 - std::cerr << __FILE__ ":" << __LINE__ <<
1.134 - ": error: Special maps should be manually created" << std::endl;
1.135 - exit(1);
1.136 + throw UninitializedData();
1.137 }
1.138 };
1.139 ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
1.140 @@ -263,9 +294,7 @@
1.141 ///
1.142 static DistMap *createDistMap(const Graph &G)
1.143 {
1.144 - std::cerr << __FILE__ ":" << __LINE__ <<
1.145 - ": error: Special maps should be manually created" << std::endl;
1.146 - exit(1);
1.147 + throw UninitializedData();
1.148 }
1.149 };
1.150 ///\ref named-templ-param "Named parameter" for setting DistMap type
1.151 @@ -283,17 +312,19 @@
1.152 ///\param _length the length map used by the algorithm.
1.153 Dijkstra(const Graph& _G, const LengthMap& _length) :
1.154 G(&_G), length(&_length),
1.155 - predecessor(NULL), local_predecessor(false),
1.156 + _pred(NULL), local_pred(false),
1.157 pred_node(NULL), local_pred_node(false),
1.158 - distance(NULL), local_distance(false)
1.159 + distance(NULL), local_distance(false),
1.160 + _reached(NULL), local_reached(false)
1.161 { }
1.162
1.163 ///Destructor.
1.164 ~Dijkstra()
1.165 {
1.166 - if(local_predecessor) delete predecessor;
1.167 + if(local_pred) delete _pred;
1.168 if(local_pred_node) delete pred_node;
1.169 if(local_distance) delete distance;
1.170 + if(local_reached) delete _reached;
1.171 }
1.172
1.173 ///Sets the length map.
1.174 @@ -315,11 +346,11 @@
1.175 ///\return <tt> (*this) </tt>
1.176 Dijkstra &predMap(PredMap &m)
1.177 {
1.178 - if(local_predecessor) {
1.179 - delete predecessor;
1.180 - local_predecessor=false;
1.181 + if(local_pred) {
1.182 + delete _pred;
1.183 + local_pred=false;
1.184 }
1.185 - predecessor = &m;
1.186 + _pred = &m;
1.187 return *this;
1.188 }
1.189
1.190 @@ -373,8 +404,9 @@
1.191 source = s;
1.192
1.193 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
1.194 - predecessor->set(u,INVALID);
1.195 + _pred->set(u,INVALID);
1.196 pred_node->set(u,INVALID);
1.197 + ///\todo *_reached is not set to false.
1.198 }
1.199
1.200 typename Graph::template NodeMap<int> heap_map(*G,-1);
1.201 @@ -386,6 +418,7 @@
1.202 while ( !heap.empty() ) {
1.203
1.204 Node v=heap.top();
1.205 + _reached->set(v,true);
1.206 Value oldvalue=heap[v];
1.207 heap.pop();
1.208 distance->set(v, oldvalue);
1.209 @@ -396,13 +429,13 @@
1.210 switch(heap.state(w)) {
1.211 case Heap::PRE_HEAP:
1.212 heap.push(w,oldvalue+(*length)[e]);
1.213 - predecessor->set(w,e);
1.214 + _pred->set(w,e);
1.215 pred_node->set(w,v);
1.216 break;
1.217 case Heap::IN_HEAP:
1.218 if ( oldvalue+(*length)[e] < heap[w] ) {
1.219 heap.decrease(w, oldvalue+(*length)[e]);
1.220 - predecessor->set(w,e);
1.221 + _pred->set(w,e);
1.222 pred_node->set(w,v);
1.223 }
1.224 break;
1.225 @@ -431,7 +464,7 @@
1.226 ///\ref predNode(Node v). \pre \ref run() must be called before using
1.227 ///this function.
1.228 ///\todo predEdge could be a better name.
1.229 - Edge pred(Node v) const { return (*predecessor)[v]; }
1.230 + Edge pred(Node v) const { return (*_pred)[v]; }
1.231
1.232 ///Returns the 'previous node' of the shortest path tree.
1.233
1.234 @@ -454,7 +487,7 @@
1.235 ///Returns a reference to the NodeMap of the edges of the
1.236 ///shortest path tree.
1.237 ///\pre \ref run() must be called before using this function.
1.238 - const PredMap &predMap() const { return *predecessor;}
1.239 + const PredMap &predMap() const { return *_pred;}
1.240
1.241 ///Returns a reference to the map of nodes of shortest paths.
1.242
1.243 @@ -469,7 +502,7 @@
1.244 ///\note The root node is reported to be reached!
1.245 ///\pre \ref run() must be called before using this function.
1.246 ///
1.247 - bool reached(Node v) { return v==source || (*predecessor)[v]!=INVALID; }
1.248 + bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; }
1.249
1.250 };
1.251
1.252 @@ -513,31 +546,31 @@
1.253 {
1.254 typedef TR Base;
1.255
1.256 - ///The type of the underlying graph.
1.257 + //The type of the underlying graph.
1.258 typedef typename TR::Graph Graph;
1.259 - ///\e
1.260 + //\e
1.261 typedef typename Graph::Node Node;
1.262 - ///\e
1.263 + //\e
1.264 typedef typename Graph::NodeIt NodeIt;
1.265 - ///\e
1.266 + //\e
1.267 typedef typename Graph::Edge Edge;
1.268 - ///\e
1.269 + //\e
1.270 typedef typename Graph::OutEdgeIt OutEdgeIt;
1.271
1.272 - ///The type of the map that stores the edge lengths.
1.273 + //The type of the map that stores the edge lengths.
1.274 typedef typename TR::LengthMap LengthMap;
1.275 - ///The type of the length of the edges.
1.276 + //The type of the length of the edges.
1.277 typedef typename LengthMap::Value Value;
1.278 - ///\brief The type of the map that stores the last
1.279 - ///edges of the shortest paths.
1.280 + //\brief The type of the map that stores the last
1.281 + //edges of the shortest paths.
1.282 typedef typename TR::PredMap PredMap;
1.283 - ///\brief The type of the map that stores the last but one
1.284 - ///nodes of the shortest paths.
1.285 + //\brief The type of the map that stores the last but one
1.286 + //nodes of the shortest paths.
1.287 typedef typename TR::PredNodeMap PredNodeMap;
1.288 - ///The type of the map that stores the dists of the nodes.
1.289 + //The type of the map that stores the dists of the nodes.
1.290 typedef typename TR::DistMap DistMap;
1.291
1.292 - ///The heap type used by the dijkstra algorithm.
1.293 + //The heap type used by the dijkstra algorithm.
1.294 typedef typename TR::Heap Heap;
1.295 public:
1.296 DijkstraWizard() : TR() {}
1.297 @@ -552,6 +585,7 @@
1.298 ///\e
1.299 void run()
1.300 {
1.301 + if(_source==0) throw UninitializedData();
1.302 Dijkstra<Graph,LengthMap,TR> Dij(*(Graph*)_g,*(LengthMap*)_length);
1.303 if(_pred) Dij.predMap(*(PredMap*)_pred);
1.304 if(_predNode) Dij.predNodeMap(*(PredNodeMap*)_predNode);