1.1 --- a/lemon/dijkstra.h Fri Oct 16 10:21:37 2009 +0200
1.2 +++ b/lemon/dijkstra.h Thu Nov 05 15:50:01 2009 +0100
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2008
1.8 + * Copyright (C) 2003-2009
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -38,8 +38,10 @@
1.13 ///
1.14 /// This operation traits class defines all computational operations and
1.15 /// constants which are used in the Dijkstra algorithm.
1.16 - template <typename Value>
1.17 + template <typename V>
1.18 struct DijkstraDefaultOperationTraits {
1.19 + /// \e
1.20 + typedef V Value;
1.21 /// \brief Gives back the zero value of the type.
1.22 static Value zero() {
1.23 return static_cast<Value>(0);
1.24 @@ -58,8 +60,8 @@
1.25
1.26 ///Default traits class of Dijkstra class.
1.27 ///\tparam GR The type of the digraph.
1.28 - ///\tparam LM The type of the length map.
1.29 - template<class GR, class LM>
1.30 + ///\tparam LEN The type of the length map.
1.31 + template<typename GR, typename LEN>
1.32 struct DijkstraDefaultTraits
1.33 {
1.34 ///The type of the digraph the algorithm runs on.
1.35 @@ -68,12 +70,12 @@
1.36 ///The type of the map that stores the arc lengths.
1.37
1.38 ///The type of the map that stores the arc lengths.
1.39 - ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.40 - typedef LM LengthMap;
1.41 - ///The type of the length of the arcs.
1.42 - typedef typename LM::Value Value;
1.43 + ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
1.44 + typedef LEN LengthMap;
1.45 + ///The type of the arc lengths.
1.46 + typedef typename LEN::Value Value;
1.47
1.48 - /// Operation traits for Dijkstra algorithm.
1.49 + /// Operation traits for %Dijkstra algorithm.
1.50
1.51 /// This class defines the operations that are used in the algorithm.
1.52 /// \see DijkstraDefaultOperationTraits
1.53 @@ -84,7 +86,7 @@
1.54 /// The cross reference type used by the heap.
1.55 /// Usually it is \c Digraph::NodeMap<int>.
1.56 typedef typename Digraph::template NodeMap<int> HeapCrossRef;
1.57 - ///Instantiates a \ref HeapCrossRef.
1.58 + ///Instantiates a \c HeapCrossRef.
1.59
1.60 ///This function instantiates a \ref HeapCrossRef.
1.61 /// \param g is the digraph, to which we would like to define the
1.62 @@ -94,14 +96,14 @@
1.63 return new HeapCrossRef(g);
1.64 }
1.65
1.66 - ///The heap type used by the Dijkstra algorithm.
1.67 + ///The heap type used by the %Dijkstra algorithm.
1.68
1.69 ///The heap type used by the Dijkstra algorithm.
1.70 ///
1.71 ///\sa BinHeap
1.72 ///\sa Dijkstra
1.73 - typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
1.74 - ///Instantiates a \ref Heap.
1.75 + typedef BinHeap<typename LEN::Value, HeapCrossRef, std::less<Value> > Heap;
1.76 + ///Instantiates a \c Heap.
1.77
1.78 ///This function instantiates a \ref Heap.
1.79 static Heap *createHeap(HeapCrossRef& r)
1.80 @@ -114,13 +116,13 @@
1.81 ///
1.82 ///The type of the map that stores the predecessor
1.83 ///arcs of the shortest paths.
1.84 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.85 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.86 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.87 - ///Instantiates a PredMap.
1.88 + ///Instantiates a \c PredMap.
1.89
1.90 - ///This function instantiates a PredMap.
1.91 + ///This function instantiates a \ref PredMap.
1.92 ///\param g is the digraph, to which we would like to define the
1.93 - ///PredMap.
1.94 + ///\ref PredMap.
1.95 static PredMap *createPredMap(const Digraph &g)
1.96 {
1.97 return new PredMap(g);
1.98 @@ -129,14 +131,14 @@
1.99 ///The type of the map that indicates which nodes are processed.
1.100
1.101 ///The type of the map that indicates which nodes are processed.
1.102 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.103 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.104 ///By default it is a NullMap.
1.105 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.106 - ///Instantiates a ProcessedMap.
1.107 + ///Instantiates a \c ProcessedMap.
1.108
1.109 - ///This function instantiates a ProcessedMap.
1.110 + ///This function instantiates a \ref ProcessedMap.
1.111 ///\param g is the digraph, to which
1.112 - ///we would like to define the ProcessedMap
1.113 + ///we would like to define the \ref ProcessedMap.
1.114 #ifdef DOXYGEN
1.115 static ProcessedMap *createProcessedMap(const Digraph &g)
1.116 #else
1.117 @@ -149,13 +151,13 @@
1.118 ///The type of the map that stores the distances of the nodes.
1.119
1.120 ///The type of the map that stores the distances of the nodes.
1.121 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.122 - typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
1.123 - ///Instantiates a DistMap.
1.124 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.125 + typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
1.126 + ///Instantiates a \c DistMap.
1.127
1.128 - ///This function instantiates a DistMap.
1.129 + ///This function instantiates a \ref DistMap.
1.130 ///\param g is the digraph, to which we would like to define
1.131 - ///the DistMap
1.132 + ///the \ref DistMap.
1.133 static DistMap *createDistMap(const Digraph &g)
1.134 {
1.135 return new DistMap(g);
1.136 @@ -167,6 +169,10 @@
1.137 /// \ingroup shortest_path
1.138 ///This class provides an efficient implementation of the %Dijkstra algorithm.
1.139 ///
1.140 + ///The %Dijkstra algorithm solves the single-source shortest path problem
1.141 + ///when all arc lengths are non-negative. If there are negative lengths,
1.142 + ///the BellmanFord algorithm should be used instead.
1.143 + ///
1.144 ///The arc lengths are passed to the algorithm using a
1.145 ///\ref concepts::ReadMap "ReadMap",
1.146 ///so it is easy to change it to any kind of length.
1.147 @@ -179,26 +185,19 @@
1.148 ///it can be used easier.
1.149 ///
1.150 ///\tparam GR The type of the digraph the algorithm runs on.
1.151 - ///The default value is \ref ListDigraph.
1.152 - ///The value of GR is not used directly by \ref Dijkstra, it is only
1.153 - ///passed to \ref DijkstraDefaultTraits.
1.154 - ///\tparam LM A readable arc map that determines the lengths of the
1.155 - ///arcs. It is read once for each arc, so the map may involve in
1.156 + ///The default type is \ref ListDigraph.
1.157 + ///\tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
1.158 + ///the lengths of the arcs.
1.159 + ///It is read once for each arc, so the map may involve in
1.160 ///relatively time consuming process to compute the arc lengths if
1.161 ///it is necessary. The default map type is \ref
1.162 - ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
1.163 - ///The value of LM is not used directly by \ref Dijkstra, it is only
1.164 - ///passed to \ref DijkstraDefaultTraits.
1.165 - ///\tparam TR Traits class to set various data types used by the algorithm.
1.166 - ///The default traits class is \ref DijkstraDefaultTraits
1.167 - ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
1.168 - ///for the documentation of a Dijkstra traits class.
1.169 + ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
1.170 #ifdef DOXYGEN
1.171 - template <typename GR, typename LM, typename TR>
1.172 + template <typename GR, typename LEN, typename TR>
1.173 #else
1.174 template <typename GR=ListDigraph,
1.175 - typename LM=typename GR::template ArcMap<int>,
1.176 - typename TR=DijkstraDefaultTraits<GR,LM> >
1.177 + typename LEN=typename GR::template ArcMap<int>,
1.178 + typename TR=DijkstraDefaultTraits<GR,LEN> >
1.179 #endif
1.180 class Dijkstra {
1.181 public:
1.182 @@ -206,7 +205,7 @@
1.183 ///The type of the digraph the algorithm runs on.
1.184 typedef typename TR::Digraph Digraph;
1.185
1.186 - ///The type of the length of the arcs.
1.187 + ///The type of the arc lengths.
1.188 typedef typename TR::LengthMap::Value Value;
1.189 ///The type of the map that stores the arc lengths.
1.190 typedef typename TR::LengthMap LengthMap;
1.191 @@ -223,10 +222,11 @@
1.192 typedef typename TR::HeapCrossRef HeapCrossRef;
1.193 ///The heap type used by the algorithm.
1.194 typedef typename TR::Heap Heap;
1.195 - ///The operation traits class.
1.196 + ///\brief The \ref DijkstraDefaultOperationTraits "operation traits class"
1.197 + ///of the algorithm.
1.198 typedef typename TR::OperationTraits OperationTraits;
1.199
1.200 - ///The traits class.
1.201 + ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
1.202 typedef TR Traits;
1.203
1.204 private:
1.205 @@ -239,7 +239,7 @@
1.206 //Pointer to the underlying digraph.
1.207 const Digraph *G;
1.208 //Pointer to the length map.
1.209 - const LengthMap *length;
1.210 + const LengthMap *_length;
1.211 //Pointer to the map of predecessors arcs.
1.212 PredMap *_pred;
1.213 //Indicates if _pred is locally allocated (true) or not.
1.214 @@ -290,7 +290,7 @@
1.215
1.216 typedef Dijkstra Create;
1.217
1.218 - ///\name Named template parameters
1.219 + ///\name Named Template Parameters
1.220
1.221 ///@{
1.222
1.223 @@ -304,10 +304,11 @@
1.224 }
1.225 };
1.226 ///\brief \ref named-templ-param "Named parameter" for setting
1.227 - ///PredMap type.
1.228 + ///\c PredMap type.
1.229 ///
1.230 ///\ref named-templ-param "Named parameter" for setting
1.231 - ///PredMap type.
1.232 + ///\c PredMap type.
1.233 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.234 template <class T>
1.235 struct SetPredMap
1.236 : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
1.237 @@ -324,10 +325,11 @@
1.238 }
1.239 };
1.240 ///\brief \ref named-templ-param "Named parameter" for setting
1.241 - ///DistMap type.
1.242 + ///\c DistMap type.
1.243 ///
1.244 ///\ref named-templ-param "Named parameter" for setting
1.245 - ///DistMap type.
1.246 + ///\c DistMap type.
1.247 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.248 template <class T>
1.249 struct SetDistMap
1.250 : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
1.251 @@ -344,10 +346,11 @@
1.252 }
1.253 };
1.254 ///\brief \ref named-templ-param "Named parameter" for setting
1.255 - ///ProcessedMap type.
1.256 + ///\c ProcessedMap type.
1.257 ///
1.258 ///\ref named-templ-param "Named parameter" for setting
1.259 - ///ProcessedMap type.
1.260 + ///\c ProcessedMap type.
1.261 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.262 template <class T>
1.263 struct SetProcessedMap
1.264 : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
1.265 @@ -362,10 +365,10 @@
1.266 }
1.267 };
1.268 ///\brief \ref named-templ-param "Named parameter" for setting
1.269 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.270 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.271 ///
1.272 ///\ref named-templ-param "Named parameter" for setting
1.273 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.274 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.275 ///If you don't set it explicitly, it will be automatically allocated.
1.276 struct SetStandardProcessedMap
1.277 : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
1.278 @@ -388,10 +391,14 @@
1.279 }
1.280 };
1.281 ///\brief \ref named-templ-param "Named parameter" for setting
1.282 - ///heap and cross reference type
1.283 + ///heap and cross reference types
1.284 ///
1.285 ///\ref named-templ-param "Named parameter" for setting heap and cross
1.286 - ///reference type.
1.287 + ///reference types. If this named parameter is used, then external
1.288 + ///heap and cross reference objects must be passed to the algorithm
1.289 + ///using the \ref heap() function before calling \ref run(Node) "run()"
1.290 + ///or \ref init().
1.291 + ///\sa SetStandardHeap
1.292 template <class H, class CR = typename Digraph::template NodeMap<int> >
1.293 struct SetHeap
1.294 : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > {
1.295 @@ -411,12 +418,18 @@
1.296 }
1.297 };
1.298 ///\brief \ref named-templ-param "Named parameter" for setting
1.299 - ///heap and cross reference type with automatic allocation
1.300 + ///heap and cross reference types with automatic allocation
1.301 ///
1.302 ///\ref named-templ-param "Named parameter" for setting heap and cross
1.303 - ///reference type. It can allocate the heap and the cross reference
1.304 - ///object if the cross reference's constructor waits for the digraph as
1.305 - ///parameter and the heap's constructor waits for the cross reference.
1.306 + ///reference types with automatic allocation.
1.307 + ///They should have standard constructor interfaces to be able to
1.308 + ///automatically created by the algorithm (i.e. the digraph should be
1.309 + ///passed to the constructor of the cross reference and the cross
1.310 + ///reference should be passed to the constructor of the heap).
1.311 + ///However external heap and cross reference objects could also be
1.312 + ///passed to the algorithm using the \ref heap() function before
1.313 + ///calling \ref run(Node) "run()" or \ref init().
1.314 + ///\sa SetHeap
1.315 template <class H, class CR = typename Digraph::template NodeMap<int> >
1.316 struct SetStandardHeap
1.317 : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > {
1.318 @@ -433,7 +446,8 @@
1.319 ///\c OperationTraits type
1.320 ///
1.321 ///\ref named-templ-param "Named parameter" for setting
1.322 - ///\ref OperationTraits type.
1.323 + ///\c OperationTraits type.
1.324 + /// For more information see \ref DijkstraDefaultOperationTraits.
1.325 template <class T>
1.326 struct SetOperationTraits
1.327 : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
1.328 @@ -452,10 +466,10 @@
1.329 ///Constructor.
1.330
1.331 ///Constructor.
1.332 - ///\param _g The digraph the algorithm runs on.
1.333 - ///\param _length The length map used by the algorithm.
1.334 - Dijkstra(const Digraph& _g, const LengthMap& _length) :
1.335 - G(&_g), length(&_length),
1.336 + ///\param g The digraph the algorithm runs on.
1.337 + ///\param length The length map used by the algorithm.
1.338 + Dijkstra(const Digraph& g, const LengthMap& length) :
1.339 + G(&g), _length(&length),
1.340 _pred(NULL), local_pred(false),
1.341 _dist(NULL), local_dist(false),
1.342 _processed(NULL), local_processed(false),
1.343 @@ -479,16 +493,17 @@
1.344 ///\return <tt> (*this) </tt>
1.345 Dijkstra &lengthMap(const LengthMap &m)
1.346 {
1.347 - length = &m;
1.348 + _length = &m;
1.349 return *this;
1.350 }
1.351
1.352 ///Sets the map that stores the predecessor arcs.
1.353
1.354 ///Sets the map that stores the predecessor arcs.
1.355 - ///If you don't use this function before calling \ref run(),
1.356 - ///it will allocate one. The destructor deallocates this
1.357 - ///automatically allocated map, of course.
1.358 + ///If you don't use this function before calling \ref run(Node) "run()"
1.359 + ///or \ref init(), an instance will be allocated automatically.
1.360 + ///The destructor deallocates this automatically allocated map,
1.361 + ///of course.
1.362 ///\return <tt> (*this) </tt>
1.363 Dijkstra &predMap(PredMap &m)
1.364 {
1.365 @@ -503,9 +518,10 @@
1.366 ///Sets the map that indicates which nodes are processed.
1.367
1.368 ///Sets the map that indicates which nodes are processed.
1.369 - ///If you don't use this function before calling \ref run(),
1.370 - ///it will allocate one. The destructor deallocates this
1.371 - ///automatically allocated map, of course.
1.372 + ///If you don't use this function before calling \ref run(Node) "run()"
1.373 + ///or \ref init(), an instance will be allocated automatically.
1.374 + ///The destructor deallocates this automatically allocated map,
1.375 + ///of course.
1.376 ///\return <tt> (*this) </tt>
1.377 Dijkstra &processedMap(ProcessedMap &m)
1.378 {
1.379 @@ -521,9 +537,10 @@
1.380
1.381 ///Sets the map that stores the distances of the nodes calculated by the
1.382 ///algorithm.
1.383 - ///If you don't use this function before calling \ref run(),
1.384 - ///it will allocate one. The destructor deallocates this
1.385 - ///automatically allocated map, of course.
1.386 + ///If you don't use this function before calling \ref run(Node) "run()"
1.387 + ///or \ref init(), an instance will be allocated automatically.
1.388 + ///The destructor deallocates this automatically allocated map,
1.389 + ///of course.
1.390 ///\return <tt> (*this) </tt>
1.391 Dijkstra &distMap(DistMap &m)
1.392 {
1.393 @@ -538,9 +555,11 @@
1.394 ///Sets the heap and the cross reference used by algorithm.
1.395
1.396 ///Sets the heap and the cross reference used by algorithm.
1.397 - ///If you don't use this function before calling \ref run(),
1.398 - ///it will allocate one. The destructor deallocates this
1.399 - ///automatically allocated heap and cross reference, of course.
1.400 + ///If you don't use this function before calling \ref run(Node) "run()"
1.401 + ///or \ref init(), heap and cross reference instances will be
1.402 + ///allocated automatically.
1.403 + ///The destructor deallocates these automatically allocated objects,
1.404 + ///of course.
1.405 ///\return <tt> (*this) </tt>
1.406 Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
1.407 {
1.408 @@ -567,22 +586,19 @@
1.409
1.410 public:
1.411
1.412 - ///\name Execution control
1.413 - ///The simplest way to execute the algorithm is to use one of the
1.414 - ///member functions called \ref lemon::Dijkstra::run() "run()".
1.415 - ///\n
1.416 - ///If you need more control on the execution, first you must call
1.417 - ///\ref lemon::Dijkstra::init() "init()", then you can add several
1.418 - ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
1.419 - ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
1.420 - ///actual path computation.
1.421 + ///\name Execution Control
1.422 + ///The simplest way to execute the %Dijkstra algorithm is to use
1.423 + ///one of the member functions called \ref run(Node) "run()".\n
1.424 + ///If you need better control on the execution, you have to call
1.425 + ///\ref init() first, then you can add several source nodes with
1.426 + ///\ref addSource(). Finally the actual path computation can be
1.427 + ///performed with one of the \ref start() functions.
1.428
1.429 ///@{
1.430
1.431 + ///\brief Initializes the internal data structures.
1.432 + ///
1.433 ///Initializes the internal data structures.
1.434 -
1.435 - ///Initializes the internal data structures.
1.436 - ///
1.437 void init()
1.438 {
1.439 create_maps();
1.440 @@ -630,12 +646,12 @@
1.441 Node w=G->target(e);
1.442 switch(_heap->state(w)) {
1.443 case Heap::PRE_HEAP:
1.444 - _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
1.445 + _heap->push(w,OperationTraits::plus(oldvalue, (*_length)[e]));
1.446 _pred->set(w,e);
1.447 break;
1.448 case Heap::IN_HEAP:
1.449 {
1.450 - Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
1.451 + Value newvalue = OperationTraits::plus(oldvalue, (*_length)[e]);
1.452 if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
1.453 _heap->decrease(w, newvalue);
1.454 _pred->set(w,e);
1.455 @@ -658,17 +674,16 @@
1.456 return !_heap->empty()?_heap->top():INVALID;
1.457 }
1.458
1.459 - ///\brief Returns \c false if there are nodes
1.460 - ///to be processed.
1.461 - ///
1.462 - ///Returns \c false if there are nodes
1.463 - ///to be processed in the priority heap.
1.464 + ///Returns \c false if there are nodes to be processed.
1.465 +
1.466 + ///Returns \c false if there are nodes to be processed
1.467 + ///in the priority heap.
1.468 bool emptyQueue() const { return _heap->empty(); }
1.469
1.470 - ///Returns the number of the nodes to be processed in the priority heap
1.471 + ///Returns the number of the nodes to be processed.
1.472
1.473 - ///Returns the number of the nodes to be processed in the priority heap.
1.474 - ///
1.475 + ///Returns the number of the nodes to be processed
1.476 + ///in the priority heap.
1.477 int queueSize() const { return _heap->size(); }
1.478
1.479 ///Executes the algorithm.
1.480 @@ -789,61 +804,62 @@
1.481 ///@}
1.482
1.483 ///\name Query Functions
1.484 - ///The result of the %Dijkstra algorithm can be obtained using these
1.485 + ///The results of the %Dijkstra algorithm can be obtained using these
1.486 ///functions.\n
1.487 - ///Either \ref lemon::Dijkstra::run() "run()" or
1.488 - ///\ref lemon::Dijkstra::start() "start()" must be called before
1.489 - ///using them.
1.490 + ///Either \ref run(Node) "run()" or \ref init() should be called
1.491 + ///before using them.
1.492
1.493 ///@{
1.494
1.495 - ///The shortest path to a node.
1.496 + ///The shortest path to the given node.
1.497
1.498 - ///Returns the shortest path to a node.
1.499 + ///Returns the shortest path to the given node from the root(s).
1.500 ///
1.501 - ///\warning \c t should be reachable from the root(s).
1.502 + ///\warning \c t should be reached from the root(s).
1.503 ///
1.504 - ///\pre Either \ref run() or \ref start() must be called before
1.505 - ///using this function.
1.506 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.507 + ///must be called before using this function.
1.508 Path path(Node t) const { return Path(*G, *_pred, t); }
1.509
1.510 - ///The distance of a node from the root(s).
1.511 + ///The distance of the given node from the root(s).
1.512
1.513 - ///Returns the distance of a node from the root(s).
1.514 + ///Returns the distance of the given node from the root(s).
1.515 ///
1.516 - ///\warning If node \c v is not reachable from the root(s), then
1.517 + ///\warning If node \c v is not reached from the root(s), then
1.518 ///the return value of this function is undefined.
1.519 ///
1.520 - ///\pre Either \ref run() or \ref start() must be called before
1.521 - ///using this function.
1.522 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.523 + ///must be called before using this function.
1.524 Value dist(Node v) const { return (*_dist)[v]; }
1.525
1.526 - ///Returns the 'previous arc' of the shortest path tree for a node.
1.527 -
1.528 + ///\brief Returns the 'previous arc' of the shortest path tree for
1.529 + ///the given node.
1.530 + ///
1.531 ///This function returns the 'previous arc' of the shortest path
1.532 ///tree for the node \c v, i.e. it returns the last arc of a
1.533 - ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
1.534 - ///is not reachable from the root(s) or if \c v is a root.
1.535 + ///shortest path from a root to \c v. It is \c INVALID if \c v
1.536 + ///is not reached from the root(s) or if \c v is a root.
1.537 ///
1.538 ///The shortest path tree used here is equal to the shortest path
1.539 - ///tree used in \ref predNode().
1.540 + ///tree used in \ref predNode() and \ref predMap().
1.541 ///
1.542 - ///\pre Either \ref run() or \ref start() must be called before
1.543 - ///using this function.
1.544 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.545 + ///must be called before using this function.
1.546 Arc predArc(Node v) const { return (*_pred)[v]; }
1.547
1.548 - ///Returns the 'previous node' of the shortest path tree for a node.
1.549 -
1.550 + ///\brief Returns the 'previous node' of the shortest path tree for
1.551 + ///the given node.
1.552 + ///
1.553 ///This function returns the 'previous node' of the shortest path
1.554 ///tree for the node \c v, i.e. it returns the last but one node
1.555 - ///from a shortest path from the root(s) to \c v. It is \c INVALID
1.556 - ///if \c v is not reachable from the root(s) or if \c v is a root.
1.557 + ///of a shortest path from a root to \c v. It is \c INVALID
1.558 + ///if \c v is not reached from the root(s) or if \c v is a root.
1.559 ///
1.560 ///The shortest path tree used here is equal to the shortest path
1.561 - ///tree used in \ref predArc().
1.562 + ///tree used in \ref predArc() and \ref predMap().
1.563 ///
1.564 - ///\pre Either \ref run() or \ref start() must be called before
1.565 - ///using this function.
1.566 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.567 + ///must be called before using this function.
1.568 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
1.569 G->source((*_pred)[v]); }
1.570
1.571 @@ -853,7 +869,7 @@
1.572 ///Returns a const reference to the node map that stores the distances
1.573 ///of the nodes calculated by the algorithm.
1.574 ///
1.575 - ///\pre Either \ref run() or \ref init()
1.576 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.577 ///must be called before using this function.
1.578 const DistMap &distMap() const { return *_dist;}
1.579
1.580 @@ -861,16 +877,17 @@
1.581 ///predecessor arcs.
1.582 ///
1.583 ///Returns a const reference to the node map that stores the predecessor
1.584 - ///arcs, which form the shortest path tree.
1.585 + ///arcs, which form the shortest path tree (forest).
1.586 ///
1.587 - ///\pre Either \ref run() or \ref init()
1.588 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.589 ///must be called before using this function.
1.590 const PredMap &predMap() const { return *_pred;}
1.591
1.592 - ///Checks if a node is reachable from the root(s).
1.593 + ///Checks if the given node is reached from the root(s).
1.594
1.595 - ///Returns \c true if \c v is reachable from the root(s).
1.596 - ///\pre Either \ref run() or \ref start()
1.597 + ///Returns \c true if \c v is reached from the root(s).
1.598 + ///
1.599 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.600 ///must be called before using this function.
1.601 bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
1.602 Heap::PRE_HEAP; }
1.603 @@ -879,16 +896,18 @@
1.604
1.605 ///Returns \c true if \c v is processed, i.e. the shortest
1.606 ///path to \c v has already found.
1.607 - ///\pre Either \ref run() or \ref init()
1.608 + ///
1.609 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.610 ///must be called before using this function.
1.611 bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
1.612 Heap::POST_HEAP; }
1.613
1.614 - ///The current distance of a node from the root(s).
1.615 + ///The current distance of the given node from the root(s).
1.616
1.617 - ///Returns the current distance of a node from the root(s).
1.618 + ///Returns the current distance of the given node from the root(s).
1.619 ///It may be decreased in the following processes.
1.620 - ///\pre Either \ref run() or \ref init()
1.621 + ///
1.622 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.623 ///must be called before using this function and
1.624 ///node \c v must be reached but not necessarily processed.
1.625 Value currentDist(Node v) const {
1.626 @@ -903,8 +922,8 @@
1.627
1.628 ///Default traits class of dijkstra() function.
1.629 ///\tparam GR The type of the digraph.
1.630 - ///\tparam LM The type of the length map.
1.631 - template<class GR, class LM>
1.632 + ///\tparam LEN The type of the length map.
1.633 + template<class GR, class LEN>
1.634 struct DijkstraWizardDefaultTraits
1.635 {
1.636 ///The type of the digraph the algorithm runs on.
1.637 @@ -912,10 +931,10 @@
1.638 ///The type of the map that stores the arc lengths.
1.639
1.640 ///The type of the map that stores the arc lengths.
1.641 - ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.642 - typedef LM LengthMap;
1.643 - ///The type of the length of the arcs.
1.644 - typedef typename LM::Value Value;
1.645 + ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
1.646 + typedef LEN LengthMap;
1.647 + ///The type of the arc lengths.
1.648 + typedef typename LEN::Value Value;
1.649
1.650 /// Operation traits for Dijkstra algorithm.
1.651
1.652 @@ -961,7 +980,7 @@
1.653 ///
1.654 ///The type of the map that stores the predecessor
1.655 ///arcs of the shortest paths.
1.656 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.657 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.658 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.659 ///Instantiates a PredMap.
1.660
1.661 @@ -976,7 +995,7 @@
1.662 ///The type of the map that indicates which nodes are processed.
1.663
1.664 ///The type of the map that indicates which nodes are processed.
1.665 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.666 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.667 ///By default it is a NullMap.
1.668 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.669 ///Instantiates a ProcessedMap.
1.670 @@ -996,8 +1015,8 @@
1.671 ///The type of the map that stores the distances of the nodes.
1.672
1.673 ///The type of the map that stores the distances of the nodes.
1.674 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.675 - typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
1.676 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.677 + typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
1.678 ///Instantiates a DistMap.
1.679
1.680 ///This function instantiates a DistMap.
1.681 @@ -1011,22 +1030,19 @@
1.682 ///The type of the shortest paths.
1.683
1.684 ///The type of the shortest paths.
1.685 - ///It must meet the \ref concepts::Path "Path" concept.
1.686 + ///It must conform to the \ref concepts::Path "Path" concept.
1.687 typedef lemon::Path<Digraph> Path;
1.688 };
1.689
1.690 /// Default traits class used by DijkstraWizard
1.691
1.692 - /// To make it easier to use Dijkstra algorithm
1.693 - /// we have created a wizard class.
1.694 - /// This \ref DijkstraWizard class needs default traits,
1.695 - /// as well as the \ref Dijkstra class.
1.696 - /// The \ref DijkstraWizardBase is a class to be the default traits of the
1.697 - /// \ref DijkstraWizard class.
1.698 - template<class GR,class LM>
1.699 - class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
1.700 + /// Default traits class used by DijkstraWizard.
1.701 + /// \tparam GR The type of the digraph.
1.702 + /// \tparam LEN The type of the length map.
1.703 + template<typename GR, typename LEN>
1.704 + class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN>
1.705 {
1.706 - typedef DijkstraWizardDefaultTraits<GR,LM> Base;
1.707 + typedef DijkstraWizardDefaultTraits<GR,LEN> Base;
1.708 protected:
1.709 //The type of the nodes in the digraph.
1.710 typedef typename Base::Digraph::Node Node;
1.711 @@ -1060,9 +1076,9 @@
1.712 /// others are initiated to \c 0.
1.713 /// \param g The digraph the algorithm runs on.
1.714 /// \param l The length map.
1.715 - DijkstraWizardBase(const GR &g,const LM &l) :
1.716 + DijkstraWizardBase(const GR &g,const LEN &l) :
1.717 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
1.718 - _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
1.719 + _length(reinterpret_cast<void*>(const_cast<LEN*>(&l))),
1.720 _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
1.721
1.722 };
1.723 @@ -1071,8 +1087,8 @@
1.724
1.725 /// This auxiliary class is created to implement the
1.726 /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
1.727 - /// It does not have own \ref run() method, it uses the functions
1.728 - /// and features of the plain \ref Dijkstra.
1.729 + /// It does not have own \ref run(Node) "run()" method, it uses the
1.730 + /// functions and features of the plain \ref Dijkstra.
1.731 ///
1.732 /// This class should only be used through the \ref dijkstra() function,
1.733 /// which makes it easier to use the algorithm.
1.734 @@ -1081,7 +1097,6 @@
1.735 {
1.736 typedef TR Base;
1.737
1.738 - ///The type of the digraph the algorithm runs on.
1.739 typedef typename TR::Digraph Digraph;
1.740
1.741 typedef typename Digraph::Node Node;
1.742 @@ -1089,20 +1104,12 @@
1.743 typedef typename Digraph::Arc Arc;
1.744 typedef typename Digraph::OutArcIt OutArcIt;
1.745
1.746 - ///The type of the map that stores the arc lengths.
1.747 typedef typename TR::LengthMap LengthMap;
1.748 - ///The type of the length of the arcs.
1.749 typedef typename LengthMap::Value Value;
1.750 - ///\brief The type of the map that stores the predecessor
1.751 - ///arcs of the shortest paths.
1.752 typedef typename TR::PredMap PredMap;
1.753 - ///The type of the map that stores the distances of the nodes.
1.754 typedef typename TR::DistMap DistMap;
1.755 - ///The type of the map that indicates which nodes are processed.
1.756 typedef typename TR::ProcessedMap ProcessedMap;
1.757 - ///The type of the shortest paths
1.758 typedef typename TR::Path Path;
1.759 - ///The heap type used by the dijkstra algorithm.
1.760 typedef typename TR::Heap Heap;
1.761
1.762 public:
1.763 @@ -1174,11 +1181,12 @@
1.764 static PredMap *createPredMap(const Digraph &) { return 0; };
1.765 SetPredMapBase(const TR &b) : TR(b) {}
1.766 };
1.767 - ///\brief \ref named-func-param "Named parameter"
1.768 - ///for setting PredMap object.
1.769 +
1.770 + ///\brief \ref named-templ-param "Named parameter" for setting
1.771 + ///the predecessor map.
1.772 ///
1.773 - ///\ref named-func-param "Named parameter"
1.774 - ///for setting PredMap object.
1.775 + ///\ref named-templ-param "Named parameter" function for setting
1.776 + ///the map that stores the predecessor arcs of the nodes.
1.777 template<class T>
1.778 DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
1.779 {
1.780 @@ -1192,11 +1200,13 @@
1.781 static DistMap *createDistMap(const Digraph &) { return 0; };
1.782 SetDistMapBase(const TR &b) : TR(b) {}
1.783 };
1.784 - ///\brief \ref named-func-param "Named parameter"
1.785 - ///for setting DistMap object.
1.786 +
1.787 + ///\brief \ref named-templ-param "Named parameter" for setting
1.788 + ///the distance map.
1.789 ///
1.790 - ///\ref named-func-param "Named parameter"
1.791 - ///for setting DistMap object.
1.792 + ///\ref named-templ-param "Named parameter" function for setting
1.793 + ///the map that stores the distances of the nodes calculated
1.794 + ///by the algorithm.
1.795 template<class T>
1.796 DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
1.797 {
1.798 @@ -1210,11 +1220,12 @@
1.799 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1.800 SetProcessedMapBase(const TR &b) : TR(b) {}
1.801 };
1.802 - ///\brief \ref named-func-param "Named parameter"
1.803 - ///for setting ProcessedMap object.
1.804 +
1.805 + ///\brief \ref named-func-param "Named parameter" for setting
1.806 + ///the processed map.
1.807 ///
1.808 - /// \ref named-func-param "Named parameter"
1.809 - ///for setting ProcessedMap object.
1.810 + ///\ref named-templ-param "Named parameter" function for setting
1.811 + ///the map that indicates which nodes are processed.
1.812 template<class T>
1.813 DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1.814 {
1.815 @@ -1227,6 +1238,7 @@
1.816 typedef T Path;
1.817 SetPathBase(const TR &b) : TR(b) {}
1.818 };
1.819 +
1.820 ///\brief \ref named-func-param "Named parameter"
1.821 ///for getting the shortest path to the target node.
1.822 ///
1.823 @@ -1267,15 +1279,15 @@
1.824 /// // Compute shortest path from s to t
1.825 /// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
1.826 ///\endcode
1.827 - ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
1.828 + ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()"
1.829 ///to the end of the parameter list.
1.830 ///\sa DijkstraWizard
1.831 ///\sa Dijkstra
1.832 - template<class GR, class LM>
1.833 - DijkstraWizard<DijkstraWizardBase<GR,LM> >
1.834 - dijkstra(const GR &digraph, const LM &length)
1.835 + template<typename GR, typename LEN>
1.836 + DijkstraWizard<DijkstraWizardBase<GR,LEN> >
1.837 + dijkstra(const GR &digraph, const LEN &length)
1.838 {
1.839 - return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length);
1.840 + return DijkstraWizard<DijkstraWizardBase<GR,LEN> >(digraph,length);
1.841 }
1.842
1.843 } //END OF NAMESPACE LEMON