1.1 --- a/lemon/dfs.h Fri Oct 16 10:21:37 2009 +0200
1.2 +++ b/lemon/dfs.h Thu Nov 05 15:50:01 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 @@ -47,13 +47,13 @@
1.13 ///
1.14 ///The type of the map that stores the predecessor
1.15 ///arcs of the %DFS paths.
1.16 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.17 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.18 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.19 - ///Instantiates a PredMap.
1.20 + ///Instantiates a \c PredMap.
1.21
1.22 - ///This function instantiates a PredMap.
1.23 + ///This function instantiates a \ref PredMap.
1.24 ///\param g is the digraph, to which we would like to define the
1.25 - ///PredMap.
1.26 + ///\ref PredMap.
1.27 static PredMap *createPredMap(const Digraph &g)
1.28 {
1.29 return new PredMap(g);
1.30 @@ -62,13 +62,14 @@
1.31 ///The type of the map that indicates which nodes are processed.
1.32
1.33 ///The type of the map that indicates which nodes are processed.
1.34 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.35 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.36 + ///By default it is a NullMap.
1.37 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.38 - ///Instantiates a ProcessedMap.
1.39 + ///Instantiates a \c ProcessedMap.
1.40
1.41 - ///This function instantiates a ProcessedMap.
1.42 + ///This function instantiates a \ref ProcessedMap.
1.43 ///\param g is the digraph, to which
1.44 - ///we would like to define the ProcessedMap
1.45 + ///we would like to define the \ref ProcessedMap.
1.46 #ifdef DOXYGEN
1.47 static ProcessedMap *createProcessedMap(const Digraph &g)
1.48 #else
1.49 @@ -81,13 +82,13 @@
1.50 ///The type of the map that indicates which nodes are reached.
1.51
1.52 ///The type of the map that indicates which nodes are reached.
1.53 - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.54 + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.55 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.56 - ///Instantiates a ReachedMap.
1.57 + ///Instantiates a \c ReachedMap.
1.58
1.59 - ///This function instantiates a ReachedMap.
1.60 + ///This function instantiates a \ref ReachedMap.
1.61 ///\param g is the digraph, to which
1.62 - ///we would like to define the ReachedMap.
1.63 + ///we would like to define the \ref ReachedMap.
1.64 static ReachedMap *createReachedMap(const Digraph &g)
1.65 {
1.66 return new ReachedMap(g);
1.67 @@ -96,13 +97,13 @@
1.68 ///The type of the map that stores the distances of the nodes.
1.69
1.70 ///The type of the map that stores the distances of the nodes.
1.71 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.72 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.73 typedef typename Digraph::template NodeMap<int> DistMap;
1.74 - ///Instantiates a DistMap.
1.75 + ///Instantiates a \c DistMap.
1.76
1.77 - ///This function instantiates a DistMap.
1.78 + ///This function instantiates a \ref DistMap.
1.79 ///\param g is the digraph, to which we would like to define the
1.80 - ///DistMap.
1.81 + ///\ref DistMap.
1.82 static DistMap *createDistMap(const Digraph &g)
1.83 {
1.84 return new DistMap(g);
1.85 @@ -119,13 +120,7 @@
1.86 ///used easier.
1.87 ///
1.88 ///\tparam GR The type of the digraph the algorithm runs on.
1.89 - ///The default value is \ref ListDigraph. The value of GR is not used
1.90 - ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
1.91 - ///\tparam TR Traits class to set various data types used by the algorithm.
1.92 - ///The default traits class is
1.93 - ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
1.94 - ///See \ref DfsDefaultTraits for the documentation of
1.95 - ///a Dfs traits class.
1.96 + ///The default type is \ref ListDigraph.
1.97 #ifdef DOXYGEN
1.98 template <typename GR,
1.99 typename TR>
1.100 @@ -151,7 +146,7 @@
1.101 ///The type of the paths.
1.102 typedef PredMapPath<Digraph, PredMap> Path;
1.103
1.104 - ///The traits class.
1.105 + ///The \ref DfsDefaultTraits "traits class" of the algorithm.
1.106 typedef TR Traits;
1.107
1.108 private:
1.109 @@ -212,7 +207,7 @@
1.110
1.111 typedef Dfs Create;
1.112
1.113 - ///\name Named template parameters
1.114 + ///\name Named Template Parameters
1.115
1.116 ///@{
1.117
1.118 @@ -226,10 +221,11 @@
1.119 }
1.120 };
1.121 ///\brief \ref named-templ-param "Named parameter" for setting
1.122 - ///PredMap type.
1.123 + ///\c PredMap type.
1.124 ///
1.125 ///\ref named-templ-param "Named parameter" for setting
1.126 - ///PredMap type.
1.127 + ///\c PredMap type.
1.128 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.129 template <class T>
1.130 struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
1.131 typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
1.132 @@ -245,10 +241,11 @@
1.133 }
1.134 };
1.135 ///\brief \ref named-templ-param "Named parameter" for setting
1.136 - ///DistMap type.
1.137 + ///\c DistMap type.
1.138 ///
1.139 ///\ref named-templ-param "Named parameter" for setting
1.140 - ///DistMap type.
1.141 + ///\c DistMap type.
1.142 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.143 template <class T>
1.144 struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
1.145 typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
1.146 @@ -264,10 +261,11 @@
1.147 }
1.148 };
1.149 ///\brief \ref named-templ-param "Named parameter" for setting
1.150 - ///ReachedMap type.
1.151 + ///\c ReachedMap type.
1.152 ///
1.153 ///\ref named-templ-param "Named parameter" for setting
1.154 - ///ReachedMap type.
1.155 + ///\c ReachedMap type.
1.156 + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.157 template <class T>
1.158 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
1.159 typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
1.160 @@ -283,10 +281,11 @@
1.161 }
1.162 };
1.163 ///\brief \ref named-templ-param "Named parameter" for setting
1.164 - ///ProcessedMap type.
1.165 + ///\c ProcessedMap type.
1.166 ///
1.167 ///\ref named-templ-param "Named parameter" for setting
1.168 - ///ProcessedMap type.
1.169 + ///\c ProcessedMap type.
1.170 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.171 template <class T>
1.172 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
1.173 typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
1.174 @@ -300,10 +299,10 @@
1.175 }
1.176 };
1.177 ///\brief \ref named-templ-param "Named parameter" for setting
1.178 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.179 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.180 ///
1.181 ///\ref named-templ-param "Named parameter" for setting
1.182 - ///ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.183 + ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.184 ///If you don't set it explicitly, it will be automatically allocated.
1.185 struct SetStandardProcessedMap :
1.186 public Dfs< Digraph, SetStandardProcessedMapTraits > {
1.187 @@ -338,9 +337,10 @@
1.188 ///Sets the map that stores the predecessor arcs.
1.189
1.190 ///Sets the map that stores the predecessor arcs.
1.191 - ///If you don't use this function before calling \ref run(),
1.192 - ///it will allocate one. The destructor deallocates this
1.193 - ///automatically allocated map, of course.
1.194 + ///If you don't use this function before calling \ref run(Node) "run()"
1.195 + ///or \ref init(), an instance will be allocated automatically.
1.196 + ///The destructor deallocates this automatically allocated map,
1.197 + ///of course.
1.198 ///\return <tt> (*this) </tt>
1.199 Dfs &predMap(PredMap &m)
1.200 {
1.201 @@ -355,9 +355,10 @@
1.202 ///Sets the map that indicates which nodes are reached.
1.203
1.204 ///Sets the map that indicates which nodes are reached.
1.205 - ///If you don't use this function before calling \ref run(),
1.206 - ///it will allocate one. The destructor deallocates this
1.207 - ///automatically allocated map, of course.
1.208 + ///If you don't use this function before calling \ref run(Node) "run()"
1.209 + ///or \ref init(), an instance will be allocated automatically.
1.210 + ///The destructor deallocates this automatically allocated map,
1.211 + ///of course.
1.212 ///\return <tt> (*this) </tt>
1.213 Dfs &reachedMap(ReachedMap &m)
1.214 {
1.215 @@ -372,9 +373,10 @@
1.216 ///Sets the map that indicates which nodes are processed.
1.217
1.218 ///Sets the map that indicates which nodes are processed.
1.219 - ///If you don't use this function before calling \ref run(),
1.220 - ///it will allocate one. The destructor deallocates this
1.221 - ///automatically allocated map, of course.
1.222 + ///If you don't use this function before calling \ref run(Node) "run()"
1.223 + ///or \ref init(), an instance will be allocated automatically.
1.224 + ///The destructor deallocates this automatically allocated map,
1.225 + ///of course.
1.226 ///\return <tt> (*this) </tt>
1.227 Dfs &processedMap(ProcessedMap &m)
1.228 {
1.229 @@ -390,9 +392,10 @@
1.230
1.231 ///Sets the map that stores the distances of the nodes calculated by
1.232 ///the algorithm.
1.233 - ///If you don't use this function before calling \ref run(),
1.234 - ///it will allocate one. The destructor deallocates this
1.235 - ///automatically allocated map, of course.
1.236 + ///If you don't use this function before calling \ref run(Node) "run()"
1.237 + ///or \ref init(), an instance will be allocated automatically.
1.238 + ///The destructor deallocates this automatically allocated map,
1.239 + ///of course.
1.240 ///\return <tt> (*this) </tt>
1.241 Dfs &distMap(DistMap &m)
1.242 {
1.243 @@ -406,22 +409,20 @@
1.244
1.245 public:
1.246
1.247 - ///\name Execution control
1.248 - ///The simplest way to execute the algorithm is to use
1.249 - ///one of the member functions called \ref lemon::Dfs::run() "run()".
1.250 - ///\n
1.251 - ///If you need more control on the execution, first you must call
1.252 - ///\ref lemon::Dfs::init() "init()", then you can add a source node
1.253 - ///with \ref lemon::Dfs::addSource() "addSource()".
1.254 - ///Finally \ref lemon::Dfs::start() "start()" will perform the
1.255 - ///actual path computation.
1.256 + ///\name Execution Control
1.257 + ///The simplest way to execute the DFS algorithm is to use one of the
1.258 + ///member functions called \ref run(Node) "run()".\n
1.259 + ///If you need better control on the execution, you have to call
1.260 + ///\ref init() first, then you can add a source node with \ref addSource()
1.261 + ///and perform the actual computation with \ref start().
1.262 + ///This procedure can be repeated if there are nodes that have not
1.263 + ///been reached.
1.264
1.265 ///@{
1.266
1.267 + ///\brief Initializes the internal data structures.
1.268 + ///
1.269 ///Initializes the internal data structures.
1.270 -
1.271 - ///Initializes the internal data structures.
1.272 - ///
1.273 void init()
1.274 {
1.275 create_maps();
1.276 @@ -438,11 +439,10 @@
1.277
1.278 ///Adds a new source node to the set of nodes to be processed.
1.279 ///
1.280 - ///\pre The stack must be empty. (Otherwise the algorithm gives
1.281 - ///false results.)
1.282 - ///
1.283 - ///\warning Distances will be wrong (or at least strange) in case of
1.284 - ///multiple sources.
1.285 + ///\pre The stack must be empty. Otherwise the algorithm gives
1.286 + ///wrong results. (One of the outgoing arcs of all the source nodes
1.287 + ///except for the last one will not be visited and distances will
1.288 + ///also be wrong.)
1.289 void addSource(Node s)
1.290 {
1.291 LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
1.292 @@ -506,16 +506,16 @@
1.293 return _stack_head>=0?_stack[_stack_head]:INVALID;
1.294 }
1.295
1.296 - ///\brief Returns \c false if there are nodes
1.297 - ///to be processed.
1.298 - ///
1.299 - ///Returns \c false if there are nodes
1.300 - ///to be processed in the queue (stack).
1.301 + ///Returns \c false if there are nodes to be processed.
1.302 +
1.303 + ///Returns \c false if there are nodes to be processed
1.304 + ///in the queue (stack).
1.305 bool emptyQueue() const { return _stack_head<0; }
1.306
1.307 ///Returns the number of the nodes to be processed.
1.308
1.309 - ///Returns the number of the nodes to be processed in the queue (stack).
1.310 + ///Returns the number of the nodes to be processed
1.311 + ///in the queue (stack).
1.312 int queueSize() const { return _stack_head+1; }
1.313
1.314 ///Executes the algorithm.
1.315 @@ -637,8 +637,8 @@
1.316 ///%DFS path to each node.
1.317 ///
1.318 ///The algorithm computes
1.319 - ///- the %DFS tree,
1.320 - ///- the distance of each node from the root in the %DFS tree.
1.321 + ///- the %DFS tree (forest),
1.322 + ///- the distance of each node from the root(s) in the %DFS tree.
1.323 ///
1.324 ///\note <tt>d.run()</tt> is just a shortcut of the following code.
1.325 ///\code
1.326 @@ -663,60 +663,60 @@
1.327 ///@}
1.328
1.329 ///\name Query Functions
1.330 - ///The result of the %DFS algorithm can be obtained using these
1.331 + ///The results of the DFS algorithm can be obtained using these
1.332 ///functions.\n
1.333 - ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
1.334 - ///"start()" must be called before using them.
1.335 + ///Either \ref run(Node) "run()" or \ref start() should be called
1.336 + ///before using them.
1.337
1.338 ///@{
1.339
1.340 - ///The DFS path to a node.
1.341 + ///The DFS path to the given node.
1.342
1.343 - ///Returns the DFS path to a node.
1.344 + ///Returns the DFS path to the given node from the root(s).
1.345 ///
1.346 - ///\warning \c t should be reachable from the root.
1.347 + ///\warning \c t should be reached from the root(s).
1.348 ///
1.349 - ///\pre Either \ref run() or \ref start() must be called before
1.350 - ///using this function.
1.351 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.352 + ///must be called before using this function.
1.353 Path path(Node t) const { return Path(*G, *_pred, t); }
1.354
1.355 - ///The distance of a node from the root.
1.356 + ///The distance of the given node from the root(s).
1.357
1.358 - ///Returns the distance of a node from the root.
1.359 + ///Returns the distance of the given node from the root(s).
1.360 ///
1.361 - ///\warning If node \c v is not reachable from the root, then
1.362 + ///\warning If node \c v is not reached from the root(s), then
1.363 ///the return value of this function is undefined.
1.364 ///
1.365 - ///\pre Either \ref run() or \ref start() must be called before
1.366 - ///using this function.
1.367 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.368 + ///must be called before using this function.
1.369 int dist(Node v) const { return (*_dist)[v]; }
1.370
1.371 - ///Returns the 'previous arc' of the %DFS tree for a node.
1.372 + ///Returns the 'previous arc' of the %DFS tree for the given node.
1.373
1.374 ///This function returns the 'previous arc' of the %DFS tree for the
1.375 - ///node \c v, i.e. it returns the last arc of a %DFS path from the
1.376 - ///root to \c v. It is \c INVALID
1.377 - ///if \c v is not reachable from the root(s) or if \c v is a root.
1.378 + ///node \c v, i.e. it returns the last arc of a %DFS path from a
1.379 + ///root to \c v. It is \c INVALID if \c v is not reached from the
1.380 + ///root(s) or if \c v is a root.
1.381 ///
1.382 ///The %DFS tree used here is equal to the %DFS tree used in
1.383 - ///\ref predNode().
1.384 + ///\ref predNode() and \ref predMap().
1.385 ///
1.386 - ///\pre Either \ref run() or \ref start() must be called before using
1.387 - ///this function.
1.388 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.389 + ///must be called before using this function.
1.390 Arc predArc(Node v) const { return (*_pred)[v];}
1.391
1.392 - ///Returns the 'previous node' of the %DFS tree.
1.393 + ///Returns the 'previous node' of the %DFS tree for the given node.
1.394
1.395 ///This function returns the 'previous node' of the %DFS
1.396 ///tree for the node \c v, i.e. it returns the last but one node
1.397 - ///from a %DFS path from the root to \c v. It is \c INVALID
1.398 - ///if \c v is not reachable from the root(s) or if \c v is a root.
1.399 + ///of a %DFS path from a root to \c v. It is \c INVALID
1.400 + ///if \c v is not reached from the root(s) or if \c v is a root.
1.401 ///
1.402 ///The %DFS tree used here is equal to the %DFS tree used in
1.403 - ///\ref predArc().
1.404 + ///\ref predArc() and \ref predMap().
1.405 ///
1.406 - ///\pre Either \ref run() or \ref start() must be called before
1.407 - ///using this function.
1.408 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.409 + ///must be called before using this function.
1.410 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
1.411 G->source((*_pred)[v]); }
1.412
1.413 @@ -726,7 +726,7 @@
1.414 ///Returns a const reference to the node map that stores the
1.415 ///distances of the nodes calculated by the algorithm.
1.416 ///
1.417 - ///\pre Either \ref run() or \ref init()
1.418 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.419 ///must be called before using this function.
1.420 const DistMap &distMap() const { return *_dist;}
1.421
1.422 @@ -734,16 +734,17 @@
1.423 ///predecessor arcs.
1.424 ///
1.425 ///Returns a const reference to the node map that stores the predecessor
1.426 - ///arcs, which form the DFS tree.
1.427 + ///arcs, which form the DFS tree (forest).
1.428 ///
1.429 - ///\pre Either \ref run() or \ref init()
1.430 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.431 ///must be called before using this function.
1.432 const PredMap &predMap() const { return *_pred;}
1.433
1.434 - ///Checks if a node is reachable from the root(s).
1.435 + ///Checks if the given node. node is reached from the root(s).
1.436
1.437 - ///Returns \c true if \c v is reachable from the root(s).
1.438 - ///\pre Either \ref run() or \ref start()
1.439 + ///Returns \c true if \c v is reached from the root(s).
1.440 + ///
1.441 + ///\pre Either \ref run(Node) "run()" or \ref init()
1.442 ///must be called before using this function.
1.443 bool reached(Node v) const { return (*_reached)[v]; }
1.444
1.445 @@ -765,7 +766,7 @@
1.446 ///
1.447 ///The type of the map that stores the predecessor
1.448 ///arcs of the %DFS paths.
1.449 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.450 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.451 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.452 ///Instantiates a PredMap.
1.453
1.454 @@ -780,7 +781,7 @@
1.455 ///The type of the map that indicates which nodes are processed.
1.456
1.457 ///The type of the map that indicates which nodes are processed.
1.458 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.459 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.460 ///By default it is a NullMap.
1.461 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.462 ///Instantiates a ProcessedMap.
1.463 @@ -800,7 +801,7 @@
1.464 ///The type of the map that indicates which nodes are reached.
1.465
1.466 ///The type of the map that indicates which nodes are reached.
1.467 - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.468 + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.469 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.470 ///Instantiates a ReachedMap.
1.471
1.472 @@ -815,7 +816,7 @@
1.473 ///The type of the map that stores the distances of the nodes.
1.474
1.475 ///The type of the map that stores the distances of the nodes.
1.476 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.477 + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
1.478 typedef typename Digraph::template NodeMap<int> DistMap;
1.479 ///Instantiates a DistMap.
1.480
1.481 @@ -830,18 +831,14 @@
1.482 ///The type of the DFS paths.
1.483
1.484 ///The type of the DFS paths.
1.485 - ///It must meet the \ref concepts::Path "Path" concept.
1.486 + ///It must conform to the \ref concepts::Path "Path" concept.
1.487 typedef lemon::Path<Digraph> Path;
1.488 };
1.489
1.490 /// Default traits class used by DfsWizard
1.491
1.492 - /// To make it easier to use Dfs algorithm
1.493 - /// we have created a wizard class.
1.494 - /// This \ref DfsWizard class needs default traits,
1.495 - /// as well as the \ref Dfs class.
1.496 - /// The \ref DfsWizardBase is a class to be the default traits of the
1.497 - /// \ref DfsWizard class.
1.498 + /// Default traits class used by DfsWizard.
1.499 + /// \tparam GR The type of the digraph.
1.500 template<class GR>
1.501 class DfsWizardBase : public DfsWizardDefaultTraits<GR>
1.502 {
1.503 @@ -869,7 +866,7 @@
1.504 public:
1.505 /// Constructor.
1.506
1.507 - /// This constructor does not require parameters, therefore it initiates
1.508 + /// This constructor does not require parameters, it initiates
1.509 /// all of the attributes to \c 0.
1.510 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
1.511 _dist(0), _path(0), _di(0) {}
1.512 @@ -889,8 +886,8 @@
1.513
1.514 /// This auxiliary class is created to implement the
1.515 /// \ref dfs() "function-type interface" of \ref Dfs algorithm.
1.516 - /// It does not have own \ref run() method, it uses the functions
1.517 - /// and features of the plain \ref Dfs.
1.518 + /// It does not have own \ref run(Node) "run()" method, it uses the
1.519 + /// functions and features of the plain \ref Dfs.
1.520 ///
1.521 /// This class should only be used through the \ref dfs() function,
1.522 /// which makes it easier to use the algorithm.
1.523 @@ -899,7 +896,6 @@
1.524 {
1.525 typedef TR Base;
1.526
1.527 - ///The type of the digraph the algorithm runs on.
1.528 typedef typename TR::Digraph Digraph;
1.529
1.530 typedef typename Digraph::Node Node;
1.531 @@ -907,16 +903,10 @@
1.532 typedef typename Digraph::Arc Arc;
1.533 typedef typename Digraph::OutArcIt OutArcIt;
1.534
1.535 - ///\brief The type of the map that stores the predecessor
1.536 - ///arcs of the DFS paths.
1.537 typedef typename TR::PredMap PredMap;
1.538 - ///\brief The type of the map that stores the distances of the nodes.
1.539 typedef typename TR::DistMap DistMap;
1.540 - ///\brief The type of the map that indicates which nodes are reached.
1.541 typedef typename TR::ReachedMap ReachedMap;
1.542 - ///\brief The type of the map that indicates which nodes are processed.
1.543 typedef typename TR::ProcessedMap ProcessedMap;
1.544 - ///The type of the DFS paths
1.545 typedef typename TR::Path Path;
1.546
1.547 public:
1.548 @@ -999,11 +989,12 @@
1.549 static PredMap *createPredMap(const Digraph &) { return 0; };
1.550 SetPredMapBase(const TR &b) : TR(b) {}
1.551 };
1.552 - ///\brief \ref named-func-param "Named parameter"
1.553 - ///for setting PredMap object.
1.554 +
1.555 + ///\brief \ref named-templ-param "Named parameter" for setting
1.556 + ///the predecessor map.
1.557 ///
1.558 - ///\ref named-func-param "Named parameter"
1.559 - ///for setting PredMap object.
1.560 + ///\ref named-templ-param "Named parameter" function for setting
1.561 + ///the map that stores the predecessor arcs of the nodes.
1.562 template<class T>
1.563 DfsWizard<SetPredMapBase<T> > predMap(const T &t)
1.564 {
1.565 @@ -1017,11 +1008,12 @@
1.566 static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1.567 SetReachedMapBase(const TR &b) : TR(b) {}
1.568 };
1.569 - ///\brief \ref named-func-param "Named parameter"
1.570 - ///for setting ReachedMap object.
1.571 +
1.572 + ///\brief \ref named-templ-param "Named parameter" for setting
1.573 + ///the reached map.
1.574 ///
1.575 - /// \ref named-func-param "Named parameter"
1.576 - ///for setting ReachedMap object.
1.577 + ///\ref named-templ-param "Named parameter" function for setting
1.578 + ///the map that indicates which nodes are reached.
1.579 template<class T>
1.580 DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
1.581 {
1.582 @@ -1035,11 +1027,13 @@
1.583 static DistMap *createDistMap(const Digraph &) { return 0; };
1.584 SetDistMapBase(const TR &b) : TR(b) {}
1.585 };
1.586 - ///\brief \ref named-func-param "Named parameter"
1.587 - ///for setting DistMap object.
1.588 +
1.589 + ///\brief \ref named-templ-param "Named parameter" for setting
1.590 + ///the distance map.
1.591 ///
1.592 - /// \ref named-func-param "Named parameter"
1.593 - ///for setting DistMap object.
1.594 + ///\ref named-templ-param "Named parameter" function for setting
1.595 + ///the map that stores the distances of the nodes calculated
1.596 + ///by the algorithm.
1.597 template<class T>
1.598 DfsWizard<SetDistMapBase<T> > distMap(const T &t)
1.599 {
1.600 @@ -1053,11 +1047,12 @@
1.601 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1.602 SetProcessedMapBase(const TR &b) : TR(b) {}
1.603 };
1.604 - ///\brief \ref named-func-param "Named parameter"
1.605 - ///for setting ProcessedMap object.
1.606 +
1.607 + ///\brief \ref named-func-param "Named parameter" for setting
1.608 + ///the processed map.
1.609 ///
1.610 - /// \ref named-func-param "Named parameter"
1.611 - ///for setting ProcessedMap object.
1.612 + ///\ref named-templ-param "Named parameter" function for setting
1.613 + ///the map that indicates which nodes are processed.
1.614 template<class T>
1.615 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1.616 {
1.617 @@ -1110,8 +1105,7 @@
1.618 /// // Compute the DFS path from s to t
1.619 /// bool reached = dfs(g).path(p).dist(d).run(s,t);
1.620 ///\endcode
1.621 -
1.622 - ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
1.623 + ///\warning Don't forget to put the \ref DfsWizard::run(Node) "run()"
1.624 ///to the end of the parameter list.
1.625 ///\sa DfsWizard
1.626 ///\sa Dfs
1.627 @@ -1127,9 +1121,9 @@
1.628 ///
1.629 /// This class defines the interface of the DfsVisit events, and
1.630 /// it could be the base of a real visitor class.
1.631 - template <typename _Digraph>
1.632 + template <typename GR>
1.633 struct DfsVisitor {
1.634 - typedef _Digraph Digraph;
1.635 + typedef GR Digraph;
1.636 typedef typename Digraph::Arc Arc;
1.637 typedef typename Digraph::Node Node;
1.638 /// \brief Called for the source node of the DFS.
1.639 @@ -1165,9 +1159,9 @@
1.640 void backtrack(const Arc& arc) {}
1.641 };
1.642 #else
1.643 - template <typename _Digraph>
1.644 + template <typename GR>
1.645 struct DfsVisitor {
1.646 - typedef _Digraph Digraph;
1.647 + typedef GR Digraph;
1.648 typedef typename Digraph::Arc Arc;
1.649 typedef typename Digraph::Node Node;
1.650 void start(const Node&) {}
1.651 @@ -1200,16 +1194,16 @@
1.652 ///
1.653 /// Default traits class of DfsVisit class.
1.654 /// \tparam _Digraph The type of the digraph the algorithm runs on.
1.655 - template<class _Digraph>
1.656 + template<class GR>
1.657 struct DfsVisitDefaultTraits {
1.658
1.659 /// \brief The type of the digraph the algorithm runs on.
1.660 - typedef _Digraph Digraph;
1.661 + typedef GR Digraph;
1.662
1.663 /// \brief The type of the map that indicates which nodes are reached.
1.664 ///
1.665 /// The type of the map that indicates which nodes are reached.
1.666 - /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.667 + /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.668 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.669
1.670 /// \brief Instantiates a ReachedMap.
1.671 @@ -1225,12 +1219,12 @@
1.672
1.673 /// \ingroup search
1.674 ///
1.675 - /// \brief %DFS algorithm class with visitor interface.
1.676 + /// \brief DFS algorithm class with visitor interface.
1.677 ///
1.678 - /// This class provides an efficient implementation of the %DFS algorithm
1.679 + /// This class provides an efficient implementation of the DFS algorithm
1.680 /// with visitor interface.
1.681 ///
1.682 - /// The %DfsVisit class provides an alternative interface to the Dfs
1.683 + /// The DfsVisit class provides an alternative interface to the Dfs
1.684 /// class. It works with callback mechanism, the DfsVisit object calls
1.685 /// the member functions of the \c Visitor class on every DFS event.
1.686 ///
1.687 @@ -1239,37 +1233,37 @@
1.688 /// events of the DFS algorithm. Otherwise consider to use Dfs or dfs()
1.689 /// instead.
1.690 ///
1.691 - /// \tparam _Digraph The type of the digraph the algorithm runs on.
1.692 - /// The default value is
1.693 - /// \ref ListDigraph. The value of _Digraph is not used directly by
1.694 - /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
1.695 - /// \tparam _Visitor The Visitor type that is used by the algorithm.
1.696 - /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
1.697 + /// \tparam GR The type of the digraph the algorithm runs on.
1.698 + /// The default type is \ref ListDigraph.
1.699 + /// The value of GR is not used directly by \ref DfsVisit,
1.700 + /// it is only passed to \ref DfsVisitDefaultTraits.
1.701 + /// \tparam VS The Visitor type that is used by the algorithm.
1.702 + /// \ref DfsVisitor "DfsVisitor<GR>" is an empty visitor, which
1.703 /// does not observe the DFS events. If you want to observe the DFS
1.704 /// events, you should implement your own visitor class.
1.705 - /// \tparam _Traits Traits class to set various data types used by the
1.706 + /// \tparam TR Traits class to set various data types used by the
1.707 /// algorithm. The default traits class is
1.708 - /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
1.709 + /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>".
1.710 /// See \ref DfsVisitDefaultTraits for the documentation of
1.711 /// a DFS visit traits class.
1.712 #ifdef DOXYGEN
1.713 - template <typename _Digraph, typename _Visitor, typename _Traits>
1.714 + template <typename GR, typename VS, typename TR>
1.715 #else
1.716 - template <typename _Digraph = ListDigraph,
1.717 - typename _Visitor = DfsVisitor<_Digraph>,
1.718 - typename _Traits = DfsVisitDefaultTraits<_Digraph> >
1.719 + template <typename GR = ListDigraph,
1.720 + typename VS = DfsVisitor<GR>,
1.721 + typename TR = DfsVisitDefaultTraits<GR> >
1.722 #endif
1.723 class DfsVisit {
1.724 public:
1.725
1.726 ///The traits class.
1.727 - typedef _Traits Traits;
1.728 + typedef TR Traits;
1.729
1.730 ///The type of the digraph the algorithm runs on.
1.731 typedef typename Traits::Digraph Digraph;
1.732
1.733 ///The visitor type used by the algorithm.
1.734 - typedef _Visitor Visitor;
1.735 + typedef VS Visitor;
1.736
1.737 ///The type of the map that indicates which nodes are reached.
1.738 typedef typename Traits::ReachedMap ReachedMap;
1.739 @@ -1309,7 +1303,7 @@
1.740
1.741 typedef DfsVisit Create;
1.742
1.743 - /// \name Named template parameters
1.744 + /// \name Named Template Parameters
1.745
1.746 ///@{
1.747 template <class T>
1.748 @@ -1351,9 +1345,10 @@
1.749 /// \brief Sets the map that indicates which nodes are reached.
1.750 ///
1.751 /// Sets the map that indicates which nodes are reached.
1.752 - /// If you don't use this function before calling \ref run(),
1.753 - /// it will allocate one. The destructor deallocates this
1.754 - /// automatically allocated map, of course.
1.755 + /// If you don't use this function before calling \ref run(Node) "run()"
1.756 + /// or \ref init(), an instance will be allocated automatically.
1.757 + /// The destructor deallocates this automatically allocated map,
1.758 + /// of course.
1.759 /// \return <tt> (*this) </tt>
1.760 DfsVisit &reachedMap(ReachedMap &m) {
1.761 if(local_reached) {
1.762 @@ -1366,16 +1361,14 @@
1.763
1.764 public:
1.765
1.766 - /// \name Execution control
1.767 - /// The simplest way to execute the algorithm is to use
1.768 - /// one of the member functions called \ref lemon::DfsVisit::run()
1.769 - /// "run()".
1.770 - /// \n
1.771 - /// If you need more control on the execution, first you must call
1.772 - /// \ref lemon::DfsVisit::init() "init()", then you can add several
1.773 - /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
1.774 - /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
1.775 - /// actual path computation.
1.776 + /// \name Execution Control
1.777 + /// The simplest way to execute the DFS algorithm is to use one of the
1.778 + /// member functions called \ref run(Node) "run()".\n
1.779 + /// If you need better control on the execution, you have to call
1.780 + /// \ref init() first, then you can add a source node with \ref addSource()
1.781 + /// and perform the actual computation with \ref start().
1.782 + /// This procedure can be repeated if there are nodes that have not
1.783 + /// been reached.
1.784
1.785 /// @{
1.786
1.787 @@ -1391,15 +1384,14 @@
1.788 }
1.789 }
1.790
1.791 - ///Adds a new source node.
1.792 -
1.793 - ///Adds a new source node to the set of nodes to be processed.
1.794 + /// \brief Adds a new source node.
1.795 ///
1.796 - ///\pre The stack must be empty. (Otherwise the algorithm gives
1.797 - ///false results.)
1.798 + /// Adds a new source node to the set of nodes to be processed.
1.799 ///
1.800 - ///\warning Distances will be wrong (or at least strange) in case of
1.801 - ///multiple sources.
1.802 + /// \pre The stack must be empty. Otherwise the algorithm gives
1.803 + /// wrong results. (One of the outgoing arcs of all the source nodes
1.804 + /// except for the last one will not be visited and distances will
1.805 + /// also be wrong.)
1.806 void addSource(Node s)
1.807 {
1.808 LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
1.809 @@ -1413,6 +1405,7 @@
1.810 _stack[++_stack_head] = e;
1.811 } else {
1.812 _visitor->leave(s);
1.813 + _visitor->stop(s);
1.814 }
1.815 }
1.816 }
1.817 @@ -1589,8 +1582,8 @@
1.818 /// compute the %DFS path to each node.
1.819 ///
1.820 /// The algorithm computes
1.821 - /// - the %DFS tree,
1.822 - /// - the distance of each node from the root in the %DFS tree.
1.823 + /// - the %DFS tree (forest),
1.824 + /// - the distance of each node from the root(s) in the %DFS tree.
1.825 ///
1.826 /// \note <tt>d.run()</tt> is just a shortcut of the following code.
1.827 ///\code
1.828 @@ -1615,19 +1608,20 @@
1.829 ///@}
1.830
1.831 /// \name Query Functions
1.832 - /// The result of the %DFS algorithm can be obtained using these
1.833 + /// The results of the DFS algorithm can be obtained using these
1.834 /// functions.\n
1.835 - /// Either \ref lemon::DfsVisit::run() "run()" or
1.836 - /// \ref lemon::DfsVisit::start() "start()" must be called before
1.837 - /// using them.
1.838 + /// Either \ref run(Node) "run()" or \ref start() should be called
1.839 + /// before using them.
1.840 +
1.841 ///@{
1.842
1.843 - /// \brief Checks if a node is reachable from the root(s).
1.844 + /// \brief Checks if the given node is reached from the root(s).
1.845 ///
1.846 - /// Returns \c true if \c v is reachable from the root(s).
1.847 - /// \pre Either \ref run() or \ref start()
1.848 + /// Returns \c true if \c v is reached from the root(s).
1.849 + ///
1.850 + /// \pre Either \ref run(Node) "run()" or \ref init()
1.851 /// must be called before using this function.
1.852 - bool reached(Node v) { return (*_reached)[v]; }
1.853 + bool reached(Node v) const { return (*_reached)[v]; }
1.854
1.855 ///@}
1.856