1.1 --- a/lemon/dfs.h Fri Nov 13 12:33:33 2009 +0100
1.2 +++ b/lemon/dfs.h Thu Dec 10 17:05:35 2009 +0100
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2008
1.8 + * Copyright (C) 2003-2009
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -49,11 +49,11 @@
1.13 ///arcs of the %DFS paths.
1.14 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.15 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.16 - ///Instantiates a PredMap.
1.17 + ///Instantiates a \c PredMap.
1.18
1.19 - ///This function instantiates a PredMap.
1.20 + ///This function instantiates a \ref PredMap.
1.21 ///\param g is the digraph, to which we would like to define the
1.22 - ///PredMap.
1.23 + ///\ref PredMap.
1.24 static PredMap *createPredMap(const Digraph &g)
1.25 {
1.26 return new PredMap(g);
1.27 @@ -64,11 +64,11 @@
1.28 ///The type of the map that indicates which nodes are processed.
1.29 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.30 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.31 - ///Instantiates a ProcessedMap.
1.32 + ///Instantiates a \c ProcessedMap.
1.33
1.34 - ///This function instantiates a ProcessedMap.
1.35 + ///This function instantiates a \ref ProcessedMap.
1.36 ///\param g is the digraph, to which
1.37 - ///we would like to define the ProcessedMap
1.38 + ///we would like to define the \ref ProcessedMap.
1.39 #ifdef DOXYGEN
1.40 static ProcessedMap *createProcessedMap(const Digraph &g)
1.41 #else
1.42 @@ -83,11 +83,11 @@
1.43 ///The type of the map that indicates which nodes are reached.
1.44 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.45 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.46 - ///Instantiates a ReachedMap.
1.47 + ///Instantiates a \c ReachedMap.
1.48
1.49 - ///This function instantiates a ReachedMap.
1.50 + ///This function instantiates a \ref ReachedMap.
1.51 ///\param g is the digraph, to which
1.52 - ///we would like to define the ReachedMap.
1.53 + ///we would like to define the \ref ReachedMap.
1.54 static ReachedMap *createReachedMap(const Digraph &g)
1.55 {
1.56 return new ReachedMap(g);
1.57 @@ -98,11 +98,11 @@
1.58 ///The type of the map that stores the distances of the nodes.
1.59 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.60 typedef typename Digraph::template NodeMap<int> DistMap;
1.61 - ///Instantiates a DistMap.
1.62 + ///Instantiates a \c DistMap.
1.63
1.64 - ///This function instantiates a DistMap.
1.65 + ///This function instantiates a \ref DistMap.
1.66 ///\param g is the digraph, to which we would like to define the
1.67 - ///DistMap.
1.68 + ///\ref DistMap.
1.69 static DistMap *createDistMap(const Digraph &g)
1.70 {
1.71 return new DistMap(g);
1.72 @@ -119,13 +119,7 @@
1.73 ///used easier.
1.74 ///
1.75 ///\tparam GR The type of the digraph the algorithm runs on.
1.76 - ///The default value is \ref ListDigraph. The value of GR is not used
1.77 - ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
1.78 - ///\tparam TR Traits class to set various data types used by the algorithm.
1.79 - ///The default traits class is
1.80 - ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
1.81 - ///See \ref DfsDefaultTraits for the documentation of
1.82 - ///a Dfs traits class.
1.83 + ///The default type is \ref ListDigraph.
1.84 #ifdef DOXYGEN
1.85 template <typename GR,
1.86 typename TR>
1.87 @@ -151,7 +145,7 @@
1.88 ///The type of the paths.
1.89 typedef PredMapPath<Digraph, PredMap> Path;
1.90
1.91 - ///The traits class.
1.92 + ///The \ref DfsDefaultTraits "traits class" of the algorithm.
1.93 typedef TR Traits;
1.94
1.95 private:
1.96 @@ -212,7 +206,7 @@
1.97
1.98 typedef Dfs Create;
1.99
1.100 - ///\name Named template parameters
1.101 + ///\name Named Template Parameters
1.102
1.103 ///@{
1.104
1.105 @@ -226,10 +220,11 @@
1.106 }
1.107 };
1.108 ///\brief \ref named-templ-param "Named parameter" for setting
1.109 - ///PredMap type.
1.110 + ///\c PredMap type.
1.111 ///
1.112 ///\ref named-templ-param "Named parameter" for setting
1.113 - ///PredMap type.
1.114 + ///\c PredMap type.
1.115 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.116 template <class T>
1.117 struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
1.118 typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
1.119 @@ -245,10 +240,11 @@
1.120 }
1.121 };
1.122 ///\brief \ref named-templ-param "Named parameter" for setting
1.123 - ///DistMap type.
1.124 + ///\c DistMap type.
1.125 ///
1.126 ///\ref named-templ-param "Named parameter" for setting
1.127 - ///DistMap type.
1.128 + ///\c DistMap type.
1.129 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.130 template <class T>
1.131 struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
1.132 typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
1.133 @@ -264,10 +260,11 @@
1.134 }
1.135 };
1.136 ///\brief \ref named-templ-param "Named parameter" for setting
1.137 - ///ReachedMap type.
1.138 + ///\c ReachedMap type.
1.139 ///
1.140 ///\ref named-templ-param "Named parameter" for setting
1.141 - ///ReachedMap type.
1.142 + ///\c ReachedMap type.
1.143 + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.144 template <class T>
1.145 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
1.146 typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
1.147 @@ -283,10 +280,11 @@
1.148 }
1.149 };
1.150 ///\brief \ref named-templ-param "Named parameter" for setting
1.151 - ///ProcessedMap type.
1.152 + ///\c ProcessedMap type.
1.153 ///
1.154 ///\ref named-templ-param "Named parameter" for setting
1.155 - ///ProcessedMap type.
1.156 + ///\c ProcessedMap type.
1.157 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.158 template <class T>
1.159 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
1.160 typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
1.161 @@ -300,10 +298,10 @@
1.162 }
1.163 };
1.164 ///\brief \ref named-templ-param "Named parameter" for setting
1.165 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.166 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.167 ///
1.168 ///\ref named-templ-param "Named parameter" for setting
1.169 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.170 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.171 ///If you don't set it explicitly, it will be automatically allocated.
1.172 struct SetStandardProcessedMap :
1.173 public Dfs< Digraph, SetStandardProcessedMapTraits > {
1.174 @@ -338,9 +336,10 @@
1.175 ///Sets the map that stores the predecessor arcs.
1.176
1.177 ///Sets the map that stores the predecessor arcs.
1.178 - ///If you don't use this function before calling \ref run(),
1.179 - ///it will allocate one. The destructor deallocates this
1.180 - ///automatically allocated map, of course.
1.181 + ///If you don't use this function before calling \ref run(Node) "run()"
1.182 + ///or \ref init(), an instance will be allocated automatically.
1.183 + ///The destructor deallocates this automatically allocated map,
1.184 + ///of course.
1.185 ///\return <tt> (*this) </tt>
1.186 Dfs &predMap(PredMap &m)
1.187 {
1.188 @@ -355,9 +354,10 @@
1.189 ///Sets the map that indicates which nodes are reached.
1.190
1.191 ///Sets the map that indicates which nodes are reached.
1.192 - ///If you don't use this function before calling \ref run(),
1.193 - ///it will allocate one. The destructor deallocates this
1.194 - ///automatically allocated map, of course.
1.195 + ///If you don't use this function before calling \ref run(Node) "run()"
1.196 + ///or \ref init(), an instance will be allocated automatically.
1.197 + ///The destructor deallocates this automatically allocated map,
1.198 + ///of course.
1.199 ///\return <tt> (*this) </tt>
1.200 Dfs &reachedMap(ReachedMap &m)
1.201 {
1.202 @@ -372,9 +372,10 @@
1.203 ///Sets the map that indicates which nodes are processed.
1.204
1.205 ///Sets the map that indicates which nodes are processed.
1.206 - ///If you don't use this function before calling \ref run(),
1.207 - ///it will allocate one. The destructor deallocates this
1.208 - ///automatically allocated map, of course.
1.209 + ///If you don't use this function before calling \ref run(Node) "run()"
1.210 + ///or \ref init(), an instance will be allocated automatically.
1.211 + ///The destructor deallocates this automatically allocated map,
1.212 + ///of course.
1.213 ///\return <tt> (*this) </tt>
1.214 Dfs &processedMap(ProcessedMap &m)
1.215 {
1.216 @@ -390,9 +391,10 @@
1.217
1.218 ///Sets the map that stores the distances of the nodes calculated by
1.219 ///the algorithm.
1.220 - ///If you don't use this function before calling \ref run(),
1.221 - ///it will allocate one. The destructor deallocates this
1.222 - ///automatically allocated map, of course.
1.223 + ///If you don't use this function before calling \ref run(Node) "run()"
1.224 + ///or \ref init(), an instance will be allocated automatically.
1.225 + ///The destructor deallocates this automatically allocated map,
1.226 + ///of course.
1.227 ///\return <tt> (*this) </tt>
1.228 Dfs &distMap(DistMap &m)
1.229 {
1.230 @@ -406,22 +408,20 @@
1.231
1.232 public:
1.233
1.234 - ///\name Execution control
1.235 - ///The simplest way to execute the algorithm is to use
1.236 - ///one of the member functions called \ref lemon::Dfs::run() "run()".
1.237 - ///\n
1.238 - ///If you need more control on the execution, first you must call
1.239 - ///\ref lemon::Dfs::init() "init()", then you can add a source node
1.240 - ///with \ref lemon::Dfs::addSource() "addSource()".
1.241 - ///Finally \ref lemon::Dfs::start() "start()" will perform the
1.242 - ///actual path computation.
1.243 + ///\name Execution Control
1.244 + ///The simplest way to execute the DFS algorithm is to use one of the
1.245 + ///member functions called \ref run(Node) "run()".\n
1.246 + ///If you need more control on the execution, first you have to call
1.247 + ///\ref init(), then you can add a source node with \ref addSource()
1.248 + ///and perform the actual computation with \ref start().
1.249 + ///This procedure can be repeated if there are nodes that have not
1.250 + ///been reached.
1.251
1.252 ///@{
1.253
1.254 + ///\brief Initializes the internal data structures.
1.255 + ///
1.256 ///Initializes the internal data structures.
1.257 -
1.258 - ///Initializes the internal data structures.
1.259 - ///
1.260 void init()
1.261 {
1.262 create_maps();
1.263 @@ -438,11 +438,10 @@
1.264
1.265 ///Adds a new source node to the set of nodes to be processed.
1.266 ///
1.267 - ///\pre The stack must be empty. (Otherwise the algorithm gives
1.268 - ///false results.)
1.269 - ///
1.270 - ///\warning Distances will be wrong (or at least strange) in case of
1.271 - ///multiple sources.
1.272 + ///\pre The stack must be empty. Otherwise the algorithm gives
1.273 + ///wrong results. (One of the outgoing arcs of all the source nodes
1.274 + ///except for the last one will not be visited and distances will
1.275 + ///also be wrong.)
1.276 void addSource(Node s)
1.277 {
1.278 LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
1.279 @@ -506,16 +505,16 @@
1.280 return _stack_head>=0?_stack[_stack_head]:INVALID;
1.281 }
1.282
1.283 - ///\brief Returns \c false if there are nodes
1.284 - ///to be processed.
1.285 - ///
1.286 - ///Returns \c false if there are nodes
1.287 - ///to be processed in the queue (stack).
1.288 + ///Returns \c false if there are nodes to be processed.
1.289 +
1.290 + ///Returns \c false if there are nodes to be processed
1.291 + ///in the queue (stack).
1.292 bool emptyQueue() const { return _stack_head<0; }
1.293
1.294 ///Returns the number of the nodes to be processed.
1.295
1.296 - ///Returns the number of the nodes to be processed in the queue (stack).
1.297 + ///Returns the number of the nodes to be processed
1.298 + ///in the queue (stack).
1.299 int queueSize() const { return _stack_head+1; }
1.300
1.301 ///Executes the algorithm.
1.302 @@ -637,8 +636,8 @@
1.303 ///%DFS path to each node.
1.304 ///
1.305 ///The algorithm computes
1.306 - ///- the %DFS tree,
1.307 - ///- the distance of each node from the root in the %DFS tree.
1.308 + ///- the %DFS tree (forest),
1.309 + ///- the distance of each node from the root(s) in the %DFS tree.
1.310 ///
1.311 ///\note <tt>d.run()</tt> is just a shortcut of the following code.
1.312 ///\code
1.313 @@ -663,10 +662,10 @@
1.314 ///@}
1.315
1.316 ///\name Query Functions
1.317 - ///The result of the %DFS algorithm can be obtained using these
1.318 + ///The results of the DFS algorithm can be obtained using these
1.319 ///functions.\n
1.320 - ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
1.321 - ///"start()" must be called before using them.
1.322 + ///Either \ref run(Node) "run()" or \ref start() should be called
1.323 + ///before using them.
1.324
1.325 ///@{
1.326
1.327 @@ -674,49 +673,49 @@
1.328
1.329 ///Returns the DFS path to a node.
1.330 ///
1.331 - ///\warning \c t should be reachable from the root.
1.332 + ///\warning \c t should be reached from the root(s).
1.333 ///
1.334 - ///\pre Either \ref run() or \ref start() must be called before
1.335 - ///using this function.
1.336 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.337 + ///must be called before using this function.
1.338 Path path(Node t) const { return Path(*G, *_pred, t); }
1.339
1.340 - ///The distance of a node from the root.
1.341 + ///The distance of a node from the root(s).
1.342
1.343 - ///Returns the distance of a node from the root.
1.344 + ///Returns the distance of a node from the root(s).
1.345 ///
1.346 - ///\warning If node \c v is not reachable from the root, then
1.347 + ///\warning If node \c v is not reached from the root(s), then
1.348 ///the return value of this function is undefined.
1.349 ///
1.350 - ///\pre Either \ref run() or \ref start() must be called before
1.351 - ///using this function.
1.352 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.353 + ///must be called before using this function.
1.354 int dist(Node v) const { return (*_dist)[v]; }
1.355
1.356 ///Returns the 'previous arc' of the %DFS tree for a node.
1.357
1.358 ///This function returns the 'previous arc' of the %DFS tree for the
1.359 - ///node \c v, i.e. it returns the last arc of a %DFS path from the
1.360 - ///root to \c v. It is \c INVALID
1.361 - ///if \c v is not reachable from the root(s) or if \c v is a root.
1.362 + ///node \c v, i.e. it returns the last arc of a %DFS path from a
1.363 + ///root to \c v. It is \c INVALID if \c v is not reached from the
1.364 + ///root(s) or if \c v is a root.
1.365 ///
1.366 ///The %DFS tree used here is equal to the %DFS tree used in
1.367 ///\ref predNode().
1.368 ///
1.369 - ///\pre Either \ref run() or \ref start() must be called before using
1.370 - ///this function.
1.371 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.372 + ///must be called before using this function.
1.373 Arc predArc(Node v) const { return (*_pred)[v];}
1.374
1.375 ///Returns the 'previous node' of the %DFS tree.
1.376
1.377 ///This function returns the 'previous node' of the %DFS
1.378 ///tree for the node \c v, i.e. it returns the last but one node
1.379 - ///from a %DFS path from the root to \c v. It is \c INVALID
1.380 - ///if \c v is not reachable from the root(s) or if \c v is a root.
1.381 + ///from a %DFS path from a root to \c v. It is \c INVALID
1.382 + ///if \c v is not reached from the root(s) or if \c v is a root.
1.383 ///
1.384 ///The %DFS tree used here is equal to the %DFS tree used in
1.385 ///\ref predArc().
1.386 ///
1.387 - ///\pre Either \ref run() or \ref start() must be called before
1.388 - ///using this function.
1.389 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.390 + ///must be called before using this function.
1.391 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
1.392 G->source((*_pred)[v]); }
1.393
1.394 @@ -726,7 +725,7 @@
1.395 ///Returns a const reference to the node map that stores the
1.396 ///distances of the nodes calculated by the algorithm.
1.397 ///
1.398 - ///\pre Either \ref run() or \ref init()
1.399 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.400 ///must be called before using this function.
1.401 const DistMap &distMap() const { return *_dist;}
1.402
1.403 @@ -736,14 +735,15 @@
1.404 ///Returns a const reference to the node map that stores the predecessor
1.405 ///arcs, which form the DFS tree.
1.406 ///
1.407 - ///\pre Either \ref run() or \ref init()
1.408 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.409 ///must be called before using this function.
1.410 const PredMap &predMap() const { return *_pred;}
1.411
1.412 - ///Checks if a node is reachable from the root(s).
1.413 + ///Checks if a node is reached from the root(s).
1.414
1.415 - ///Returns \c true if \c v is reachable from the root(s).
1.416 - ///\pre Either \ref run() or \ref start()
1.417 + ///Returns \c true if \c v is reached from the root(s).
1.418 + ///
1.419 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.420 ///must be called before using this function.
1.421 bool reached(Node v) const { return (*_reached)[v]; }
1.422
1.423 @@ -889,8 +889,8 @@
1.424
1.425 /// This auxiliary class is created to implement the
1.426 /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
1.427 - /// It does not have own \ref run() method, it uses the functions
1.428 - /// and features of the plain \ref Dfs.
1.429 + /// It does not have own \ref run(Node) "run()" method, it uses the
1.430 + /// functions and features of the plain \ref Dfs.
1.431 ///
1.432 /// This class should only be used through the \ref dfs() function,
1.433 /// which makes it easier to use the algorithm.
1.434 @@ -1110,8 +1110,7 @@
1.435 /// // Compute the DFS path from s to t
1.436 /// bool reached = dfs(g).path(p).dist(d).run(s,t);
1.437 ///\endcode
1.438 -
1.439 - ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
1.440 + ///\warning Don't forget to put the \ref DfsWizard::run(Node) "run()"
1.441 ///to the end of the parameter list.
1.442 ///\sa DfsWizard
1.443 ///\sa Dfs
1.444 @@ -1127,9 +1126,9 @@
1.445 ///
1.446 /// This class defines the interface of the DfsVisit events, and
1.447 /// it could be the base of a real visitor class.
1.448 - template <typename _Digraph>
1.449 + template <typename GR>
1.450 struct DfsVisitor {
1.451 - typedef _Digraph Digraph;
1.452 + typedef GR Digraph;
1.453 typedef typename Digraph::Arc Arc;
1.454 typedef typename Digraph::Node Node;
1.455 /// \brief Called for the source node of the DFS.
1.456 @@ -1165,9 +1164,9 @@
1.457 void backtrack(const Arc& arc) {}
1.458 };
1.459 #else
1.460 - template <typename _Digraph>
1.461 + template <typename GR>
1.462 struct DfsVisitor {
1.463 - typedef _Digraph Digraph;
1.464 + typedef GR Digraph;
1.465 typedef typename Digraph::Arc Arc;
1.466 typedef typename Digraph::Node Node;
1.467 void start(const Node&) {}
1.468 @@ -1200,11 +1199,11 @@
1.469 ///
1.470 /// Default traits class of DfsVisit class.
1.471 /// \tparam _Digraph The type of the digraph the algorithm runs on.
1.472 - template<class _Digraph>
1.473 + template<class GR>
1.474 struct DfsVisitDefaultTraits {
1.475
1.476 /// \brief The type of the digraph the algorithm runs on.
1.477 - typedef _Digraph Digraph;
1.478 + typedef GR Digraph;
1.479
1.480 /// \brief The type of the map that indicates which nodes are reached.
1.481 ///
1.482 @@ -1225,12 +1224,12 @@
1.483
1.484 /// \ingroup search
1.485 ///
1.486 - /// \brief %DFS algorithm class with visitor interface.
1.487 + /// \brief DFS algorithm class with visitor interface.
1.488 ///
1.489 - /// This class provides an efficient implementation of the %DFS algorithm
1.490 + /// This class provides an efficient implementation of the DFS algorithm
1.491 /// with visitor interface.
1.492 ///
1.493 - /// The %DfsVisit class provides an alternative interface to the Dfs
1.494 + /// The DfsVisit class provides an alternative interface to the Dfs
1.495 /// class. It works with callback mechanism, the DfsVisit object calls
1.496 /// the member functions of the \c Visitor class on every DFS event.
1.497 ///
1.498 @@ -1239,37 +1238,37 @@
1.499 /// events of the DFS algorithm. Otherwise consider to use Dfs or dfs()
1.500 /// instead.
1.501 ///
1.502 - /// \tparam _Digraph The type of the digraph the algorithm runs on.
1.503 - /// The default value is
1.504 - /// \ref ListDigraph. The value of _Digraph is not used directly by
1.505 - /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
1.506 - /// \tparam _Visitor The Visitor type that is used by the algorithm.
1.507 - /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
1.508 + /// \tparam GR The type of the digraph the algorithm runs on.
1.509 + /// The default type is \ref ListDigraph.
1.510 + /// The value of GR is not used directly by \ref DfsVisit,
1.511 + /// it is only passed to \ref DfsVisitDefaultTraits.
1.512 + /// \tparam VS The Visitor type that is used by the algorithm.
1.513 + /// \ref DfsVisitor "DfsVisitor<GR>" is an empty visitor, which
1.514 /// does not observe the DFS events. If you want to observe the DFS
1.515 /// events, you should implement your own visitor class.
1.516 - /// \tparam _Traits Traits class to set various data types used by the
1.517 + /// \tparam TR Traits class to set various data types used by the
1.518 /// algorithm. The default traits class is
1.519 - /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
1.520 + /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>".
1.521 /// See \ref DfsVisitDefaultTraits for the documentation of
1.522 /// a DFS visit traits class.
1.523 #ifdef DOXYGEN
1.524 - template <typename _Digraph, typename _Visitor, typename _Traits>
1.525 + template <typename GR, typename VS, typename TR>
1.526 #else
1.527 - template <typename _Digraph = ListDigraph,
1.528 - typename _Visitor = DfsVisitor<_Digraph>,
1.529 - typename _Traits = DfsVisitDefaultTraits<_Digraph> >
1.530 + template <typename GR = ListDigraph,
1.531 + typename VS = DfsVisitor<GR>,
1.532 + typename TR = DfsVisitDefaultTraits<GR> >
1.533 #endif
1.534 class DfsVisit {
1.535 public:
1.536
1.537 ///The traits class.
1.538 - typedef _Traits Traits;
1.539 + typedef TR Traits;
1.540
1.541 ///The type of the digraph the algorithm runs on.
1.542 typedef typename Traits::Digraph Digraph;
1.543
1.544 ///The visitor type used by the algorithm.
1.545 - typedef _Visitor Visitor;
1.546 + typedef VS Visitor;
1.547
1.548 ///The type of the map that indicates which nodes are reached.
1.549 typedef typename Traits::ReachedMap ReachedMap;
1.550 @@ -1309,7 +1308,7 @@
1.551
1.552 typedef DfsVisit Create;
1.553
1.554 - /// \name Named template parameters
1.555 + /// \name Named Template Parameters
1.556
1.557 ///@{
1.558 template <class T>
1.559 @@ -1351,9 +1350,10 @@
1.560 /// \brief Sets the map that indicates which nodes are reached.
1.561 ///
1.562 /// Sets the map that indicates which nodes are reached.
1.563 - /// If you don't use this function before calling \ref run(),
1.564 - /// it will allocate one. The destructor deallocates this
1.565 - /// automatically allocated map, of course.
1.566 + /// If you don't use this function before calling \ref run(Node) "run()"
1.567 + /// or \ref init(), an instance will be allocated automatically.
1.568 + /// The destructor deallocates this automatically allocated map,
1.569 + /// of course.
1.570 /// \return <tt> (*this) </tt>
1.571 DfsVisit &reachedMap(ReachedMap &m) {
1.572 if(local_reached) {
1.573 @@ -1366,16 +1366,14 @@
1.574
1.575 public:
1.576
1.577 - /// \name Execution control
1.578 - /// The simplest way to execute the algorithm is to use
1.579 - /// one of the member functions called \ref lemon::DfsVisit::run()
1.580 - /// "run()".
1.581 - /// \n
1.582 - /// If you need more control on the execution, first you must call
1.583 - /// \ref lemon::DfsVisit::init() "init()", then you can add several
1.584 - /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
1.585 - /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
1.586 - /// actual path computation.
1.587 + /// \name Execution Control
1.588 + /// The simplest way to execute the DFS algorithm is to use one of the
1.589 + /// member functions called \ref run(Node) "run()".\n
1.590 + /// If you need more control on the execution, first you have to call
1.591 + /// \ref init(), then you can add a source node with \ref addSource()
1.592 + /// and perform the actual computation with \ref start().
1.593 + /// This procedure can be repeated if there are nodes that have not
1.594 + /// been reached.
1.595
1.596 /// @{
1.597
1.598 @@ -1391,15 +1389,14 @@
1.599 }
1.600 }
1.601
1.602 - ///Adds a new source node.
1.603 -
1.604 - ///Adds a new source node to the set of nodes to be processed.
1.605 + /// \brief Adds a new source node.
1.606 ///
1.607 - ///\pre The stack must be empty. (Otherwise the algorithm gives
1.608 - ///false results.)
1.609 + /// Adds a new source node to the set of nodes to be processed.
1.610 ///
1.611 - ///\warning Distances will be wrong (or at least strange) in case of
1.612 - ///multiple sources.
1.613 + /// \pre The stack must be empty. Otherwise the algorithm gives
1.614 + /// wrong results. (One of the outgoing arcs of all the source nodes
1.615 + /// except for the last one will not be visited and distances will
1.616 + /// also be wrong.)
1.617 void addSource(Node s)
1.618 {
1.619 LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
1.620 @@ -1413,6 +1410,7 @@
1.621 _stack[++_stack_head] = e;
1.622 } else {
1.623 _visitor->leave(s);
1.624 + _visitor->stop(s);
1.625 }
1.626 }
1.627 }
1.628 @@ -1589,8 +1587,8 @@
1.629 /// compute the %DFS path to each node.
1.630 ///
1.631 /// The algorithm computes
1.632 - /// - the %DFS tree,
1.633 - /// - the distance of each node from the root in the %DFS tree.
1.634 + /// - the %DFS tree (forest),
1.635 + /// - the distance of each node from the root(s) in the %DFS tree.
1.636 ///
1.637 /// \note <tt>d.run()</tt> is just a shortcut of the following code.
1.638 ///\code
1.639 @@ -1615,19 +1613,20 @@
1.640 ///@}
1.641
1.642 /// \name Query Functions
1.643 - /// The result of the %DFS algorithm can be obtained using these
1.644 + /// The results of the DFS algorithm can be obtained using these
1.645 /// functions.\n
1.646 - /// Either \ref lemon::DfsVisit::run() "run()" or
1.647 - /// \ref lemon::DfsVisit::start() "start()" must be called before
1.648 - /// using them.
1.649 + /// Either \ref run(Node) "run()" or \ref start() should be called
1.650 + /// before using them.
1.651 +
1.652 ///@{
1.653
1.654 - /// \brief Checks if a node is reachable from the root(s).
1.655 + /// \brief Checks if a node is reached from the root(s).
1.656 ///
1.657 - /// Returns \c true if \c v is reachable from the root(s).
1.658 - /// \pre Either \ref run() or \ref start()
1.659 + /// Returns \c true if \c v is reached from the root(s).
1.660 + ///
1.661 + /// \pre Either \ref run(Node) "run()" or \ref init()
1.662 /// must be called before using this function.
1.663 - bool reached(Node v) { return (*_reached)[v]; }
1.664 + bool reached(Node v) const { return (*_reached)[v]; }
1.665
1.666 ///@}
1.667