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