1.1 --- a/lemon/bfs.h Tue Dec 02 10:30:52 2008 +0000
1.2 +++ b/lemon/bfs.h Tue Dec 02 10:31:20 2008 +0000
1.3 @@ -51,7 +51,7 @@
1.4 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.5 ///Instantiates a PredMap.
1.6
1.7 - ///This function instantiates a PredMap.
1.8 + ///This function instantiates a PredMap.
1.9 ///\param g is the digraph, to which we would like to define the
1.10 ///PredMap.
1.11 static PredMap *createPredMap(const Digraph &g)
1.12 @@ -80,7 +80,8 @@
1.13
1.14 ///The type of the map that indicates which nodes are reached.
1.15
1.16 - ///The type of the map that indicates which nodes are reached.///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.17 + ///The type of the map that indicates which nodes are reached.
1.18 + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.19 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.20 ///Instantiates a ReachedMap.
1.21
1.22 @@ -118,13 +119,7 @@
1.23 ///used easier.
1.24 ///
1.25 ///\tparam GR The type of the digraph the algorithm runs on.
1.26 - ///The default value is \ref ListDigraph. The value of GR is not used
1.27 - ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
1.28 - ///\tparam TR Traits class to set various data types used by the algorithm.
1.29 - ///The default traits class is
1.30 - ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
1.31 - ///See \ref BfsDefaultTraits for the documentation of
1.32 - ///a Bfs traits class.
1.33 + ///The default type is \ref ListDigraph.
1.34 #ifdef DOXYGEN
1.35 template <typename GR,
1.36 typename TR>
1.37 @@ -150,7 +145,7 @@
1.38 ///The type of the paths.
1.39 typedef PredMapPath<Digraph, PredMap> Path;
1.40
1.41 - ///The traits class.
1.42 + ///The \ref BfsDefaultTraits "traits class" of the algorithm.
1.43 typedef TR Traits;
1.44
1.45 private:
1.46 @@ -212,7 +207,7 @@
1.47
1.48 typedef Bfs Create;
1.49
1.50 - ///\name Named template parameters
1.51 + ///\name Named Template Parameters
1.52
1.53 ///@{
1.54
1.55 @@ -230,6 +225,7 @@
1.56 ///
1.57 ///\ref named-templ-param "Named parameter" for setting
1.58 ///PredMap type.
1.59 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.60 template <class T>
1.61 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
1.62 typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
1.63 @@ -249,6 +245,7 @@
1.64 ///
1.65 ///\ref named-templ-param "Named parameter" for setting
1.66 ///DistMap type.
1.67 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.68 template <class T>
1.69 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
1.70 typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
1.71 @@ -268,6 +265,7 @@
1.72 ///
1.73 ///\ref named-templ-param "Named parameter" for setting
1.74 ///ReachedMap type.
1.75 + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.76 template <class T>
1.77 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
1.78 typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
1.79 @@ -287,6 +285,7 @@
1.80 ///
1.81 ///\ref named-templ-param "Named parameter" for setting
1.82 ///ProcessedMap type.
1.83 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.84 template <class T>
1.85 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
1.86 typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
1.87 @@ -339,9 +338,10 @@
1.88 ///Sets the map that stores the predecessor arcs.
1.89
1.90 ///Sets the map that stores the predecessor arcs.
1.91 - ///If you don't use this function before calling \ref run(),
1.92 - ///it will allocate one. The destructor deallocates this
1.93 - ///automatically allocated map, of course.
1.94 + ///If you don't use this function before calling \ref run(Node) "run()"
1.95 + ///or \ref init(), an instance will be allocated automatically.
1.96 + ///The destructor deallocates this automatically allocated map,
1.97 + ///of course.
1.98 ///\return <tt> (*this) </tt>
1.99 Bfs &predMap(PredMap &m)
1.100 {
1.101 @@ -356,9 +356,10 @@
1.102 ///Sets the map that indicates which nodes are reached.
1.103
1.104 ///Sets the map that indicates which nodes are reached.
1.105 - ///If you don't use this function before calling \ref run(),
1.106 - ///it will allocate one. The destructor deallocates this
1.107 - ///automatically allocated map, of course.
1.108 + ///If you don't use this function before calling \ref run(Node) "run()"
1.109 + ///or \ref init(), an instance will be allocated automatically.
1.110 + ///The destructor deallocates this automatically allocated map,
1.111 + ///of course.
1.112 ///\return <tt> (*this) </tt>
1.113 Bfs &reachedMap(ReachedMap &m)
1.114 {
1.115 @@ -373,9 +374,10 @@
1.116 ///Sets the map that indicates which nodes are processed.
1.117
1.118 ///Sets the map that indicates which nodes are processed.
1.119 - ///If you don't use this function before calling \ref run(),
1.120 - ///it will allocate one. The destructor deallocates this
1.121 - ///automatically allocated map, of course.
1.122 + ///If you don't use this function before calling \ref run(Node) "run()"
1.123 + ///or \ref init(), an instance will be allocated automatically.
1.124 + ///The destructor deallocates this automatically allocated map,
1.125 + ///of course.
1.126 ///\return <tt> (*this) </tt>
1.127 Bfs &processedMap(ProcessedMap &m)
1.128 {
1.129 @@ -391,9 +393,10 @@
1.130
1.131 ///Sets the map that stores the distances of the nodes calculated by
1.132 ///the algorithm.
1.133 - ///If you don't use this function before calling \ref run(),
1.134 - ///it will allocate one. The destructor deallocates this
1.135 - ///automatically allocated map, of course.
1.136 + ///If you don't use this function before calling \ref run(Node) "run()"
1.137 + ///or \ref init(), an instance will be allocated automatically.
1.138 + ///The destructor deallocates this automatically allocated map,
1.139 + ///of course.
1.140 ///\return <tt> (*this) </tt>
1.141 Bfs &distMap(DistMap &m)
1.142 {
1.143 @@ -407,22 +410,19 @@
1.144
1.145 public:
1.146
1.147 - ///\name Execution control
1.148 - ///The simplest way to execute the algorithm is to use
1.149 - ///one of the member functions called \ref lemon::Bfs::run() "run()".
1.150 - ///\n
1.151 - ///If you need more control on the execution, first you must call
1.152 - ///\ref lemon::Bfs::init() "init()", then you can add several source
1.153 - ///nodes with \ref lemon::Bfs::addSource() "addSource()".
1.154 - ///Finally \ref lemon::Bfs::start() "start()" will perform the
1.155 - ///actual path computation.
1.156 + ///\name Execution Control
1.157 + ///The simplest way to execute the BFS algorithm is to use one of the
1.158 + ///member functions called \ref run(Node) "run()".\n
1.159 + ///If you need more control on the execution, first you have to call
1.160 + ///\ref init(), then you can add several source nodes with
1.161 + ///\ref addSource(). Finally the actual path computation can be
1.162 + ///performed with one of the \ref start() functions.
1.163
1.164 ///@{
1.165
1.166 + ///\brief Initializes the internal data structures.
1.167 + ///
1.168 ///Initializes the internal data structures.
1.169 -
1.170 - ///Initializes the internal data structures.
1.171 - ///
1.172 void init()
1.173 {
1.174 create_maps();
1.175 @@ -556,16 +556,16 @@
1.176 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
1.177 }
1.178
1.179 - ///\brief Returns \c false if there are nodes
1.180 - ///to be processed.
1.181 - ///
1.182 - ///Returns \c false if there are nodes
1.183 - ///to be processed in the queue.
1.184 + ///Returns \c false if there are nodes to be processed.
1.185 +
1.186 + ///Returns \c false if there are nodes to be processed
1.187 + ///in the queue.
1.188 bool emptyQueue() const { return _queue_tail==_queue_head; }
1.189
1.190 ///Returns the number of the nodes to be processed.
1.191
1.192 - ///Returns the number of the nodes to be processed in the queue.
1.193 + ///Returns the number of the nodes to be processed
1.194 + ///in the queue.
1.195 int queueSize() const { return _queue_head-_queue_tail; }
1.196
1.197 ///Executes the algorithm.
1.198 @@ -730,10 +730,10 @@
1.199 ///@}
1.200
1.201 ///\name Query Functions
1.202 - ///The result of the %BFS algorithm can be obtained using these
1.203 + ///The results of the BFS algorithm can be obtained using these
1.204 ///functions.\n
1.205 - ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
1.206 - ///"start()" must be called before using them.
1.207 + ///Either \ref run(Node) "run()" or \ref start() should be called
1.208 + ///before using them.
1.209
1.210 ///@{
1.211
1.212 @@ -741,49 +741,49 @@
1.213
1.214 ///Returns the shortest path to a node.
1.215 ///
1.216 - ///\warning \c t should be reachable from the root(s).
1.217 + ///\warning \c t should be reached from the root(s).
1.218 ///
1.219 - ///\pre Either \ref run() or \ref start() must be called before
1.220 - ///using this function.
1.221 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.222 + ///must be called before using this function.
1.223 Path path(Node t) const { return Path(*G, *_pred, t); }
1.224
1.225 ///The distance of a node from the root(s).
1.226
1.227 ///Returns the distance of a node from the root(s).
1.228 ///
1.229 - ///\warning If node \c v is not reachable from the root(s), then
1.230 + ///\warning If node \c v is not reached from the root(s), then
1.231 ///the return value of this function is undefined.
1.232 ///
1.233 - ///\pre Either \ref run() or \ref start() must be called before
1.234 - ///using this function.
1.235 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.236 + ///must be called before using this function.
1.237 int dist(Node v) const { return (*_dist)[v]; }
1.238
1.239 ///Returns the 'previous arc' of the shortest path tree for a node.
1.240
1.241 ///This function returns the 'previous arc' of the shortest path
1.242 ///tree for the node \c v, i.e. it returns the last arc of a
1.243 - ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
1.244 - ///is not reachable from the root(s) or if \c v is a root.
1.245 + ///shortest path from a root to \c v. It is \c INVALID if \c v
1.246 + ///is not reached from the root(s) or if \c v is a root.
1.247 ///
1.248 ///The shortest path tree used here is equal to the shortest path
1.249 ///tree used in \ref predNode().
1.250 ///
1.251 - ///\pre Either \ref run() or \ref start() must be called before
1.252 - ///using this function.
1.253 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.254 + ///must be called before using this function.
1.255 Arc predArc(Node v) const { return (*_pred)[v];}
1.256
1.257 ///Returns the 'previous node' of the shortest path tree for a node.
1.258
1.259 ///This function returns the 'previous node' of the shortest path
1.260 ///tree for the node \c v, i.e. it returns the last but one node
1.261 - ///from a shortest path from the root(s) to \c v. It is \c INVALID
1.262 - ///if \c v is not reachable from the root(s) or if \c v is a root.
1.263 + ///from a shortest path from a root to \c v. It is \c INVALID
1.264 + ///if \c v is not reached from the root(s) or if \c v is a root.
1.265 ///
1.266 ///The shortest path tree used here is equal to the shortest path
1.267 ///tree used in \ref predArc().
1.268 ///
1.269 - ///\pre Either \ref run() or \ref start() must be called before
1.270 - ///using this function.
1.271 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.272 + ///must be called before using this function.
1.273 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
1.274 G->source((*_pred)[v]); }
1.275
1.276 @@ -793,7 +793,7 @@
1.277 ///Returns a const reference to the node map that stores the distances
1.278 ///of the nodes calculated by the algorithm.
1.279 ///
1.280 - ///\pre Either \ref run() or \ref init()
1.281 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.282 ///must be called before using this function.
1.283 const DistMap &distMap() const { return *_dist;}
1.284
1.285 @@ -803,14 +803,15 @@
1.286 ///Returns a const reference to the node map that stores the predecessor
1.287 ///arcs, which form the shortest path tree.
1.288 ///
1.289 - ///\pre Either \ref run() or \ref init()
1.290 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.291 ///must be called before using this function.
1.292 const PredMap &predMap() const { return *_pred;}
1.293
1.294 - ///Checks if a node is reachable from the root(s).
1.295 + ///Checks if a node is reached from the root(s).
1.296
1.297 - ///Returns \c true if \c v is reachable from the root(s).
1.298 - ///\pre Either \ref run() or \ref start()
1.299 + ///Returns \c true if \c v is reached from the root(s).
1.300 + ///
1.301 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.302 ///must be called before using this function.
1.303 bool reached(Node v) const { return (*_reached)[v]; }
1.304
1.305 @@ -956,8 +957,8 @@
1.306
1.307 /// This auxiliary class is created to implement the
1.308 /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
1.309 - /// It does not have own \ref run() method, it uses the functions
1.310 - /// and features of the plain \ref Bfs.
1.311 + /// It does not have own \ref run(Node) "run()" method, it uses the
1.312 + /// functions and features of the plain \ref Bfs.
1.313 ///
1.314 /// This class should only be used through the \ref bfs() function,
1.315 /// which makes it easier to use the algorithm.
1.316 @@ -1177,7 +1178,7 @@
1.317 /// // Compute shortest path from s to t
1.318 /// bool reached = bfs(g).path(p).dist(d).run(s,t);
1.319 ///\endcode
1.320 - ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
1.321 + ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
1.322 ///to the end of the parameter list.
1.323 ///\sa BfsWizard
1.324 ///\sa Bfs
1.325 @@ -1363,7 +1364,7 @@
1.326
1.327 typedef BfsVisit Create;
1.328
1.329 - /// \name Named template parameters
1.330 + /// \name Named Template Parameters
1.331
1.332 ///@{
1.333 template <class T>
1.334 @@ -1405,9 +1406,10 @@
1.335 /// \brief Sets the map that indicates which nodes are reached.
1.336 ///
1.337 /// Sets the map that indicates which nodes are reached.
1.338 - /// If you don't use this function before calling \ref run(),
1.339 - /// it will allocate one. The destructor deallocates this
1.340 - /// automatically allocated map, of course.
1.341 + /// If you don't use this function before calling \ref run(Node) "run()"
1.342 + /// or \ref init(), an instance will be allocated automatically.
1.343 + /// The destructor deallocates this automatically allocated map,
1.344 + /// of course.
1.345 /// \return <tt> (*this) </tt>
1.346 BfsVisit &reachedMap(ReachedMap &m) {
1.347 if(local_reached) {
1.348 @@ -1420,16 +1422,13 @@
1.349
1.350 public:
1.351
1.352 - /// \name Execution control
1.353 - /// The simplest way to execute the algorithm is to use
1.354 - /// one of the member functions called \ref lemon::BfsVisit::run()
1.355 - /// "run()".
1.356 - /// \n
1.357 - /// If you need more control on the execution, first you must call
1.358 - /// \ref lemon::BfsVisit::init() "init()", then you can add several
1.359 - /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
1.360 - /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
1.361 - /// actual path computation.
1.362 + /// \name Execution Control
1.363 + /// The simplest way to execute the BFS algorithm is to use one of the
1.364 + /// member functions called \ref run(Node) "run()".\n
1.365 + /// If you need more control on the execution, first you have to call
1.366 + /// \ref init(), then you can add several source nodes with
1.367 + /// \ref addSource(). Finally the actual path computation can be
1.368 + /// performed with one of the \ref start() functions.
1.369
1.370 /// @{
1.371
1.372 @@ -1729,17 +1728,18 @@
1.373 ///@}
1.374
1.375 /// \name Query Functions
1.376 - /// The result of the %BFS algorithm can be obtained using these
1.377 + /// The results of the BFS algorithm can be obtained using these
1.378 /// functions.\n
1.379 - /// Either \ref lemon::BfsVisit::run() "run()" or
1.380 - /// \ref lemon::BfsVisit::start() "start()" must be called before
1.381 - /// using them.
1.382 + /// Either \ref run(Node) "run()" or \ref start() should be called
1.383 + /// before using them.
1.384 +
1.385 ///@{
1.386
1.387 - /// \brief Checks if a node is reachable from the root(s).
1.388 + /// \brief Checks if a node is reached from the root(s).
1.389 ///
1.390 - /// Returns \c true if \c v is reachable from the root(s).
1.391 - /// \pre Either \ref run() or \ref start()
1.392 + /// Returns \c true if \c v is reached from the root(s).
1.393 + ///
1.394 + /// \pre Either \ref run(Node) "run()" or \ref init()
1.395 /// must be called before using this function.
1.396 bool reached(Node v) { return (*_reached)[v]; }
1.397
2.1 --- a/lemon/dfs.h Tue Dec 02 10:30:52 2008 +0000
2.2 +++ b/lemon/dfs.h Tue Dec 02 10:31:20 2008 +0000
2.3 @@ -119,13 +119,7 @@
2.4 ///used easier.
2.5 ///
2.6 ///\tparam GR The type of the digraph the algorithm runs on.
2.7 - ///The default value is \ref ListDigraph. The value of GR is not used
2.8 - ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
2.9 - ///\tparam TR Traits class to set various data types used by the algorithm.
2.10 - ///The default traits class is
2.11 - ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
2.12 - ///See \ref DfsDefaultTraits for the documentation of
2.13 - ///a Dfs traits class.
2.14 + ///The default type is \ref ListDigraph.
2.15 #ifdef DOXYGEN
2.16 template <typename GR,
2.17 typename TR>
2.18 @@ -151,7 +145,7 @@
2.19 ///The type of the paths.
2.20 typedef PredMapPath<Digraph, PredMap> Path;
2.21
2.22 - ///The traits class.
2.23 + ///The \ref DfsDefaultTraits "traits class" of the algorithm.
2.24 typedef TR Traits;
2.25
2.26 private:
2.27 @@ -230,6 +224,7 @@
2.28 ///
2.29 ///\ref named-templ-param "Named parameter" for setting
2.30 ///PredMap type.
2.31 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
2.32 template <class T>
2.33 struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
2.34 typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
2.35 @@ -249,6 +244,7 @@
2.36 ///
2.37 ///\ref named-templ-param "Named parameter" for setting
2.38 ///DistMap type.
2.39 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
2.40 template <class T>
2.41 struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
2.42 typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
2.43 @@ -268,6 +264,7 @@
2.44 ///
2.45 ///\ref named-templ-param "Named parameter" for setting
2.46 ///ReachedMap type.
2.47 + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
2.48 template <class T>
2.49 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
2.50 typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
2.51 @@ -287,6 +284,7 @@
2.52 ///
2.53 ///\ref named-templ-param "Named parameter" for setting
2.54 ///ProcessedMap type.
2.55 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
2.56 template <class T>
2.57 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
2.58 typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
2.59 @@ -338,9 +336,10 @@
2.60 ///Sets the map that stores the predecessor arcs.
2.61
2.62 ///Sets the map that stores the predecessor arcs.
2.63 - ///If you don't use this function before calling \ref run(),
2.64 - ///it will allocate one. The destructor deallocates this
2.65 - ///automatically allocated map, of course.
2.66 + ///If you don't use this function before calling \ref run(Node) "run()"
2.67 + ///or \ref init(), an instance will be allocated automatically.
2.68 + ///The destructor deallocates this automatically allocated map,
2.69 + ///of course.
2.70 ///\return <tt> (*this) </tt>
2.71 Dfs &predMap(PredMap &m)
2.72 {
2.73 @@ -355,9 +354,10 @@
2.74 ///Sets the map that indicates which nodes are reached.
2.75
2.76 ///Sets the map that indicates which nodes are reached.
2.77 - ///If you don't use this function before calling \ref run(),
2.78 - ///it will allocate one. The destructor deallocates this
2.79 - ///automatically allocated map, of course.
2.80 + ///If you don't use this function before calling \ref run(Node) "run()"
2.81 + ///or \ref init(), an instance will be allocated automatically.
2.82 + ///The destructor deallocates this automatically allocated map,
2.83 + ///of course.
2.84 ///\return <tt> (*this) </tt>
2.85 Dfs &reachedMap(ReachedMap &m)
2.86 {
2.87 @@ -372,9 +372,10 @@
2.88 ///Sets the map that indicates which nodes are processed.
2.89
2.90 ///Sets the map that indicates which nodes are processed.
2.91 - ///If you don't use this function before calling \ref run(),
2.92 - ///it will allocate one. The destructor deallocates this
2.93 - ///automatically allocated map, of course.
2.94 + ///If you don't use this function before calling \ref run(Node) "run()"
2.95 + ///or \ref init(), an instance will be allocated automatically.
2.96 + ///The destructor deallocates this automatically allocated map,
2.97 + ///of course.
2.98 ///\return <tt> (*this) </tt>
2.99 Dfs &processedMap(ProcessedMap &m)
2.100 {
2.101 @@ -390,9 +391,10 @@
2.102
2.103 ///Sets the map that stores the distances of the nodes calculated by
2.104 ///the algorithm.
2.105 - ///If you don't use this function before calling \ref run(),
2.106 - ///it will allocate one. The destructor deallocates this
2.107 - ///automatically allocated map, of course.
2.108 + ///If you don't use this function before calling \ref run(Node) "run()"
2.109 + ///or \ref init(), an instance will be allocated automatically.
2.110 + ///The destructor deallocates this automatically allocated map,
2.111 + ///of course.
2.112 ///\return <tt> (*this) </tt>
2.113 Dfs &distMap(DistMap &m)
2.114 {
2.115 @@ -406,22 +408,20 @@
2.116
2.117 public:
2.118
2.119 - ///\name Execution control
2.120 - ///The simplest way to execute the algorithm is to use
2.121 - ///one of the member functions called \ref lemon::Dfs::run() "run()".
2.122 - ///\n
2.123 - ///If you need more control on the execution, first you must call
2.124 - ///\ref lemon::Dfs::init() "init()", then you can add a source node
2.125 - ///with \ref lemon::Dfs::addSource() "addSource()".
2.126 - ///Finally \ref lemon::Dfs::start() "start()" will perform the
2.127 - ///actual path computation.
2.128 + ///\name Execution Control
2.129 + ///The simplest way to execute the DFS algorithm is to use one of the
2.130 + ///member functions called \ref run(Node) "run()".\n
2.131 + ///If you need more control on the execution, first you have to call
2.132 + ///\ref init(), then you can add a source node with \ref addSource()
2.133 + ///and perform the actual computation with \ref start().
2.134 + ///This procedure can be repeated if there are nodes that have not
2.135 + ///been reached.
2.136
2.137 ///@{
2.138
2.139 + ///\brief Initializes the internal data structures.
2.140 + ///
2.141 ///Initializes the internal data structures.
2.142 -
2.143 - ///Initializes the internal data structures.
2.144 - ///
2.145 void init()
2.146 {
2.147 create_maps();
2.148 @@ -438,11 +438,10 @@
2.149
2.150 ///Adds a new source node to the set of nodes to be processed.
2.151 ///
2.152 - ///\pre The stack must be empty. (Otherwise the algorithm gives
2.153 - ///false results.)
2.154 - ///
2.155 - ///\warning Distances will be wrong (or at least strange) in case of
2.156 - ///multiple sources.
2.157 + ///\pre The stack must be empty. Otherwise the algorithm gives
2.158 + ///wrong results. (One of the outgoing arcs of all the source nodes
2.159 + ///except for the last one will not be visited and distances will
2.160 + ///also be wrong.)
2.161 void addSource(Node s)
2.162 {
2.163 LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
2.164 @@ -506,16 +505,16 @@
2.165 return _stack_head>=0?_stack[_stack_head]:INVALID;
2.166 }
2.167
2.168 - ///\brief Returns \c false if there are nodes
2.169 - ///to be processed.
2.170 - ///
2.171 - ///Returns \c false if there are nodes
2.172 - ///to be processed in the queue (stack).
2.173 + ///Returns \c false if there are nodes to be processed.
2.174 +
2.175 + ///Returns \c false if there are nodes to be processed
2.176 + ///in the queue (stack).
2.177 bool emptyQueue() const { return _stack_head<0; }
2.178
2.179 ///Returns the number of the nodes to be processed.
2.180
2.181 - ///Returns the number of the nodes to be processed in the queue (stack).
2.182 + ///Returns the number of the nodes to be processed
2.183 + ///in the queue (stack).
2.184 int queueSize() const { return _stack_head+1; }
2.185
2.186 ///Executes the algorithm.
2.187 @@ -637,8 +636,8 @@
2.188 ///%DFS path to each node.
2.189 ///
2.190 ///The algorithm computes
2.191 - ///- the %DFS tree,
2.192 - ///- the distance of each node from the root in the %DFS tree.
2.193 + ///- the %DFS tree (forest),
2.194 + ///- the distance of each node from the root(s) in the %DFS tree.
2.195 ///
2.196 ///\note <tt>d.run()</tt> is just a shortcut of the following code.
2.197 ///\code
2.198 @@ -663,10 +662,10 @@
2.199 ///@}
2.200
2.201 ///\name Query Functions
2.202 - ///The result of the %DFS algorithm can be obtained using these
2.203 + ///The results of the DFS algorithm can be obtained using these
2.204 ///functions.\n
2.205 - ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
2.206 - ///"start()" must be called before using them.
2.207 + ///Either \ref run(Node) "run()" or \ref start() should be called
2.208 + ///before using them.
2.209
2.210 ///@{
2.211
2.212 @@ -674,49 +673,49 @@
2.213
2.214 ///Returns the DFS path to a node.
2.215 ///
2.216 - ///\warning \c t should be reachable from the root.
2.217 + ///\warning \c t should be reached from the root(s).
2.218 ///
2.219 - ///\pre Either \ref run() or \ref start() must be called before
2.220 - ///using this function.
2.221 + ///\pre Either \ref run(Node) "run()" or \ref init()
2.222 + ///must be called before using this function.
2.223 Path path(Node t) const { return Path(*G, *_pred, t); }
2.224
2.225 - ///The distance of a node from the root.
2.226 + ///The distance of a node from the root(s).
2.227
2.228 - ///Returns the distance of a node from the root.
2.229 + ///Returns the distance of a node from the root(s).
2.230 ///
2.231 - ///\warning If node \c v is not reachable from the root, then
2.232 + ///\warning If node \c v is not reached from the root(s), then
2.233 ///the return value of this function is undefined.
2.234 ///
2.235 - ///\pre Either \ref run() or \ref start() must be called before
2.236 - ///using this function.
2.237 + ///\pre Either \ref run(Node) "run()" or \ref init()
2.238 + ///must be called before using this function.
2.239 int dist(Node v) const { return (*_dist)[v]; }
2.240
2.241 ///Returns the 'previous arc' of the %DFS tree for a node.
2.242
2.243 ///This function returns the 'previous arc' of the %DFS tree for the
2.244 - ///node \c v, i.e. it returns the last arc of a %DFS path from the
2.245 - ///root to \c v. It is \c INVALID
2.246 - ///if \c v is not reachable from the root(s) or if \c v is a root.
2.247 + ///node \c v, i.e. it returns the last arc of a %DFS path from a
2.248 + ///root to \c v. It is \c INVALID if \c v is not reached from the
2.249 + ///root(s) or if \c v is a root.
2.250 ///
2.251 ///The %DFS tree used here is equal to the %DFS tree used in
2.252 ///\ref predNode().
2.253 ///
2.254 - ///\pre Either \ref run() or \ref start() must be called before using
2.255 - ///this function.
2.256 + ///\pre Either \ref run(Node) "run()" or \ref init()
2.257 + ///must be called before using this function.
2.258 Arc predArc(Node v) const { return (*_pred)[v];}
2.259
2.260 ///Returns the 'previous node' of the %DFS tree.
2.261
2.262 ///This function returns the 'previous node' of the %DFS
2.263 ///tree for the node \c v, i.e. it returns the last but one node
2.264 - ///from a %DFS path from the root to \c v. It is \c INVALID
2.265 - ///if \c v is not reachable from the root(s) or if \c v is a root.
2.266 + ///from a %DFS path from a root to \c v. It is \c INVALID
2.267 + ///if \c v is not reached from the root(s) or if \c v is a root.
2.268 ///
2.269 ///The %DFS tree used here is equal to the %DFS tree used in
2.270 ///\ref predArc().
2.271 ///
2.272 - ///\pre Either \ref run() or \ref start() must be called before
2.273 - ///using this function.
2.274 + ///\pre Either \ref run(Node) "run()" or \ref init()
2.275 + ///must be called before using this function.
2.276 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
2.277 G->source((*_pred)[v]); }
2.278
2.279 @@ -726,7 +725,7 @@
2.280 ///Returns a const reference to the node map that stores the
2.281 ///distances of the nodes calculated by the algorithm.
2.282 ///
2.283 - ///\pre Either \ref run() or \ref init()
2.284 + ///\pre Either \ref run(Node) "run()" or \ref init()
2.285 ///must be called before using this function.
2.286 const DistMap &distMap() const { return *_dist;}
2.287
2.288 @@ -736,14 +735,15 @@
2.289 ///Returns a const reference to the node map that stores the predecessor
2.290 ///arcs, which form the DFS tree.
2.291 ///
2.292 - ///\pre Either \ref run() or \ref init()
2.293 + ///\pre Either \ref run(Node) "run()" or \ref init()
2.294 ///must be called before using this function.
2.295 const PredMap &predMap() const { return *_pred;}
2.296
2.297 - ///Checks if a node is reachable from the root(s).
2.298 + ///Checks if a node is reached from the root(s).
2.299
2.300 - ///Returns \c true if \c v is reachable from the root(s).
2.301 - ///\pre Either \ref run() or \ref start()
2.302 + ///Returns \c true if \c v is reached from the root(s).
2.303 + ///
2.304 + ///\pre Either \ref run(Node) "run()" or \ref init()
2.305 ///must be called before using this function.
2.306 bool reached(Node v) const { return (*_reached)[v]; }
2.307
2.308 @@ -889,8 +889,8 @@
2.309
2.310 /// This auxiliary class is created to implement the
2.311 /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
2.312 - /// It does not have own \ref run() method, it uses the functions
2.313 - /// and features of the plain \ref Dfs.
2.314 + /// It does not have own \ref run(Node) "run()" method, it uses the
2.315 + /// functions and features of the plain \ref Dfs.
2.316 ///
2.317 /// This class should only be used through the \ref dfs() function,
2.318 /// which makes it easier to use the algorithm.
2.319 @@ -1110,8 +1110,7 @@
2.320 /// // Compute the DFS path from s to t
2.321 /// bool reached = dfs(g).path(p).dist(d).run(s,t);
2.322 ///\endcode
2.323 -
2.324 - ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
2.325 + ///\warning Don't forget to put the \ref DfsWizard::run(Node) "run()"
2.326 ///to the end of the parameter list.
2.327 ///\sa DfsWizard
2.328 ///\sa Dfs
2.329 @@ -1309,7 +1308,7 @@
2.330
2.331 typedef DfsVisit Create;
2.332
2.333 - /// \name Named template parameters
2.334 + /// \name Named Template Parameters
2.335
2.336 ///@{
2.337 template <class T>
2.338 @@ -1351,9 +1350,10 @@
2.339 /// \brief Sets the map that indicates which nodes are reached.
2.340 ///
2.341 /// Sets the map that indicates which nodes are reached.
2.342 - /// If you don't use this function before calling \ref run(),
2.343 - /// it will allocate one. The destructor deallocates this
2.344 - /// automatically allocated map, of course.
2.345 + /// If you don't use this function before calling \ref run(Node) "run()"
2.346 + /// or \ref init(), an instance will be allocated automatically.
2.347 + /// The destructor deallocates this automatically allocated map,
2.348 + /// of course.
2.349 /// \return <tt> (*this) </tt>
2.350 DfsVisit &reachedMap(ReachedMap &m) {
2.351 if(local_reached) {
2.352 @@ -1366,16 +1366,14 @@
2.353
2.354 public:
2.355
2.356 - /// \name Execution control
2.357 - /// The simplest way to execute the algorithm is to use
2.358 - /// one of the member functions called \ref lemon::DfsVisit::run()
2.359 - /// "run()".
2.360 - /// \n
2.361 - /// If you need more control on the execution, first you must call
2.362 - /// \ref lemon::DfsVisit::init() "init()", then you can add several
2.363 - /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
2.364 - /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
2.365 - /// actual path computation.
2.366 + /// \name Execution Control
2.367 + /// The simplest way to execute the DFS algorithm is to use one of the
2.368 + /// member functions called \ref run(Node) "run()".\n
2.369 + /// If you need more control on the execution, first you have to call
2.370 + /// \ref init(), then you can add a source node with \ref addSource()
2.371 + /// and perform the actual computation with \ref start().
2.372 + /// This procedure can be repeated if there are nodes that have not
2.373 + /// been reached.
2.374
2.375 /// @{
2.376
2.377 @@ -1391,15 +1389,14 @@
2.378 }
2.379 }
2.380
2.381 - ///Adds a new source node.
2.382 -
2.383 - ///Adds a new source node to the set of nodes to be processed.
2.384 + /// \brief Adds a new source node.
2.385 ///
2.386 - ///\pre The stack must be empty. (Otherwise the algorithm gives
2.387 - ///false results.)
2.388 + /// Adds a new source node to the set of nodes to be processed.
2.389 ///
2.390 - ///\warning Distances will be wrong (or at least strange) in case of
2.391 - ///multiple sources.
2.392 + /// \pre The stack must be empty. Otherwise the algorithm gives
2.393 + /// wrong results. (One of the outgoing arcs of all the source nodes
2.394 + /// except for the last one will not be visited and distances will
2.395 + /// also be wrong.)
2.396 void addSource(Node s)
2.397 {
2.398 LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
2.399 @@ -1589,8 +1586,8 @@
2.400 /// compute the %DFS path to each node.
2.401 ///
2.402 /// The algorithm computes
2.403 - /// - the %DFS tree,
2.404 - /// - the distance of each node from the root in the %DFS tree.
2.405 + /// - the %DFS tree (forest),
2.406 + /// - the distance of each node from the root(s) in the %DFS tree.
2.407 ///
2.408 /// \note <tt>d.run()</tt> is just a shortcut of the following code.
2.409 ///\code
2.410 @@ -1615,17 +1612,18 @@
2.411 ///@}
2.412
2.413 /// \name Query Functions
2.414 - /// The result of the %DFS algorithm can be obtained using these
2.415 + /// The results of the DFS algorithm can be obtained using these
2.416 /// functions.\n
2.417 - /// Either \ref lemon::DfsVisit::run() "run()" or
2.418 - /// \ref lemon::DfsVisit::start() "start()" must be called before
2.419 - /// using them.
2.420 + /// Either \ref run(Node) "run()" or \ref start() should be called
2.421 + /// before using them.
2.422 +
2.423 ///@{
2.424
2.425 - /// \brief Checks if a node is reachable from the root(s).
2.426 + /// \brief Checks if a node is reached from the root(s).
2.427 ///
2.428 - /// Returns \c true if \c v is reachable from the root(s).
2.429 - /// \pre Either \ref run() or \ref start()
2.430 + /// Returns \c true if \c v is reached from the root(s).
2.431 + ///
2.432 + /// \pre Either \ref run(Node) "run()" or \ref init()
2.433 /// must be called before using this function.
2.434 bool reached(Node v) { return (*_reached)[v]; }
2.435
3.1 --- a/lemon/dijkstra.h Tue Dec 02 10:30:52 2008 +0000
3.2 +++ b/lemon/dijkstra.h Tue Dec 02 10:31:20 2008 +0000
3.3 @@ -179,20 +179,13 @@
3.4 ///it can be used easier.
3.5 ///
3.6 ///\tparam GR The type of the digraph the algorithm runs on.
3.7 - ///The default value is \ref ListDigraph.
3.8 - ///The value of GR is not used directly by \ref Dijkstra, it is only
3.9 - ///passed to \ref DijkstraDefaultTraits.
3.10 - ///\tparam LM A readable arc map that determines the lengths of the
3.11 - ///arcs. It is read once for each arc, so the map may involve in
3.12 + ///The default type is \ref ListDigraph.
3.13 + ///\tparam LM A \ref concepts::ReadMap "readable" arc map that specifies
3.14 + ///the lengths of the arcs.
3.15 + ///It is read once for each arc, so the map may involve in
3.16 ///relatively time consuming process to compute the arc lengths if
3.17 ///it is necessary. The default map type is \ref
3.18 - ///concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
3.19 - ///The value of LM is not used directly by \ref Dijkstra, it is only
3.20 - ///passed to \ref DijkstraDefaultTraits.
3.21 - ///\tparam TR Traits class to set various data types used by the algorithm.
3.22 - ///The default traits class is \ref DijkstraDefaultTraits
3.23 - ///"DijkstraDefaultTraits<GR,LM>". See \ref DijkstraDefaultTraits
3.24 - ///for the documentation of a Dijkstra traits class.
3.25 + ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
3.26 #ifdef DOXYGEN
3.27 template <typename GR, typename LM, typename TR>
3.28 #else
3.29 @@ -226,7 +219,7 @@
3.30 ///The operation traits class.
3.31 typedef typename TR::OperationTraits OperationTraits;
3.32
3.33 - ///The traits class.
3.34 + ///The \ref DijkstraDefaultTraits "traits class" of the algorithm.
3.35 typedef TR Traits;
3.36
3.37 private:
3.38 @@ -308,6 +301,7 @@
3.39 ///
3.40 ///\ref named-templ-param "Named parameter" for setting
3.41 ///PredMap type.
3.42 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
3.43 template <class T>
3.44 struct SetPredMap
3.45 : public Dijkstra< Digraph, LengthMap, SetPredMapTraits<T> > {
3.46 @@ -328,6 +322,7 @@
3.47 ///
3.48 ///\ref named-templ-param "Named parameter" for setting
3.49 ///DistMap type.
3.50 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
3.51 template <class T>
3.52 struct SetDistMap
3.53 : public Dijkstra< Digraph, LengthMap, SetDistMapTraits<T> > {
3.54 @@ -348,6 +343,7 @@
3.55 ///
3.56 ///\ref named-templ-param "Named parameter" for setting
3.57 ///ProcessedMap type.
3.58 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
3.59 template <class T>
3.60 struct SetProcessedMap
3.61 : public Dijkstra< Digraph, LengthMap, SetProcessedMapTraits<T> > {
3.62 @@ -388,10 +384,14 @@
3.63 }
3.64 };
3.65 ///\brief \ref named-templ-param "Named parameter" for setting
3.66 - ///heap and cross reference type
3.67 + ///heap and cross reference types
3.68 ///
3.69 ///\ref named-templ-param "Named parameter" for setting heap and cross
3.70 - ///reference type.
3.71 + ///reference types. If this named parameter is used, then external
3.72 + ///heap and cross reference objects must be passed to the algorithm
3.73 + ///using the \ref heap() function before calling \ref run(Node) "run()"
3.74 + ///or \ref init().
3.75 + ///\sa SetStandardHeap
3.76 template <class H, class CR = typename Digraph::template NodeMap<int> >
3.77 struct SetHeap
3.78 : public Dijkstra< Digraph, LengthMap, SetHeapTraits<H, CR> > {
3.79 @@ -411,12 +411,18 @@
3.80 }
3.81 };
3.82 ///\brief \ref named-templ-param "Named parameter" for setting
3.83 - ///heap and cross reference type with automatic allocation
3.84 + ///heap and cross reference types with automatic allocation
3.85 ///
3.86 ///\ref named-templ-param "Named parameter" for setting heap and cross
3.87 - ///reference type. It can allocate the heap and the cross reference
3.88 - ///object if the cross reference's constructor waits for the digraph as
3.89 - ///parameter and the heap's constructor waits for the cross reference.
3.90 + ///reference types with automatic allocation.
3.91 + ///They should have standard constructor interfaces to be able to
3.92 + ///automatically created by the algorithm (i.e. the digraph should be
3.93 + ///passed to the constructor of the cross reference and the cross
3.94 + ///reference should be passed to the constructor of the heap).
3.95 + ///However external heap and cross reference objects could also be
3.96 + ///passed to the algorithm using the \ref heap() function before
3.97 + ///calling \ref run(Node) "run()" or \ref init().
3.98 + ///\sa SetHeap
3.99 template <class H, class CR = typename Digraph::template NodeMap<int> >
3.100 struct SetStandardHeap
3.101 : public Dijkstra< Digraph, LengthMap, SetStandardHeapTraits<H, CR> > {
3.102 @@ -486,9 +492,10 @@
3.103 ///Sets the map that stores the predecessor arcs.
3.104
3.105 ///Sets the map that stores the predecessor arcs.
3.106 - ///If you don't use this function before calling \ref run(),
3.107 - ///it will allocate one. The destructor deallocates this
3.108 - ///automatically allocated map, of course.
3.109 + ///If you don't use this function before calling \ref run(Node) "run()"
3.110 + ///or \ref init(), an instance will be allocated automatically.
3.111 + ///The destructor deallocates this automatically allocated map,
3.112 + ///of course.
3.113 ///\return <tt> (*this) </tt>
3.114 Dijkstra &predMap(PredMap &m)
3.115 {
3.116 @@ -503,9 +510,10 @@
3.117 ///Sets the map that indicates which nodes are processed.
3.118
3.119 ///Sets the map that indicates which nodes are processed.
3.120 - ///If you don't use this function before calling \ref run(),
3.121 - ///it will allocate one. The destructor deallocates this
3.122 - ///automatically allocated map, of course.
3.123 + ///If you don't use this function before calling \ref run(Node) "run()"
3.124 + ///or \ref init(), an instance will be allocated automatically.
3.125 + ///The destructor deallocates this automatically allocated map,
3.126 + ///of course.
3.127 ///\return <tt> (*this) </tt>
3.128 Dijkstra &processedMap(ProcessedMap &m)
3.129 {
3.130 @@ -521,9 +529,10 @@
3.131
3.132 ///Sets the map that stores the distances of the nodes calculated by the
3.133 ///algorithm.
3.134 - ///If you don't use this function before calling \ref run(),
3.135 - ///it will allocate one. The destructor deallocates this
3.136 - ///automatically allocated map, of course.
3.137 + ///If you don't use this function before calling \ref run(Node) "run()"
3.138 + ///or \ref init(), an instance will be allocated automatically.
3.139 + ///The destructor deallocates this automatically allocated map,
3.140 + ///of course.
3.141 ///\return <tt> (*this) </tt>
3.142 Dijkstra &distMap(DistMap &m)
3.143 {
3.144 @@ -538,9 +547,11 @@
3.145 ///Sets the heap and the cross reference used by algorithm.
3.146
3.147 ///Sets the heap and the cross reference used by algorithm.
3.148 - ///If you don't use this function before calling \ref run(),
3.149 - ///it will allocate one. The destructor deallocates this
3.150 - ///automatically allocated heap and cross reference, of course.
3.151 + ///If you don't use this function before calling \ref run(Node) "run()"
3.152 + ///or \ref init(), heap and cross reference instances will be
3.153 + ///allocated automatically.
3.154 + ///The destructor deallocates these automatically allocated objects,
3.155 + ///of course.
3.156 ///\return <tt> (*this) </tt>
3.157 Dijkstra &heap(Heap& hp, HeapCrossRef &cr)
3.158 {
3.159 @@ -567,22 +578,19 @@
3.160
3.161 public:
3.162
3.163 - ///\name Execution control
3.164 - ///The simplest way to execute the algorithm is to use one of the
3.165 - ///member functions called \ref lemon::Dijkstra::run() "run()".
3.166 - ///\n
3.167 - ///If you need more control on the execution, first you must call
3.168 - ///\ref lemon::Dijkstra::init() "init()", then you can add several
3.169 - ///source nodes with \ref lemon::Dijkstra::addSource() "addSource()".
3.170 - ///Finally \ref lemon::Dijkstra::start() "start()" will perform the
3.171 - ///actual path computation.
3.172 + ///\name Execution Control
3.173 + ///The simplest way to execute the %Dijkstra algorithm is to use
3.174 + ///one of the member functions called \ref run(Node) "run()".\n
3.175 + ///If you need more control on the execution, first you have to call
3.176 + ///\ref init(), then you can add several source nodes with
3.177 + ///\ref addSource(). Finally the actual path computation can be
3.178 + ///performed with one of the \ref start() functions.
3.179
3.180 ///@{
3.181
3.182 + ///\brief Initializes the internal data structures.
3.183 + ///
3.184 ///Initializes the internal data structures.
3.185 -
3.186 - ///Initializes the internal data structures.
3.187 - ///
3.188 void init()
3.189 {
3.190 create_maps();
3.191 @@ -658,17 +666,16 @@
3.192 return !_heap->empty()?_heap->top():INVALID;
3.193 }
3.194
3.195 - ///\brief Returns \c false if there are nodes
3.196 - ///to be processed.
3.197 - ///
3.198 - ///Returns \c false if there are nodes
3.199 - ///to be processed in the priority heap.
3.200 + ///Returns \c false if there are nodes to be processed.
3.201 +
3.202 + ///Returns \c false if there are nodes to be processed
3.203 + ///in the priority heap.
3.204 bool emptyQueue() const { return _heap->empty(); }
3.205
3.206 - ///Returns the number of the nodes to be processed in the priority heap
3.207 + ///Returns the number of the nodes to be processed.
3.208
3.209 - ///Returns the number of the nodes to be processed in the priority heap.
3.210 - ///
3.211 + ///Returns the number of the nodes to be processed
3.212 + ///in the priority heap.
3.213 int queueSize() const { return _heap->size(); }
3.214
3.215 ///Executes the algorithm.
3.216 @@ -789,11 +796,10 @@
3.217 ///@}
3.218
3.219 ///\name Query Functions
3.220 - ///The result of the %Dijkstra algorithm can be obtained using these
3.221 + ///The results of the %Dijkstra algorithm can be obtained using these
3.222 ///functions.\n
3.223 - ///Either \ref lemon::Dijkstra::run() "run()" or
3.224 - ///\ref lemon::Dijkstra::start() "start()" must be called before
3.225 - ///using them.
3.226 + ///Either \ref run(Node) "run()" or \ref start() should be called
3.227 + ///before using them.
3.228
3.229 ///@{
3.230
3.231 @@ -801,49 +807,49 @@
3.232
3.233 ///Returns the shortest path to a node.
3.234 ///
3.235 - ///\warning \c t should be reachable from the root(s).
3.236 + ///\warning \c t should be reached from the root(s).
3.237 ///
3.238 - ///\pre Either \ref run() or \ref start() must be called before
3.239 - ///using this function.
3.240 + ///\pre Either \ref run(Node) "run()" or \ref init()
3.241 + ///must be called before using this function.
3.242 Path path(Node t) const { return Path(*G, *_pred, t); }
3.243
3.244 ///The distance of a node from the root(s).
3.245
3.246 ///Returns the distance of a node from the root(s).
3.247 ///
3.248 - ///\warning If node \c v is not reachable from the root(s), then
3.249 + ///\warning If node \c v is not reached from the root(s), then
3.250 ///the return value of this function is undefined.
3.251 ///
3.252 - ///\pre Either \ref run() or \ref start() must be called before
3.253 - ///using this function.
3.254 + ///\pre Either \ref run(Node) "run()" or \ref init()
3.255 + ///must be called before using this function.
3.256 Value dist(Node v) const { return (*_dist)[v]; }
3.257
3.258 ///Returns the 'previous arc' of the shortest path tree for a node.
3.259
3.260 ///This function returns the 'previous arc' of the shortest path
3.261 ///tree for the node \c v, i.e. it returns the last arc of a
3.262 - ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
3.263 - ///is not reachable from the root(s) or if \c v is a root.
3.264 + ///shortest path from a root to \c v. It is \c INVALID if \c v
3.265 + ///is not reached from the root(s) or if \c v is a root.
3.266 ///
3.267 ///The shortest path tree used here is equal to the shortest path
3.268 ///tree used in \ref predNode().
3.269 ///
3.270 - ///\pre Either \ref run() or \ref start() must be called before
3.271 - ///using this function.
3.272 + ///\pre Either \ref run(Node) "run()" or \ref init()
3.273 + ///must be called before using this function.
3.274 Arc predArc(Node v) const { return (*_pred)[v]; }
3.275
3.276 ///Returns the 'previous node' of the shortest path tree for a node.
3.277
3.278 ///This function returns the 'previous node' of the shortest path
3.279 ///tree for the node \c v, i.e. it returns the last but one node
3.280 - ///from a shortest path from the root(s) to \c v. It is \c INVALID
3.281 - ///if \c v is not reachable from the root(s) or if \c v is a root.
3.282 + ///from a shortest path from a root to \c v. It is \c INVALID
3.283 + ///if \c v is not reached from the root(s) or if \c v is a root.
3.284 ///
3.285 ///The shortest path tree used here is equal to the shortest path
3.286 ///tree used in \ref predArc().
3.287 ///
3.288 - ///\pre Either \ref run() or \ref start() must be called before
3.289 - ///using this function.
3.290 + ///\pre Either \ref run(Node) "run()" or \ref init()
3.291 + ///must be called before using this function.
3.292 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
3.293 G->source((*_pred)[v]); }
3.294
3.295 @@ -853,7 +859,7 @@
3.296 ///Returns a const reference to the node map that stores the distances
3.297 ///of the nodes calculated by the algorithm.
3.298 ///
3.299 - ///\pre Either \ref run() or \ref init()
3.300 + ///\pre Either \ref run(Node) "run()" or \ref init()
3.301 ///must be called before using this function.
3.302 const DistMap &distMap() const { return *_dist;}
3.303
3.304 @@ -863,14 +869,15 @@
3.305 ///Returns a const reference to the node map that stores the predecessor
3.306 ///arcs, which form the shortest path tree.
3.307 ///
3.308 - ///\pre Either \ref run() or \ref init()
3.309 + ///\pre Either \ref run(Node) "run()" or \ref init()
3.310 ///must be called before using this function.
3.311 const PredMap &predMap() const { return *_pred;}
3.312
3.313 - ///Checks if a node is reachable from the root(s).
3.314 + ///Checks if a node is reached from the root(s).
3.315
3.316 - ///Returns \c true if \c v is reachable from the root(s).
3.317 - ///\pre Either \ref run() or \ref start()
3.318 + ///Returns \c true if \c v is reached from the root(s).
3.319 + ///
3.320 + ///\pre Either \ref run(Node) "run()" or \ref init()
3.321 ///must be called before using this function.
3.322 bool reached(Node v) const { return (*_heap_cross_ref)[v] !=
3.323 Heap::PRE_HEAP; }
3.324 @@ -879,7 +886,8 @@
3.325
3.326 ///Returns \c true if \c v is processed, i.e. the shortest
3.327 ///path to \c v has already found.
3.328 - ///\pre Either \ref run() or \ref init()
3.329 + ///
3.330 + ///\pre Either \ref run(Node) "run()" or \ref init()
3.331 ///must be called before using this function.
3.332 bool processed(Node v) const { return (*_heap_cross_ref)[v] ==
3.333 Heap::POST_HEAP; }
3.334 @@ -888,7 +896,8 @@
3.335
3.336 ///Returns the current distance of a node from the root(s).
3.337 ///It may be decreased in the following processes.
3.338 - ///\pre Either \ref run() or \ref init()
3.339 + ///
3.340 + ///\pre Either \ref run(Node) "run()" or \ref init()
3.341 ///must be called before using this function and
3.342 ///node \c v must be reached but not necessarily processed.
3.343 Value currentDist(Node v) const {
3.344 @@ -1071,8 +1080,8 @@
3.345
3.346 /// This auxiliary class is created to implement the
3.347 /// \ref dijkstra() "function-type interface" of \ref Dijkstra algorithm.
3.348 - /// It does not have own \ref run() method, it uses the functions
3.349 - /// and features of the plain \ref Dijkstra.
3.350 + /// It does not have own \ref run(Node) "run()" method, it uses the
3.351 + /// functions and features of the plain \ref Dijkstra.
3.352 ///
3.353 /// This class should only be used through the \ref dijkstra() function,
3.354 /// which makes it easier to use the algorithm.
3.355 @@ -1267,7 +1276,7 @@
3.356 /// // Compute shortest path from s to t
3.357 /// bool reached = dijkstra(g,length).path(p).dist(d).run(s,t);
3.358 ///\endcode
3.359 - ///\warning Don't forget to put the \ref DijkstraWizard::run() "run()"
3.360 + ///\warning Don't forget to put the \ref DijkstraWizard::run(Node) "run()"
3.361 ///to the end of the parameter list.
3.362 ///\sa DijkstraWizard
3.363 ///\sa Dijkstra