1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/dijkstra.h Mon May 23 04:48:14 2005 +0000
1.3 @@ -0,0 +1,1074 @@
1.4 +/* -*- C++ -*-
1.5 + * lemon/dijkstra.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +#ifndef LEMON_DIJKSTRA_H
1.21 +#define LEMON_DIJKSTRA_H
1.22 +
1.23 +///\ingroup flowalgs
1.24 +///\file
1.25 +///\brief Dijkstra algorithm.
1.26 +///
1.27 +///\todo getPath() should be implemented! (also for BFS and DFS)
1.28 +
1.29 +#include <lemon/list_graph.h>
1.30 +#include <lemon/bin_heap.h>
1.31 +#include <lemon/invalid.h>
1.32 +#include <lemon/error.h>
1.33 +#include <lemon/maps.h>
1.34 +
1.35 +namespace lemon {
1.36 +
1.37 +
1.38 +
1.39 + ///Default traits class of Dijkstra class.
1.40 +
1.41 + ///Default traits class of Dijkstra class.
1.42 + ///\param GR Graph type.
1.43 + ///\param LM Type of length map.
1.44 + template<class GR, class LM>
1.45 + struct DijkstraDefaultTraits
1.46 + {
1.47 + ///The graph type the algorithm runs on.
1.48 + typedef GR Graph;
1.49 + ///The type of the map that stores the edge lengths.
1.50 +
1.51 + ///The type of the map that stores the edge lengths.
1.52 + ///It must meet the \ref concept::ReadMap "ReadMap" concept.
1.53 + typedef LM LengthMap;
1.54 + //The type of the length of the edges.
1.55 + typedef typename LM::Value Value;
1.56 + ///The heap type used by Dijkstra algorithm.
1.57 +
1.58 + ///The heap type used by Dijkstra algorithm.
1.59 + ///
1.60 + ///\sa BinHeap
1.61 + ///\sa Dijkstra
1.62 + typedef BinHeap<typename Graph::Node,
1.63 + typename LM::Value,
1.64 + typename GR::template NodeMap<int>,
1.65 + std::less<Value> > Heap;
1.66 +
1.67 + ///\brief The type of the map that stores the last
1.68 + ///edges of the shortest paths.
1.69 + ///
1.70 + ///The type of the map that stores the last
1.71 + ///edges of the shortest paths.
1.72 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.73 + ///
1.74 + typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
1.75 + ///Instantiates a PredMap.
1.76 +
1.77 + ///This function instantiates a \ref PredMap.
1.78 + ///\param G is the graph, to which we would like to define the PredMap.
1.79 + ///\todo The graph alone may be insufficient for the initialization
1.80 + static PredMap *createPredMap(const GR &G)
1.81 + {
1.82 + return new PredMap(G);
1.83 + }
1.84 +// ///\brief The type of the map that stores the last but one
1.85 +// ///nodes of the shortest paths.
1.86 +// ///
1.87 +// ///The type of the map that stores the last but one
1.88 +// ///nodes of the shortest paths.
1.89 +// ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.90 +// ///
1.91 +// typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
1.92 +// ///Instantiates a PredNodeMap.
1.93 +
1.94 +// ///This function instantiates a \ref PredNodeMap.
1.95 +// ///\param G is the graph, to which
1.96 +// ///we would like to define the \ref PredNodeMap
1.97 +// static PredNodeMap *createPredNodeMap(const GR &G)
1.98 +// {
1.99 +// return new PredNodeMap();
1.100 +// }
1.101 +
1.102 + ///The type of the map that stores whether a nodes is processed.
1.103 +
1.104 + ///The type of the map that stores whether a nodes is processed.
1.105 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.106 + ///By default it is a NullMap.
1.107 + ///\todo If it is set to a real map,
1.108 + ///Dijkstra::processed() should read this.
1.109 + ///\todo named parameter to set this type, function to read and write.
1.110 + typedef NullMap<typename Graph::Node,bool> ProcessedMap;
1.111 + ///Instantiates a ProcessedMap.
1.112 +
1.113 + ///This function instantiates a \ref ProcessedMap.
1.114 + ///\param G is the graph, to which
1.115 + ///we would like to define the \ref ProcessedMap
1.116 + static ProcessedMap *createProcessedMap(const GR &)
1.117 + {
1.118 + return new ProcessedMap();
1.119 + }
1.120 + ///The type of the map that stores the dists of the nodes.
1.121 +
1.122 + ///The type of the map that stores the dists of the nodes.
1.123 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.124 + ///
1.125 + typedef typename Graph::template NodeMap<typename LM::Value> DistMap;
1.126 + ///Instantiates a DistMap.
1.127 +
1.128 + ///This function instantiates a \ref DistMap.
1.129 + ///\param G is the graph, to which we would like to define the \ref DistMap
1.130 + static DistMap *createDistMap(const GR &G)
1.131 + {
1.132 + return new DistMap(G);
1.133 + }
1.134 + };
1.135 +
1.136 + ///%Dijkstra algorithm class.
1.137 +
1.138 + /// \ingroup flowalgs
1.139 + ///This class provides an efficient implementation of %Dijkstra algorithm.
1.140 + ///The edge lengths are passed to the algorithm using a
1.141 + ///\ref concept::ReadMap "ReadMap",
1.142 + ///so it is easy to change it to any kind of length.
1.143 + ///
1.144 + ///The type of the length is determined by the
1.145 + ///\ref concept::ReadMap::Value "Value" of the length map.
1.146 + ///
1.147 + ///It is also possible to change the underlying priority heap.
1.148 + ///
1.149 + ///\param GR The graph type the algorithm runs on. The default value
1.150 + ///is \ref ListGraph. The value of GR is not used directly by
1.151 + ///Dijkstra, it is only passed to \ref DijkstraDefaultTraits.
1.152 + ///\param LM This read-only EdgeMap determines the lengths of the
1.153 + ///edges. It is read once for each edge, so the map may involve in
1.154 + ///relatively time consuming process to compute the edge length if
1.155 + ///it is necessary. The default map type is \ref
1.156 + ///concept::StaticGraph::EdgeMap "Graph::EdgeMap<int>". The value
1.157 + ///of LM is not used directly by Dijkstra, it is only passed to \ref
1.158 + ///DijkstraDefaultTraits. \param TR Traits class to set
1.159 + ///various data types used by the algorithm. The default traits
1.160 + ///class is \ref DijkstraDefaultTraits
1.161 + ///"DijkstraDefaultTraits<GR,LM>". See \ref
1.162 + ///DijkstraDefaultTraits for the documentation of a Dijkstra traits
1.163 + ///class.
1.164 + ///
1.165 + ///\author Jacint Szabo and Alpar Juttner
1.166 + ///\todo A compare object would be nice.
1.167 +
1.168 +#ifdef DOXYGEN
1.169 + template <typename GR,
1.170 + typename LM,
1.171 + typename TR>
1.172 +#else
1.173 + template <typename GR=ListGraph,
1.174 + typename LM=typename GR::template EdgeMap<int>,
1.175 + typename TR=DijkstraDefaultTraits<GR,LM> >
1.176 +#endif
1.177 + class Dijkstra {
1.178 + public:
1.179 + /**
1.180 + * \brief \ref Exception for uninitialized parameters.
1.181 + *
1.182 + * This error represents problems in the initialization
1.183 + * of the parameters of the algorithms.
1.184 + */
1.185 + class UninitializedParameter : public lemon::UninitializedParameter {
1.186 + public:
1.187 + virtual const char* exceptionName() const {
1.188 + return "lemon::Dijkstra::UninitializedParameter";
1.189 + }
1.190 + };
1.191 +
1.192 + typedef TR Traits;
1.193 + ///The type of the underlying graph.
1.194 + typedef typename TR::Graph Graph;
1.195 + ///\e
1.196 + typedef typename Graph::Node Node;
1.197 + ///\e
1.198 + typedef typename Graph::NodeIt NodeIt;
1.199 + ///\e
1.200 + typedef typename Graph::Edge Edge;
1.201 + ///\e
1.202 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.203 +
1.204 + ///The type of the length of the edges.
1.205 + typedef typename TR::LengthMap::Value Value;
1.206 + ///The type of the map that stores the edge lengths.
1.207 + typedef typename TR::LengthMap LengthMap;
1.208 + ///\brief The type of the map that stores the last
1.209 + ///edges of the shortest paths.
1.210 + typedef typename TR::PredMap PredMap;
1.211 +// ///\brief The type of the map that stores the last but one
1.212 +// ///nodes of the shortest paths.
1.213 +// typedef typename TR::PredNodeMap PredNodeMap;
1.214 + ///The type of the map indicating if a node is processed.
1.215 + typedef typename TR::ProcessedMap ProcessedMap;
1.216 + ///The type of the map that stores the dists of the nodes.
1.217 + typedef typename TR::DistMap DistMap;
1.218 + ///The heap type used by the dijkstra algorithm.
1.219 + typedef typename TR::Heap Heap;
1.220 + private:
1.221 + /// Pointer to the underlying graph.
1.222 + const Graph *G;
1.223 + /// Pointer to the length map
1.224 + const LengthMap *length;
1.225 + ///Pointer to the map of predecessors edges.
1.226 + PredMap *_pred;
1.227 + ///Indicates if \ref _pred is locally allocated (\c true) or not.
1.228 + bool local_pred;
1.229 +// ///Pointer to the map of predecessors nodes.
1.230 +// PredNodeMap *_predNode;
1.231 +// ///Indicates if \ref _predNode is locally allocated (\c true) or not.
1.232 +// bool local_predNode;
1.233 + ///Pointer to the map of distances.
1.234 + DistMap *_dist;
1.235 + ///Indicates if \ref _dist is locally allocated (\c true) or not.
1.236 + bool local_dist;
1.237 + ///Pointer to the map of processed status of the nodes.
1.238 + ProcessedMap *_processed;
1.239 + ///Indicates if \ref _processed is locally allocated (\c true) or not.
1.240 + bool local_processed;
1.241 +
1.242 +// ///The source node of the last execution.
1.243 +// Node source;
1.244 +
1.245 + ///Creates the maps if necessary.
1.246 +
1.247 + ///\todo Error if \c G or are \c NULL. What about \c length?
1.248 + ///\todo Better memory allocation (instead of new).
1.249 + void create_maps()
1.250 + {
1.251 + if(!_pred) {
1.252 + local_pred = true;
1.253 + _pred = Traits::createPredMap(*G);
1.254 + }
1.255 +// if(!_predNode) {
1.256 +// local_predNode = true;
1.257 +// _predNode = Traits::createPredNodeMap(*G);
1.258 +// }
1.259 + if(!_dist) {
1.260 + local_dist = true;
1.261 + _dist = Traits::createDistMap(*G);
1.262 + }
1.263 + if(!_processed) {
1.264 + local_processed = true;
1.265 + _processed = Traits::createProcessedMap(*G);
1.266 + }
1.267 + }
1.268 +
1.269 + public :
1.270 +
1.271 + ///\name Named template parameters
1.272 +
1.273 + ///@{
1.274 +
1.275 + template <class T>
1.276 + struct DefPredMapTraits : public Traits {
1.277 + typedef T PredMap;
1.278 + static PredMap *createPredMap(const Graph &G)
1.279 + {
1.280 + throw UninitializedParameter();
1.281 + }
1.282 + };
1.283 + ///\ref named-templ-param "Named parameter" for setting PredMap type
1.284 +
1.285 + ///\ref named-templ-param "Named parameter" for setting PredMap type
1.286 + ///
1.287 + template <class T>
1.288 + class DefPredMap : public Dijkstra< Graph,
1.289 + LengthMap,
1.290 + DefPredMapTraits<T> > { };
1.291 +
1.292 +// template <class T>
1.293 +// struct DefPredNodeMapTraits : public Traits {
1.294 +// typedef T PredNodeMap;
1.295 +// static PredNodeMap *createPredNodeMap(const Graph &G)
1.296 +// {
1.297 +// throw UninitializedParameter();
1.298 +// }
1.299 +// };
1.300 +// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
1.301 +
1.302 +// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
1.303 +// ///
1.304 +// template <class T>
1.305 +// class DefPredNodeMap : public Dijkstra< Graph,
1.306 +// LengthMap,
1.307 +// DefPredNodeMapTraits<T> > { };
1.308 +
1.309 + template <class T>
1.310 + struct DefDistMapTraits : public Traits {
1.311 + typedef T DistMap;
1.312 + static DistMap *createDistMap(const Graph &G)
1.313 + {
1.314 + throw UninitializedParameter();
1.315 + }
1.316 + };
1.317 + ///\ref named-templ-param "Named parameter" for setting DistMap type
1.318 +
1.319 + ///\ref named-templ-param "Named parameter" for setting DistMap type
1.320 + ///
1.321 + template <class T>
1.322 + class DefDistMap : public Dijkstra< Graph,
1.323 + LengthMap,
1.324 + DefDistMapTraits<T> > { };
1.325 +
1.326 + template <class T>
1.327 + struct DefProcessedMapTraits : public Traits {
1.328 + typedef T ProcessedMap;
1.329 + static ProcessedMap *createProcessedMap(const Graph &G)
1.330 + {
1.331 + throw UninitializedParameter();
1.332 + }
1.333 + };
1.334 + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
1.335 +
1.336 + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
1.337 + ///
1.338 + template <class T>
1.339 + class DefProcessedMap : public Dijkstra< Graph,
1.340 + LengthMap,
1.341 + DefProcessedMapTraits<T> > { };
1.342 +
1.343 + struct DefGraphProcessedMapTraits : public Traits {
1.344 + typedef typename Graph::template NodeMap<bool> ProcessedMap;
1.345 + static ProcessedMap *createProcessedMap(const Graph &G)
1.346 + {
1.347 + return new ProcessedMap(G);
1.348 + }
1.349 + };
1.350 + ///\brief \ref named-templ-param "Named parameter"
1.351 + ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
1.352 + ///
1.353 + ///\ref named-templ-param "Named parameter"
1.354 + ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
1.355 + ///If you don't set it explicitely, it will be automatically allocated.
1.356 + template <class T>
1.357 + class DefProcessedMapToBeDefaultMap :
1.358 + public Dijkstra< Graph,
1.359 + LengthMap,
1.360 + DefGraphProcessedMapTraits> { };
1.361 +
1.362 + ///@}
1.363 +
1.364 +
1.365 + private:
1.366 + typename Graph::template NodeMap<int> _heap_map;
1.367 + Heap _heap;
1.368 + public:
1.369 +
1.370 + ///Constructor.
1.371 +
1.372 + ///\param _G the graph the algorithm will run on.
1.373 + ///\param _length the length map used by the algorithm.
1.374 + Dijkstra(const Graph& _G, const LengthMap& _length) :
1.375 + G(&_G), length(&_length),
1.376 + _pred(NULL), local_pred(false),
1.377 +// _predNode(NULL), local_predNode(false),
1.378 + _dist(NULL), local_dist(false),
1.379 + _processed(NULL), local_processed(false),
1.380 + _heap_map(*G,-1),_heap(_heap_map)
1.381 + { }
1.382 +
1.383 + ///Destructor.
1.384 + ~Dijkstra()
1.385 + {
1.386 + if(local_pred) delete _pred;
1.387 +// if(local_predNode) delete _predNode;
1.388 + if(local_dist) delete _dist;
1.389 + if(local_processed) delete _processed;
1.390 + }
1.391 +
1.392 + ///Sets the length map.
1.393 +
1.394 + ///Sets the length map.
1.395 + ///\return <tt> (*this) </tt>
1.396 + Dijkstra &lengthMap(const LengthMap &m)
1.397 + {
1.398 + length = &m;
1.399 + return *this;
1.400 + }
1.401 +
1.402 + ///Sets the map storing the predecessor edges.
1.403 +
1.404 + ///Sets the map storing the predecessor edges.
1.405 + ///If you don't use this function before calling \ref run(),
1.406 + ///it will allocate one. The destuctor deallocates this
1.407 + ///automatically allocated map, of course.
1.408 + ///\return <tt> (*this) </tt>
1.409 + Dijkstra &predMap(PredMap &m)
1.410 + {
1.411 + if(local_pred) {
1.412 + delete _pred;
1.413 + local_pred=false;
1.414 + }
1.415 + _pred = &m;
1.416 + return *this;
1.417 + }
1.418 +
1.419 +// ///Sets the map storing the predecessor nodes.
1.420 +
1.421 +// ///Sets the map storing the predecessor nodes.
1.422 +// ///If you don't use this function before calling \ref run(),
1.423 +// ///it will allocate one. The destuctor deallocates this
1.424 +// ///automatically allocated map, of course.
1.425 +// ///\return <tt> (*this) </tt>
1.426 +// Dijkstra &predNodeMap(PredNodeMap &m)
1.427 +// {
1.428 +// if(local_predNode) {
1.429 +// delete _predNode;
1.430 +// local_predNode=false;
1.431 +// }
1.432 +// _predNode = &m;
1.433 +// return *this;
1.434 +// }
1.435 +
1.436 + ///Sets the map storing the distances calculated by the algorithm.
1.437 +
1.438 + ///Sets the map storing the distances calculated by the algorithm.
1.439 + ///If you don't use this function before calling \ref run(),
1.440 + ///it will allocate one. The destuctor deallocates this
1.441 + ///automatically allocated map, of course.
1.442 + ///\return <tt> (*this) </tt>
1.443 + Dijkstra &distMap(DistMap &m)
1.444 + {
1.445 + if(local_dist) {
1.446 + delete _dist;
1.447 + local_dist=false;
1.448 + }
1.449 + _dist = &m;
1.450 + return *this;
1.451 + }
1.452 +
1.453 + private:
1.454 + void finalizeNodeData(Node v,Value dst)
1.455 + {
1.456 + _processed->set(v,true);
1.457 + _dist->set(v, dst);
1.458 +// if((*_pred)[v]!=INVALID)
1.459 +// _predNode->set(v,G->source((*_pred)[v])); ///\todo What to do?
1.460 + }
1.461 +
1.462 + public:
1.463 + ///\name Execution control
1.464 + ///The simplest way to execute the algorithm is to use
1.465 + ///one of the member functions called \c run(...).
1.466 + ///\n
1.467 + ///If you need more control on the execution,
1.468 + ///first you must call \ref init(), then you can add several source nodes
1.469 + ///with \ref addSource().
1.470 + ///Finally \ref start() will perform the actual path
1.471 + ///computation.
1.472 +
1.473 + ///@{
1.474 +
1.475 + ///Initializes the internal data structures.
1.476 +
1.477 + ///Initializes the internal data structures.
1.478 + ///
1.479 + ///\todo _heap_map's type could also be in the traits class.
1.480 + ///\todo The heaps should be able to make themselves empty directly.
1.481 + void init()
1.482 + {
1.483 + create_maps();
1.484 + while(!_heap.empty()) _heap.pop();
1.485 + for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
1.486 + _pred->set(u,INVALID);
1.487 +// _predNode->set(u,INVALID);
1.488 + _processed->set(u,false);
1.489 + _heap_map.set(u,Heap::PRE_HEAP);
1.490 + }
1.491 + }
1.492 +
1.493 + ///Adds a new source node.
1.494 +
1.495 + ///Adds a new source node to the priority heap.
1.496 + ///
1.497 + ///The optional second parameter is the initial distance of the node.
1.498 + ///
1.499 + ///It checks if the node has already been added to the heap and
1.500 + ///It is pushed to the heap only if either it was not in the heap
1.501 + ///or the shortest path found till then is longer then \c dst.
1.502 + void addSource(Node s,Value dst=0)
1.503 + {
1.504 +// source = s;
1.505 + if(_heap.state(s) != Heap::IN_HEAP) _heap.push(s,dst);
1.506 + else if(_heap[s]<dst) {
1.507 + _heap.push(s,dst);
1.508 + _pred->set(s,INVALID);
1.509 + }
1.510 + }
1.511 +
1.512 + ///Processes the next node in the priority heap
1.513 +
1.514 + ///Processes the next node in the priority heap.
1.515 + ///
1.516 + ///\warning The priority heap must not be empty!
1.517 + void processNextNode()
1.518 + {
1.519 + Node v=_heap.top();
1.520 + Value oldvalue=_heap[v];
1.521 + _heap.pop();
1.522 + finalizeNodeData(v,oldvalue);
1.523 +
1.524 + for(OutEdgeIt e(*G,v); e!=INVALID; ++e) {
1.525 + Node w=G->target(e);
1.526 + switch(_heap.state(w)) {
1.527 + case Heap::PRE_HEAP:
1.528 + _heap.push(w,oldvalue+(*length)[e]);
1.529 + _pred->set(w,e);
1.530 +// _predNode->set(w,v);
1.531 + break;
1.532 + case Heap::IN_HEAP:
1.533 + if ( oldvalue+(*length)[e] < _heap[w] ) {
1.534 + _heap.decrease(w, oldvalue+(*length)[e]);
1.535 + _pred->set(w,e);
1.536 +// _predNode->set(w,v);
1.537 + }
1.538 + break;
1.539 + case Heap::POST_HEAP:
1.540 + break;
1.541 + }
1.542 + }
1.543 + }
1.544 +
1.545 + ///\brief Returns \c false if there are nodes
1.546 + ///to be processed in the priority heap
1.547 + ///
1.548 + ///Returns \c false if there are nodes
1.549 + ///to be processed in the priority heap
1.550 + bool emptyQueue() { return _heap.empty(); }
1.551 + ///Returns the number of the nodes to be processed in the priority heap
1.552 +
1.553 + ///Returns the number of the nodes to be processed in the priority heap
1.554 + ///
1.555 + int queueSize() { return _heap.size(); }
1.556 +
1.557 + ///Executes the algorithm.
1.558 +
1.559 + ///Executes the algorithm.
1.560 + ///
1.561 + ///\pre init() must be called and at least one node should be added
1.562 + ///with addSource() before using this function.
1.563 + ///
1.564 + ///This method runs the %Dijkstra algorithm from the root node(s)
1.565 + ///in order to
1.566 + ///compute the
1.567 + ///shortest path to each node. The algorithm computes
1.568 + ///- The shortest path tree.
1.569 + ///- The distance of each node from the root(s).
1.570 + ///
1.571 + void start()
1.572 + {
1.573 + while ( !_heap.empty() ) processNextNode();
1.574 + }
1.575 +
1.576 + ///Executes the algorithm until \c dest is reached.
1.577 +
1.578 + ///Executes the algorithm until \c dest is reached.
1.579 + ///
1.580 + ///\pre init() must be called and at least one node should be added
1.581 + ///with addSource() before using this function.
1.582 + ///
1.583 + ///This method runs the %Dijkstra algorithm from the root node(s)
1.584 + ///in order to
1.585 + ///compute the
1.586 + ///shortest path to \c dest. The algorithm computes
1.587 + ///- The shortest path to \c dest.
1.588 + ///- The distance of \c dest from the root(s).
1.589 + ///
1.590 + void start(Node dest)
1.591 + {
1.592 + while ( !_heap.empty() && _heap.top()!=dest ) processNextNode();
1.593 + if ( !_heap.empty() ) finalizeNodeData(_heap.top(),_heap.prio());
1.594 + }
1.595 +
1.596 + ///Executes the algorithm until a condition is met.
1.597 +
1.598 + ///Executes the algorithm until a condition is met.
1.599 + ///
1.600 + ///\pre init() must be called and at least one node should be added
1.601 + ///with addSource() before using this function.
1.602 + ///
1.603 + ///\param nm must be a bool (or convertible) node map. The algorithm
1.604 + ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
1.605 + template<class NodeBoolMap>
1.606 + void start(const NodeBoolMap &nm)
1.607 + {
1.608 + while ( !_heap.empty() && !nm[_heap.top()] ) processNextNode();
1.609 + if ( !_heap.empty() ) finalizeNodeData(_heap.top(),_heap.prio());
1.610 + }
1.611 +
1.612 + ///Runs %Dijkstra algorithm from node \c s.
1.613 +
1.614 + ///This method runs the %Dijkstra algorithm from a root node \c s
1.615 + ///in order to
1.616 + ///compute the
1.617 + ///shortest path to each node. The algorithm computes
1.618 + ///- The shortest path tree.
1.619 + ///- The distance of each node from the root.
1.620 + ///
1.621 + ///\note d.run(s) is just a shortcut of the following code.
1.622 + ///\code
1.623 + /// d.init();
1.624 + /// d.addSource(s);
1.625 + /// d.start();
1.626 + ///\endcode
1.627 + void run(Node s) {
1.628 + init();
1.629 + addSource(s);
1.630 + start();
1.631 + }
1.632 +
1.633 + ///Finds the shortest path between \c s and \c t.
1.634 +
1.635 + ///Finds the shortest path between \c s and \c t.
1.636 + ///
1.637 + ///\return The length of the shortest s---t path if there exists one,
1.638 + ///0 otherwise.
1.639 + ///\note Apart from the return value, d.run(s) is
1.640 + ///just a shortcut of the following code.
1.641 + ///\code
1.642 + /// d.init();
1.643 + /// d.addSource(s);
1.644 + /// d.start(t);
1.645 + ///\endcode
1.646 + Value run(Node s,Node t) {
1.647 + init();
1.648 + addSource(s);
1.649 + start(t);
1.650 + return (*_pred)[t]==INVALID?0:(*_dist)[t];
1.651 + }
1.652 +
1.653 + ///@}
1.654 +
1.655 + ///\name Query Functions
1.656 + ///The result of the %Dijkstra algorithm can be obtained using these
1.657 + ///functions.\n
1.658 + ///Before the use of these functions,
1.659 + ///either run() or start() must be called.
1.660 +
1.661 + ///@{
1.662 +
1.663 + ///Copies the shortest path to \c t into \c p
1.664 +
1.665 + ///This function copies the shortest path to \c t into \c p.
1.666 + ///If it \c \t is a source itself or unreachable, then it does not
1.667 + ///alter \c p.
1.668 + ///\todo Is it the right way to handle unreachable nodes?
1.669 + ///\return Returns \c true if a path to \c t was actually copied to \c p,
1.670 + ///\c false otherwise.
1.671 + ///\sa DirPath
1.672 + template<class P>
1.673 + bool getPath(P &p,Node t)
1.674 + {
1.675 + if(reached(t)) {
1.676 + p.clear();
1.677 + typename P::Builder b(p);
1.678 + for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
1.679 + b.pushFront(pred(t));
1.680 + b.commit();
1.681 + return true;
1.682 + }
1.683 + return false;
1.684 + }
1.685 +
1.686 + ///The distance of a node from the root.
1.687 +
1.688 + ///Returns the distance of a node from the root.
1.689 + ///\pre \ref run() must be called before using this function.
1.690 + ///\warning If node \c v in unreachable from the root the return value
1.691 + ///of this funcion is undefined.
1.692 + Value dist(Node v) const { return (*_dist)[v]; }
1.693 +
1.694 + ///Returns the 'previous edge' of the shortest path tree.
1.695 +
1.696 + ///For a node \c v it returns the 'previous edge' of the shortest path tree,
1.697 + ///i.e. it returns the last edge of a shortest path from the root to \c
1.698 + ///v. It is \ref INVALID
1.699 + ///if \c v is unreachable from the root or if \c v=s. The
1.700 + ///shortest path tree used here is equal to the shortest path tree used in
1.701 + ///\ref predNode(Node v). \pre \ref run() must be called before using
1.702 + ///this function.
1.703 + ///\todo predEdge could be a better name.
1.704 + Edge pred(Node v) const { return (*_pred)[v]; }
1.705 +
1.706 + ///Returns the 'previous node' of the shortest path tree.
1.707 +
1.708 + ///For a node \c v it returns the 'previous node' of the shortest path tree,
1.709 + ///i.e. it returns the last but one node from a shortest path from the
1.710 + ///root to \c /v. It is INVALID if \c v is unreachable from the root or if
1.711 + ///\c v=s. The shortest path tree used here is equal to the shortest path
1.712 + ///tree used in \ref pred(Node v). \pre \ref run() must be called before
1.713 + ///using this function.
1.714 + Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
1.715 + G->source((*_pred)[v]); }
1.716 +
1.717 + ///Returns a reference to the NodeMap of distances.
1.718 +
1.719 + ///Returns a reference to the NodeMap of distances. \pre \ref run() must
1.720 + ///be called before using this function.
1.721 + const DistMap &distMap() const { return *_dist;}
1.722 +
1.723 + ///Returns a reference to the shortest path tree map.
1.724 +
1.725 + ///Returns a reference to the NodeMap of the edges of the
1.726 + ///shortest path tree.
1.727 + ///\pre \ref run() must be called before using this function.
1.728 + const PredMap &predMap() const { return *_pred;}
1.729 +
1.730 +// ///Returns a reference to the map of nodes of shortest paths.
1.731 +
1.732 +// ///Returns a reference to the NodeMap of the last but one nodes of the
1.733 +// ///shortest path tree.
1.734 +// ///\pre \ref run() must be called before using this function.
1.735 +// const PredNodeMap &predNodeMap() const { return *_predNode;}
1.736 +
1.737 + ///Checks if a node is reachable from the root.
1.738 +
1.739 + ///Returns \c true if \c v is reachable from the root.
1.740 + ///\warning The source nodes are inditated as unreached.
1.741 + ///\pre \ref run() must be called before using this function.
1.742 + ///
1.743 + bool reached(Node v) { return _heap_map[v]!=Heap::PRE_HEAP; }
1.744 +
1.745 + ///@}
1.746 + };
1.747 +
1.748 +
1.749 +
1.750 +
1.751 +
1.752 + ///Default traits class of Dijkstra function.
1.753 +
1.754 + ///Default traits class of Dijkstra function.
1.755 + ///\param GR Graph type.
1.756 + ///\param LM Type of length map.
1.757 + template<class GR, class LM>
1.758 + struct DijkstraWizardDefaultTraits
1.759 + {
1.760 + ///The graph type the algorithm runs on.
1.761 + typedef GR Graph;
1.762 + ///The type of the map that stores the edge lengths.
1.763 +
1.764 + ///The type of the map that stores the edge lengths.
1.765 + ///It must meet the \ref concept::ReadMap "ReadMap" concept.
1.766 + typedef LM LengthMap;
1.767 + //The type of the length of the edges.
1.768 + typedef typename LM::Value Value;
1.769 + ///The heap type used by Dijkstra algorithm.
1.770 +
1.771 + ///The heap type used by Dijkstra algorithm.
1.772 + ///
1.773 + ///\sa BinHeap
1.774 + ///\sa Dijkstra
1.775 + typedef BinHeap<typename Graph::Node,
1.776 + typename LM::Value,
1.777 + typename GR::template NodeMap<int>,
1.778 + std::less<Value> > Heap;
1.779 +
1.780 + ///\brief The type of the map that stores the last
1.781 + ///edges of the shortest paths.
1.782 + ///
1.783 + ///The type of the map that stores the last
1.784 + ///edges of the shortest paths.
1.785 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.786 + ///
1.787 + typedef NullMap <typename GR::Node,typename GR::Edge> PredMap;
1.788 + ///Instantiates a PredMap.
1.789 +
1.790 + ///This function instantiates a \ref PredMap.
1.791 + ///\param G is the graph, to which we would like to define the PredMap.
1.792 + ///\todo The graph alone may be insufficient for the initialization
1.793 + static PredMap *createPredMap(const GR &)
1.794 + {
1.795 + return new PredMap();
1.796 + }
1.797 + ///The type of the map that stores whether a nodes is processed.
1.798 +
1.799 + ///The type of the map that stores whether a nodes is processed.
1.800 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.801 + ///By default it is a NullMap.
1.802 + ///\todo If it is set to a real map,
1.803 + ///Dijkstra::processed() should read this.
1.804 + ///\todo named parameter to set this type, function to read and write.
1.805 + typedef NullMap<typename Graph::Node,bool> ProcessedMap;
1.806 + ///Instantiates a ProcessedMap.
1.807 +
1.808 + ///This function instantiates a \ref ProcessedMap.
1.809 + ///\param G is the graph, to which
1.810 + ///we would like to define the \ref ProcessedMap
1.811 + static ProcessedMap *createProcessedMap(const GR &)
1.812 + {
1.813 + return new ProcessedMap();
1.814 + }
1.815 + ///The type of the map that stores the dists of the nodes.
1.816 +
1.817 + ///The type of the map that stores the dists of the nodes.
1.818 + ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.819 + ///
1.820 + typedef NullMap<typename Graph::Node,typename LM::Value> DistMap;
1.821 + ///Instantiates a DistMap.
1.822 +
1.823 + ///This function instantiates a \ref DistMap.
1.824 + ///\param G is the graph, to which we would like to define the \ref DistMap
1.825 + static DistMap *createDistMap(const GR &)
1.826 + {
1.827 + return new DistMap();
1.828 + }
1.829 + };
1.830 +
1.831 + /// Default traits used by \ref DijkstraWizard
1.832 +
1.833 + /// To make it easier to use Dijkstra algorithm
1.834 + ///we have created a wizard class.
1.835 + /// This \ref DijkstraWizard class needs default traits,
1.836 + ///as well as the \ref Dijkstra class.
1.837 + /// The \ref DijkstraWizardBase is a class to be the default traits of the
1.838 + /// \ref DijkstraWizard class.
1.839 + /// \todo More named parameters are required...
1.840 + template<class GR,class LM>
1.841 + class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
1.842 + {
1.843 +
1.844 + typedef DijkstraWizardDefaultTraits<GR,LM> Base;
1.845 + protected:
1.846 + /// Type of the nodes in the graph.
1.847 + typedef typename Base::Graph::Node Node;
1.848 +
1.849 + /// Pointer to the underlying graph.
1.850 + void *_g;
1.851 + /// Pointer to the length map
1.852 + void *_length;
1.853 + ///Pointer to the map of predecessors edges.
1.854 + void *_pred;
1.855 +// ///Pointer to the map of predecessors nodes.
1.856 +// void *_predNode;
1.857 + ///Pointer to the map of distances.
1.858 + void *_dist;
1.859 + ///Pointer to the source node.
1.860 + Node _source;
1.861 +
1.862 + public:
1.863 + /// Constructor.
1.864 +
1.865 + /// This constructor does not require parameters, therefore it initiates
1.866 + /// all of the attributes to default values (0, INVALID).
1.867 + DijkstraWizardBase() : _g(0), _length(0), _pred(0),
1.868 +// _predNode(0),
1.869 + _dist(0), _source(INVALID) {}
1.870 +
1.871 + /// Constructor.
1.872 +
1.873 + /// This constructor requires some parameters,
1.874 + /// listed in the parameters list.
1.875 + /// Others are initiated to 0.
1.876 + /// \param g is the initial value of \ref _g
1.877 + /// \param l is the initial value of \ref _length
1.878 + /// \param s is the initial value of \ref _source
1.879 + DijkstraWizardBase(const GR &g,const LM &l, Node s=INVALID) :
1.880 + _g((void *)&g), _length((void *)&l), _pred(0),
1.881 +// _predNode(0),
1.882 + _dist(0), _source(s) {}
1.883 +
1.884 + };
1.885 +
1.886 + /// A class to make the usage of Dijkstra algorithm easier
1.887 +
1.888 + /// This class is created to make it easier to use Dijkstra algorithm.
1.889 + /// It uses the functions and features of the plain \ref Dijkstra,
1.890 + /// but it is much simpler to use it.
1.891 + ///
1.892 + /// Simplicity means that the way to change the types defined
1.893 + /// in the traits class is based on functions that returns the new class
1.894 + /// and not on templatable built-in classes.
1.895 + /// When using the plain \ref Dijkstra
1.896 + /// the new class with the modified type comes from
1.897 + /// the original class by using the ::
1.898 + /// operator. In the case of \ref DijkstraWizard only
1.899 + /// a function have to be called and it will
1.900 + /// return the needed class.
1.901 + ///
1.902 + /// It does not have own \ref run method. When its \ref run method is called
1.903 + /// it initiates a plain \ref Dijkstra class, and calls the \ref Dijkstra::run
1.904 + /// method of it.
1.905 + template<class TR>
1.906 + class DijkstraWizard : public TR
1.907 + {
1.908 + typedef TR Base;
1.909 +
1.910 + ///The type of the underlying graph.
1.911 + typedef typename TR::Graph Graph;
1.912 + //\e
1.913 + typedef typename Graph::Node Node;
1.914 + //\e
1.915 + typedef typename Graph::NodeIt NodeIt;
1.916 + //\e
1.917 + typedef typename Graph::Edge Edge;
1.918 + //\e
1.919 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.920 +
1.921 + ///The type of the map that stores the edge lengths.
1.922 + typedef typename TR::LengthMap LengthMap;
1.923 + ///The type of the length of the edges.
1.924 + typedef typename LengthMap::Value Value;
1.925 + ///\brief The type of the map that stores the last
1.926 + ///edges of the shortest paths.
1.927 + typedef typename TR::PredMap PredMap;
1.928 +// ///\brief The type of the map that stores the last but one
1.929 +// ///nodes of the shortest paths.
1.930 +// typedef typename TR::PredNodeMap PredNodeMap;
1.931 + ///The type of the map that stores the dists of the nodes.
1.932 + typedef typename TR::DistMap DistMap;
1.933 +
1.934 + ///The heap type used by the dijkstra algorithm.
1.935 + typedef typename TR::Heap Heap;
1.936 +public:
1.937 + /// Constructor.
1.938 + DijkstraWizard() : TR() {}
1.939 +
1.940 + /// Constructor that requires parameters.
1.941 +
1.942 + /// Constructor that requires parameters.
1.943 + /// These parameters will be the default values for the traits class.
1.944 + DijkstraWizard(const Graph &g,const LengthMap &l, Node s=INVALID) :
1.945 + TR(g,l,s) {}
1.946 +
1.947 + ///Copy constructor
1.948 + DijkstraWizard(const TR &b) : TR(b) {}
1.949 +
1.950 + ~DijkstraWizard() {}
1.951 +
1.952 + ///Runs Dijkstra algorithm from a given node.
1.953 +
1.954 + ///Runs Dijkstra algorithm from a given node.
1.955 + ///The node can be given by the \ref source function.
1.956 + void run()
1.957 + {
1.958 + if(Base::_source==INVALID) throw UninitializedParameter();
1.959 + Dijkstra<Graph,LengthMap,TR>
1.960 + dij(*(Graph*)Base::_g,*(LengthMap*)Base::_length);
1.961 + if(Base::_pred) dij.predMap(*(PredMap*)Base::_pred);
1.962 +// if(Base::_predNode) Dij.predNodeMap(*(PredNodeMap*)Base::_predNode);
1.963 + if(Base::_dist) dij.distMap(*(DistMap*)Base::_dist);
1.964 + dij.run(Base::_source);
1.965 + }
1.966 +
1.967 + ///Runs Dijkstra algorithm from the given node.
1.968 +
1.969 + ///Runs Dijkstra algorithm from the given node.
1.970 + ///\param s is the given source.
1.971 + void run(Node s)
1.972 + {
1.973 + Base::_source=s;
1.974 + run();
1.975 + }
1.976 +
1.977 + template<class T>
1.978 + struct DefPredMapBase : public Base {
1.979 + typedef T PredMap;
1.980 + static PredMap *createPredMap(const Graph &) { return 0; };
1.981 + DefPredMapBase(const TR &b) : TR(b) {}
1.982 + };
1.983 +
1.984 + ///\brief \ref named-templ-param "Named parameter"
1.985 + ///function for setting PredMap type
1.986 + ///
1.987 + /// \ref named-templ-param "Named parameter"
1.988 + ///function for setting PredMap type
1.989 + ///
1.990 + template<class T>
1.991 + DijkstraWizard<DefPredMapBase<T> > predMap(const T &t)
1.992 + {
1.993 + Base::_pred=(void *)&t;
1.994 + return DijkstraWizard<DefPredMapBase<T> >(*this);
1.995 + }
1.996 +
1.997 +
1.998 +// template<class T>
1.999 +// struct DefPredNodeMapBase : public Base {
1.1000 +// typedef T PredNodeMap;
1.1001 +// static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
1.1002 +// DefPredNodeMapBase(const TR &b) : TR(b) {}
1.1003 +// };
1.1004 +
1.1005 +// ///\brief \ref named-templ-param "Named parameter"
1.1006 +// ///function for setting PredNodeMap type
1.1007 +// ///
1.1008 +// /// \ref named-templ-param "Named parameter"
1.1009 +// ///function for setting PredNodeMap type
1.1010 +// ///
1.1011 +// template<class T>
1.1012 +// DijkstraWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1.1013 +// {
1.1014 +// Base::_predNode=(void *)&t;
1.1015 +// return DijkstraWizard<DefPredNodeMapBase<T> >(*this);
1.1016 +// }
1.1017 +
1.1018 + template<class T>
1.1019 + struct DefDistMapBase : public Base {
1.1020 + typedef T DistMap;
1.1021 + static DistMap *createDistMap(const Graph &) { return 0; };
1.1022 + DefDistMapBase(const TR &b) : TR(b) {}
1.1023 + };
1.1024 +
1.1025 + ///\brief \ref named-templ-param "Named parameter"
1.1026 + ///function for setting DistMap type
1.1027 + ///
1.1028 + /// \ref named-templ-param "Named parameter"
1.1029 + ///function for setting DistMap type
1.1030 + ///
1.1031 + template<class T>
1.1032 + DijkstraWizard<DefDistMapBase<T> > distMap(const T &t)
1.1033 + {
1.1034 + Base::_dist=(void *)&t;
1.1035 + return DijkstraWizard<DefDistMapBase<T> >(*this);
1.1036 + }
1.1037 +
1.1038 + /// Sets the source node, from which the Dijkstra algorithm runs.
1.1039 +
1.1040 + /// Sets the source node, from which the Dijkstra algorithm runs.
1.1041 + /// \param s is the source node.
1.1042 + DijkstraWizard<TR> &source(Node s)
1.1043 + {
1.1044 + Base::_source=s;
1.1045 + return *this;
1.1046 + }
1.1047 +
1.1048 + };
1.1049 +
1.1050 + ///Function type interface for Dijkstra algorithm.
1.1051 +
1.1052 + /// \ingroup flowalgs
1.1053 + ///Function type interface for Dijkstra algorithm.
1.1054 + ///
1.1055 + ///This function also has several
1.1056 + ///\ref named-templ-func-param "named parameters",
1.1057 + ///they are declared as the members of class \ref DijkstraWizard.
1.1058 + ///The following
1.1059 + ///example shows how to use these parameters.
1.1060 + ///\code
1.1061 + /// dijkstra(g,length,source).predMap(preds).run();
1.1062 + ///\endcode
1.1063 + ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
1.1064 + ///to the end of the parameter list.
1.1065 + ///\sa DijkstraWizard
1.1066 + ///\sa Dijkstra
1.1067 + template<class GR, class LM>
1.1068 + DijkstraWizard<DijkstraWizardBase<GR,LM> >
1.1069 + dijkstra(const GR &g,const LM &l,typename GR::Node s=INVALID)
1.1070 + {
1.1071 + return DijkstraWizard<DijkstraWizardBase<GR,LM> >(g,l,s);
1.1072 + }
1.1073 +
1.1074 +} //END OF NAMESPACE LEMON
1.1075 +
1.1076 +#endif
1.1077 +