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