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