1.1 --- a/src/lemon/dijkstra.h Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,1074 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/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 -