1.1 --- a/lemon/dijkstra.h Tue Dec 20 17:44:38 2011 +0100
1.2 +++ b/lemon/dijkstra.h Tue Dec 20 18:15:14 2011 +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-2009
1.8 + * Copyright (C) 2003-2010
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -70,9 +70,9 @@
1.13 ///The type of the map that stores the arc lengths.
1.14
1.15 ///The type of the map that stores the arc lengths.
1.16 - ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.17 + ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
1.18 typedef LEN LengthMap;
1.19 - ///The type of the length of the arcs.
1.20 + ///The type of the arc lengths.
1.21 typedef typename LEN::Value Value;
1.22
1.23 /// Operation traits for %Dijkstra algorithm.
1.24 @@ -116,7 +116,7 @@
1.25 ///
1.26 ///The type of the map that stores the predecessor
1.27 ///arcs of the shortest paths.
1.28 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.29 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.30 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.31 ///Instantiates a \c PredMap.
1.32
1.33 @@ -131,8 +131,8 @@
1.34 ///The type of the map that indicates which nodes are processed.
1.35
1.36 ///The type of the map that indicates which nodes are processed.
1.37 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.38 - ///By default it is a NullMap.
1.39 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.40 + ///By default, it is a NullMap.
1.41 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.42 ///Instantiates a \c ProcessedMap.
1.43
1.44 @@ -151,7 +151,7 @@
1.45 ///The type of the map that stores the distances of the nodes.
1.46
1.47 ///The type of the map that stores the distances of the nodes.
1.48 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.49 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.50 typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
1.51 ///Instantiates a \c DistMap.
1.52
1.53 @@ -169,6 +169,10 @@
1.54 /// \ingroup shortest_path
1.55 ///This class provides an efficient implementation of the %Dijkstra algorithm.
1.56 ///
1.57 + ///The %Dijkstra algorithm solves the single-source shortest path problem
1.58 + ///when all arc lengths are non-negative. If there are negative lengths,
1.59 + ///the BellmanFord algorithm should be used instead.
1.60 + ///
1.61 ///The arc lengths are passed to the algorithm using a
1.62 ///\ref concepts::ReadMap "ReadMap",
1.63 ///so it is easy to change it to any kind of length.
1.64 @@ -188,6 +192,11 @@
1.65 ///relatively time consuming process to compute the arc lengths if
1.66 ///it is necessary. The default map type is \ref
1.67 ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
1.68 + ///\tparam TR The traits class that defines various types used by the
1.69 + ///algorithm. By default, it is \ref DijkstraDefaultTraits
1.70 + ///"DijkstraDefaultTraits<GR, LEN>".
1.71 + ///In most cases, this parameter should not be set directly,
1.72 + ///consider to use the named template parameters instead.
1.73 #ifdef DOXYGEN
1.74 template <typename GR, typename LEN, typename TR>
1.75 #else
1.76 @@ -201,8 +210,8 @@
1.77 ///The type of the digraph the algorithm runs on.
1.78 typedef typename TR::Digraph Digraph;
1.79
1.80 - ///The type of the length of the arcs.
1.81 - typedef typename TR::LengthMap::Value Value;
1.82 + ///The type of the arc lengths.
1.83 + typedef typename TR::Value Value;
1.84 ///The type of the map that stores the arc lengths.
1.85 typedef typename TR::LengthMap LengthMap;
1.86 ///\brief The type of the map that stores the predecessor arcs of the
1.87 @@ -304,7 +313,7 @@
1.88 ///
1.89 ///\ref named-templ-param "Named parameter" for setting
1.90 ///\c PredMap type.
1.91 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.92 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.93 template <class T>
1.94 struct SetPredMap
1.95 : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
1.96 @@ -325,7 +334,7 @@
1.97 ///
1.98 ///\ref named-templ-param "Named parameter" for setting
1.99 ///\c DistMap type.
1.100 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.101 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.102 template <class T>
1.103 struct SetDistMap
1.104 : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
1.105 @@ -346,7 +355,7 @@
1.106 ///
1.107 ///\ref named-templ-param "Named parameter" for setting
1.108 ///\c ProcessedMap type.
1.109 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.110 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.111 template <class T>
1.112 struct SetProcessedMap
1.113 : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
1.114 @@ -422,7 +431,7 @@
1.115 ///automatically created by the algorithm (i.e. the digraph should be
1.116 ///passed to the constructor of the cross reference and the cross
1.117 ///reference should be passed to the constructor of the heap).
1.118 - ///However external heap and cross reference objects could also be
1.119 + ///However, external heap and cross reference objects could also be
1.120 ///passed to the algorithm using the \ref heap() function before
1.121 ///calling \ref run(Node) "run()" or \ref init().
1.122 ///\sa SetHeap
1.123 @@ -443,6 +452,7 @@
1.124 ///
1.125 ///\ref named-templ-param "Named parameter" for setting
1.126 ///\c OperationTraits type.
1.127 + /// For more information, see \ref DijkstraDefaultOperationTraits.
1.128 template <class T>
1.129 struct SetOperationTraits
1.130 : public Dijkstra<Digraph, LengthMap, SetOperationTraitsTraits<T> > {
1.131 @@ -584,8 +594,8 @@
1.132 ///\name Execution Control
1.133 ///The simplest way to execute the %Dijkstra algorithm is to use
1.134 ///one of the member functions called \ref run(Node) "run()".\n
1.135 - ///If you need more control on the execution, first you have to call
1.136 - ///\ref init(), then you can add several source nodes with
1.137 + ///If you need better control on the execution, you have to call
1.138 + ///\ref init() first, then you can add several source nodes with
1.139 ///\ref addSource(). Finally the actual path computation can be
1.140 ///performed with one of the \ref start() functions.
1.141
1.142 @@ -801,14 +811,14 @@
1.143 ///\name Query Functions
1.144 ///The results of the %Dijkstra algorithm can be obtained using these
1.145 ///functions.\n
1.146 - ///Either \ref run(Node) "run()" or \ref start() should be called
1.147 + ///Either \ref run(Node) "run()" or \ref init() should be called
1.148 ///before using them.
1.149
1.150 ///@{
1.151
1.152 - ///The shortest path to a node.
1.153 + ///The shortest path to the given node.
1.154
1.155 - ///Returns the shortest path to a node.
1.156 + ///Returns the shortest path to the given node from the root(s).
1.157 ///
1.158 ///\warning \c t should be reached from the root(s).
1.159 ///
1.160 @@ -816,9 +826,9 @@
1.161 ///must be called before using this function.
1.162 Path path(Node t) const { return Path(*G, *_pred, t); }
1.163
1.164 - ///The distance of a node from the root(s).
1.165 + ///The distance of the given node from the root(s).
1.166
1.167 - ///Returns the distance of a node from the root(s).
1.168 + ///Returns the distance of the given node from the root(s).
1.169 ///
1.170 ///\warning If node \c v is not reached from the root(s), then
1.171 ///the return value of this function is undefined.
1.172 @@ -827,29 +837,31 @@
1.173 ///must be called before using this function.
1.174 Value dist(Node v) const { return (*_dist)[v]; }
1.175
1.176 - ///Returns the 'previous arc' of the shortest path tree for a node.
1.177 -
1.178 + ///\brief Returns the 'previous arc' of the shortest path tree for
1.179 + ///the given node.
1.180 + ///
1.181 ///This function returns the 'previous arc' of the shortest path
1.182 ///tree for the node \c v, i.e. it returns the last arc of a
1.183 ///shortest path from a root to \c v. It is \c INVALID if \c v
1.184 ///is not reached from the root(s) or if \c v is a root.
1.185 ///
1.186 ///The shortest path tree used here is equal to the shortest path
1.187 - ///tree used in \ref predNode().
1.188 + ///tree used in \ref predNode() and \ref predMap().
1.189 ///
1.190 ///\pre Either \ref run(Node) "run()" or \ref init()
1.191 ///must be called before using this function.
1.192 Arc predArc(Node v) const { return (*_pred)[v]; }
1.193
1.194 - ///Returns the 'previous node' of the shortest path tree for a node.
1.195 -
1.196 + ///\brief Returns the 'previous node' of the shortest path tree for
1.197 + ///the given node.
1.198 + ///
1.199 ///This function returns the 'previous node' of the shortest path
1.200 ///tree for the node \c v, i.e. it returns the last but one node
1.201 - ///from a shortest path from a root to \c v. It is \c INVALID
1.202 + ///of a shortest path from a root to \c v. It is \c INVALID
1.203 ///if \c v is not reached from the root(s) or if \c v is a root.
1.204 ///
1.205 ///The shortest path tree used here is equal to the shortest path
1.206 - ///tree used in \ref predArc().
1.207 + ///tree used in \ref predArc() and \ref predMap().
1.208 ///
1.209 ///\pre Either \ref run(Node) "run()" or \ref init()
1.210 ///must be called before using this function.
1.211 @@ -870,13 +882,13 @@
1.212 ///predecessor arcs.
1.213 ///
1.214 ///Returns a const reference to the node map that stores the predecessor
1.215 - ///arcs, which form the shortest path tree.
1.216 + ///arcs, which form the shortest path tree (forest).
1.217 ///
1.218 ///\pre Either \ref run(Node) "run()" or \ref init()
1.219 ///must be called before using this function.
1.220 const PredMap &predMap() const { return *_pred;}
1.221
1.222 - ///Checks if a node is reached from the root(s).
1.223 + ///Checks if the given node is reached from the root(s).
1.224
1.225 ///Returns \c true if \c v is reached from the root(s).
1.226 ///
1.227 @@ -895,9 +907,9 @@
1.228 bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
1.229 Heap::POST_HEAP; }
1.230
1.231 - ///The current distance of a node from the root(s).
1.232 + ///The current distance of the given node from the root(s).
1.233
1.234 - ///Returns the current distance of a node from the root(s).
1.235 + ///Returns the current distance of the given node from the root(s).
1.236 ///It may be decreased in the following processes.
1.237 ///
1.238 ///\pre Either \ref run(Node) "run()" or \ref init()
1.239 @@ -924,9 +936,9 @@
1.240 ///The type of the map that stores the arc lengths.
1.241
1.242 ///The type of the map that stores the arc lengths.
1.243 - ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.244 + ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
1.245 typedef LEN LengthMap;
1.246 - ///The type of the length of the arcs.
1.247 + ///The type of the arc lengths.
1.248 typedef typename LEN::Value Value;
1.249
1.250 /// Operation traits for Dijkstra algorithm.
1.251 @@ -973,7 +985,7 @@
1.252 ///
1.253 ///The type of the map that stores the predecessor
1.254 ///arcs of the shortest paths.
1.255 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.256 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.257 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.258 ///Instantiates a PredMap.
1.259
1.260 @@ -988,8 +1000,8 @@
1.261 ///The type of the map that indicates which nodes are processed.
1.262
1.263 ///The type of the map that indicates which nodes are processed.
1.264 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.265 - ///By default it is a NullMap.
1.266 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.267 + ///By default, it is a NullMap.
1.268 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.269 ///Instantiates a ProcessedMap.
1.270
1.271 @@ -1008,7 +1020,7 @@
1.272 ///The type of the map that stores the distances of the nodes.
1.273
1.274 ///The type of the map that stores the distances of the nodes.
1.275 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.276 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.277 typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
1.278 ///Instantiates a DistMap.
1.279
1.280 @@ -1023,18 +1035,15 @@
1.281 ///The type of the shortest paths.
1.282
1.283 ///The type of the shortest paths.
1.284 - ///It must meet the \ref concepts::Path "Path" concept.
1.285 + ///It must conform to the \ref concepts::Path "Path" concept.
1.286 typedef lemon::Path<Digraph> Path;
1.287 };
1.288
1.289 /// Default traits class used by DijkstraWizard
1.290
1.291 - /// To make it easier to use Dijkstra algorithm
1.292 - /// we have created a wizard class.
1.293 - /// This \ref DijkstraWizard class needs default traits,
1.294 - /// as well as the \ref Dijkstra class.
1.295 - /// The \ref DijkstraWizardBase is a class to be the default traits of the
1.296 - /// \ref DijkstraWizard class.
1.297 + /// Default traits class used by DijkstraWizard.
1.298 + /// \tparam GR The type of the digraph.
1.299 + /// \tparam LEN The type of the length map.
1.300 template<typename GR, typename LEN>
1.301 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN>
1.302 {
1.303 @@ -1088,12 +1097,14 @@
1.304 ///
1.305 /// This class should only be used through the \ref dijkstra() function,
1.306 /// which makes it easier to use the algorithm.
1.307 + ///
1.308 + /// \tparam TR The traits class that defines various types used by the
1.309 + /// algorithm.
1.310 template<class TR>
1.311 class DijkstraWizard : public TR
1.312 {
1.313 typedef TR Base;
1.314
1.315 - ///The type of the digraph the algorithm runs on.
1.316 typedef typename TR::Digraph Digraph;
1.317
1.318 typedef typename Digraph::Node Node;
1.319 @@ -1101,20 +1112,12 @@
1.320 typedef typename Digraph::Arc Arc;
1.321 typedef typename Digraph::OutArcIt OutArcIt;
1.322
1.323 - ///The type of the map that stores the arc lengths.
1.324 typedef typename TR::LengthMap LengthMap;
1.325 - ///The type of the length of the arcs.
1.326 typedef typename LengthMap::Value Value;
1.327 - ///\brief The type of the map that stores the predecessor
1.328 - ///arcs of the shortest paths.
1.329 typedef typename TR::PredMap PredMap;
1.330 - ///The type of the map that stores the distances of the nodes.
1.331 typedef typename TR::DistMap DistMap;
1.332 - ///The type of the map that indicates which nodes are processed.
1.333 typedef typename TR::ProcessedMap ProcessedMap;
1.334 - ///The type of the shortest paths
1.335 typedef typename TR::Path Path;
1.336 - ///The heap type used by the dijkstra algorithm.
1.337 typedef typename TR::Heap Heap;
1.338
1.339 public:
1.340 @@ -1186,11 +1189,12 @@
1.341 static PredMap *createPredMap(const Digraph &) { return 0; };
1.342 SetPredMapBase(const TR &b) : TR(b) {}
1.343 };
1.344 - ///\brief \ref named-func-param "Named parameter"
1.345 - ///for setting PredMap object.
1.346 +
1.347 + ///\brief \ref named-templ-param "Named parameter" for setting
1.348 + ///the predecessor map.
1.349 ///
1.350 - ///\ref named-func-param "Named parameter"
1.351 - ///for setting PredMap object.
1.352 + ///\ref named-templ-param "Named parameter" function for setting
1.353 + ///the map that stores the predecessor arcs of the nodes.
1.354 template<class T>
1.355 DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
1.356 {
1.357 @@ -1204,11 +1208,13 @@
1.358 static DistMap *createDistMap(const Digraph &) { return 0; };
1.359 SetDistMapBase(const TR &b) : TR(b) {}
1.360 };
1.361 - ///\brief \ref named-func-param "Named parameter"
1.362 - ///for setting DistMap object.
1.363 +
1.364 + ///\brief \ref named-templ-param "Named parameter" for setting
1.365 + ///the distance map.
1.366 ///
1.367 - ///\ref named-func-param "Named parameter"
1.368 - ///for setting DistMap object.
1.369 + ///\ref named-templ-param "Named parameter" function for setting
1.370 + ///the map that stores the distances of the nodes calculated
1.371 + ///by the algorithm.
1.372 template<class T>
1.373 DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
1.374 {
1.375 @@ -1222,11 +1228,12 @@
1.376 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1.377 SetProcessedMapBase(const TR &b) : TR(b) {}
1.378 };
1.379 - ///\brief \ref named-func-param "Named parameter"
1.380 - ///for setting ProcessedMap object.
1.381 +
1.382 + ///\brief \ref named-func-param "Named parameter" for setting
1.383 + ///the processed map.
1.384 ///
1.385 - /// \ref named-func-param "Named parameter"
1.386 - ///for setting ProcessedMap object.
1.387 + ///\ref named-templ-param "Named parameter" function for setting
1.388 + ///the map that indicates which nodes are processed.
1.389 template<class T>
1.390 DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1.391 {
1.392 @@ -1239,6 +1246,7 @@
1.393 typedef T Path;
1.394 SetPathBase(const TR &b) : TR(b) {}
1.395 };
1.396 +
1.397 ///\brief \ref named-func-param "Named parameter"
1.398 ///for getting the shortest path to the target node.
1.399 ///