1.1 --- a/src/lemon/dijkstra.h Wed Mar 16 07:52:16 2005 +0000
1.2 +++ b/src/lemon/dijkstra.h Wed Mar 16 07:56:25 2005 +0000
1.3 @@ -76,40 +76,41 @@
1.4 {
1.5 return new PredMap(G);
1.6 }
1.7 - ///\brief The type of the map that stores the last but one
1.8 - ///nodes of the shortest paths.
1.9 - ///
1.10 - ///The type of the map that stores the last but one
1.11 - ///nodes of the shortest paths.
1.12 - ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.13 - ///
1.14 - typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
1.15 - ///Instantiates a PredNodeMap.
1.16 +// ///\brief The type of the map that stores the last but one
1.17 +// ///nodes of the shortest paths.
1.18 +// ///
1.19 +// ///The type of the map that stores the last but one
1.20 +// ///nodes of the shortest paths.
1.21 +// ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.22 +// ///
1.23 +// typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
1.24 +// ///Instantiates a PredNodeMap.
1.25
1.26 - ///This function instantiates a \ref PredNodeMap.
1.27 - ///\param G is the graph, to which
1.28 - ///we would like to define the \ref PredNodeMap
1.29 - static PredNodeMap *createPredNodeMap(const GR &G)
1.30 - {
1.31 - return new PredNodeMap();
1.32 - }
1.33 +// ///This function instantiates a \ref PredNodeMap.
1.34 +// ///\param G is the graph, to which
1.35 +// ///we would like to define the \ref PredNodeMap
1.36 +// static PredNodeMap *createPredNodeMap(const GR &G)
1.37 +// {
1.38 +// return new PredNodeMap();
1.39 +// }
1.40
1.41 - ///The type of the map that stores whether a nodes is reached.
1.42 + ///The type of the map that stores whether a nodes is processed.
1.43
1.44 - ///The type of the map that stores whether a nodes is reached.
1.45 + ///The type of the map that stores whether a nodes is processed.
1.46 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.47 ///By default it is a NullMap.
1.48 - ///\todo If it is set to a real map, Dijkstra::reached() should read this.
1.49 + ///\todo If it is set to a real map,
1.50 + ///Dijkstra::processed() should read this.
1.51 ///\todo named parameter to set this type, function to read and write.
1.52 - typedef NullMap<typename Graph::Node,bool> ReachedMap;
1.53 - ///Instantiates a ReachedMap.
1.54 + typedef NullMap<typename Graph::Node,bool> ProcessedMap;
1.55 + ///Instantiates a ProcessedMap.
1.56
1.57 - ///This function instantiates a \ref ReachedMap.
1.58 + ///This function instantiates a \ref ProcessedMap.
1.59 ///\param G is the graph, to which
1.60 - ///we would like to define the \ref ReachedMap
1.61 - static ReachedMap *createReachedMap(const GR &G)
1.62 + ///we would like to define the \ref ProcessedMap
1.63 + static ProcessedMap *createProcessedMap(const GR &G)
1.64 {
1.65 - return new ReachedMap();
1.66 + return new ProcessedMap();
1.67 }
1.68 ///The type of the map that stores the dists of the nodes.
1.69
1.70 @@ -140,23 +141,21 @@
1.71 ///
1.72 ///It is also possible to change the underlying priority heap.
1.73 ///
1.74 - ///\param GR The graph type the algorithm runs on. The default value is
1.75 - ///\ref ListGraph. The value of GR is not used directly by Dijkstra, it
1.76 - ///is only passed to \ref DijkstraDefaultTraits.
1.77 - ///\param LM This read-only
1.78 - ///EdgeMap
1.79 - ///determines the
1.80 - ///lengths of the edges. It is read once for each edge, so the map
1.81 - ///may involve in relatively time consuming process to compute the edge
1.82 - ///length if it is necessary. The default map type is
1.83 - ///\ref concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>".
1.84 - ///The value of LM is not used directly by Dijkstra, it
1.85 - ///is only passed to \ref DijkstraDefaultTraits.
1.86 - ///\param TR Traits class to set various data types used by the algorithm.
1.87 - ///The default traits class is
1.88 - ///\ref DijkstraDefaultTraits "DijkstraDefaultTraits<GR,LM>".
1.89 - ///See \ref DijkstraDefaultTraits for the documentation of
1.90 - ///a Dijkstra traits class.
1.91 + ///\param GR The graph type the algorithm runs on. The default value
1.92 + ///is \ref ListGraph. The value of GR is not used directly by
1.93 + ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.
1.94 + ///\param LM This read-only EdgeMap determines the lengths of the
1.95 + ///edges. It is read once for each edge, so the map may involve in
1.96 + ///relatively time consuming process to compute the edge length if
1.97 + ///it is necessary. The default map type is \ref
1.98 + ///concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value
1.99 + ///of LM is not used directly by Dijkstra, it is only passed to \ref
1.100 + ///DijkstraDefaultTraits. \param TR Traits class to set
1.101 + ///various data types used by the algorithm. The default traits
1.102 + ///class is \ref DijkstraDefaultTraits
1.103 + ///"DijkstraDefaultTraits<GR,LM>". See \ref
1.104 + ///DijkstraDefaultTraits for the documentation of a Dijkstra traits
1.105 + ///class.
1.106 ///
1.107 ///\author Jacint Szabo and Alpar Juttner
1.108 ///\todo A compare object would be nice.
1.109 @@ -181,7 +180,7 @@
1.110 class UninitializedParameter : public lemon::UninitializedParameter {
1.111 public:
1.112 virtual const char* exceptionName() const {
1.113 - return "lemon::Dijsktra::UninitializedParameter";
1.114 + return "lemon::Dijkstra::UninitializedParameter";
1.115 }
1.116 };
1.117
1.118 @@ -204,11 +203,11 @@
1.119 ///\brief The type of the map that stores the last
1.120 ///edges of the shortest paths.
1.121 typedef typename TR::PredMap PredMap;
1.122 - ///\brief The type of the map that stores the last but one
1.123 - ///nodes of the shortest paths.
1.124 - typedef typename TR::PredNodeMap PredNodeMap;
1.125 - ///The type of the map indicating if a node is reached.
1.126 - typedef typename TR::ReachedMap ReachedMap;
1.127 +// ///\brief The type of the map that stores the last but one
1.128 +// ///nodes of the shortest paths.
1.129 +// typedef typename TR::PredNodeMap PredNodeMap;
1.130 + ///The type of the map indicating if a node is processed.
1.131 + typedef typename TR::ProcessedMap ProcessedMap;
1.132 ///The type of the map that stores the dists of the nodes.
1.133 typedef typename TR::DistMap DistMap;
1.134 ///The heap type used by the dijkstra algorithm.
1.135 @@ -222,21 +221,21 @@
1.136 PredMap *_pred;
1.137 ///Indicates if \ref _pred is locally allocated (\c true) or not.
1.138 bool local_pred;
1.139 - ///Pointer to the map of predecessors nodes.
1.140 - PredNodeMap *_predNode;
1.141 - ///Indicates if \ref _predNode is locally allocated (\c true) or not.
1.142 - bool local_predNode;
1.143 +// ///Pointer to the map of predecessors nodes.
1.144 +// PredNodeMap *_predNode;
1.145 +// ///Indicates if \ref _predNode is locally allocated (\c true) or not.
1.146 +// bool local_predNode;
1.147 ///Pointer to the map of distances.
1.148 DistMap *_dist;
1.149 ///Indicates if \ref _dist is locally allocated (\c true) or not.
1.150 bool local_dist;
1.151 - ///Pointer to the map of reached status of the nodes.
1.152 - ReachedMap *_reached;
1.153 - ///Indicates if \ref _reached is locally allocated (\c true) or not.
1.154 - bool local_reached;
1.155 + ///Pointer to the map of processed status of the nodes.
1.156 + ProcessedMap *_processed;
1.157 + ///Indicates if \ref _processed is locally allocated (\c true) or not.
1.158 + bool local_processed;
1.159
1.160 - ///The source node of the last execution.
1.161 - Node source;
1.162 +// ///The source node of the last execution.
1.163 +// Node source;
1.164
1.165 ///Creates the maps if necessary.
1.166
1.167 @@ -248,17 +247,17 @@
1.168 local_pred = true;
1.169 _pred = Traits::createPredMap(*G);
1.170 }
1.171 - if(!_predNode) {
1.172 - local_predNode = true;
1.173 - _predNode = Traits::createPredNodeMap(*G);
1.174 - }
1.175 +// if(!_predNode) {
1.176 +// local_predNode = true;
1.177 +// _predNode = Traits::createPredNodeMap(*G);
1.178 +// }
1.179 if(!_dist) {
1.180 local_dist = true;
1.181 _dist = Traits::createDistMap(*G);
1.182 }
1.183 - if(!_reached) {
1.184 - local_reached = true;
1.185 - _reached = Traits::createReachedMap(*G);
1.186 + if(!_processed) {
1.187 + local_processed = true;
1.188 + _processed = Traits::createProcessedMap(*G);
1.189 }
1.190 }
1.191
1.192 @@ -285,22 +284,22 @@
1.193 LengthMap,
1.194 DefPredMapTraits<T> > { };
1.195
1.196 - template <class T>
1.197 - struct DefPredNodeMapTraits : public Traits {
1.198 - typedef T PredNodeMap;
1.199 - static PredNodeMap *createPredNodeMap(const Graph &G)
1.200 - {
1.201 - throw UninitializedParameter();
1.202 - }
1.203 - };
1.204 - ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
1.205 +// template <class T>
1.206 +// struct DefPredNodeMapTraits : public Traits {
1.207 +// typedef T PredNodeMap;
1.208 +// static PredNodeMap *createPredNodeMap(const Graph &G)
1.209 +// {
1.210 +// throw UninitializedParameter();
1.211 +// }
1.212 +// };
1.213 +// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
1.214
1.215 - ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
1.216 - ///
1.217 - template <class T>
1.218 - class DefPredNodeMap : public Dijkstra< Graph,
1.219 - LengthMap,
1.220 - DefPredNodeMapTraits<T> > { };
1.221 +// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
1.222 +// ///
1.223 +// template <class T>
1.224 +// class DefPredNodeMap : public Dijkstra< Graph,
1.225 +// LengthMap,
1.226 +// DefPredNodeMapTraits<T> > { };
1.227
1.228 template <class T>
1.229 struct DefDistMapTraits : public Traits {
1.230 @@ -320,40 +319,40 @@
1.231 DefDistMapTraits<T> > { };
1.232
1.233 template <class T>
1.234 - struct DefReachedMapTraits : public Traits {
1.235 - typedef T ReachedMap;
1.236 - static ReachedMap *createReachedMap(const Graph &G)
1.237 + struct DefProcessedMapTraits : public Traits {
1.238 + typedef T ProcessedMap;
1.239 + static ProcessedMap *createProcessedMap(const Graph &G)
1.240 {
1.241 throw UninitializedParameter();
1.242 }
1.243 };
1.244 - ///\ref named-templ-param "Named parameter" for setting ReachedMap type
1.245 + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
1.246
1.247 - ///\ref named-templ-param "Named parameter" for setting ReachedMap type
1.248 + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
1.249 ///
1.250 template <class T>
1.251 - class DefReachedMap : public Dijkstra< Graph,
1.252 + class DefProcessedMap : public Dijkstra< Graph,
1.253 LengthMap,
1.254 - DefReachedMapTraits<T> > { };
1.255 + DefProcessedMapTraits<T> > { };
1.256
1.257 - struct DefGraphReachedMapTraits : public Traits {
1.258 - typedef typename Graph::template NodeMap<bool> ReachedMap;
1.259 - static ReachedMap *createReachedMap(const Graph &G)
1.260 + struct DefGraphProcessedMapTraits : public Traits {
1.261 + typedef typename Graph::template NodeMap<bool> ProcessedMap;
1.262 + static ProcessedMap *createProcessedMap(const Graph &G)
1.263 {
1.264 - return new ReachedMap(G);
1.265 + return new ProcessedMap(G);
1.266 }
1.267 };
1.268 ///\brief \ref named-templ-param "Named parameter"
1.269 - ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
1.270 + ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
1.271 ///
1.272 ///\ref named-templ-param "Named parameter"
1.273 - ///for setting the ReachedMap type to be Graph::NodeMap<bool>.
1.274 + ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
1.275 ///If you don't set it explicitely, it will be automatically allocated.
1.276 template <class T>
1.277 - class DefReachedMapToBeDefaultMap :
1.278 + class DefProcessedMapToBeDefaultMap :
1.279 public Dijkstra< Graph,
1.280 LengthMap,
1.281 - DefGraphReachedMapTraits> { };
1.282 + DefGraphProcessedMapTraits> { };
1.283
1.284 ///@}
1.285
1.286 @@ -370,9 +369,9 @@
1.287 Dijkstra(const Graph& _G, const LengthMap& _length) :
1.288 G(&_G), length(&_length),
1.289 _pred(NULL), local_pred(false),
1.290 - _predNode(NULL), local_predNode(false),
1.291 +// _predNode(NULL), local_predNode(false),
1.292 _dist(NULL), local_dist(false),
1.293 - _reached(NULL), local_reached(false),
1.294 + _processed(NULL), local_processed(false),
1.295 _heap_map(*G,-1),_heap(_heap_map)
1.296 { }
1.297
1.298 @@ -380,9 +379,9 @@
1.299 ~Dijkstra()
1.300 {
1.301 if(local_pred) delete _pred;
1.302 - if(local_predNode) delete _predNode;
1.303 +// if(local_predNode) delete _predNode;
1.304 if(local_dist) delete _dist;
1.305 - if(local_reached) delete _reached;
1.306 + if(local_processed) delete _processed;
1.307 }
1.308
1.309 ///Sets the length map.
1.310 @@ -412,22 +411,22 @@
1.311 return *this;
1.312 }
1.313
1.314 - ///Sets the map storing the predecessor nodes.
1.315 +// ///Sets the map storing the predecessor nodes.
1.316
1.317 - ///Sets the map storing the predecessor nodes.
1.318 - ///If you don't use this function before calling \ref run(),
1.319 - ///it will allocate one. The destuctor deallocates this
1.320 - ///automatically allocated map, of course.
1.321 - ///\return <tt> (*this) </tt>
1.322 - Dijkstra &predNodeMap(PredNodeMap &m)
1.323 - {
1.324 - if(local_predNode) {
1.325 - delete _predNode;
1.326 - local_predNode=false;
1.327 - }
1.328 - _predNode = &m;
1.329 - return *this;
1.330 - }
1.331 +// ///Sets the map storing the predecessor nodes.
1.332 +// ///If you don't use this function before calling \ref run(),
1.333 +// ///it will allocate one. The destuctor deallocates this
1.334 +// ///automatically allocated map, of course.
1.335 +// ///\return <tt> (*this) </tt>
1.336 +// Dijkstra &predNodeMap(PredNodeMap &m)
1.337 +// {
1.338 +// if(local_predNode) {
1.339 +// delete _predNode;
1.340 +// local_predNode=false;
1.341 +// }
1.342 +// _predNode = &m;
1.343 +// return *this;
1.344 +// }
1.345
1.346 ///Sets the map storing the distances calculated by the algorithm.
1.347
1.348 @@ -449,19 +448,21 @@
1.349 private:
1.350 void finalizeNodeData(Node v,Value dst)
1.351 {
1.352 - _reached->set(v,true);
1.353 + _processed->set(v,true);
1.354 _dist->set(v, dst);
1.355 - if((*_pred)[v]!=INVALID) _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do?
1.356 +// if((*_pred)[v]!=INVALID)
1.357 +// _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do?
1.358 }
1.359
1.360 public:
1.361 - ///\name Excetution control
1.362 + ///\name Execution control
1.363 ///The simplest way to execute the algorithm is to use
1.364 ///one of the member functions called \c run(...).
1.365 ///\n
1.366 - ///It you need more control on the execution,
1.367 + ///If you need more control on the execution,
1.368 ///first you must call \ref init(), then you can add several source nodes
1.369 - ///with \ref addSource(). Finally \ref start() will perform the actual path
1.370 + ///with \ref addSource().
1.371 + ///Finally \ref start() will perform the actual path
1.372 ///computation.
1.373
1.374 ///@{
1.375 @@ -477,8 +478,8 @@
1.376
1.377 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
1.378 _pred->set(u,INVALID);
1.379 - _predNode->set(u,INVALID);
1.380 - ///\todo *_reached is not set to false.
1.381 +// _predNode->set(u,INVALID);
1.382 + _processed->set(u,false);
1.383 _heap_map.set(u,Heap::PRE_HEAP);
1.384 }
1.385 }
1.386 @@ -494,7 +495,7 @@
1.387 ///or the shortest path found till then is longer then \c dst.
1.388 void addSource(Node s,Value dst=0)
1.389 {
1.390 - source = s;
1.391 +// source = s;
1.392 if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
1.393 else if(_heap[s]<dst) {
1.394 _heap.push(s,dst);
1.395 @@ -535,16 +536,17 @@
1.396 }
1.397 }
1.398
1.399 - ///Returns \c false if there are nodes to be processed in the priority heap
1.400 -
1.401 - ///Returns \c false if there are nodes to be processed in the priority heap
1.402 + ///\brief Returns \c false if there are nodes
1.403 + ///to be processed in the priority heap
1.404 ///
1.405 - bool emptyHeap() { return _heap.empty(); }
1.406 + ///Returns \c false if there are nodes
1.407 + ///to be processed in the priority heap
1.408 + bool emptyQueue() { return _heap.empty(); }
1.409 ///Returns the number of the nodes to be processed in the priority heap
1.410
1.411 ///Returns the number of the nodes to be processed in the priority heap
1.412 ///
1.413 - int heapSize() { return _heap.size(); }
1.414 + int queueSize() { return _heap.size(); }
1.415
1.416 ///Executes the algorithm.
1.417
1.418 @@ -696,25 +698,107 @@
1.419 ///\pre \ref run() must be called before using this function.
1.420 const PredMap &predMap() const { return *_pred;}
1.421
1.422 - ///Returns a reference to the map of nodes of shortest paths.
1.423 +// ///Returns a reference to the map of nodes of shortest paths.
1.424
1.425 - ///Returns a reference to the NodeMap of the last but one nodes of the
1.426 - ///shortest path tree.
1.427 - ///\pre \ref run() must be called before using this function.
1.428 - const PredNodeMap &predNodeMap() const { return *_predNode;}
1.429 +// ///Returns a reference to the NodeMap of the last but one nodes of the
1.430 +// ///shortest path tree.
1.431 +// ///\pre \ref run() must be called before using this function.
1.432 +// const PredNodeMap &predNodeMap() const { return *_predNode;}
1.433
1.434 ///Checks if a node is reachable from the root.
1.435
1.436 ///Returns \c true if \c v is reachable from the root.
1.437 - ///\warning If the algorithm is started from multiple nodes,
1.438 - ///this function may give false result for the source nodes.
1.439 + ///\warning The source nodes are inditated as unreached.
1.440 ///\pre \ref run() must be called before using this function.
1.441 ///
1.442 - bool reached(Node v) { return v==source || (*_pred)[v]!=INVALID; }
1.443 + bool reached(Node v) { return _heap_map[v]!=Heap::PRE_HEAP; }
1.444
1.445 ///@}
1.446 };
1.447
1.448 +
1.449 +
1.450 +
1.451 +
1.452 + ///Default traits class of Dijkstra function.
1.453 +
1.454 + ///Default traits class of Dijkstra function.
1.455 + ///\param GR Graph type.
1.456 + ///\param LM Type of length map.
1.457 + template<class GR, class LM>
1.458 + struct DijkstraWizardDefaultTraits
1.459 + {
1.460 + ///The graph type the algorithm runs on.
1.461 + typedef GR Graph;
1.462 + ///The type of the map that stores the edge lengths.
1.463 +
1.464 + ///The type of the map that stores the edge lengths.
1.465 + ///It must meet the \ref concept::ReadMap "ReadMap" concept.
1.466 + typedef LM LengthMap;
1.467 + //The type of the length of the edges.
1.468 + typedef typename LM::Value Value;
1.469 + ///The heap type used by Dijkstra algorithm.
1.470 +
1.471 + ///The heap type used by Dijkstra algorithm.
1.472 + ///
1.473 + ///\sa BinHeap
1.474 + ///\sa Dijkstra
1.475 + typedef BinHeap<typename Graph::Node,
1.476 + typename LM::Value,
1.477 + typename GR::template NodeMap<int>,
1.478 + std::less<Value> > Heap;
1.479 +
1.480 + ///\brief The type of the map that stores the last
1.481 + ///edges of the shortest paths.
1.482 + ///
1.483 + ///The type of the map that stores the last
1.484 + ///edges of the shortest paths.
1.485 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.486 + ///
1.487 + typedef NullMap <typename GR::Node,typename GR::Edge> PredMap;
1.488 + ///Instantiates a PredMap.
1.489 +
1.490 + ///This function instantiates a \ref PredMap.
1.491 + ///\param G is the graph, to which we would like to define the PredMap.
1.492 + ///\todo The graph alone may be insufficient for the initialization
1.493 + static PredMap *createPredMap(const GR &G)
1.494 + {
1.495 + return new PredMap();
1.496 + }
1.497 + ///The type of the map that stores whether a nodes is processed.
1.498 +
1.499 + ///The type of the map that stores whether a nodes is processed.
1.500 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.501 + ///By default it is a NullMap.
1.502 + ///\todo If it is set to a real map,
1.503 + ///Dijkstra::processed() should read this.
1.504 + ///\todo named parameter to set this type, function to read and write.
1.505 + typedef NullMap<typename Graph::Node,bool> ProcessedMap;
1.506 + ///Instantiates a ProcessedMap.
1.507 +
1.508 + ///This function instantiates a \ref ProcessedMap.
1.509 + ///\param G is the graph, to which
1.510 + ///we would like to define the \ref ProcessedMap
1.511 + static ProcessedMap *createProcessedMap(const GR &G)
1.512 + {
1.513 + return new ProcessedMap();
1.514 + }
1.515 + ///The type of the map that stores the dists of the nodes.
1.516 +
1.517 + ///The type of the map that stores the dists of the nodes.
1.518 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.519 + ///
1.520 + typedef NullMap<typename Graph::Node,typename LM::Value> DistMap;
1.521 + ///Instantiates a DistMap.
1.522 +
1.523 + ///This function instantiates a \ref DistMap.
1.524 + ///\param G is the graph, to which we would like to define the \ref DistMap
1.525 + static DistMap *createDistMap(const GR &G)
1.526 + {
1.527 + return new DistMap();
1.528 + }
1.529 + };
1.530 +
1.531 /// Default traits used by \ref DijkstraWizard
1.532
1.533 /// To make it easier to use Dijkstra algorithm
1.534 @@ -724,10 +808,10 @@
1.535 /// The \ref DijkstraWizardBase is a class to be the default traits of the
1.536 /// \ref DijkstraWizard class.
1.537 template<class GR,class LM>
1.538 - class DijkstraWizardBase : public DijkstraDefaultTraits<GR,LM>
1.539 + class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
1.540 {
1.541
1.542 - typedef DijkstraDefaultTraits<GR,LM> Base;
1.543 + typedef DijkstraWizardDefaultTraits<GR,LM> Base;
1.544 protected:
1.545 /// Type of the nodes in the graph.
1.546 typedef typename Base::Graph::Node Node;
1.547 @@ -738,8 +822,8 @@
1.548 void *_length;
1.549 ///Pointer to the map of predecessors edges.
1.550 void *_pred;
1.551 - ///Pointer to the map of predecessors nodes.
1.552 - void *_predNode;
1.553 +// ///Pointer to the map of predecessors nodes.
1.554 +// void *_predNode;
1.555 ///Pointer to the map of distances.
1.556 void *_dist;
1.557 ///Pointer to the source node.
1.558 @@ -750,8 +834,9 @@
1.559
1.560 /// This constructor does not require parameters, therefore it initiates
1.561 /// all of the attributes to default values (0, INVALID).
1.562 - DijkstraWizardBase() : _g(0), _length(0), _pred(0), _predNode(0),
1.563 - _dist(0), _source(INVALID) {}
1.564 + DijkstraWizardBase() : _g(0), _length(0), _pred(0),
1.565 +// _predNode(0),
1.566 + _dist(0), _source(INVALID) {}
1.567
1.568 /// Constructor.
1.569
1.570 @@ -762,14 +847,14 @@
1.571 /// \param l is the initial value of \ref _length
1.572 /// \param s is the initial value of \ref _source
1.573 DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
1.574 - _g((void *)&g), _length((void *)&l), _pred(0), _predNode(0),
1.575 - _dist(0), _source(s) {}
1.576 + _g((void *)&g), _length((void *)&l), _pred(0),
1.577 +// _predNode(0),
1.578 + _dist(0), _source(s) {}
1.579
1.580 };
1.581
1.582 /// A class to make easier the usage of Dijkstra algorithm
1.583
1.584 - /// \ingroup flowalgs
1.585 /// This class is created to make it easier to use Dijkstra algorithm.
1.586 /// It uses the functions and features of the plain \ref Dijkstra,
1.587 /// but it is much simpler to use it.
1.588 @@ -810,9 +895,9 @@
1.589 ///\brief The type of the map that stores the last
1.590 ///edges of the shortest paths.
1.591 typedef typename TR::PredMap PredMap;
1.592 - ///\brief The type of the map that stores the last but one
1.593 - ///nodes of the shortest paths.
1.594 - typedef typename TR::PredNodeMap PredNodeMap;
1.595 +// ///\brief The type of the map that stores the last but one
1.596 +// ///nodes of the shortest paths.
1.597 +// typedef typename TR::PredNodeMap PredNodeMap;
1.598 ///The type of the map that stores the dists of the nodes.
1.599 typedef typename TR::DistMap DistMap;
1.600
1.601 @@ -844,7 +929,7 @@
1.602 Dijkstra<Graph,LengthMap,TR>
1.603 Dij(*(Graph*)Base::_g,*(LengthMap*)Base::_length);
1.604 if(Base::_pred) Dij.predMap(*(PredMap*)Base::_pred);
1.605 - if(Base::_predNode) Dij.predNodeMap(*(PredNodeMap*)Base::_predNode);
1.606 +// if(Base::_predNode) Dij.predNodeMap(*(PredNodeMap*)Base::_predNode);
1.607 if(Base::_dist) Dij.distMap(*(DistMap*)Base::_dist);
1.608 Dij.run(Base::_source);
1.609 }
1.610 @@ -880,25 +965,25 @@
1.611 }
1.612
1.613
1.614 - template<class T>
1.615 - struct DefPredNodeMapBase : public Base {
1.616 - typedef T PredNodeMap;
1.617 - static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
1.618 - DefPredNodeMapBase(const Base &b) : Base(b) {}
1.619 - };
1.620 +// template<class T>
1.621 +// struct DefPredNodeMapBase : public Base {
1.622 +// typedef T PredNodeMap;
1.623 +// static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
1.624 +// DefPredNodeMapBase(const Base &b) : Base(b) {}
1.625 +// };
1.626
1.627 - ///\brief \ref named-templ-param "Named parameter"
1.628 - ///function for setting PredNodeMap type
1.629 - ///
1.630 - /// \ref named-templ-param "Named parameter"
1.631 - ///function for setting PredNodeMap type
1.632 - ///
1.633 - template<class T>
1.634 - DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1.635 - {
1.636 - Base::_predNode=(void *)&t;
1.637 - return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
1.638 - }
1.639 +// ///\brief \ref named-templ-param "Named parameter"
1.640 +// ///function for setting PredNodeMap type
1.641 +// ///
1.642 +// /// \ref named-templ-param "Named parameter"
1.643 +// ///function for setting PredNodeMap type
1.644 +// ///
1.645 +// template<class T>
1.646 +// DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1.647 +// {
1.648 +// Base::_predNode=(void *)&t;
1.649 +// return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
1.650 +// }
1.651
1.652 template<class T>
1.653 struct DefDistMapBase : public Base {
1.654 @@ -932,11 +1017,23 @@
1.655
1.656 };
1.657
1.658 - ///\e
1.659 + ///Function type interface for Dijkstra algorithm.
1.660
1.661 /// \ingroup flowalgs
1.662 - ///\todo Please document...
1.663 + ///Function type interface for Dijkstra algorithm.
1.664 ///
1.665 + ///This function also has several
1.666 + ///\ref named-templ-func-param "named parameters",
1.667 + ///they are declared as the members of class \ref DijkstraWizard.
1.668 + ///The following
1.669 + ///example shows how to use these parameters.
1.670 + ///\code
1.671 + /// dijkstra(g,length,source).predMap(preds).run();
1.672 + ///\endcode
1.673 + ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
1.674 + ///to the end of the parameter list.
1.675 + ///\sa DijkstraWizard
1.676 + ///\sa Dijkstra
1.677 template<class GR, class LM>
1.678 DijkstraWizard<DijkstraWizardBase<GR,LM> >
1.679 dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
1.680 @@ -944,8 +1041,6 @@
1.681 return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
1.682 }
1.683
1.684 -/// @}
1.685 -
1.686 } //END OF NAMESPACE LEMON
1.687
1.688 #endif