1.1 --- a/lemon/dfs.h Sun Nov 30 09:39:34 2008 +0000
1.2 +++ b/lemon/dfs.h Sun Nov 30 19:17:51 2008 +0100
1.3 @@ -119,13 +119,7 @@
1.4 ///used easier.
1.5 ///
1.6 ///\tparam GR The type of the digraph the algorithm runs on.
1.7 - ///The default value is \ref ListDigraph. The value of GR is not used
1.8 - ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
1.9 - ///\tparam TR Traits class to set various data types used by the algorithm.
1.10 - ///The default traits class is
1.11 - ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
1.12 - ///See \ref DfsDefaultTraits for the documentation of
1.13 - ///a Dfs traits class.
1.14 + ///The default type is \ref ListDigraph.
1.15 #ifdef DOXYGEN
1.16 template <typename GR,
1.17 typename TR>
1.18 @@ -151,7 +145,7 @@
1.19 ///The type of the paths.
1.20 typedef PredMapPath<Digraph, PredMap> Path;
1.21
1.22 - ///The traits class.
1.23 + ///The \ref DfsDefaultTraits "traits class" of the algorithm.
1.24 typedef TR Traits;
1.25
1.26 private:
1.27 @@ -230,6 +224,7 @@
1.28 ///
1.29 ///\ref named-templ-param "Named parameter" for setting
1.30 ///PredMap type.
1.31 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.32 template <class T>
1.33 struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
1.34 typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
1.35 @@ -249,6 +244,7 @@
1.36 ///
1.37 ///\ref named-templ-param "Named parameter" for setting
1.38 ///DistMap type.
1.39 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.40 template <class T>
1.41 struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
1.42 typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
1.43 @@ -268,6 +264,7 @@
1.44 ///
1.45 ///\ref named-templ-param "Named parameter" for setting
1.46 ///ReachedMap type.
1.47 + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.48 template <class T>
1.49 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
1.50 typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
1.51 @@ -287,6 +284,7 @@
1.52 ///
1.53 ///\ref named-templ-param "Named parameter" for setting
1.54 ///ProcessedMap type.
1.55 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.56 template <class T>
1.57 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
1.58 typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
1.59 @@ -338,9 +336,10 @@
1.60 ///Sets the map that stores the predecessor arcs.
1.61
1.62 ///Sets the map that stores the predecessor arcs.
1.63 - ///If you don't use this function before calling \ref run(),
1.64 - ///it will allocate one. The destructor deallocates this
1.65 - ///automatically allocated map, of course.
1.66 + ///If you don't use this function before calling \ref run(Node) "run()"
1.67 + ///or \ref init(), an instance will be allocated automatically.
1.68 + ///The destructor deallocates this automatically allocated map,
1.69 + ///of course.
1.70 ///\return <tt> (*this) </tt>
1.71 Dfs &predMap(PredMap &m)
1.72 {
1.73 @@ -355,9 +354,10 @@
1.74 ///Sets the map that indicates which nodes are reached.
1.75
1.76 ///Sets the map that indicates which nodes are reached.
1.77 - ///If you don't use this function before calling \ref run(),
1.78 - ///it will allocate one. The destructor deallocates this
1.79 - ///automatically allocated map, of course.
1.80 + ///If you don't use this function before calling \ref run(Node) "run()"
1.81 + ///or \ref init(), an instance will be allocated automatically.
1.82 + ///The destructor deallocates this automatically allocated map,
1.83 + ///of course.
1.84 ///\return <tt> (*this) </tt>
1.85 Dfs &reachedMap(ReachedMap &m)
1.86 {
1.87 @@ -372,9 +372,10 @@
1.88 ///Sets the map that indicates which nodes are processed.
1.89
1.90 ///Sets the map that indicates which nodes are processed.
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 Dfs &processedMap(ProcessedMap &m)
1.100 {
1.101 @@ -390,9 +391,10 @@
1.102
1.103 ///Sets the map that stores the distances of the nodes calculated by
1.104 ///the algorithm.
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 Dfs &distMap(DistMap &m)
1.114 {
1.115 @@ -406,22 +408,20 @@
1.116
1.117 public:
1.118
1.119 - ///\name Execution control
1.120 - ///The simplest way to execute the algorithm is to use
1.121 - ///one of the member functions called \ref lemon::Dfs::run() "run()".
1.122 - ///\n
1.123 - ///If you need more control on the execution, first you must call
1.124 - ///\ref lemon::Dfs::init() "init()", then you can add a source node
1.125 - ///with \ref lemon::Dfs::addSource() "addSource()".
1.126 - ///Finally \ref lemon::Dfs::start() "start()" will perform the
1.127 - ///actual path computation.
1.128 + ///\name Execution Control
1.129 + ///The simplest way to execute the DFS algorithm is to use one of the
1.130 + ///member functions called \ref run(Node) "run()".\n
1.131 + ///If you need more control on the execution, first you have to call
1.132 + ///\ref init(), then you can add a source node with \ref addSource()
1.133 + ///and perform the actual computation with \ref start().
1.134 + ///This procedure can be repeated if there are nodes that have not
1.135 + ///been reached.
1.136
1.137 ///@{
1.138
1.139 + ///\brief Initializes the internal data structures.
1.140 + ///
1.141 ///Initializes the internal data structures.
1.142 -
1.143 - ///Initializes the internal data structures.
1.144 - ///
1.145 void init()
1.146 {
1.147 create_maps();
1.148 @@ -438,11 +438,10 @@
1.149
1.150 ///Adds a new source node to the set of nodes to be processed.
1.151 ///
1.152 - ///\pre The stack must be empty. (Otherwise the algorithm gives
1.153 - ///false results.)
1.154 - ///
1.155 - ///\warning Distances will be wrong (or at least strange) in case of
1.156 - ///multiple sources.
1.157 + ///\pre The stack must be empty. Otherwise the algorithm gives
1.158 + ///wrong results. (One of the outgoing arcs of all the source nodes
1.159 + ///except for the last one will not be visited and distances will
1.160 + ///also be wrong.)
1.161 void addSource(Node s)
1.162 {
1.163 LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
1.164 @@ -506,16 +505,16 @@
1.165 return _stack_head>=0?_stack[_stack_head]:INVALID;
1.166 }
1.167
1.168 - ///\brief Returns \c false if there are nodes
1.169 - ///to be processed.
1.170 - ///
1.171 - ///Returns \c false if there are nodes
1.172 - ///to be processed in the queue (stack).
1.173 + ///Returns \c false if there are nodes to be processed.
1.174 +
1.175 + ///Returns \c false if there are nodes to be processed
1.176 + ///in the queue (stack).
1.177 bool emptyQueue() const { return _stack_head<0; }
1.178
1.179 ///Returns the number of the nodes to be processed.
1.180
1.181 - ///Returns the number of the nodes to be processed in the queue (stack).
1.182 + ///Returns the number of the nodes to be processed
1.183 + ///in the queue (stack).
1.184 int queueSize() const { return _stack_head+1; }
1.185
1.186 ///Executes the algorithm.
1.187 @@ -637,8 +636,8 @@
1.188 ///%DFS path to each node.
1.189 ///
1.190 ///The algorithm computes
1.191 - ///- the %DFS tree,
1.192 - ///- the distance of each node from the root in the %DFS tree.
1.193 + ///- the %DFS tree (forest),
1.194 + ///- the distance of each node from the root(s) in the %DFS tree.
1.195 ///
1.196 ///\note <tt>d.run()</tt> is just a shortcut of the following code.
1.197 ///\code
1.198 @@ -663,10 +662,10 @@
1.199 ///@}
1.200
1.201 ///\name Query Functions
1.202 - ///The result of the %DFS algorithm can be obtained using these
1.203 + ///The results of the DFS algorithm can be obtained using these
1.204 ///functions.\n
1.205 - ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::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 @@ -674,49 +673,49 @@
1.213
1.214 ///Returns the DFS path to a node.
1.215 ///
1.216 - ///\warning \c t should be reachable from the root.
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.
1.226 + ///The distance of a node from the root(s).
1.227
1.228 - ///Returns the distance of a node from the root.
1.229 + ///Returns the distance of a node from the root(s).
1.230 ///
1.231 - ///\warning If node \c v is not reachable from the root, then
1.232 + ///\warning If node \c v is not reached from the root(s), then
1.233 ///the return value of this function is undefined.
1.234 ///
1.235 - ///\pre Either \ref run() or \ref start() must be called before
1.236 - ///using this function.
1.237 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.238 + ///must be called before using this function.
1.239 int dist(Node v) const { return (*_dist)[v]; }
1.240
1.241 ///Returns the 'previous arc' of the %DFS tree for a node.
1.242
1.243 ///This function returns the 'previous arc' of the %DFS tree for the
1.244 - ///node \c v, i.e. it returns the last arc of a %DFS path from the
1.245 - ///root to \c v. It is \c INVALID
1.246 - ///if \c v is not reachable from the root(s) or if \c v is a root.
1.247 + ///node \c v, i.e. it returns the last arc of a %DFS path from a
1.248 + ///root to \c v. It is \c INVALID if \c v is not reached from the
1.249 + ///root(s) or if \c v is a root.
1.250 ///
1.251 ///The %DFS tree used here is equal to the %DFS tree used in
1.252 ///\ref predNode().
1.253 ///
1.254 - ///\pre Either \ref run() or \ref start() must be called before using
1.255 - ///this function.
1.256 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.257 + ///must be called before using this function.
1.258 Arc predArc(Node v) const { return (*_pred)[v];}
1.259
1.260 ///Returns the 'previous node' of the %DFS tree.
1.261
1.262 ///This function returns the 'previous node' of the %DFS
1.263 ///tree for the node \c v, i.e. it returns the last but one node
1.264 - ///from a %DFS path from the root to \c v. It is \c INVALID
1.265 - ///if \c v is not reachable from the root(s) or if \c v is a root.
1.266 + ///from a %DFS path from a root to \c v. It is \c INVALID
1.267 + ///if \c v is not reached from the root(s) or if \c v is a root.
1.268 ///
1.269 ///The %DFS tree used here is equal to the %DFS tree used in
1.270 ///\ref predArc().
1.271 ///
1.272 - ///\pre Either \ref run() or \ref start() must be called before
1.273 - ///using this function.
1.274 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.275 + ///must be called before using this function.
1.276 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
1.277 G->source((*_pred)[v]); }
1.278
1.279 @@ -726,7 +725,7 @@
1.280 ///Returns a const reference to the node map that stores the
1.281 ///distances of the nodes calculated by the algorithm.
1.282 ///
1.283 - ///\pre Either \ref run() or \ref init()
1.284 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.285 ///must be called before using this function.
1.286 const DistMap &distMap() const { return *_dist;}
1.287
1.288 @@ -736,14 +735,15 @@
1.289 ///Returns a const reference to the node map that stores the predecessor
1.290 ///arcs, which form the DFS tree.
1.291 ///
1.292 - ///\pre Either \ref run() or \ref init()
1.293 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.294 ///must be called before using this function.
1.295 const PredMap &predMap() const { return *_pred;}
1.296
1.297 - ///Checks if a node is reachable from the root(s).
1.298 + ///Checks if a node is reached from the root(s).
1.299
1.300 - ///Returns \c true if \c v is reachable from the root(s).
1.301 - ///\pre Either \ref run() or \ref start()
1.302 + ///Returns \c true if \c v is reached from the root(s).
1.303 + ///
1.304 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.305 ///must be called before using this function.
1.306 bool reached(Node v) const { return (*_reached)[v]; }
1.307
1.308 @@ -889,8 +889,8 @@
1.309
1.310 /// This auxiliary class is created to implement the
1.311 /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
1.312 - /// It does not have own \ref run() method, it uses the functions
1.313 - /// and features of the plain \ref Dfs.
1.314 + /// It does not have own \ref run(Node) "run()" method, it uses the
1.315 + /// functions and features of the plain \ref Dfs.
1.316 ///
1.317 /// This class should only be used through the \ref dfs() function,
1.318 /// which makes it easier to use the algorithm.
1.319 @@ -1110,8 +1110,7 @@
1.320 /// // Compute the DFS path from s to t
1.321 /// bool reached = dfs(g).path(p).dist(d).run(s,t);
1.322 ///\endcode
1.323 -
1.324 - ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
1.325 + ///\warning Don't forget to put the \ref DfsWizard::run(Node) "run()"
1.326 ///to the end of the parameter list.
1.327 ///\sa DfsWizard
1.328 ///\sa Dfs
1.329 @@ -1309,7 +1308,7 @@
1.330
1.331 typedef DfsVisit Create;
1.332
1.333 - /// \name Named template parameters
1.334 + /// \name Named Template Parameters
1.335
1.336 ///@{
1.337 template <class T>
1.338 @@ -1351,9 +1350,10 @@
1.339 /// \brief Sets the map that indicates which nodes are reached.
1.340 ///
1.341 /// Sets the map that indicates which nodes are reached.
1.342 - /// If you don't use this function before calling \ref run(),
1.343 - /// it will allocate one. The destructor deallocates this
1.344 - /// automatically allocated map, of course.
1.345 + /// If you don't use this function before calling \ref run(Node) "run()"
1.346 + /// or \ref init(), an instance will be allocated automatically.
1.347 + /// The destructor deallocates this automatically allocated map,
1.348 + /// of course.
1.349 /// \return <tt> (*this) </tt>
1.350 DfsVisit &reachedMap(ReachedMap &m) {
1.351 if(local_reached) {
1.352 @@ -1366,16 +1366,14 @@
1.353
1.354 public:
1.355
1.356 - /// \name Execution control
1.357 - /// The simplest way to execute the algorithm is to use
1.358 - /// one of the member functions called \ref lemon::DfsVisit::run()
1.359 - /// "run()".
1.360 - /// \n
1.361 - /// If you need more control on the execution, first you must call
1.362 - /// \ref lemon::DfsVisit::init() "init()", then you can add several
1.363 - /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
1.364 - /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
1.365 - /// actual path computation.
1.366 + /// \name Execution Control
1.367 + /// The simplest way to execute the DFS algorithm is to use one of the
1.368 + /// member functions called \ref run(Node) "run()".\n
1.369 + /// If you need more control on the execution, first you have to call
1.370 + /// \ref init(), then you can add a source node with \ref addSource()
1.371 + /// and perform the actual computation with \ref start().
1.372 + /// This procedure can be repeated if there are nodes that have not
1.373 + /// been reached.
1.374
1.375 /// @{
1.376
1.377 @@ -1391,15 +1389,14 @@
1.378 }
1.379 }
1.380
1.381 - ///Adds a new source node.
1.382 -
1.383 - ///Adds a new source node to the set of nodes to be processed.
1.384 + /// \brief Adds a new source node.
1.385 ///
1.386 - ///\pre The stack must be empty. (Otherwise the algorithm gives
1.387 - ///false results.)
1.388 + /// Adds a new source node to the set of nodes to be processed.
1.389 ///
1.390 - ///\warning Distances will be wrong (or at least strange) in case of
1.391 - ///multiple sources.
1.392 + /// \pre The stack must be empty. Otherwise the algorithm gives
1.393 + /// wrong results. (One of the outgoing arcs of all the source nodes
1.394 + /// except for the last one will not be visited and distances will
1.395 + /// also be wrong.)
1.396 void addSource(Node s)
1.397 {
1.398 LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
1.399 @@ -1589,8 +1586,8 @@
1.400 /// compute the %DFS path to each node.
1.401 ///
1.402 /// The algorithm computes
1.403 - /// - the %DFS tree,
1.404 - /// - the distance of each node from the root in the %DFS tree.
1.405 + /// - the %DFS tree (forest),
1.406 + /// - the distance of each node from the root(s) in the %DFS tree.
1.407 ///
1.408 /// \note <tt>d.run()</tt> is just a shortcut of the following code.
1.409 ///\code
1.410 @@ -1615,17 +1612,18 @@
1.411 ///@}
1.412
1.413 /// \name Query Functions
1.414 - /// The result of the %DFS algorithm can be obtained using these
1.415 + /// The results of the DFS algorithm can be obtained using these
1.416 /// functions.\n
1.417 - /// Either \ref lemon::DfsVisit::run() "run()" or
1.418 - /// \ref lemon::DfsVisit::start() "start()" must be called before
1.419 - /// using them.
1.420 + /// Either \ref run(Node) "run()" or \ref start() should be called
1.421 + /// before using them.
1.422 +
1.423 ///@{
1.424
1.425 - /// \brief Checks if a node is reachable from the root(s).
1.426 + /// \brief Checks if a node is reached from the root(s).
1.427 ///
1.428 - /// Returns \c true if \c v is reachable from the root(s).
1.429 - /// \pre Either \ref run() or \ref start()
1.430 + /// Returns \c true if \c v is reached from the root(s).
1.431 + ///
1.432 + /// \pre Either \ref run(Node) "run()" or \ref init()
1.433 /// must be called before using this function.
1.434 bool reached(Node v) { return (*_reached)[v]; }
1.435