1.1 --- a/lemon/dijkstra.h Fri Nov 13 12:33:33 2009 +0100
1.2 +++ b/lemon/dijkstra.h Thu Dec 10 17:05:35 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 @@ -69,11 +71,11 @@
1.36
1.37 ///The type of the map that stores the arc lengths.
1.38 ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.39 - typedef LM LengthMap;
1.40 + typedef LEN LengthMap;
1.41 ///The type of the length of the arcs.
1.42 - typedef typename LM::Value Value;
1.43 + typedef typename LEN::Value Value;
1.44
1.45 - /// Operation traits for Dijkstra algorithm.
1.46 + /// Operation traits for %Dijkstra algorithm.
1.47
1.48 /// This class defines the operations that are used in the algorithm.
1.49 /// \see DijkstraDefaultOperationTraits
1.50 @@ -84,7 +86,7 @@
1.51 /// The cross reference type used by the heap.
1.52 /// Usually it is \c Digraph::NodeMap<int>.
1.53 typedef typename Digraph::template NodeMap<int> HeapCrossRef;
1.54 - ///Instantiates a \ref HeapCrossRef.
1.55 + ///Instantiates a \c HeapCrossRef.
1.56
1.57 ///This function instantiates a \ref HeapCrossRef.
1.58 /// \param g is the digraph, to which we would like to define the
1.59 @@ -94,14 +96,14 @@
1.60 return new HeapCrossRef(g);
1.61 }
1.62
1.63 - ///The heap type used by the Dijkstra algorithm.
1.64 + ///The heap type used by the %Dijkstra algorithm.
1.65
1.66 ///The heap type used by the Dijkstra algorithm.
1.67 ///
1.68 ///\sa BinHeap
1.69 ///\sa Dijkstra
1.70 - typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
1.71 - ///Instantiates a \ref Heap.
1.72 + typedef BinHeap<typename LEN::Value, HeapCrossRef, std::less<Value> > Heap;
1.73 + ///Instantiates a \c Heap.
1.74
1.75 ///This function instantiates a \ref Heap.
1.76 static Heap *createHeap(HeapCrossRef& r)
1.77 @@ -116,11 +118,11 @@
1.78 ///arcs of the shortest paths.
1.79 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.80 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.81 - ///Instantiates a PredMap.
1.82 + ///Instantiates a \c PredMap.
1.83
1.84 - ///This function instantiates a PredMap.
1.85 + ///This function instantiates a \ref PredMap.
1.86 ///\param g is the digraph, to which we would like to define the
1.87 - ///PredMap.
1.88 + ///\ref PredMap.
1.89 static PredMap *createPredMap(const Digraph &g)
1.90 {
1.91 return new PredMap(g);
1.92 @@ -132,11 +134,11 @@
1.93 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.94 ///By default it is a NullMap.
1.95 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.96 - ///Instantiates a ProcessedMap.
1.97 + ///Instantiates a \c ProcessedMap.
1.98
1.99 - ///This function instantiates a ProcessedMap.
1.100 + ///This function instantiates a \ref ProcessedMap.
1.101 ///\param g is the digraph, to which
1.102 - ///we would like to define the ProcessedMap
1.103 + ///we would like to define the \ref ProcessedMap.
1.104 #ifdef DOXYGEN
1.105 static ProcessedMap *createProcessedMap(const Digraph &g)
1.106 #else
1.107 @@ -150,12 +152,12 @@
1.108
1.109 ///The type of the map that stores the distances of the nodes.
1.110 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.111 - typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
1.112 - ///Instantiates a DistMap.
1.113 + typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
1.114 + ///Instantiates a \c DistMap.
1.115
1.116 - ///This function instantiates a DistMap.
1.117 + ///This function instantiates a \ref DistMap.
1.118 ///\param g is the digraph, to which we would like to define
1.119 - ///the DistMap
1.120 + ///the \ref DistMap.
1.121 static DistMap *createDistMap(const Digraph &g)
1.122 {
1.123 return new DistMap(g);
1.124 @@ -179,26 +181,19 @@
1.125 ///it can be used easier.
1.126 ///
1.127 ///\tparam GR The type of the digraph the algorithm runs on.
1.128 - ///The default value is \ref ListDigraph.
1.129 - ///The value of GR is not used directly by \ref Dijkstra, it is only
1.130 - ///passed to \ref DijkstraDefaultTraits.
1.131 - ///\tparam LM A readable arc map that determines the lengths of the
1.132 - ///arcs. It is read once for each arc, so the map may involve in
1.133 + ///The default type is \ref ListDigraph.
1.134 + ///\tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
1.135 + ///the lengths of the arcs.
1.136 + ///It is read once for each arc, so the map may involve in
1.137 ///relatively time consuming process to compute the arc lengths if
1.138 ///it is necessary. The default map type is \ref
1.139 - ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
1.140 - ///The value of LM is not used directly by \ref Dijkstra, it is only
1.141 - ///passed to \ref DijkstraDefaultTraits.
1.142 - ///\tparam TR Traits class to set various data types used by the algorithm.
1.143 - ///The default traits class is \ref DijkstraDefaultTraits
1.144 - ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
1.145 - ///for the documentation of a Dijkstra traits class.
1.146 + ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
1.147 #ifdef DOXYGEN
1.148 - template <typename GR, typename LM, typename TR>
1.149 + template <typename GR, typename LEN, typename TR>
1.150 #else
1.151 template <typename GR=ListDigraph,
1.152 - typename LM=typename GR::template ArcMap<int>,
1.153 - typename TR=DijkstraDefaultTraits<GR,LM> >
1.154 + typename LEN=typename GR::template ArcMap<int>,
1.155 + typename TR=DijkstraDefaultTraits<GR,LEN> >
1.156 #endif
1.157 class Dijkstra {
1.158 public:
1.159 @@ -223,10 +218,11 @@
1.160 typedef typename TR::HeapCrossRef HeapCrossRef;
1.161 ///The heap type used by the algorithm.
1.162 typedef typename TR::Heap Heap;
1.163 - ///The operation traits class.
1.164 + ///\brief The \ref DijkstraDefaultOperationTraits "operation traits class"
1.165 + ///of the algorithm.
1.166 typedef typename TR::OperationTraits OperationTraits;
1.167
1.168 - ///The traits class.
1.169 + ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
1.170 typedef TR Traits;
1.171
1.172 private:
1.173 @@ -239,7 +235,7 @@
1.174 //Pointer to the underlying digraph.
1.175 const Digraph *G;
1.176 //Pointer to the length map.
1.177 - const LengthMap *length;
1.178 + const LengthMap *_length;
1.179 //Pointer to the map of predecessors arcs.
1.180 PredMap *_pred;
1.181 //Indicates if _pred is locally allocated (true) or not.
1.182 @@ -290,7 +286,7 @@
1.183
1.184 typedef Dijkstra Create;
1.185
1.186 - ///\name Named template parameters
1.187 + ///\name Named Template Parameters
1.188
1.189 ///@{
1.190
1.191 @@ -304,10 +300,11 @@
1.192 }
1.193 };
1.194 ///\brief \ref named-templ-param "Named parameter" for setting
1.195 - ///PredMap type.
1.196 + ///\c PredMap type.
1.197 ///
1.198 ///\ref named-templ-param "Named parameter" for setting
1.199 - ///PredMap type.
1.200 + ///\c PredMap type.
1.201 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.202 template <class T>
1.203 struct SetPredMap
1.204 : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
1.205 @@ -324,10 +321,11 @@
1.206 }
1.207 };
1.208 ///\brief \ref named-templ-param "Named parameter" for setting
1.209 - ///DistMap type.
1.210 + ///\c DistMap type.
1.211 ///
1.212 ///\ref named-templ-param "Named parameter" for setting
1.213 - ///DistMap type.
1.214 + ///\c DistMap type.
1.215 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.216 template <class T>
1.217 struct SetDistMap
1.218 : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
1.219 @@ -344,10 +342,11 @@
1.220 }
1.221 };
1.222 ///\brief \ref named-templ-param "Named parameter" for setting
1.223 - ///ProcessedMap type.
1.224 + ///\c ProcessedMap type.
1.225 ///
1.226 ///\ref named-templ-param "Named parameter" for setting
1.227 - ///ProcessedMap type.
1.228 + ///\c ProcessedMap type.
1.229 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.230 template <class T>
1.231 struct SetProcessedMap
1.232 : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
1.233 @@ -362,10 +361,10 @@
1.234 }
1.235 };
1.236 ///\brief \ref named-templ-param "Named parameter" for setting
1.237 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.238 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.239 ///
1.240 ///\ref named-templ-param "Named parameter" for setting
1.241 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.242 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.243 ///If you don't set it explicitly, it will be automatically allocated.
1.244 struct SetStandardProcessedMap
1.245 : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
1.246 @@ -388,10 +387,14 @@
1.247 }
1.248 };
1.249 ///\brief \ref named-templ-param "Named parameter" for setting
1.250 - ///heap and cross reference type
1.251 + ///heap and cross reference types
1.252 ///
1.253 ///\ref named-templ-param "Named parameter" for setting heap and cross
1.254 - ///reference type.
1.255 + ///reference types. If this named parameter is used, then external
1.256 + ///heap and cross reference objects must be passed to the algorithm
1.257 + ///using the \ref heap() function before calling \ref run(Node) "run()"
1.258 + ///or \ref init().
1.259 + ///\sa SetStandardHeap
1.260 template <class H, class CR = typename Digraph::template NodeMap<int> >
1.261 struct SetHeap
1.262 : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > {
1.263 @@ -411,12 +414,18 @@
1.264 }
1.265 };
1.266 ///\brief \ref named-templ-param "Named parameter" for setting
1.267 - ///heap and cross reference type with automatic allocation
1.268 + ///heap and cross reference types with automatic allocation
1.269 ///
1.270 ///\ref named-templ-param "Named parameter" for setting heap and cross
1.271 - ///reference type. It can allocate the heap and the cross reference
1.272 - ///object if the cross reference's constructor waits for the digraph as
1.273 - ///parameter and the heap's constructor waits for the cross reference.
1.274 + ///reference types with automatic allocation.
1.275 + ///They should have standard constructor interfaces to be able to
1.276 + ///automatically created by the algorithm (i.e. the digraph should be
1.277 + ///passed to the constructor of the cross reference and the cross
1.278 + ///reference should be passed to the constructor of the heap).
1.279 + ///However external heap and cross reference objects could also be
1.280 + ///passed to the algorithm using the \ref heap() function before
1.281 + ///calling \ref run(Node) "run()" or \ref init().
1.282 + ///\sa SetHeap
1.283 template <class H, class CR = typename Digraph::template NodeMap<int> >
1.284 struct SetStandardHeap
1.285 : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > {
1.286 @@ -433,7 +442,7 @@
1.287 ///\c OperationTraits type
1.288 ///
1.289 ///\ref named-templ-param "Named parameter" for setting
1.290 - ///\ref OperationTraits type.
1.291 + ///\c OperationTraits type.
1.292 template <class T>
1.293 struct SetOperationTraits
1.294 : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
1.295 @@ -452,10 +461,10 @@
1.296 ///Constructor.
1.297
1.298 ///Constructor.
1.299 - ///\param _g The digraph the algorithm runs on.
1.300 - ///\param _length The length map used by the algorithm.
1.301 - Dijkstra(const Digraph& _g, const LengthMap& _length) :
1.302 - G(&_g), length(&_length),
1.303 + ///\param g The digraph the algorithm runs on.
1.304 + ///\param length The length map used by the algorithm.
1.305 + Dijkstra(const Digraph& g, const LengthMap& length) :
1.306 + G(&g), _length(&length),
1.307 _pred(NULL), local_pred(false),
1.308 _dist(NULL), local_dist(false),
1.309 _processed(NULL), local_processed(false),
1.310 @@ -479,16 +488,17 @@
1.311 ///\return <tt> (*this) </tt>
1.312 Dijkstra &lengthMap(const LengthMap &m)
1.313 {
1.314 - length = &m;
1.315 + _length = &m;
1.316 return *this;
1.317 }
1.318
1.319 ///Sets the map that stores the predecessor arcs.
1.320
1.321 ///Sets the map that stores the predecessor arcs.
1.322 - ///If you don't use this function before calling \ref run(),
1.323 - ///it will allocate one. The destructor deallocates this
1.324 - ///automatically allocated map, of course.
1.325 + ///If you don't use this function before calling \ref run(Node) "run()"
1.326 + ///or \ref init(), an instance will be allocated automatically.
1.327 + ///The destructor deallocates this automatically allocated map,
1.328 + ///of course.
1.329 ///\return <tt> (*this) </tt>
1.330 Dijkstra &predMap(PredMap &m)
1.331 {
1.332 @@ -503,9 +513,10 @@
1.333 ///Sets the map that indicates which nodes are processed.
1.334
1.335 ///Sets the map that indicates which nodes are processed.
1.336 - ///If you don't use this function before calling \ref run(),
1.337 - ///it will allocate one. The destructor deallocates this
1.338 - ///automatically allocated map, of course.
1.339 + ///If you don't use this function before calling \ref run(Node) "run()"
1.340 + ///or \ref init(), an instance will be allocated automatically.
1.341 + ///The destructor deallocates this automatically allocated map,
1.342 + ///of course.
1.343 ///\return <tt> (*this) </tt>
1.344 Dijkstra &processedMap(ProcessedMap &m)
1.345 {
1.346 @@ -521,9 +532,10 @@
1.347
1.348 ///Sets the map that stores the distances of the nodes calculated by the
1.349 ///algorithm.
1.350 - ///If you don't use this function before calling \ref run(),
1.351 - ///it will allocate one. The destructor deallocates this
1.352 - ///automatically allocated map, of course.
1.353 + ///If you don't use this function before calling \ref run(Node) "run()"
1.354 + ///or \ref init(), an instance will be allocated automatically.
1.355 + ///The destructor deallocates this automatically allocated map,
1.356 + ///of course.
1.357 ///\return <tt> (*this) </tt>
1.358 Dijkstra &distMap(DistMap &m)
1.359 {
1.360 @@ -538,9 +550,11 @@
1.361 ///Sets the heap and the cross reference used by algorithm.
1.362
1.363 ///Sets the heap and the cross reference used by algorithm.
1.364 - ///If you don't use this function before calling \ref run(),
1.365 - ///it will allocate one. The destructor deallocates this
1.366 - ///automatically allocated heap and cross reference, of course.
1.367 + ///If you don't use this function before calling \ref run(Node) "run()"
1.368 + ///or \ref init(), heap and cross reference instances will be
1.369 + ///allocated automatically.
1.370 + ///The destructor deallocates these automatically allocated objects,
1.371 + ///of course.
1.372 ///\return <tt> (*this) </tt>
1.373 Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
1.374 {
1.375 @@ -567,22 +581,19 @@
1.376
1.377 public:
1.378
1.379 - ///\name Execution control
1.380 - ///The simplest way to execute the algorithm is to use one of the
1.381 - ///member functions called \ref lemon::Dijkstra::run() "run()".
1.382 - ///\n
1.383 - ///If you need more control on the execution, first you must call
1.384 - ///\ref lemon::Dijkstra::init() "init()", then you can add several
1.385 - ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
1.386 - ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
1.387 - ///actual path computation.
1.388 + ///\name Execution Control
1.389 + ///The simplest way to execute the %Dijkstra algorithm is to use
1.390 + ///one of the member functions called \ref run(Node) "run()".\n
1.391 + ///If you need more control on the execution, first you have to call
1.392 + ///\ref init(), then you can add several source nodes with
1.393 + ///\ref addSource(). Finally the actual path computation can be
1.394 + ///performed with one of the \ref start() functions.
1.395
1.396 ///@{
1.397
1.398 + ///\brief Initializes the internal data structures.
1.399 + ///
1.400 ///Initializes the internal data structures.
1.401 -
1.402 - ///Initializes the internal data structures.
1.403 - ///
1.404 void init()
1.405 {
1.406 create_maps();
1.407 @@ -630,12 +641,12 @@
1.408 Node w=G->target(e);
1.409 switch(_heap->state(w)) {
1.410 case Heap::PRE_HEAP:
1.411 - _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
1.412 + _heap->push(w,OperationTraits::plus(oldvalue, (*_length)[e]));
1.413 _pred->set(w,e);
1.414 break;
1.415 case Heap::IN_HEAP:
1.416 {
1.417 - Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
1.418 + Value newvalue = OperationTraits::plus(oldvalue, (*_length)[e]);
1.419 if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
1.420 _heap->decrease(w, newvalue);
1.421 _pred->set(w,e);
1.422 @@ -658,17 +669,16 @@
1.423 return !_heap->empty()?_heap->top():INVALID;
1.424 }
1.425
1.426 - ///\brief Returns \c false if there are nodes
1.427 - ///to be processed.
1.428 - ///
1.429 - ///Returns \c false if there are nodes
1.430 - ///to be processed in the priority heap.
1.431 + ///Returns \c false if there are nodes to be processed.
1.432 +
1.433 + ///Returns \c false if there are nodes to be processed
1.434 + ///in the priority heap.
1.435 bool emptyQueue() const { return _heap->empty(); }
1.436
1.437 - ///Returns the number of the nodes to be processed in the priority heap
1.438 + ///Returns the number of the nodes to be processed.
1.439
1.440 - ///Returns the number of the nodes to be processed in the priority heap.
1.441 - ///
1.442 + ///Returns the number of the nodes to be processed
1.443 + ///in the priority heap.
1.444 int queueSize() const { return _heap->size(); }
1.445
1.446 ///Executes the algorithm.
1.447 @@ -789,11 +799,10 @@
1.448 ///@}
1.449
1.450 ///\name Query Functions
1.451 - ///The result of the %Dijkstra algorithm can be obtained using these
1.452 + ///The results of the %Dijkstra algorithm can be obtained using these
1.453 ///functions.\n
1.454 - ///Either \ref lemon::Dijkstra::run() "run()" or
1.455 - ///\ref lemon::Dijkstra::start() "start()" must be called before
1.456 - ///using them.
1.457 + ///Either \ref run(Node) "run()" or \ref start() should be called
1.458 + ///before using them.
1.459
1.460 ///@{
1.461
1.462 @@ -801,49 +810,49 @@
1.463
1.464 ///Returns the shortest path to a node.
1.465 ///
1.466 - ///\warning \c t should be reachable from the root(s).
1.467 + ///\warning \c t should be reached from the root(s).
1.468 ///
1.469 - ///\pre Either \ref run() or \ref start() must be called before
1.470 - ///using this function.
1.471 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.472 + ///must be called before using this function.
1.473 Path path(Node t) const { return Path(*G, *_pred, t); }
1.474
1.475 ///The distance of a node from the root(s).
1.476
1.477 ///Returns the distance of a node from the root(s).
1.478 ///
1.479 - ///\warning If node \c v is not reachable from the root(s), then
1.480 + ///\warning If node \c v is not reached from the root(s), then
1.481 ///the return value of this function is undefined.
1.482 ///
1.483 - ///\pre Either \ref run() or \ref start() must be called before
1.484 - ///using this function.
1.485 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.486 + ///must be called before using this function.
1.487 Value dist(Node v) const { return (*_dist)[v]; }
1.488
1.489 ///Returns the 'previous arc' of the shortest path tree for a node.
1.490
1.491 ///This function returns the 'previous arc' of the shortest path
1.492 ///tree for the node \c v, i.e. it returns the last arc of a
1.493 - ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
1.494 - ///is not reachable from the root(s) or if \c v is a root.
1.495 + ///shortest path from a root to \c v. It is \c INVALID if \c v
1.496 + ///is not reached from the root(s) or if \c v is a root.
1.497 ///
1.498 ///The shortest path tree used here is equal to the shortest path
1.499 ///tree used in \ref predNode().
1.500 ///
1.501 - ///\pre Either \ref run() or \ref start() must be called before
1.502 - ///using this function.
1.503 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.504 + ///must be called before using this function.
1.505 Arc predArc(Node v) const { return (*_pred)[v]; }
1.506
1.507 ///Returns the 'previous node' of the shortest path tree for a node.
1.508
1.509 ///This function returns the 'previous node' of the shortest path
1.510 ///tree for the node \c v, i.e. it returns the last but one node
1.511 - ///from a shortest path from the root(s) to \c v. It is \c INVALID
1.512 - ///if \c v is not reachable from the root(s) or if \c v is a root.
1.513 + ///from a shortest path from a root to \c v. It is \c INVALID
1.514 + ///if \c v is not reached from the root(s) or if \c v is a root.
1.515 ///
1.516 ///The shortest path tree used here is equal to the shortest path
1.517 ///tree used in \ref predArc().
1.518 ///
1.519 - ///\pre Either \ref run() or \ref start() must be called before
1.520 - ///using this function.
1.521 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.522 + ///must be called before using this function.
1.523 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
1.524 G->source((*_pred)[v]); }
1.525
1.526 @@ -853,7 +862,7 @@
1.527 ///Returns a const reference to the node map that stores the distances
1.528 ///of the nodes calculated by the algorithm.
1.529 ///
1.530 - ///\pre Either \ref run() or \ref init()
1.531 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.532 ///must be called before using this function.
1.533 const DistMap &distMap() const { return *_dist;}
1.534
1.535 @@ -863,14 +872,15 @@
1.536 ///Returns a const reference to the node map that stores the predecessor
1.537 ///arcs, which form the shortest path tree.
1.538 ///
1.539 - ///\pre Either \ref run() or \ref init()
1.540 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.541 ///must be called before using this function.
1.542 const PredMap &predMap() const { return *_pred;}
1.543
1.544 - ///Checks if a node is reachable from the root(s).
1.545 + ///Checks if a node is reached from the root(s).
1.546
1.547 - ///Returns \c true if \c v is reachable from the root(s).
1.548 - ///\pre Either \ref run() or \ref start()
1.549 + ///Returns \c true if \c v is reached from the root(s).
1.550 + ///
1.551 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.552 ///must be called before using this function.
1.553 bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
1.554 Heap::PRE_HEAP; }
1.555 @@ -879,7 +889,8 @@
1.556
1.557 ///Returns \c true if \c v is processed, i.e. the shortest
1.558 ///path to \c v has already found.
1.559 - ///\pre Either \ref run() or \ref init()
1.560 + ///
1.561 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.562 ///must be called before using this function.
1.563 bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
1.564 Heap::POST_HEAP; }
1.565 @@ -888,7 +899,8 @@
1.566
1.567 ///Returns the current distance of a node from the root(s).
1.568 ///It may be decreased in the following processes.
1.569 - ///\pre Either \ref run() or \ref init()
1.570 + ///
1.571 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.572 ///must be called before using this function and
1.573 ///node \c v must be reached but not necessarily processed.
1.574 Value currentDist(Node v) const {
1.575 @@ -903,8 +915,8 @@
1.576
1.577 ///Default traits class of dijkstra() function.
1.578 ///\tparam GR The type of the digraph.
1.579 - ///\tparam LM The type of the length map.
1.580 - template<class GR, class LM>
1.581 + ///\tparam LEN The type of the length map.
1.582 + template<class GR, class LEN>
1.583 struct DijkstraWizardDefaultTraits
1.584 {
1.585 ///The type of the digraph the algorithm runs on.
1.586 @@ -913,9 +925,9 @@
1.587
1.588 ///The type of the map that stores the arc lengths.
1.589 ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.590 - typedef LM LengthMap;
1.591 + typedef LEN LengthMap;
1.592 ///The type of the length of the arcs.
1.593 - typedef typename LM::Value Value;
1.594 + typedef typename LEN::Value Value;
1.595
1.596 /// Operation traits for Dijkstra algorithm.
1.597
1.598 @@ -997,7 +1009,7 @@
1.599
1.600 ///The type of the map that stores the distances of the nodes.
1.601 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.602 - typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
1.603 + typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
1.604 ///Instantiates a DistMap.
1.605
1.606 ///This function instantiates a DistMap.
1.607 @@ -1023,10 +1035,10 @@
1.608 /// as well as the \ref Dijkstra class.
1.609 /// The \ref DijkstraWizardBase is a class to be the default traits of the
1.610 /// \ref DijkstraWizard class.
1.611 - template<class GR,class LM>
1.612 - class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
1.613 + template<typename GR, typename LEN>
1.614 + class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN>
1.615 {
1.616 - typedef DijkstraWizardDefaultTraits<GR,LM> Base;
1.617 + typedef DijkstraWizardDefaultTraits<GR,LEN> Base;
1.618 protected:
1.619 //The type of the nodes in the digraph.
1.620 typedef typename Base::Digraph::Node Node;
1.621 @@ -1060,9 +1072,9 @@
1.622 /// others are initiated to \c 0.
1.623 /// \param g The digraph the algorithm runs on.
1.624 /// \param l The length map.
1.625 - DijkstraWizardBase(const GR &g,const LM &l) :
1.626 + DijkstraWizardBase(const GR &g,const LEN &l) :
1.627 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
1.628 - _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
1.629 + _length(reinterpret_cast<void*>(const_cast<LEN*>(&l))),
1.630 _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
1.631
1.632 };
1.633 @@ -1071,8 +1083,8 @@
1.634
1.635 /// This auxiliary class is created to implement the
1.636 /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
1.637 - /// It does not have own \ref run() method, it uses the functions
1.638 - /// and features of the plain \ref Dijkstra.
1.639 + /// It does not have own \ref run(Node) "run()" method, it uses the
1.640 + /// functions and features of the plain \ref Dijkstra.
1.641 ///
1.642 /// This class should only be used through the \ref dijkstra() function,
1.643 /// which makes it easier to use the algorithm.
1.644 @@ -1267,15 +1279,15 @@
1.645 /// // Compute shortest path from s to t
1.646 /// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
1.647 ///\endcode
1.648 - ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
1.649 + ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()"
1.650 ///to the end of the parameter list.
1.651 ///\sa DijkstraWizard
1.652 ///\sa Dijkstra
1.653 - template<class GR, class LM>
1.654 - DijkstraWizard<DijkstraWizardBase<GR,LM> >
1.655 - dijkstra(const GR &digraph, const LM &length)
1.656 + template<typename GR, typename LEN>
1.657 + DijkstraWizard<DijkstraWizardBase<GR,LEN> >
1.658 + dijkstra(const GR &digraph, const LEN &length)
1.659 {
1.660 - return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length);
1.661 + return DijkstraWizard<DijkstraWizardBase<GR,LEN> >(digraph,length);
1.662 }
1.663
1.664 } //END OF NAMESPACE LEMON