1.1 --- a/lemon/dijkstra.h Fri May 29 17:46:48 2009 +0100
1.2 +++ b/lemon/dijkstra.h Sun Aug 02 12:40:20 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 @@ -801,14 +806,14 @@
1.98 ///\name Query Functions
1.99 ///The results of the %Dijkstra algorithm can be obtained using these
1.100 ///functions.\n
1.101 - ///Either \ref run(Node) "run()" or \ref start() should be called
1.102 + ///Either \ref run(Node) "run()" or \ref init() should be called
1.103 ///before using them.
1.104
1.105 ///@{
1.106
1.107 - ///The shortest path to a node.
1.108 + ///The shortest path to the given node.
1.109
1.110 - ///Returns the shortest path to a node.
1.111 + ///Returns the shortest path to the given node from the root(s).
1.112 ///
1.113 ///\warning \c t should be reached from the root(s).
1.114 ///
1.115 @@ -816,9 +821,9 @@
1.116 ///must be called before using this function.
1.117 Path path(Node t) const { return Path(*G, *_pred, t); }
1.118
1.119 - ///The distance of a node from the root(s).
1.120 + ///The distance of the given node from the root(s).
1.121
1.122 - ///Returns the distance of a node from the root(s).
1.123 + ///Returns the distance of the given node from the root(s).
1.124 ///
1.125 ///\warning If node \c v is not reached from the root(s), then
1.126 ///the return value of this function is undefined.
1.127 @@ -827,29 +832,31 @@
1.128 ///must be called before using this function.
1.129 Value dist(Node v) const { return (*_dist)[v]; }
1.130
1.131 - ///Returns the 'previous arc' of the shortest path tree for a node.
1.132 -
1.133 + ///\brief Returns the 'previous arc' of the shortest path tree for
1.134 + ///the given node.
1.135 + ///
1.136 ///This function returns the 'previous arc' of the shortest path
1.137 ///tree for the node \c v, i.e. it returns the last arc of a
1.138 ///shortest path from a root to \c v. It is \c INVALID if \c v
1.139 ///is not reached from the root(s) or if \c v is a root.
1.140 ///
1.141 ///The shortest path tree used here is equal to the shortest path
1.142 - ///tree used in \ref predNode().
1.143 + ///tree used in \ref predNode() and \ref predMap().
1.144 ///
1.145 ///\pre Either \ref run(Node) "run()" or \ref init()
1.146 ///must be called before using this function.
1.147 Arc predArc(Node v) const { return (*_pred)[v]; }
1.148
1.149 - ///Returns the 'previous node' of the shortest path tree for a node.
1.150 -
1.151 + ///\brief Returns the 'previous node' of the shortest path tree for
1.152 + ///the given node.
1.153 + ///
1.154 ///This function returns the 'previous node' of the shortest path
1.155 ///tree for the node \c v, i.e. it returns the last but one node
1.156 - ///from a shortest path from a root to \c v. It is \c INVALID
1.157 + ///of a shortest path from a root to \c v. It is \c INVALID
1.158 ///if \c v is not reached from the root(s) or if \c v is a root.
1.159 ///
1.160 ///The shortest path tree used here is equal to the shortest path
1.161 - ///tree used in \ref predArc().
1.162 + ///tree used in \ref predArc() and \ref predMap().
1.163 ///
1.164 ///\pre Either \ref run(Node) "run()" or \ref init()
1.165 ///must be called before using this function.
1.166 @@ -870,13 +877,13 @@
1.167 ///predecessor arcs.
1.168 ///
1.169 ///Returns a const reference to the node map that stores the predecessor
1.170 - ///arcs, which form the shortest path tree.
1.171 + ///arcs, which form the shortest path tree (forest).
1.172 ///
1.173 ///\pre Either \ref run(Node) "run()" or \ref init()
1.174 ///must be called before using this function.
1.175 const PredMap &predMap() const { return *_pred;}
1.176
1.177 - ///Checks if a node is reached from the root(s).
1.178 + ///Checks if the given node is reached from the root(s).
1.179
1.180 ///Returns \c true if \c v is reached from the root(s).
1.181 ///
1.182 @@ -895,9 +902,9 @@
1.183 bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
1.184 Heap::POST_HEAP; }
1.185
1.186 - ///The current distance of a node from the root(s).
1.187 + ///The current distance of the given node from the root(s).
1.188
1.189 - ///Returns the current distance of a node from the root(s).
1.190 + ///Returns the current distance of the given node from the root(s).
1.191 ///It may be decreased in the following processes.
1.192 ///
1.193 ///\pre Either \ref run(Node) "run()" or \ref init()
1.194 @@ -924,9 +931,9 @@
1.195 ///The type of the map that stores the arc lengths.
1.196
1.197 ///The type of the map that stores the arc lengths.
1.198 - ///It must meet the \ref concepts::ReadMap "ReadMap" concept.
1.199 + ///It must conform to the \ref concepts::ReadMap "ReadMap" concept.
1.200 typedef LEN LengthMap;
1.201 - ///The type of the length of the arcs.
1.202 + ///The type of the arc lengths.
1.203 typedef typename LEN::Value Value;
1.204
1.205 /// Operation traits for Dijkstra algorithm.
1.206 @@ -973,7 +980,7 @@
1.207 ///
1.208 ///The type of the map that stores the predecessor
1.209 ///arcs of the shortest paths.
1.210 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.211 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.212 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.213 ///Instantiates a PredMap.
1.214
1.215 @@ -988,7 +995,7 @@
1.216 ///The type of the map that indicates which nodes are processed.
1.217
1.218 ///The type of the map that indicates which nodes are processed.
1.219 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.220 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.221 ///By default it is a NullMap.
1.222 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.223 ///Instantiates a ProcessedMap.
1.224 @@ -1008,7 +1015,7 @@
1.225 ///The type of the map that stores the distances of the nodes.
1.226
1.227 ///The type of the map that stores the distances of the nodes.
1.228 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.229 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.230 typedef typename Digraph::template NodeMap<typename LEN::Value> DistMap;
1.231 ///Instantiates a DistMap.
1.232
1.233 @@ -1023,18 +1030,15 @@
1.234 ///The type of the shortest paths.
1.235
1.236 ///The type of the shortest paths.
1.237 - ///It must meet the \ref concepts::Path "Path" concept.
1.238 + ///It must conform to the \ref concepts::Path "Path" concept.
1.239 typedef lemon::Path<Digraph> Path;
1.240 };
1.241
1.242 /// Default traits class used by DijkstraWizard
1.243
1.244 - /// To make it easier to use Dijkstra algorithm
1.245 - /// we have created a wizard class.
1.246 - /// This \ref DijkstraWizard class needs default traits,
1.247 - /// as well as the \ref Dijkstra class.
1.248 - /// The \ref DijkstraWizardBase is a class to be the default traits of the
1.249 - /// \ref DijkstraWizard class.
1.250 + /// Default traits class used by DijkstraWizard.
1.251 + /// \tparam GR The type of the digraph.
1.252 + /// \tparam LEN The type of the length map.
1.253 template<typename GR, typename LEN>
1.254 class DijkstraWizardBase : public DijkstraWizardDefaultTraits<GR,LEN>
1.255 {
1.256 @@ -1093,7 +1097,6 @@
1.257 {
1.258 typedef TR Base;
1.259
1.260 - ///The type of the digraph the algorithm runs on.
1.261 typedef typename TR::Digraph Digraph;
1.262
1.263 typedef typename Digraph::Node Node;
1.264 @@ -1101,20 +1104,12 @@
1.265 typedef typename Digraph::Arc Arc;
1.266 typedef typename Digraph::OutArcIt OutArcIt;
1.267
1.268 - ///The type of the map that stores the arc lengths.
1.269 typedef typename TR::LengthMap LengthMap;
1.270 - ///The type of the length of the arcs.
1.271 typedef typename LengthMap::Value Value;
1.272 - ///\brief The type of the map that stores the predecessor
1.273 - ///arcs of the shortest paths.
1.274 typedef typename TR::PredMap PredMap;
1.275 - ///The type of the map that stores the distances of the nodes.
1.276 typedef typename TR::DistMap DistMap;
1.277 - ///The type of the map that indicates which nodes are processed.
1.278 typedef typename TR::ProcessedMap ProcessedMap;
1.279 - ///The type of the shortest paths
1.280 typedef typename TR::Path Path;
1.281 - ///The heap type used by the dijkstra algorithm.
1.282 typedef typename TR::Heap Heap;
1.283
1.284 public:
1.285 @@ -1186,11 +1181,12 @@
1.286 static PredMap *createPredMap(const Digraph &) { return 0; };
1.287 SetPredMapBase(const TR &b) : TR(b) {}
1.288 };
1.289 - ///\brief \ref named-func-param "Named parameter"
1.290 - ///for setting PredMap object.
1.291 +
1.292 + ///\brief \ref named-templ-param "Named parameter" for setting
1.293 + ///the predecessor map.
1.294 ///
1.295 - ///\ref named-func-param "Named parameter"
1.296 - ///for setting PredMap object.
1.297 + ///\ref named-templ-param "Named parameter" function for setting
1.298 + ///the map that stores the predecessor arcs of the nodes.
1.299 template<class T>
1.300 DijkstraWizard<SetPredMapBase<T> > predMap(const T &t)
1.301 {
1.302 @@ -1204,11 +1200,13 @@
1.303 static DistMap *createDistMap(const Digraph &) { return 0; };
1.304 SetDistMapBase(const TR &b) : TR(b) {}
1.305 };
1.306 - ///\brief \ref named-func-param "Named parameter"
1.307 - ///for setting DistMap object.
1.308 +
1.309 + ///\brief \ref named-templ-param "Named parameter" for setting
1.310 + ///the distance map.
1.311 ///
1.312 - ///\ref named-func-param "Named parameter"
1.313 - ///for setting DistMap object.
1.314 + ///\ref named-templ-param "Named parameter" function for setting
1.315 + ///the map that stores the distances of the nodes calculated
1.316 + ///by the algorithm.
1.317 template<class T>
1.318 DijkstraWizard<SetDistMapBase<T> > distMap(const T &t)
1.319 {
1.320 @@ -1222,11 +1220,12 @@
1.321 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1.322 SetProcessedMapBase(const TR &b) : TR(b) {}
1.323 };
1.324 - ///\brief \ref named-func-param "Named parameter"
1.325 - ///for setting ProcessedMap object.
1.326 +
1.327 + ///\brief \ref named-func-param "Named parameter" for setting
1.328 + ///the processed map.
1.329 ///
1.330 - /// \ref named-func-param "Named parameter"
1.331 - ///for setting ProcessedMap object.
1.332 + ///\ref named-templ-param "Named parameter" function for setting
1.333 + ///the map that indicates which nodes are processed.
1.334 template<class T>
1.335 DijkstraWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1.336 {
1.337 @@ -1239,6 +1238,7 @@
1.338 typedef T Path;
1.339 SetPathBase(const TR &b) : TR(b) {}
1.340 };
1.341 +
1.342 ///\brief \ref named-func-param "Named parameter"
1.343 ///for getting the shortest path to the target node.
1.344 ///