1.1 --- a/lemon/dijkstra.h Mon Jan 12 23:11:39 2009 +0100
1.2 +++ b/lemon/dijkstra.h Thu Nov 05 15:48:01 2009 +0100
1.3 @@ -38,8 +38,10 @@
1.4 ///
1.5 /// This operation traits class defines all computational operations and
1.6 /// constants which are used in the Dijkstra algorithm.
1.7 - template <typename Value>
1.8 + template <typename V>
1.9 struct DijkstraDefaultOperationTraits {
1.10 + /// \e
1.11 + typedef V Value;
1.12 /// \brief Gives back the zero value of the type.
1.13 static Value zero() {
1.14 return static_cast<Value>(0);
1.15 @@ -58,8 +60,8 @@
1.16
1.17 ///Default traits class of Dijkstra class.
1.18 ///\tparam GR The type of the digraph.
1.19 - ///\tparam LM The type of the length map.
1.20 - template<class GR, class LM>
1.21 + ///\tparam LEN The type of the length map.
1.22 + template<typename GR, typename LEN>
1.23 struct DijkstraDefaultTraits
1.24 {
1.25 ///The type of the digraph the algorithm runs on.
1.26 @@ -68,12 +70,12 @@
1.27 ///The type of the map that stores the arc lengths.
1.28
1.29 ///The type of the map that stores the arc lengths.
1.30 - ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.31 - typedef LM LengthMap;
1.32 - ///The type of the length of the arcs.
1.33 - typedef typename LM::Value Value;
1.34 + ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
1.35 + typedef LEN LengthMap;
1.36 + ///The type of the arc lengths.
1.37 + typedef typename LEN::Value Value;
1.38
1.39 - /// Operation traits for Dijkstra algorithm.
1.40 + /// Operation traits for %Dijkstra algorithm.
1.41
1.42 /// This class defines the operations that are used in the algorithm.
1.43 /// \see DijkstraDefaultOperationTraits
1.44 @@ -84,7 +86,7 @@
1.45 /// The cross reference type used by the heap.
1.46 /// Usually it is \c Digraph::NodeMap<int>.
1.47 typedef typename Digraph::template NodeMap<int> HeapCrossRef;
1.48 - ///Instantiates a \ref HeapCrossRef.
1.49 + ///Instantiates a \c HeapCrossRef.
1.50
1.51 ///This function instantiates a \ref HeapCrossRef.
1.52 /// \param g is the digraph, to which we would like to define the
1.53 @@ -94,14 +96,14 @@
1.54 return new HeapCrossRef(g);
1.55 }
1.56
1.57 - ///The heap type used by the Dijkstra algorithm.
1.58 + ///The heap type used by the %Dijkstra algorithm.
1.59
1.60 ///The heap type used by the Dijkstra algorithm.
1.61 ///
1.62 ///\sa BinHeap
1.63 ///\sa Dijkstra
1.64 - typedef BinHeap<typename LM::Value, HeapCrossRef, std::less<Value> > Heap;
1.65 - ///Instantiates a \ref Heap.
1.66 + typedef BinHeap<typename LEN::Value, HeapCrossRef, std::less<Value> > Heap;
1.67 + ///Instantiates a \c Heap.
1.68
1.69 ///This function instantiates a \ref Heap.
1.70 static Heap *createHeap(HeapCrossRef& r)
1.71 @@ -114,13 +116,13 @@
1.72 ///
1.73 ///The type of the map that stores the predecessor
1.74 ///arcs of the shortest paths.
1.75 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.76 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.77 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.78 - ///Instantiates a PredMap.
1.79 + ///Instantiates a \c PredMap.
1.80
1.81 - ///This function instantiates a PredMap.
1.82 + ///This function instantiates a \ref PredMap.
1.83 ///\param g is the digraph, to which we would like to define the
1.84 - ///PredMap.
1.85 + ///\ref PredMap.
1.86 static PredMap *createPredMap(const Digraph &g)
1.87 {
1.88 return new PredMap(g);
1.89 @@ -129,14 +131,14 @@
1.90 ///The type of the map that indicates which nodes are processed.
1.91
1.92 ///The type of the map that indicates which nodes are processed.
1.93 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.94 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.95 ///By default it is a NullMap.
1.96 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.97 - ///Instantiates a ProcessedMap.
1.98 + ///Instantiates a \c ProcessedMap.
1.99
1.100 - ///This function instantiates a ProcessedMap.
1.101 + ///This function instantiates a \ref ProcessedMap.
1.102 ///\param g is the digraph, to which
1.103 - ///we would like to define the ProcessedMap
1.104 + ///we would like to define the \ref ProcessedMap.
1.105 #ifdef DOXYGEN
1.106 static ProcessedMap *createProcessedMap(const Digraph &g)
1.107 #else
1.108 @@ -149,13 +151,13 @@
1.109 ///The type of the map that stores the distances of the nodes.
1.110
1.111 ///The type of the map that stores the distances of the nodes.
1.112 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.113 - typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
1.114 - ///Instantiates a DistMap.
1.115 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.116 + typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
1.117 + ///Instantiates a \c DistMap.
1.118
1.119 - ///This function instantiates a DistMap.
1.120 + ///This function instantiates a \ref DistMap.
1.121 ///\param g is the digraph, to which we would like to define
1.122 - ///the DistMap
1.123 + ///the \ref DistMap.
1.124 static DistMap *createDistMap(const Digraph &g)
1.125 {
1.126 return new DistMap(g);
1.127 @@ -167,6 +169,10 @@
1.128 /// \ingroup shortest_path
1.129 ///This class provides an efficient implementation of the %Dijkstra algorithm.
1.130 ///
1.131 + ///The %Dijkstra algorithm solves the single-source shortest path problem
1.132 + ///when all arc lengths are non-negative. If there are negative lengths,
1.133 + ///the BellmanFord algorithm should be used instead.
1.134 + ///
1.135 ///The arc lengths are passed to the algorithm using a
1.136 ///\ref concepts::ReadMap "ReadMap",
1.137 ///so it is easy to change it to any kind of length.
1.138 @@ -180,18 +186,18 @@
1.139 ///
1.140 ///\tparam GR The type of the digraph the algorithm runs on.
1.141 ///The default type is \ref ListDigraph.
1.142 - ///\tparam LM A \ref concepts::ReadMap "readable" arc map that specifies
1.143 + ///\tparam LEN A \ref concepts::ReadMap "readable" arc map that specifies
1.144 ///the lengths of the arcs.
1.145 ///It is read once for each arc, so the map may involve in
1.146 ///relatively time consuming process to compute the arc lengths if
1.147 ///it is necessary. The default map type is \ref
1.148 ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
1.149 #ifdef DOXYGEN
1.150 - template <typename GR, typename LM, typename TR>
1.151 + template <typename GR, typename LEN, typename TR>
1.152 #else
1.153 template <typename GR=ListDigraph,
1.154 - typename LM=typename GR::template ArcMap<int>,
1.155 - typename TR=DijkstraDefaultTraits<GR,LM> >
1.156 + typename LEN=typename GR::template ArcMap<int>,
1.157 + typename TR=DijkstraDefaultTraits<GR,LEN> >
1.158 #endif
1.159 class Dijkstra {
1.160 public:
1.161 @@ -199,7 +205,7 @@
1.162 ///The type of the digraph the algorithm runs on.
1.163 typedef typename TR::Digraph Digraph;
1.164
1.165 - ///The type of the length of the arcs.
1.166 + ///The type of the arc lengths.
1.167 typedef typename TR::LengthMap::Value Value;
1.168 ///The type of the map that stores the arc lengths.
1.169 typedef typename TR::LengthMap LengthMap;
1.170 @@ -216,7 +222,8 @@
1.171 typedef typename TR::HeapCrossRef HeapCrossRef;
1.172 ///The heap type used by the algorithm.
1.173 typedef typename TR::Heap Heap;
1.174 - ///The operation traits class.
1.175 + ///\brief The \ref DijkstraDefaultOperationTraits "operation traits class"
1.176 + ///of the algorithm.
1.177 typedef typename TR::OperationTraits OperationTraits;
1.178
1.179 ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
1.180 @@ -232,7 +239,7 @@
1.181 //Pointer to the underlying digraph.
1.182 const Digraph *G;
1.183 //Pointer to the length map.
1.184 - const LengthMap *length;
1.185 + const LengthMap *_length;
1.186 //Pointer to the map of predecessors arcs.
1.187 PredMap *_pred;
1.188 //Indicates if _pred is locally allocated (true) or not.
1.189 @@ -283,7 +290,7 @@
1.190
1.191 typedef Dijkstra Create;
1.192
1.193 - ///\name Named template parameters
1.194 + ///\name Named Template Parameters
1.195
1.196 ///@{
1.197
1.198 @@ -297,11 +304,11 @@
1.199 }
1.200 };
1.201 ///\brief \ref named-templ-param "Named parameter" for setting
1.202 - ///PredMap type.
1.203 + ///\c PredMap type.
1.204 ///
1.205 ///\ref named-templ-param "Named parameter" for setting
1.206 - ///PredMap type.
1.207 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.208 + ///\c PredMap type.
1.209 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.210 template <class T>
1.211 struct SetPredMap
1.212 : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
1.213 @@ -318,11 +325,11 @@
1.214 }
1.215 };
1.216 ///\brief \ref named-templ-param "Named parameter" for setting
1.217 - ///DistMap type.
1.218 + ///\c DistMap type.
1.219 ///
1.220 ///\ref named-templ-param "Named parameter" for setting
1.221 - ///DistMap type.
1.222 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.223 + ///\c DistMap type.
1.224 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.225 template <class T>
1.226 struct SetDistMap
1.227 : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
1.228 @@ -339,11 +346,11 @@
1.229 }
1.230 };
1.231 ///\brief \ref named-templ-param "Named parameter" for setting
1.232 - ///ProcessedMap type.
1.233 + ///\c ProcessedMap type.
1.234 ///
1.235 ///\ref named-templ-param "Named parameter" for setting
1.236 - ///ProcessedMap type.
1.237 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.238 + ///\c ProcessedMap type.
1.239 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.240 template <class T>
1.241 struct SetProcessedMap
1.242 : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
1.243 @@ -358,10 +365,10 @@
1.244 }
1.245 };
1.246 ///\brief \ref named-templ-param "Named parameter" for setting
1.247 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.248 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.249 ///
1.250 ///\ref named-templ-param "Named parameter" for setting
1.251 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.252 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.253 ///If you don't set it explicitly, it will be automatically allocated.
1.254 struct SetStandardProcessedMap
1.255 : public Dijkstra< Digraph, LengthMap, SetStandardProcessedMapTraits > {
1.256 @@ -439,7 +446,8 @@
1.257 ///\c OperationTraits type
1.258 ///
1.259 ///\ref named-templ-param "Named parameter" for setting
1.260 - ///\ref OperationTraits type.
1.261 + ///\c OperationTraits type.
1.262 + /// For more information see \ref DijkstraDefaultOperationTraits.
1.263 template <class T>
1.264 struct SetOperationTraits
1.265 : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
1.266 @@ -458,10 +466,10 @@
1.267 ///Constructor.
1.268
1.269 ///Constructor.
1.270 - ///\param _g The digraph the algorithm runs on.
1.271 - ///\param _length The length map used by the algorithm.
1.272 - Dijkstra(const Digraph& _g, const LengthMap& _length) :
1.273 - G(&_g), length(&_length),
1.274 + ///\param g The digraph the algorithm runs on.
1.275 + ///\param length The length map used by the algorithm.
1.276 + Dijkstra(const Digraph& g, const LengthMap& length) :
1.277 + G(&g), _length(&length),
1.278 _pred(NULL), local_pred(false),
1.279 _dist(NULL), local_dist(false),
1.280 _processed(NULL), local_processed(false),
1.281 @@ -485,7 +493,7 @@
1.282 ///\return <tt> (*this) </tt>
1.283 Dijkstra &lengthMap(const LengthMap &m)
1.284 {
1.285 - length = &m;
1.286 + _length = &m;
1.287 return *this;
1.288 }
1.289
1.290 @@ -581,8 +589,8 @@
1.291 ///\name Execution Control
1.292 ///The simplest way to execute the %Dijkstra algorithm is to use
1.293 ///one of the member functions called \ref run(Node) "run()".\n
1.294 - ///If you need more control on the execution, first you have to call
1.295 - ///\ref init(), then you can add several source nodes with
1.296 + ///If you need better control on the execution, you have to call
1.297 + ///\ref init() first, then you can add several source nodes with
1.298 ///\ref addSource(). Finally the actual path computation can be
1.299 ///performed with one of the \ref start() functions.
1.300
1.301 @@ -638,12 +646,12 @@
1.302 Node w=G->target(e);
1.303 switch(_heap->state(w)) {
1.304 case Heap::PRE_HEAP:
1.305 - _heap->push(w,OperationTraits::plus(oldvalue, (*length)[e]));
1.306 + _heap->push(w,OperationTraits::plus(oldvalue, (*_length)[e]));
1.307 _pred->set(w,e);
1.308 break;
1.309 case Heap::IN_HEAP:
1.310 {
1.311 - Value newvalue = OperationTraits::plus(oldvalue, (*length)[e]);
1.312 + Value newvalue = OperationTraits::plus(oldvalue, (*_length)[e]);
1.313 if ( OperationTraits::less(newvalue, (*_heap)[w]) ) {
1.314 _heap->decrease(w, newvalue);
1.315 _pred->set(w,e);
1.316 @@ -798,14 +806,14 @@
1.317 ///\name Query Functions
1.318 ///The results of the %Dijkstra algorithm can be obtained using these
1.319 ///functions.\n
1.320 - ///Either \ref run(Node) "run()" or \ref start() should be called
1.321 + ///Either \ref run(Node) "run()" or \ref init() should be called
1.322 ///before using them.
1.323
1.324 ///@{
1.325
1.326 - ///The shortest path to a node.
1.327 + ///The shortest path to the given node.
1.328
1.329 - ///Returns the shortest path to a node.
1.330 + ///Returns the shortest path to the given node from the root(s).
1.331 ///
1.332 ///\warning \c t should be reached from the root(s).
1.333 ///
1.334 @@ -813,9 +821,9 @@
1.335 ///must be called before using this function.
1.336 Path path(Node t) const { return Path(*G, *_pred, t); }
1.337
1.338 - ///The distance of a node from the root(s).
1.339 + ///The distance of the given node from the root(s).
1.340
1.341 - ///Returns the distance of a node from the root(s).
1.342 + ///Returns the distance of the given node from the root(s).
1.343 ///
1.344 ///\warning If node \c v is not reached from the root(s), then
1.345 ///the return value of this function is undefined.
1.346 @@ -824,29 +832,31 @@
1.347 ///must be called before using this function.
1.348 Value dist(Node v) const { return (*_dist)[v]; }
1.349
1.350 - ///Returns the 'previous arc' of the shortest path tree for a node.
1.351 -
1.352 + ///\brief Returns the 'previous arc' of the shortest path tree for
1.353 + ///the given node.
1.354 + ///
1.355 ///This function returns the 'previous arc' of the shortest path
1.356 ///tree for the node \c v, i.e. it returns the last arc of a
1.357 ///shortest path from a root to \c v. It is \c INVALID if \c v
1.358 ///is not reached from the root(s) or if \c v is a root.
1.359 ///
1.360 ///The shortest path tree used here is equal to the shortest path
1.361 - ///tree used in \ref predNode().
1.362 + ///tree used in \ref predNode() and \ref predMap().
1.363 ///
1.364 ///\pre Either \ref run(Node) "run()" or \ref init()
1.365 ///must be called before using this function.
1.366 Arc predArc(Node v) const { return (*_pred)[v]; }
1.367
1.368 - ///Returns the 'previous node' of the shortest path tree for a node.
1.369 -
1.370 + ///\brief Returns the 'previous node' of the shortest path tree for
1.371 + ///the given node.
1.372 + ///
1.373 ///This function returns the 'previous node' of the shortest path
1.374 ///tree for the node \c v, i.e. it returns the last but one node
1.375 - ///from a shortest path from a root to \c v. It is \c INVALID
1.376 + ///of a shortest path from a root to \c v. It is \c INVALID
1.377 ///if \c v is not reached from the root(s) or if \c v is a root.
1.378 ///
1.379 ///The shortest path tree used here is equal to the shortest path
1.380 - ///tree used in \ref predArc().
1.381 + ///tree used in \ref predArc() and \ref predMap().
1.382 ///
1.383 ///\pre Either \ref run(Node) "run()" or \ref init()
1.384 ///must be called before using this function.
1.385 @@ -867,13 +877,13 @@
1.386 ///predecessor arcs.
1.387 ///
1.388 ///Returns a const reference to the node map that stores the predecessor
1.389 - ///arcs, which form the shortest path tree.
1.390 + ///arcs, which form the shortest path tree (forest).
1.391 ///
1.392 ///\pre Either \ref run(Node) "run()" or \ref init()
1.393 ///must be called before using this function.
1.394 const PredMap &predMap() const { return *_pred;}
1.395
1.396 - ///Checks if a node is reached from the root(s).
1.397 + ///Checks if the given node is reached from the root(s).
1.398
1.399 ///Returns \c true if \c v is reached from the root(s).
1.400 ///
1.401 @@ -892,9 +902,9 @@
1.402 bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
1.403 Heap::POST_HEAP; }
1.404
1.405 - ///The current distance of a node from the root(s).
1.406 + ///The current distance of the given node from the root(s).
1.407
1.408 - ///Returns the current distance of a node from the root(s).
1.409 + ///Returns the current distance of the given node from the root(s).
1.410 ///It may be decreased in the following processes.
1.411 ///
1.412 ///\pre Either \ref run(Node) "run()" or \ref init()
1.413 @@ -912,8 +922,8 @@
1.414
1.415 ///Default traits class of dijkstra() function.
1.416 ///\tparam GR The type of the digraph.
1.417 - ///\tparam LM The type of the length map.
1.418 - template<class GR, class LM>
1.419 + ///\tparam LEN The type of the length map.
1.420 + template<class GR, class LEN>
1.421 struct DijkstraWizardDefaultTraits
1.422 {
1.423 ///The type of the digraph the algorithm runs on.
1.424 @@ -921,10 +931,10 @@
1.425 ///The type of the map that stores the arc lengths.
1.426
1.427 ///The type of the map that stores the arc lengths.
1.428 - ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.429 - typedef LM LengthMap;
1.430 - ///The type of the length of the arcs.
1.431 - typedef typename LM::Value Value;
1.432 + ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
1.433 + typedef LEN LengthMap;
1.434 + ///The type of the arc lengths.
1.435 + typedef typename LEN::Value Value;
1.436
1.437 /// Operation traits for Dijkstra algorithm.
1.438
1.439 @@ -970,7 +980,7 @@
1.440 ///
1.441 ///The type of the map that stores the predecessor
1.442 ///arcs of the shortest paths.
1.443 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.444 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.445 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.446 ///Instantiates a PredMap.
1.447
1.448 @@ -985,7 +995,7 @@
1.449 ///The type of the map that indicates which nodes are processed.
1.450
1.451 ///The type of the map that indicates which nodes are processed.
1.452 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.453 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.454 ///By default it is a NullMap.
1.455 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.456 ///Instantiates a ProcessedMap.
1.457 @@ -1005,8 +1015,8 @@
1.458 ///The type of the map that stores the distances of the nodes.
1.459
1.460 ///The type of the map that stores the distances of the nodes.
1.461 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.462 - typedef typename Digraph::template NodeMap<typename LM::Value> DistMap;
1.463 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.464 + typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
1.465 ///Instantiates a DistMap.
1.466
1.467 ///This function instantiates a DistMap.
1.468 @@ -1020,22 +1030,19 @@
1.469 ///The type of the shortest paths.
1.470
1.471 ///The type of the shortest paths.
1.472 - ///It must meet the \ref concepts::Path "Path" concept.
1.473 + ///It must conform to the \ref concepts::Path "Path" concept.
1.474 typedef lemon::Path<Digraph> Path;
1.475 };
1.476
1.477 /// Default traits class used by DijkstraWizard
1.478
1.479 - /// To make it easier to use Dijkstra algorithm
1.480 - /// we have created a wizard class.
1.481 - /// This \ref DijkstraWizard class needs default traits,
1.482 - /// as well as the \ref Dijkstra class.
1.483 - /// The \ref DijkstraWizardBase is a class to be the default traits of the
1.484 - /// \ref DijkstraWizard class.
1.485 - template<class GR,class LM>
1.486 - class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LM>
1.487 + /// Default traits class used by DijkstraWizard.
1.488 + /// \tparam GR The type of the digraph.
1.489 + /// \tparam LEN The type of the length map.
1.490 + template<typename GR, typename LEN>
1.491 + class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN>
1.492 {
1.493 - typedef DijkstraWizardDefaultTraits<GR,LM> Base;
1.494 + typedef DijkstraWizardDefaultTraits<GR,LEN> Base;
1.495 protected:
1.496 //The type of the nodes in the digraph.
1.497 typedef typename Base::Digraph::Node Node;
1.498 @@ -1069,9 +1076,9 @@
1.499 /// others are initiated to \c 0.
1.500 /// \param g The digraph the algorithm runs on.
1.501 /// \param l The length map.
1.502 - DijkstraWizardBase(const GR &g,const LM &l) :
1.503 + DijkstraWizardBase(const GR &g,const LEN &l) :
1.504 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
1.505 - _length(reinterpret_cast<void*>(const_cast<LM*>(&l))),
1.506 + _length(reinterpret_cast<void*>(const_cast<LEN*>(&l))),
1.507 _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
1.508
1.509 };
1.510 @@ -1090,7 +1097,6 @@
1.511 {
1.512 typedef TR Base;
1.513
1.514 - ///The type of the digraph the algorithm runs on.
1.515 typedef typename TR::Digraph Digraph;
1.516
1.517 typedef typename Digraph::Node Node;
1.518 @@ -1098,20 +1104,12 @@
1.519 typedef typename Digraph::Arc Arc;
1.520 typedef typename Digraph::OutArcIt OutArcIt;
1.521
1.522 - ///The type of the map that stores the arc lengths.
1.523 typedef typename TR::LengthMap LengthMap;
1.524 - ///The type of the length of the arcs.
1.525 typedef typename LengthMap::Value Value;
1.526 - ///\brief The type of the map that stores the predecessor
1.527 - ///arcs of the shortest paths.
1.528 typedef typename TR::PredMap PredMap;
1.529 - ///The type of the map that stores the distances of the nodes.
1.530 typedef typename TR::DistMap DistMap;
1.531 - ///The type of the map that indicates which nodes are processed.
1.532 typedef typename TR::ProcessedMap ProcessedMap;
1.533 - ///The type of the shortest paths
1.534 typedef typename TR::Path Path;
1.535 - ///The heap type used by the dijkstra algorithm.
1.536 typedef typename TR::Heap Heap;
1.537
1.538 public:
1.539 @@ -1183,11 +1181,12 @@
1.540 static PredMap *createPredMap(const Digraph &) { return 0; };
1.541 SetPredMapBase(const TR &b) : TR(b) {}
1.542 };
1.543 - ///\brief \ref named-func-param "Named parameter"
1.544 - ///for setting PredMap object.
1.545 +
1.546 + ///\brief \ref named-templ-param "Named parameter" for setting
1.547 + ///the predecessor map.
1.548 ///
1.549 - ///\ref named-func-param "Named parameter"
1.550 - ///for setting PredMap object.
1.551 + ///\ref named-templ-param "Named parameter" function for setting
1.552 + ///the map that stores the predecessor arcs of the nodes.
1.553 template<class T>
1.554 DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
1.555 {
1.556 @@ -1201,11 +1200,13 @@
1.557 static DistMap *createDistMap(const Digraph &) { return 0; };
1.558 SetDistMapBase(const TR &b) : TR(b) {}
1.559 };
1.560 - ///\brief \ref named-func-param "Named parameter"
1.561 - ///for setting DistMap object.
1.562 +
1.563 + ///\brief \ref named-templ-param "Named parameter" for setting
1.564 + ///the distance map.
1.565 ///
1.566 - ///\ref named-func-param "Named parameter"
1.567 - ///for setting DistMap object.
1.568 + ///\ref named-templ-param "Named parameter" function for setting
1.569 + ///the map that stores the distances of the nodes calculated
1.570 + ///by the algorithm.
1.571 template<class T>
1.572 DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
1.573 {
1.574 @@ -1219,11 +1220,12 @@
1.575 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1.576 SetProcessedMapBase(const TR &b) : TR(b) {}
1.577 };
1.578 - ///\brief \ref named-func-param "Named parameter"
1.579 - ///for setting ProcessedMap object.
1.580 +
1.581 + ///\brief \ref named-func-param "Named parameter" for setting
1.582 + ///the processed map.
1.583 ///
1.584 - /// \ref named-func-param "Named parameter"
1.585 - ///for setting ProcessedMap object.
1.586 + ///\ref named-templ-param "Named parameter" function for setting
1.587 + ///the map that indicates which nodes are processed.
1.588 template<class T>
1.589 DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1.590 {
1.591 @@ -1236,6 +1238,7 @@
1.592 typedef T Path;
1.593 SetPathBase(const TR &b) : TR(b) {}
1.594 };
1.595 +
1.596 ///\brief \ref named-func-param "Named parameter"
1.597 ///for getting the shortest path to the target node.
1.598 ///
1.599 @@ -1280,11 +1283,11 @@
1.600 ///to the end of the parameter list.
1.601 ///\sa DijkstraWizard
1.602 ///\sa Dijkstra
1.603 - template<class GR, class LM>
1.604 - DijkstraWizard<DijkstraWizardBase<GR,LM> >
1.605 - dijkstra(const GR &digraph, const LM &length)
1.606 + template<typename GR, typename LEN>
1.607 + DijkstraWizard<DijkstraWizardBase<GR,LEN> >
1.608 + dijkstra(const GR &digraph, const LEN &length)
1.609 {
1.610 - return DijkstraWizard<DijkstraWizardBase<GR,LM> >(digraph,length);
1.611 + return DijkstraWizard<DijkstraWizardBase<GR,LEN> >(digraph,length);
1.612 }
1.613
1.614 } //END OF NAMESPACE LEMON