1.1 --- a/lemon/dfs.h Wed Jul 30 12:07:48 2008 +0100
1.2 +++ b/lemon/dfs.h Mon Aug 04 22:00:36 2008 +0200
1.3 @@ -21,19 +21,17 @@
1.4
1.5 ///\ingroup search
1.6 ///\file
1.7 -///\brief Dfs algorithm.
1.8 +///\brief DFS algorithm.
1.9
1.10 #include <lemon/list_graph.h>
1.11 #include <lemon/bits/path_dump.h>
1.12 #include <lemon/core.h>
1.13 #include <lemon/error.h>
1.14 +#include <lemon/assert.h>
1.15 #include <lemon/maps.h>
1.16
1.17 -#include <lemon/concept_check.h>
1.18 -
1.19 namespace lemon {
1.20
1.21 -
1.22 ///Default traits class of Dfs class.
1.23
1.24 ///Default traits class of Dfs class.
1.25 @@ -41,74 +39,75 @@
1.26 template<class GR>
1.27 struct DfsDefaultTraits
1.28 {
1.29 - ///The digraph type the algorithm runs on.
1.30 + ///The type of the digraph the algorithm runs on.
1.31 typedef GR Digraph;
1.32 - ///\brief The type of the map that stores the last
1.33 +
1.34 + ///\brief The type of the map that stores the predecessor
1.35 ///arcs of the %DFS paths.
1.36 ///
1.37 - ///The type of the map that stores the last
1.38 + ///The type of the map that stores the predecessor
1.39 ///arcs of the %DFS paths.
1.40 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.41 - ///
1.42 - typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
1.43 - ///Instantiates a PredMap.
1.44 + typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
1.45 + ///Instantiates a \ref PredMap.
1.46
1.47 ///This function instantiates a \ref PredMap.
1.48 - ///\param G is the digraph, to which we would like to define the PredMap.
1.49 + ///\param g is the digraph, to which we would like to define the
1.50 + ///\ref PredMap.
1.51 ///\todo The digraph alone may be insufficient to initialize
1.52 - static PredMap *createPredMap(const GR &G)
1.53 + static PredMap *createPredMap(const Digraph &g)
1.54 {
1.55 - return new PredMap(G);
1.56 + return new PredMap(g);
1.57 }
1.58
1.59 ///The type of the map that indicates which nodes are processed.
1.60
1.61 ///The type of the map that indicates which nodes are processed.
1.62 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.63 - ///\todo named parameter to set this type, function to read and write.
1.64 + ///By default it is a NullMap.
1.65 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.66 - ///Instantiates a ProcessedMap.
1.67 + ///Instantiates a \ref ProcessedMap.
1.68
1.69 ///This function instantiates a \ref ProcessedMap.
1.70 ///\param g is the digraph, to which
1.71 ///we would like to define the \ref ProcessedMap
1.72 #ifdef DOXYGEN
1.73 - static ProcessedMap *createProcessedMap(const GR &g)
1.74 + static ProcessedMap *createProcessedMap(const Digraph &g)
1.75 #else
1.76 - static ProcessedMap *createProcessedMap(const GR &)
1.77 + static ProcessedMap *createProcessedMap(const Digraph &)
1.78 #endif
1.79 {
1.80 return new ProcessedMap();
1.81 }
1.82 +
1.83 ///The type of the map that indicates which nodes are reached.
1.84
1.85 ///The type of the map that indicates which nodes are reached.
1.86 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.87 - ///\todo named parameter to set this type, function to read and write.
1.88 + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.89 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.90 - ///Instantiates a ReachedMap.
1.91 + ///Instantiates a \ref ReachedMap.
1.92
1.93 ///This function instantiates a \ref ReachedMap.
1.94 - ///\param G is the digraph, to which
1.95 + ///\param g is the digraph, to which
1.96 ///we would like to define the \ref ReachedMap.
1.97 - static ReachedMap *createReachedMap(const GR &G)
1.98 + static ReachedMap *createReachedMap(const Digraph &g)
1.99 {
1.100 - return new ReachedMap(G);
1.101 + return new ReachedMap(g);
1.102 }
1.103 - ///The type of the map that stores the dists of the nodes.
1.104
1.105 - ///The type of the map that stores the dists of the nodes.
1.106 + ///The type of the map that stores the distances of the nodes.
1.107 +
1.108 + ///The type of the map that stores the distances of the nodes.
1.109 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.110 - ///
1.111 typedef typename Digraph::template NodeMap<int> DistMap;
1.112 - ///Instantiates a DistMap.
1.113 + ///Instantiates a \ref DistMap.
1.114
1.115 ///This function instantiates a \ref DistMap.
1.116 - ///\param G is the digraph, to which we would like to define
1.117 - ///the \ref DistMap
1.118 - static DistMap *createDistMap(const GR &G)
1.119 + ///\param g is the digraph, to which we would like to define the
1.120 + ///\ref DistMap.
1.121 + static DistMap *createDistMap(const Digraph &g)
1.122 {
1.123 - return new DistMap(G);
1.124 + return new DistMap(g);
1.125 }
1.126 };
1.127
1.128 @@ -117,9 +116,13 @@
1.129 ///\ingroup search
1.130 ///This class provides an efficient implementation of the %DFS algorithm.
1.131 ///
1.132 - ///\tparam GR The digraph type the algorithm runs on. The default value is
1.133 - ///\ref ListDigraph. The value of GR is not used directly by Dfs, it
1.134 - ///is only passed to \ref DfsDefaultTraits.
1.135 + ///There is also a \ref dfs() "function type interface" for the DFS
1.136 + ///algorithm, which is convenient in the simplier cases and it can be
1.137 + ///used easier.
1.138 + ///
1.139 + ///\tparam GR The type of the digraph the algorithm runs on.
1.140 + ///The default value is \ref ListDigraph. The value of GR is not used
1.141 + ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
1.142 ///\tparam TR Traits class to set various data types used by the algorithm.
1.143 ///The default traits class is
1.144 ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
1.145 @@ -134,12 +137,10 @@
1.146 #endif
1.147 class Dfs {
1.148 public:
1.149 - /**
1.150 - * \brief \ref Exception for uninitialized parameters.
1.151 - *
1.152 - * This error represents problems in the initialization
1.153 - * of the parameters of the algorithms.
1.154 - */
1.155 + ///\ref Exception for uninitialized parameters.
1.156 +
1.157 + ///This error represents problems in the initialization of the
1.158 + ///parameters of the algorithm.
1.159 class UninitializedParameter : public lemon::UninitializedParameter {
1.160 public:
1.161 virtual const char* what() const throw() {
1.162 @@ -147,52 +148,54 @@
1.163 }
1.164 };
1.165
1.166 + ///The type of the digraph the algorithm runs on.
1.167 + typedef typename TR::Digraph Digraph;
1.168 +
1.169 + ///\brief The type of the map that stores the predecessor arcs of the
1.170 + ///DFS paths.
1.171 + typedef typename TR::PredMap PredMap;
1.172 + ///The type of the map that stores the distances of the nodes.
1.173 + typedef typename TR::DistMap DistMap;
1.174 + ///The type of the map that indicates which nodes are reached.
1.175 + typedef typename TR::ReachedMap ReachedMap;
1.176 + ///The type of the map that indicates which nodes are processed.
1.177 + typedef typename TR::ProcessedMap ProcessedMap;
1.178 + ///The type of the paths.
1.179 + typedef PredMapPath<Digraph, PredMap> Path;
1.180 +
1.181 + ///The traits class.
1.182 typedef TR Traits;
1.183 - ///The type of the underlying digraph.
1.184 - typedef typename TR::Digraph Digraph;
1.185 - ///\e
1.186 +
1.187 + private:
1.188 +
1.189 typedef typename Digraph::Node Node;
1.190 - ///\e
1.191 typedef typename Digraph::NodeIt NodeIt;
1.192 - ///\e
1.193 typedef typename Digraph::Arc Arc;
1.194 - ///\e
1.195 typedef typename Digraph::OutArcIt OutArcIt;
1.196
1.197 - ///\brief The type of the map that stores the last
1.198 - ///arcs of the %DFS paths.
1.199 - typedef typename TR::PredMap PredMap;
1.200 - ///The type of the map indicating which nodes are reached.
1.201 - typedef typename TR::ReachedMap ReachedMap;
1.202 - ///The type of the map indicating which nodes are processed.
1.203 - typedef typename TR::ProcessedMap ProcessedMap;
1.204 - ///The type of the map that stores the dists of the nodes.
1.205 - typedef typename TR::DistMap DistMap;
1.206 - private:
1.207 - /// Pointer to the underlying digraph.
1.208 + //Pointer to the underlying digraph.
1.209 const Digraph *G;
1.210 - ///Pointer to the map of predecessors arcs.
1.211 + //Pointer to the map of predecessor arcs.
1.212 PredMap *_pred;
1.213 - ///Indicates if \ref _pred is locally allocated (\c true) or not.
1.214 + //Indicates if _pred is locally allocated (true) or not.
1.215 bool local_pred;
1.216 - ///Pointer to the map of distances.
1.217 + //Pointer to the map of distances.
1.218 DistMap *_dist;
1.219 - ///Indicates if \ref _dist is locally allocated (\c true) or not.
1.220 + //Indicates if _dist is locally allocated (true) or not.
1.221 bool local_dist;
1.222 - ///Pointer to the map of reached status of the nodes.
1.223 + //Pointer to the map of reached status of the nodes.
1.224 ReachedMap *_reached;
1.225 - ///Indicates if \ref _reached is locally allocated (\c true) or not.
1.226 + //Indicates if _reached is locally allocated (true) or not.
1.227 bool local_reached;
1.228 - ///Pointer to the map of processed status of the nodes.
1.229 + //Pointer to the map of processed status of the nodes.
1.230 ProcessedMap *_processed;
1.231 - ///Indicates if \ref _processed is locally allocated (\c true) or not.
1.232 + //Indicates if _processed is locally allocated (true) or not.
1.233 bool local_processed;
1.234
1.235 std::vector<typename Digraph::OutArcIt> _stack;
1.236 int _stack_head;
1.237
1.238 ///Creates the maps if necessary.
1.239 -
1.240 ///\todo Better memory allocation (instead of new).
1.241 void create_maps()
1.242 {
1.243 @@ -229,22 +232,21 @@
1.244 template <class T>
1.245 struct DefPredMapTraits : public Traits {
1.246 typedef T PredMap;
1.247 - static PredMap *createPredMap(const Digraph &G)
1.248 + static PredMap *createPredMap(const Digraph &)
1.249 {
1.250 throw UninitializedParameter();
1.251 }
1.252 };
1.253 ///\brief \ref named-templ-param "Named parameter" for setting
1.254 - ///PredMap type
1.255 + ///\ref PredMap type.
1.256 ///
1.257 - ///\ref named-templ-param "Named parameter" for setting PredMap type
1.258 - ///
1.259 + ///\ref named-templ-param "Named parameter" for setting
1.260 + ///\ref PredMap type.
1.261 template <class T>
1.262 struct DefPredMap : public Dfs<Digraph, DefPredMapTraits<T> > {
1.263 typedef Dfs<Digraph, DefPredMapTraits<T> > Create;
1.264 };
1.265
1.266 -
1.267 template <class T>
1.268 struct DefDistMapTraits : public Traits {
1.269 typedef T DistMap;
1.270 @@ -254,12 +256,12 @@
1.271 }
1.272 };
1.273 ///\brief \ref named-templ-param "Named parameter" for setting
1.274 - ///DistMap type
1.275 + ///\ref DistMap type.
1.276 ///
1.277 - ///\ref named-templ-param "Named parameter" for setting DistMap
1.278 - ///type
1.279 + ///\ref named-templ-param "Named parameter" for setting
1.280 + ///\ref DistMap type.
1.281 template <class T>
1.282 - struct DefDistMap {
1.283 + struct DefDistMap : public Dfs< Digraph, DefDistMapTraits<T> > {
1.284 typedef Dfs<Digraph, DefDistMapTraits<T> > Create;
1.285 };
1.286
1.287 @@ -272,10 +274,10 @@
1.288 }
1.289 };
1.290 ///\brief \ref named-templ-param "Named parameter" for setting
1.291 - ///ReachedMap type
1.292 + ///\ref ReachedMap type.
1.293 ///
1.294 - ///\ref named-templ-param "Named parameter" for setting ReachedMap type
1.295 - ///
1.296 + ///\ref named-templ-param "Named parameter" for setting
1.297 + ///\ref ReachedMap type.
1.298 template <class T>
1.299 struct DefReachedMap : public Dfs< Digraph, DefReachedMapTraits<T> > {
1.300 typedef Dfs< Digraph, DefReachedMapTraits<T> > Create;
1.301 @@ -290,10 +292,10 @@
1.302 }
1.303 };
1.304 ///\brief \ref named-templ-param "Named parameter" for setting
1.305 - ///ProcessedMap type
1.306 + ///\ref ProcessedMap type.
1.307 ///
1.308 - ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
1.309 - ///
1.310 + ///\ref named-templ-param "Named parameter" for setting
1.311 + ///\ref ProcessedMap type.
1.312 template <class T>
1.313 struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > {
1.314 typedef Dfs< Digraph, DefProcessedMapTraits<T> > Create;
1.315 @@ -301,19 +303,19 @@
1.316
1.317 struct DefDigraphProcessedMapTraits : public Traits {
1.318 typedef typename Digraph::template NodeMap<bool> ProcessedMap;
1.319 - static ProcessedMap *createProcessedMap(const Digraph &G)
1.320 + static ProcessedMap *createProcessedMap(const Digraph &g)
1.321 {
1.322 - return new ProcessedMap(G);
1.323 + return new ProcessedMap(g);
1.324 }
1.325 };
1.326 - ///\brief \ref named-templ-param "Named parameter"
1.327 - ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
1.328 + ///\brief \ref named-templ-param "Named parameter" for setting
1.329 + ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.330 ///
1.331 - ///\ref named-templ-param "Named parameter"
1.332 - ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
1.333 - ///If you don't set it explicitely, it will be automatically allocated.
1.334 + ///\ref named-templ-param "Named parameter" for setting
1.335 + ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
1.336 + ///If you don't set it explicitly, it will be automatically allocated.
1.337 template <class T>
1.338 - class DefProcessedMapToBeDefaultMap :
1.339 + struct DefProcessedMapToBeDefaultMap :
1.340 public Dfs< Digraph, DefDigraphProcessedMapTraits> {
1.341 typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create;
1.342 };
1.343 @@ -324,10 +326,10 @@
1.344
1.345 ///Constructor.
1.346
1.347 - ///\param _G the digraph the algorithm will run on.
1.348 - ///
1.349 - Dfs(const Digraph& _G) :
1.350 - G(&_G),
1.351 + ///Constructor.
1.352 + ///\param g The digraph the algorithm runs on.
1.353 + Dfs(const Digraph &g) :
1.354 + G(&g),
1.355 _pred(NULL), local_pred(false),
1.356 _dist(NULL), local_dist(false),
1.357 _reached(NULL), local_reached(false),
1.358 @@ -343,11 +345,11 @@
1.359 if(local_processed) delete _processed;
1.360 }
1.361
1.362 - ///Sets the map storing the predecessor arcs.
1.363 + ///Sets the map that stores the predecessor arcs.
1.364
1.365 - ///Sets the map storing the predecessor arcs.
1.366 + ///Sets the map that stores the predecessor arcs.
1.367 ///If you don't use this function before calling \ref run(),
1.368 - ///it will allocate one. The destuctor deallocates this
1.369 + ///it will allocate one. The destructor deallocates this
1.370 ///automatically allocated map, of course.
1.371 ///\return <tt> (*this) </tt>
1.372 Dfs &predMap(PredMap &m)
1.373 @@ -360,11 +362,46 @@
1.374 return *this;
1.375 }
1.376
1.377 - ///Sets the map storing the distances calculated by the algorithm.
1.378 + ///Sets the map that indicates which nodes are reached.
1.379
1.380 - ///Sets the map storing the distances calculated by the algorithm.
1.381 + ///Sets the map that indicates which nodes are reached.
1.382 ///If you don't use this function before calling \ref run(),
1.383 - ///it will allocate one. The destuctor deallocates this
1.384 + ///it will allocate one. The destructor deallocates this
1.385 + ///automatically allocated map, of course.
1.386 + ///\return <tt> (*this) </tt>
1.387 + Dfs &reachedMap(ReachedMap &m)
1.388 + {
1.389 + if(local_reached) {
1.390 + delete _reached;
1.391 + local_reached=false;
1.392 + }
1.393 + _reached = &m;
1.394 + return *this;
1.395 + }
1.396 +
1.397 + ///Sets the map that indicates which nodes are processed.
1.398 +
1.399 + ///Sets the map that indicates which nodes are processed.
1.400 + ///If you don't use this function before calling \ref run(),
1.401 + ///it will allocate one. The destructor deallocates this
1.402 + ///automatically allocated map, of course.
1.403 + ///\return <tt> (*this) </tt>
1.404 + Dfs &processedMap(ProcessedMap &m)
1.405 + {
1.406 + if(local_processed) {
1.407 + delete _processed;
1.408 + local_processed=false;
1.409 + }
1.410 + _processed = &m;
1.411 + return *this;
1.412 + }
1.413 +
1.414 + ///Sets the map that stores the distances of the nodes.
1.415 +
1.416 + ///Sets the map that stores the distances of the nodes calculated by
1.417 + ///the algorithm.
1.418 + ///If you don't use this function before calling \ref run(),
1.419 + ///it will allocate one. The destructor deallocates this
1.420 ///automatically allocated map, of course.
1.421 ///\return <tt> (*this) </tt>
1.422 Dfs &distMap(DistMap &m)
1.423 @@ -377,50 +414,17 @@
1.424 return *this;
1.425 }
1.426
1.427 - ///Sets the map indicating if a node is reached.
1.428 + public:
1.429
1.430 - ///Sets the map indicating if a node is reached.
1.431 - ///If you don't use this function before calling \ref run(),
1.432 - ///it will allocate one. The destuctor deallocates this
1.433 - ///automatically allocated map, of course.
1.434 - ///\return <tt> (*this) </tt>
1.435 - Dfs &reachedMap(ReachedMap &m)
1.436 - {
1.437 - if(local_reached) {
1.438 - delete _reached;
1.439 - local_reached=false;
1.440 - }
1.441 - _reached = &m;
1.442 - return *this;
1.443 - }
1.444 -
1.445 - ///Sets the map indicating if a node is processed.
1.446 -
1.447 - ///Sets the map indicating if a node is processed.
1.448 - ///If you don't use this function before calling \ref run(),
1.449 - ///it will allocate one. The destuctor deallocates this
1.450 - ///automatically allocated map, of course.
1.451 - ///\return <tt> (*this) </tt>
1.452 - Dfs &processedMap(ProcessedMap &m)
1.453 - {
1.454 - if(local_processed) {
1.455 - delete _processed;
1.456 - local_processed=false;
1.457 - }
1.458 - _processed = &m;
1.459 - return *this;
1.460 - }
1.461 -
1.462 - public:
1.463 ///\name Execution control
1.464 ///The simplest way to execute the algorithm is to use
1.465 - ///one of the member functions called \c run(...).
1.466 + ///one of the member functions called \ref lemon::Dfs::run() "run()".
1.467 ///\n
1.468 - ///If you need more control on the execution,
1.469 - ///first you must call \ref init(), then you can add a source node
1.470 - ///with \ref addSource().
1.471 - ///Finally \ref start() will perform the actual path
1.472 - ///computation.
1.473 + ///If you need more control on the execution, first you must call
1.474 + ///\ref lemon::Dfs::init() "init()", then you can add a source node
1.475 + ///with \ref lemon::Dfs::addSource() "addSource()".
1.476 + ///Finally \ref lemon::Dfs::start() "start()" will perform the
1.477 + ///actual path computation.
1.478
1.479 ///@{
1.480
1.481 @@ -435,7 +439,6 @@
1.482 _stack_head=-1;
1.483 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
1.484 _pred->set(u,INVALID);
1.485 - // _predNode->set(u,INVALID);
1.486 _reached->set(u,false);
1.487 _processed->set(u,false);
1.488 }
1.489 @@ -445,10 +448,14 @@
1.490
1.491 ///Adds a new source node to the set of nodes to be processed.
1.492 ///
1.493 - ///\warning dists are wrong (or at least strange)
1.494 - ///in case of multiple sources.
1.495 + ///\pre The stack must be empty. (Otherwise the algorithm gives
1.496 + ///false results.)
1.497 + ///
1.498 + ///\warning Distances will be wrong (or at least strange) in case of
1.499 + ///multiple sources.
1.500 void addSource(Node s)
1.501 {
1.502 + LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
1.503 if(!(*_reached)[s])
1.504 {
1.505 _reached->set(s,true);
1.506 @@ -471,7 +478,7 @@
1.507 ///
1.508 ///\return The processed arc.
1.509 ///
1.510 - ///\pre The stack must not be empty!
1.511 + ///\pre The stack must not be empty.
1.512 Arc processNextArc()
1.513 {
1.514 Node m;
1.515 @@ -497,61 +504,68 @@
1.516 }
1.517 return e;
1.518 }
1.519 +
1.520 ///Next arc to be processed.
1.521
1.522 ///Next arc to be processed.
1.523 ///
1.524 - ///\return The next arc to be processed or INVALID if the stack is
1.525 - /// empty.
1.526 - OutArcIt nextArc()
1.527 + ///\return The next arc to be processed or \c INVALID if the stack
1.528 + ///is empty.
1.529 + OutArcIt nextArc() const
1.530 {
1.531 return _stack_head>=0?_stack[_stack_head]:INVALID;
1.532 }
1.533
1.534 ///\brief Returns \c false if there are nodes
1.535 - ///to be processed in the queue
1.536 + ///to be processed.
1.537 ///
1.538 ///Returns \c false if there are nodes
1.539 - ///to be processed in the queue
1.540 - bool emptyQueue() { return _stack_head<0; }
1.541 + ///to be processed in the queue (stack).
1.542 + bool emptyQueue() const { return _stack_head<0; }
1.543 +
1.544 ///Returns the number of the nodes to be processed.
1.545
1.546 - ///Returns the number of the nodes to be processed in the queue.
1.547 - int queueSize() { return _stack_head+1; }
1.548 + ///Returns the number of the nodes to be processed in the queue (stack).
1.549 + int queueSize() const { return _stack_head+1; }
1.550
1.551 ///Executes the algorithm.
1.552
1.553 ///Executes the algorithm.
1.554 ///
1.555 - ///\pre init() must be called and at least one node should be added
1.556 - ///with addSource() before using this function.
1.557 + ///This method runs the %DFS algorithm from the root node
1.558 + ///in order to compute the DFS path to each node.
1.559 ///
1.560 - ///This method runs the %DFS algorithm from the root node(s)
1.561 - ///in order to
1.562 - ///compute the
1.563 - ///%DFS path to each node. The algorithm computes
1.564 - ///- The %DFS tree.
1.565 - ///- The distance of each node from the root(s) in the %DFS tree.
1.566 + /// The algorithm computes
1.567 + ///- the %DFS tree,
1.568 + ///- the distance of each node from the root in the %DFS tree.
1.569 ///
1.570 + ///\pre init() must be called and a root node should be
1.571 + ///added with addSource() before using this function.
1.572 + ///
1.573 + ///\note <tt>d.start()</tt> is just a shortcut of the following code.
1.574 + ///\code
1.575 + /// while ( !d.emptyQueue() ) {
1.576 + /// d.processNextArc();
1.577 + /// }
1.578 + ///\endcode
1.579 void start()
1.580 {
1.581 while ( !emptyQueue() ) processNextArc();
1.582 }
1.583
1.584 - ///Executes the algorithm until \c dest is reached.
1.585 + ///Executes the algorithm until the given target node is reached.
1.586
1.587 - ///Executes the algorithm until \c dest is reached.
1.588 + ///Executes the algorithm until the given target node is reached.
1.589 ///
1.590 - ///\pre init() must be called and at least one node should be added
1.591 - ///with addSource() before using this function.
1.592 + ///This method runs the %DFS algorithm from the root node
1.593 + ///in order to compute the DFS path to \c dest.
1.594 ///
1.595 - ///This method runs the %DFS algorithm from the root node(s)
1.596 - ///in order to
1.597 - ///compute the
1.598 - ///%DFS path to \c dest. The algorithm computes
1.599 - ///- The %DFS path to \c dest.
1.600 - ///- The distance of \c dest from the root(s) in the %DFS tree.
1.601 + ///The algorithm computes
1.602 + ///- the %DFS path to \c dest,
1.603 + ///- the distance of \c dest from the root in the %DFS tree.
1.604 ///
1.605 + ///\pre init() must be called and a root node should be
1.606 + ///added with addSource() before using this function.
1.607 void start(Node dest)
1.608 {
1.609 while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
1.610 @@ -562,39 +576,86 @@
1.611
1.612 ///Executes the algorithm until a condition is met.
1.613 ///
1.614 - ///\pre init() must be called and at least one node should be added
1.615 - ///with addSource() before using this function.
1.616 + ///This method runs the %DFS algorithm from the root node
1.617 + ///until an arc \c a with <tt>am[a]</tt> true is found.
1.618 ///
1.619 - ///\param em must be a bool (or convertible) arc map. The algorithm
1.620 - ///will stop when it reaches an arc \c e with <tt>em[e]</tt> true.
1.621 + ///\param am A \c bool (or convertible) arc map. The algorithm
1.622 + ///will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
1.623 ///
1.624 - ///\return The reached arc \c e with <tt>em[e]</tt> true or
1.625 + ///\return The reached arc \c a with <tt>am[a]</tt> true or
1.626 ///\c INVALID if no such arc was found.
1.627 ///
1.628 - ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map,
1.629 + ///\pre init() must be called and a root node should be
1.630 + ///added with addSource() before using this function.
1.631 + ///
1.632 + ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
1.633 ///not a node map.
1.634 - template<class EM>
1.635 - Arc start(const EM &em)
1.636 + template<class ArcBoolMap>
1.637 + Arc start(const ArcBoolMap &am)
1.638 {
1.639 - while ( !emptyQueue() && !em[_stack[_stack_head]] )
1.640 + while ( !emptyQueue() && !am[_stack[_stack_head]] )
1.641 processNextArc();
1.642 return emptyQueue() ? INVALID : _stack[_stack_head];
1.643 }
1.644
1.645 - ///Runs %DFS algorithm to visit all nodes in the digraph.
1.646 + ///Runs the algorithm from the given node.
1.647
1.648 - ///This method runs the %DFS algorithm in order to
1.649 - ///compute the
1.650 - ///%DFS path to each node. The algorithm computes
1.651 - ///- The %DFS tree.
1.652 - ///- The distance of each node from the root in the %DFS tree.
1.653 + ///This method runs the %DFS algorithm from node \c s
1.654 + ///in order to compute the DFS path to each node.
1.655 ///
1.656 - ///\note d.run() is just a shortcut of the following code.
1.657 + ///The algorithm computes
1.658 + ///- the %DFS tree,
1.659 + ///- the distance of each node from the root in the %DFS tree.
1.660 + ///
1.661 + ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
1.662 ///\code
1.663 /// d.init();
1.664 - /// for (NodeIt it(digraph); it != INVALID; ++it) {
1.665 - /// if (!d.reached(it)) {
1.666 - /// d.addSource(it);
1.667 + /// d.addSource(s);
1.668 + /// d.start();
1.669 + ///\endcode
1.670 + void run(Node s) {
1.671 + init();
1.672 + addSource(s);
1.673 + start();
1.674 + }
1.675 +
1.676 + ///Finds the %DFS path between \c s and \c t.
1.677 +
1.678 + ///This method runs the %DFS algorithm from node \c s
1.679 + ///in order to compute the DFS path to \c t.
1.680 + ///
1.681 + ///\return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
1.682 + ///if \c t is reachable form \c s, \c 0 otherwise.
1.683 + ///
1.684 + ///\note Apart from the return value, <tt>d.run(s,t)</tt> is
1.685 + ///just a shortcut of the following code.
1.686 + ///\code
1.687 + /// d.init();
1.688 + /// d.addSource(s);
1.689 + /// d.start(t);
1.690 + ///\endcode
1.691 + int run(Node s,Node t) {
1.692 + init();
1.693 + addSource(s);
1.694 + start(t);
1.695 + return reached(t)?_stack_head+1:0;
1.696 + }
1.697 +
1.698 + ///Runs the algorithm to visit all nodes in the digraph.
1.699 +
1.700 + ///This method runs the %DFS algorithm in order to compute the
1.701 + ///%DFS path to each node.
1.702 + ///
1.703 + ///The algorithm computes
1.704 + ///- the %DFS tree,
1.705 + ///- the distance of each node from the root in the %DFS tree.
1.706 + ///
1.707 + ///\note <tt>d.run()</tt> is just a shortcut of the following code.
1.708 + ///\code
1.709 + /// d.init();
1.710 + /// for (NodeIt n(digraph); n != INVALID; ++n) {
1.711 + /// if (!d.reached(n)) {
1.712 + /// d.addSource(n);
1.713 /// d.start();
1.714 /// }
1.715 /// }
1.716 @@ -609,157 +670,124 @@
1.717 }
1.718 }
1.719
1.720 - ///Runs %DFS algorithm from node \c s.
1.721 -
1.722 - ///This method runs the %DFS algorithm from a root node \c s
1.723 - ///in order to
1.724 - ///compute the
1.725 - ///%DFS path to each node. The algorithm computes
1.726 - ///- The %DFS tree.
1.727 - ///- The distance of each node from the root in the %DFS tree.
1.728 - ///
1.729 - ///\note d.run(s) is just a shortcut of the following code.
1.730 - ///\code
1.731 - /// d.init();
1.732 - /// d.addSource(s);
1.733 - /// d.start();
1.734 - ///\endcode
1.735 - void run(Node s) {
1.736 - init();
1.737 - addSource(s);
1.738 - start();
1.739 - }
1.740 -
1.741 - ///Finds the %DFS path between \c s and \c t.
1.742 -
1.743 - ///Finds the %DFS path between \c s and \c t.
1.744 - ///
1.745 - ///\return The length of the %DFS s---t path if there exists one,
1.746 - ///0 otherwise.
1.747 - ///\note Apart from the return value, d.run(s,t) is
1.748 - ///just a shortcut of the following code.
1.749 - ///\code
1.750 - /// d.init();
1.751 - /// d.addSource(s);
1.752 - /// d.start(t);
1.753 - ///\endcode
1.754 - int run(Node s,Node t) {
1.755 - init();
1.756 - addSource(s);
1.757 - start(t);
1.758 - return reached(t)?_stack_head+1:0;
1.759 - }
1.760 -
1.761 ///@}
1.762
1.763 ///\name Query Functions
1.764 ///The result of the %DFS algorithm can be obtained using these
1.765 ///functions.\n
1.766 - ///Before the use of these functions,
1.767 - ///either run() or start() must be called.
1.768 + ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
1.769 + ///"start()" must be called before using them.
1.770
1.771 ///@{
1.772
1.773 - typedef PredMapPath<Digraph, PredMap> Path;
1.774 + ///The DFS path to a node.
1.775
1.776 - ///Gives back the shortest path.
1.777 + ///Returns the DFS path to a node.
1.778 + ///
1.779 + ///\warning \c t should be reachable from the root.
1.780 + ///
1.781 + ///\pre Either \ref run() or \ref start() must be called before
1.782 + ///using this function.
1.783 + Path path(Node t) const { return Path(*G, *_pred, t); }
1.784
1.785 - ///Gives back the shortest path.
1.786 - ///\pre The \c t should be reachable from the source.
1.787 - Path path(Node t)
1.788 - {
1.789 - return Path(*G, *_pred, t);
1.790 - }
1.791 + ///The distance of a node from the root.
1.792
1.793 - ///The distance of a node from the root(s).
1.794 -
1.795 - ///Returns the distance of a node from the root(s).
1.796 - ///\pre \ref run() must be called before using this function.
1.797 - ///\warning If node \c v is unreachable from the root(s) then the return
1.798 - ///value of this funcion is undefined.
1.799 + ///Returns the distance of a node from the root.
1.800 + ///
1.801 + ///\warning If node \c v is not reachable from the root, then
1.802 + ///the return value of this function is undefined.
1.803 + ///
1.804 + ///\pre Either \ref run() or \ref start() must be called before
1.805 + ///using this function.
1.806 int dist(Node v) const { return (*_dist)[v]; }
1.807
1.808 - ///Returns the 'previous arc' of the %DFS tree.
1.809 + ///Returns the 'previous arc' of the %DFS tree for a node.
1.810
1.811 - ///For a node \c v it returns the 'previous arc'
1.812 - ///of the %DFS path,
1.813 - ///i.e. it returns the last arc of a %DFS path from the root(s) to \c
1.814 - ///v. It is \ref INVALID
1.815 - ///if \c v is unreachable from the root(s) or \c v is a root. The
1.816 - ///%DFS tree used here is equal to the %DFS tree used in
1.817 + ///This function returns the 'previous arc' of the %DFS tree for the
1.818 + ///node \c v, i.e. it returns the last arc of a %DFS path from the
1.819 + ///root to \c v. It is \c INVALID
1.820 + ///if \c v is not reachable from the root(s) or if \c v is a root.
1.821 + ///
1.822 + ///The %DFS tree used here is equal to the %DFS tree used in
1.823 ///\ref predNode().
1.824 + ///
1.825 ///\pre Either \ref run() or \ref start() must be called before using
1.826 ///this function.
1.827 Arc predArc(Node v) const { return (*_pred)[v];}
1.828
1.829 ///Returns the 'previous node' of the %DFS tree.
1.830
1.831 - ///For a node \c v it returns the 'previous node'
1.832 - ///of the %DFS tree,
1.833 - ///i.e. it returns the last but one node from a %DFS path from the
1.834 - ///root(s) to \c v.
1.835 - ///It is INVALID if \c v is unreachable from the root(s) or
1.836 - ///if \c v itself a root.
1.837 - ///The %DFS tree used here is equal to the %DFS
1.838 - ///tree used in \ref predArc().
1.839 + ///This function returns the 'previous node' of the %DFS
1.840 + ///tree for the node \c v, i.e. it returns the last but one node
1.841 + ///from a %DFS path from the root to \c v. It is \c INVALID
1.842 + ///if \c v is not reachable from the root(s) or if \c v is a root.
1.843 + ///
1.844 + ///The %DFS tree used here is equal to the %DFS tree used in
1.845 + ///\ref predArc().
1.846 + ///
1.847 ///\pre Either \ref run() or \ref start() must be called before
1.848 ///using this function.
1.849 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
1.850 G->source((*_pred)[v]); }
1.851
1.852 - ///Returns a reference to the NodeMap of distances.
1.853 -
1.854 - ///Returns a reference to the NodeMap of distances.
1.855 - ///\pre Either \ref run() or \ref init() must
1.856 - ///be called before using this function.
1.857 + ///\brief Returns a const reference to the node map that stores the
1.858 + ///distances of the nodes.
1.859 + ///
1.860 + ///Returns a const reference to the node map that stores the
1.861 + ///distances of the nodes calculated by the algorithm.
1.862 + ///
1.863 + ///\pre Either \ref run() or \ref init()
1.864 + ///must be called before using this function.
1.865 const DistMap &distMap() const { return *_dist;}
1.866
1.867 - ///Returns a reference to the %DFS arc-tree map.
1.868 -
1.869 - ///Returns a reference to the NodeMap of the arcs of the
1.870 - ///%DFS tree.
1.871 + ///\brief Returns a const reference to the node map that stores the
1.872 + ///predecessor arcs.
1.873 + ///
1.874 + ///Returns a const reference to the node map that stores the predecessor
1.875 + ///arcs, which form the DFS tree.
1.876 + ///
1.877 ///\pre Either \ref run() or \ref init()
1.878 ///must be called before using this function.
1.879 const PredMap &predMap() const { return *_pred;}
1.880
1.881 - ///Checks if a node is reachable from the root.
1.882 + ///Checks if a node is reachable from the root(s).
1.883
1.884 ///Returns \c true if \c v is reachable from the root(s).
1.885 - ///\warning The source nodes are inditated as unreachable.
1.886 ///\pre Either \ref run() or \ref start()
1.887 ///must be called before using this function.
1.888 - ///
1.889 - bool reached(Node v) { return (*_reached)[v]; }
1.890 + bool reached(Node v) const { return (*_reached)[v]; }
1.891
1.892 ///@}
1.893 };
1.894
1.895 - ///Default traits class of Dfs function.
1.896 + ///Default traits class of dfs() function.
1.897
1.898 - ///Default traits class of Dfs function.
1.899 + ///Default traits class of dfs() function.
1.900 ///\tparam GR Digraph type.
1.901 template<class GR>
1.902 struct DfsWizardDefaultTraits
1.903 {
1.904 - ///The digraph type the algorithm runs on.
1.905 + ///The type of the digraph the algorithm runs on.
1.906 typedef GR Digraph;
1.907 - ///\brief The type of the map that stores the last
1.908 +
1.909 + ///\brief The type of the map that stores the predecessor
1.910 ///arcs of the %DFS paths.
1.911 ///
1.912 - ///The type of the map that stores the last
1.913 + ///The type of the map that stores the predecessor
1.914 ///arcs of the %DFS paths.
1.915 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.916 ///
1.917 - typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
1.918 - ///Instantiates a PredMap.
1.919 + typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
1.920 + ///Instantiates a \ref PredMap.
1.921
1.922 ///This function instantiates a \ref PredMap.
1.923 - ///\param g is the digraph, to which we would like to define the PredMap.
1.924 + ///\param g is the digraph, to which we would like to define the
1.925 + ///\ref PredMap.
1.926 ///\todo The digraph alone may be insufficient to initialize
1.927 #ifdef DOXYGEN
1.928 - static PredMap *createPredMap(const GR &g)
1.929 + static PredMap *createPredMap(const Digraph &g)
1.930 #else
1.931 - static PredMap *createPredMap(const GR &)
1.932 + static PredMap *createPredMap(const Digraph &)
1.933 #endif
1.934 {
1.935 return new PredMap();
1.936 @@ -769,63 +797,63 @@
1.937
1.938 ///The type of the map that indicates which nodes are processed.
1.939 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.940 - ///\todo named parameter to set this type, function to read and write.
1.941 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.942 - ///Instantiates a ProcessedMap.
1.943 + ///Instantiates a \ref ProcessedMap.
1.944
1.945 ///This function instantiates a \ref ProcessedMap.
1.946 ///\param g is the digraph, to which
1.947 - ///we would like to define the \ref ProcessedMap
1.948 + ///we would like to define the \ref ProcessedMap.
1.949 #ifdef DOXYGEN
1.950 - static ProcessedMap *createProcessedMap(const GR &g)
1.951 + static ProcessedMap *createProcessedMap(const Digraph &g)
1.952 #else
1.953 - static ProcessedMap *createProcessedMap(const GR &)
1.954 + static ProcessedMap *createProcessedMap(const Digraph &)
1.955 #endif
1.956 {
1.957 return new ProcessedMap();
1.958 }
1.959 +
1.960 ///The type of the map that indicates which nodes are reached.
1.961
1.962 ///The type of the map that indicates which nodes are reached.
1.963 - ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.964 - ///\todo named parameter to set this type, function to read and write.
1.965 + ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.966 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.967 - ///Instantiates a ReachedMap.
1.968 + ///Instantiates a \ref ReachedMap.
1.969
1.970 ///This function instantiates a \ref ReachedMap.
1.971 - ///\param G is the digraph, to which
1.972 + ///\param g is the digraph, to which
1.973 ///we would like to define the \ref ReachedMap.
1.974 - static ReachedMap *createReachedMap(const GR &G)
1.975 + static ReachedMap *createReachedMap(const Digraph &g)
1.976 {
1.977 - return new ReachedMap(G);
1.978 + return new ReachedMap(g);
1.979 }
1.980 - ///The type of the map that stores the dists of the nodes.
1.981
1.982 - ///The type of the map that stores the dists of the nodes.
1.983 + ///The type of the map that stores the distances of the nodes.
1.984 +
1.985 + ///The type of the map that stores the distances of the nodes.
1.986 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.987 ///
1.988 typedef NullMap<typename Digraph::Node,int> DistMap;
1.989 - ///Instantiates a DistMap.
1.990 + ///Instantiates a \ref DistMap.
1.991
1.992 ///This function instantiates a \ref DistMap.
1.993 ///\param g is the digraph, to which we would like to define
1.994 ///the \ref DistMap
1.995 #ifdef DOXYGEN
1.996 - static DistMap *createDistMap(const GR &g)
1.997 + static DistMap *createDistMap(const Digraph &g)
1.998 #else
1.999 - static DistMap *createDistMap(const GR &)
1.1000 + static DistMap *createDistMap(const Digraph &)
1.1001 #endif
1.1002 {
1.1003 return new DistMap();
1.1004 }
1.1005 };
1.1006
1.1007 - /// Default traits used by \ref DfsWizard
1.1008 + /// Default traits class used by \ref DfsWizard
1.1009
1.1010 /// To make it easier to use Dfs algorithm
1.1011 - ///we have created a wizard class.
1.1012 + /// we have created a wizard class.
1.1013 /// This \ref DfsWizard class needs default traits,
1.1014 - ///as well as the \ref Dfs class.
1.1015 + /// as well as the \ref Dfs class.
1.1016 /// The \ref DfsWizardBase is a class to be the default traits of the
1.1017 /// \ref DfsWizard class.
1.1018 template<class GR>
1.1019 @@ -834,20 +862,20 @@
1.1020
1.1021 typedef DfsWizardDefaultTraits<GR> Base;
1.1022 protected:
1.1023 - /// Type of the nodes in the digraph.
1.1024 + //The type of the nodes in the digraph.
1.1025 typedef typename Base::Digraph::Node Node;
1.1026
1.1027 - /// Pointer to the underlying digraph.
1.1028 + //Pointer to the digraph the algorithm runs on.
1.1029 void *_g;
1.1030 - ///Pointer to the map of reached nodes.
1.1031 + //Pointer to the map of reached nodes.
1.1032 void *_reached;
1.1033 - ///Pointer to the map of processed nodes.
1.1034 + //Pointer to the map of processed nodes.
1.1035 void *_processed;
1.1036 - ///Pointer to the map of predecessors arcs.
1.1037 + //Pointer to the map of predecessors arcs.
1.1038 void *_pred;
1.1039 - ///Pointer to the map of distances.
1.1040 + //Pointer to the map of distances.
1.1041 void *_dist;
1.1042 - ///Pointer to the source node.
1.1043 + //Pointer to the source node.
1.1044 Node _source;
1.1045
1.1046 public:
1.1047 @@ -856,26 +884,28 @@
1.1048 /// This constructor does not require parameters, therefore it initiates
1.1049 /// all of the attributes to default values (0, INVALID).
1.1050 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
1.1051 - _dist(0), _source(INVALID) {}
1.1052 + _dist(0), _source(INVALID) {}
1.1053
1.1054 /// Constructor.
1.1055
1.1056 /// This constructor requires some parameters,
1.1057 /// listed in the parameters list.
1.1058 /// Others are initiated to 0.
1.1059 - /// \param g is the initial value of \ref _g
1.1060 - /// \param s is the initial value of \ref _source
1.1061 + /// \param g The digraph the algorithm runs on.
1.1062 + /// \param s The source node.
1.1063 DfsWizardBase(const GR &g, Node s=INVALID) :
1.1064 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
1.1065 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
1.1066
1.1067 };
1.1068
1.1069 - /// A class to make the usage of the Dfs algorithm easier
1.1070 + /// Auxiliary class for the function type interface of DFS algorithm.
1.1071
1.1072 - /// This class is created to make it easier to use the Dfs algorithm.
1.1073 - /// It uses the functions and features of the plain \ref Dfs,
1.1074 - /// but it is much simpler to use it.
1.1075 + /// This auxiliary class is created to implement the function type
1.1076 + /// interface of \ref Dfs algorithm. It uses the functions and features
1.1077 + /// of the plain \ref Dfs, but it is much simpler to use it.
1.1078 + /// It should only be used through the \ref dfs() function, which makes
1.1079 + /// it easier to use the algorithm.
1.1080 ///
1.1081 /// Simplicity means that the way to change the types defined
1.1082 /// in the traits class is based on functions that returns the new class
1.1083 @@ -884,41 +914,37 @@
1.1084 /// the new class with the modified type comes from
1.1085 /// the original class by using the ::
1.1086 /// operator. In the case of \ref DfsWizard only
1.1087 - /// a function have to be called and it will
1.1088 + /// a function have to be called, and it will
1.1089 /// return the needed class.
1.1090 ///
1.1091 - /// It does not have own \ref run method. When its \ref run method is called
1.1092 - /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run
1.1093 - /// method of it.
1.1094 + /// It does not have own \ref run() method. When its \ref run() method
1.1095 + /// is called, it initiates a plain \ref Dfs object, and calls the
1.1096 + /// \ref Dfs::run() method of it.
1.1097 template<class TR>
1.1098 class DfsWizard : public TR
1.1099 {
1.1100 typedef TR Base;
1.1101
1.1102 - ///The type of the underlying digraph.
1.1103 + ///The type of the digraph the algorithm runs on.
1.1104 typedef typename TR::Digraph Digraph;
1.1105 - //\e
1.1106 +
1.1107 typedef typename Digraph::Node Node;
1.1108 - //\e
1.1109 typedef typename Digraph::NodeIt NodeIt;
1.1110 - //\e
1.1111 typedef typename Digraph::Arc Arc;
1.1112 - //\e
1.1113 typedef typename Digraph::OutArcIt OutArcIt;
1.1114
1.1115 - ///\brief The type of the map that stores
1.1116 - ///the reached nodes
1.1117 + ///\brief The type of the map that stores the predecessor
1.1118 + ///arcs of the shortest paths.
1.1119 + typedef typename TR::PredMap PredMap;
1.1120 + ///\brief The type of the map that stores the distances of the nodes.
1.1121 + typedef typename TR::DistMap DistMap;
1.1122 + ///\brief The type of the map that indicates which nodes are reached.
1.1123 typedef typename TR::ReachedMap ReachedMap;
1.1124 - ///\brief The type of the map that stores
1.1125 - ///the processed nodes
1.1126 + ///\brief The type of the map that indicates which nodes are processed.
1.1127 typedef typename TR::ProcessedMap ProcessedMap;
1.1128 - ///\brief The type of the map that stores the last
1.1129 - ///arcs of the %DFS paths.
1.1130 - typedef typename TR::PredMap PredMap;
1.1131 - ///The type of the map that stores the distances of the nodes.
1.1132 - typedef typename TR::DistMap DistMap;
1.1133
1.1134 public:
1.1135 +
1.1136 /// Constructor.
1.1137 DfsWizard() : TR() {}
1.1138
1.1139 @@ -934,10 +960,10 @@
1.1140
1.1141 ~DfsWizard() {}
1.1142
1.1143 - ///Runs Dfs algorithm from a given node.
1.1144 + ///Runs DFS algorithm from a source node.
1.1145
1.1146 - ///Runs Dfs algorithm from a given node.
1.1147 - ///The node can be given by the \ref source function.
1.1148 + ///Runs DFS algorithm from a source node.
1.1149 + ///The node can be given with the \ref source() function.
1.1150 void run()
1.1151 {
1.1152 if(Base::_source==INVALID) throw UninitializedParameter();
1.1153 @@ -953,9 +979,9 @@
1.1154 alg.run(Base::_source);
1.1155 }
1.1156
1.1157 - ///Runs Dfs algorithm from the given node.
1.1158 + ///Runs DFS algorithm from the given node.
1.1159
1.1160 - ///Runs Dfs algorithm from the given node.
1.1161 + ///Runs DFS algorithm from the given node.
1.1162 ///\param s is the given source.
1.1163 void run(Node s)
1.1164 {
1.1165 @@ -963,19 +989,27 @@
1.1166 run();
1.1167 }
1.1168
1.1169 + /// Sets the source node, from which the Dfs algorithm runs.
1.1170 +
1.1171 + /// Sets the source node, from which the Dfs algorithm runs.
1.1172 + /// \param s is the source node.
1.1173 + DfsWizard<TR> &source(Node s)
1.1174 + {
1.1175 + Base::_source=s;
1.1176 + return *this;
1.1177 + }
1.1178 +
1.1179 template<class T>
1.1180 struct DefPredMapBase : public Base {
1.1181 typedef T PredMap;
1.1182 static PredMap *createPredMap(const Digraph &) { return 0; };
1.1183 DefPredMapBase(const TR &b) : TR(b) {}
1.1184 };
1.1185 -
1.1186 ///\brief \ref named-templ-param "Named parameter"
1.1187 - ///function for setting PredMap type
1.1188 + ///for setting \ref PredMap object.
1.1189 ///
1.1190 - /// \ref named-templ-param "Named parameter"
1.1191 - ///function for setting PredMap type
1.1192 - ///
1.1193 + ///\ref named-templ-param "Named parameter"
1.1194 + ///for setting \ref PredMap object.
1.1195 template<class T>
1.1196 DfsWizard<DefPredMapBase<T> > predMap(const T &t)
1.1197 {
1.1198 @@ -983,20 +1017,17 @@
1.1199 return DfsWizard<DefPredMapBase<T> >(*this);
1.1200 }
1.1201
1.1202 -
1.1203 template<class T>
1.1204 struct DefReachedMapBase : public Base {
1.1205 typedef T ReachedMap;
1.1206 static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1.1207 DefReachedMapBase(const TR &b) : TR(b) {}
1.1208 };
1.1209 -
1.1210 ///\brief \ref named-templ-param "Named parameter"
1.1211 - ///function for setting ReachedMap
1.1212 + ///for setting \ref ReachedMap object.
1.1213 ///
1.1214 /// \ref named-templ-param "Named parameter"
1.1215 - ///function for setting ReachedMap
1.1216 - ///
1.1217 + ///for setting \ref ReachedMap object.
1.1218 template<class T>
1.1219 DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1.1220 {
1.1221 @@ -1004,20 +1035,17 @@
1.1222 return DfsWizard<DefReachedMapBase<T> >(*this);
1.1223 }
1.1224
1.1225 -
1.1226 template<class T>
1.1227 struct DefProcessedMapBase : public Base {
1.1228 typedef T ProcessedMap;
1.1229 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1.1230 DefProcessedMapBase(const TR &b) : TR(b) {}
1.1231 };
1.1232 -
1.1233 ///\brief \ref named-templ-param "Named parameter"
1.1234 - ///function for setting ProcessedMap
1.1235 + ///for setting \ref ProcessedMap object.
1.1236 ///
1.1237 /// \ref named-templ-param "Named parameter"
1.1238 - ///function for setting ProcessedMap
1.1239 - ///
1.1240 + ///for setting \ref ProcessedMap object.
1.1241 template<class T>
1.1242 DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1.1243 {
1.1244 @@ -1031,13 +1059,11 @@
1.1245 static DistMap *createDistMap(const Digraph &) { return 0; };
1.1246 DefDistMapBase(const TR &b) : TR(b) {}
1.1247 };
1.1248 -
1.1249 ///\brief \ref named-templ-param "Named parameter"
1.1250 - ///function for setting DistMap type
1.1251 + ///for setting \ref DistMap object.
1.1252 ///
1.1253 - /// \ref named-templ-param "Named parameter"
1.1254 - ///function for setting DistMap type
1.1255 - ///
1.1256 + ///\ref named-templ-param "Named parameter"
1.1257 + ///for setting \ref DistMap object.
1.1258 template<class T>
1.1259 DfsWizard<DefDistMapBase<T> > distMap(const T &t)
1.1260 {
1.1261 @@ -1045,16 +1071,6 @@
1.1262 return DfsWizard<DefDistMapBase<T> >(*this);
1.1263 }
1.1264
1.1265 - /// Sets the source node, from which the Dfs algorithm runs.
1.1266 -
1.1267 - /// Sets the source node, from which the Dfs algorithm runs.
1.1268 - /// \param s is the source node.
1.1269 - DfsWizard<TR> &source(Node s)
1.1270 - {
1.1271 - Base::_source=s;
1.1272 - return *this;
1.1273 - }
1.1274 -
1.1275 };
1.1276
1.1277 ///Function type interface for Dfs algorithm.
1.1278 @@ -1082,47 +1098,46 @@
1.1279 }
1.1280
1.1281 #ifdef DOXYGEN
1.1282 - /// \brief Visitor class for dfs.
1.1283 + /// \brief Visitor class for DFS.
1.1284 ///
1.1285 - /// It gives a simple interface for a functional interface for dfs
1.1286 - /// traversal. The traversal on a linear data structure.
1.1287 + /// This class defines the interface of the DfsVisit events, and
1.1288 + /// it could be the base of a real visitor class.
1.1289 template <typename _Digraph>
1.1290 struct DfsVisitor {
1.1291 typedef _Digraph Digraph;
1.1292 typedef typename Digraph::Arc Arc;
1.1293 typedef typename Digraph::Node Node;
1.1294 - /// \brief Called when the arc reach a node.
1.1295 + /// \brief Called for the source node of the DFS.
1.1296 ///
1.1297 - /// It is called when the dfs find an arc which target is not
1.1298 - /// reached yet.
1.1299 + /// This function is called for the source node of the DFS.
1.1300 + void start(const Node& node) {}
1.1301 + /// \brief Called when the source node is leaved.
1.1302 + ///
1.1303 + /// This function is called when the source node is leaved.
1.1304 + void stop(const Node& node) {}
1.1305 + /// \brief Called when a node is reached first time.
1.1306 + ///
1.1307 + /// This function is called when a node is reached first time.
1.1308 + void reach(const Node& node) {}
1.1309 + /// \brief Called when an arc reaches a new node.
1.1310 + ///
1.1311 + /// This function is called when the DFS finds an arc whose target node
1.1312 + /// is not reached yet.
1.1313 void discover(const Arc& arc) {}
1.1314 - /// \brief Called when the node reached first time.
1.1315 - ///
1.1316 - /// It is Called when the node reached first time.
1.1317 - void reach(const Node& node) {}
1.1318 - /// \brief Called when we step back on an arc.
1.1319 - ///
1.1320 - /// It is called when the dfs should step back on the arc.
1.1321 - void backtrack(const Arc& arc) {}
1.1322 - /// \brief Called when we step back from the node.
1.1323 - ///
1.1324 - /// It is called when we step back from the node.
1.1325 - void leave(const Node& node) {}
1.1326 - /// \brief Called when the arc examined but target of the arc
1.1327 + /// \brief Called when an arc is examined but its target node is
1.1328 /// already discovered.
1.1329 ///
1.1330 - /// It called when the arc examined but the target of the arc
1.1331 + /// This function is called when an arc is examined but its target node is
1.1332 /// already discovered.
1.1333 void examine(const Arc& arc) {}
1.1334 - /// \brief Called for the source node of the dfs.
1.1335 + /// \brief Called when the DFS steps back from a node.
1.1336 ///
1.1337 - /// It is called for the source node of the dfs.
1.1338 - void start(const Node& node) {}
1.1339 - /// \brief Called when we leave the source node of the dfs.
1.1340 + /// This function is called when the DFS steps back from a node.
1.1341 + void leave(const Node& node) {}
1.1342 + /// \brief Called when the DFS steps back on an arc.
1.1343 ///
1.1344 - /// It is called when we leave the source node of the dfs.
1.1345 - void stop(const Node& node) {}
1.1346 -
1.1347 + /// This function is called when the DFS steps back on an arc.
1.1348 + void backtrack(const Arc& arc) {}
1.1349 };
1.1350 #else
1.1351 template <typename _Digraph>
1.1352 @@ -1130,26 +1145,26 @@
1.1353 typedef _Digraph Digraph;
1.1354 typedef typename Digraph::Arc Arc;
1.1355 typedef typename Digraph::Node Node;
1.1356 - void discover(const Arc&) {}
1.1357 - void reach(const Node&) {}
1.1358 - void backtrack(const Arc&) {}
1.1359 - void leave(const Node&) {}
1.1360 - void examine(const Arc&) {}
1.1361 void start(const Node&) {}
1.1362 void stop(const Node&) {}
1.1363 + void reach(const Node&) {}
1.1364 + void discover(const Arc&) {}
1.1365 + void examine(const Arc&) {}
1.1366 + void leave(const Node&) {}
1.1367 + void backtrack(const Arc&) {}
1.1368
1.1369 template <typename _Visitor>
1.1370 struct Constraints {
1.1371 void constraints() {
1.1372 Arc arc;
1.1373 Node node;
1.1374 - visitor.discover(arc);
1.1375 - visitor.reach(node);
1.1376 - visitor.backtrack(arc);
1.1377 - visitor.leave(node);
1.1378 - visitor.examine(arc);
1.1379 visitor.start(node);
1.1380 visitor.stop(arc);
1.1381 + visitor.reach(node);
1.1382 + visitor.discover(arc);
1.1383 + visitor.examine(arc);
1.1384 + visitor.leave(node);
1.1385 + visitor.backtrack(arc);
1.1386 }
1.1387 _Visitor& visitor;
1.1388 };
1.1389 @@ -1159,21 +1174,20 @@
1.1390 /// \brief Default traits class of DfsVisit class.
1.1391 ///
1.1392 /// Default traits class of DfsVisit class.
1.1393 - /// \tparam _Digraph Digraph type.
1.1394 + /// \tparam _Digraph The type of the digraph the algorithm runs on.
1.1395 template<class _Digraph>
1.1396 struct DfsVisitDefaultTraits {
1.1397
1.1398 - /// \brief The digraph type the algorithm runs on.
1.1399 + /// \brief The type of the digraph the algorithm runs on.
1.1400 typedef _Digraph Digraph;
1.1401
1.1402 /// \brief The type of the map that indicates which nodes are reached.
1.1403 ///
1.1404 /// The type of the map that indicates which nodes are reached.
1.1405 - /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.1406 - /// \todo named parameter to set this type, function to read and write.
1.1407 + /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1.1408 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.1409
1.1410 - /// \brief Instantiates a ReachedMap.
1.1411 + /// \brief Instantiates a \ref ReachedMap.
1.1412 ///
1.1413 /// This function instantiates a \ref ReachedMap.
1.1414 /// \param digraph is the digraph, to which
1.1415 @@ -1184,31 +1198,30 @@
1.1416
1.1417 };
1.1418
1.1419 - /// %DFS Visit algorithm class.
1.1420 -
1.1421 /// \ingroup search
1.1422 + ///
1.1423 + /// \brief %DFS algorithm class with visitor interface.
1.1424 + ///
1.1425 /// This class provides an efficient implementation of the %DFS algorithm
1.1426 /// with visitor interface.
1.1427 ///
1.1428 /// The %DfsVisit class provides an alternative interface to the Dfs
1.1429 /// class. It works with callback mechanism, the DfsVisit object calls
1.1430 - /// on every dfs event the \c Visitor class member functions.
1.1431 + /// the member functions of the \c Visitor class on every DFS event.
1.1432 ///
1.1433 - /// \tparam _Digraph The digraph type the algorithm runs on.
1.1434 + /// \tparam _Digraph The type of the digraph the algorithm runs on.
1.1435 /// The default value is
1.1436 - /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it
1.1437 - /// is only passed to \ref DfsDefaultTraits.
1.1438 - /// \tparam _Visitor The Visitor object for the algorithm. The
1.1439 - /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitor which
1.1440 - /// does not observe the Dfs events. If you want to observe the dfs
1.1441 - /// events you should implement your own Visitor class.
1.1442 + /// \ref ListDigraph. The value of _Digraph is not used directly by
1.1443 + /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
1.1444 + /// \tparam _Visitor The Visitor type that is used by the algorithm.
1.1445 + /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
1.1446 + /// does not observe the DFS events. If you want to observe the DFS
1.1447 + /// events, you should implement your own visitor class.
1.1448 /// \tparam _Traits Traits class to set various data types used by the
1.1449 /// algorithm. The default traits class is
1.1450 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
1.1451 /// See \ref DfsVisitDefaultTraits for the documentation of
1.1452 - /// a Dfs visit traits class.
1.1453 - ///
1.1454 - /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
1.1455 + /// a DFS visit traits class.
1.1456 #ifdef DOXYGEN
1.1457 template <typename _Digraph, typename _Visitor, typename _Traits>
1.1458 #else
1.1459 @@ -1222,7 +1235,7 @@
1.1460 /// \brief \ref Exception for uninitialized parameters.
1.1461 ///
1.1462 /// This error represents problems in the initialization
1.1463 - /// of the parameters of the algorithms.
1.1464 + /// of the parameters of the algorithm.
1.1465 class UninitializedParameter : public lemon::UninitializedParameter {
1.1466 public:
1.1467 virtual const char* what() const throw()
1.1468 @@ -1231,13 +1244,16 @@
1.1469 }
1.1470 };
1.1471
1.1472 + ///The traits class.
1.1473 typedef _Traits Traits;
1.1474
1.1475 + ///The type of the digraph the algorithm runs on.
1.1476 typedef typename Traits::Digraph Digraph;
1.1477
1.1478 + ///The visitor type used by the algorithm.
1.1479 typedef _Visitor Visitor;
1.1480
1.1481 - ///The type of the map indicating which nodes are reached.
1.1482 + ///The type of the map that indicates which nodes are reached.
1.1483 typedef typename Traits::ReachedMap ReachedMap;
1.1484
1.1485 private:
1.1486 @@ -1247,21 +1263,20 @@
1.1487 typedef typename Digraph::Arc Arc;
1.1488 typedef typename Digraph::OutArcIt OutArcIt;
1.1489
1.1490 - /// Pointer to the underlying digraph.
1.1491 + //Pointer to the underlying digraph.
1.1492 const Digraph *_digraph;
1.1493 - /// Pointer to the visitor object.
1.1494 + //Pointer to the visitor object.
1.1495 Visitor *_visitor;
1.1496 - ///Pointer to the map of reached status of the nodes.
1.1497 + //Pointer to the map of reached status of the nodes.
1.1498 ReachedMap *_reached;
1.1499 - ///Indicates if \ref _reached is locally allocated (\c true) or not.
1.1500 + //Indicates if _reached is locally allocated (true) or not.
1.1501 bool local_reached;
1.1502
1.1503 std::vector<typename Digraph::Arc> _stack;
1.1504 int _stack_head;
1.1505
1.1506 - /// \brief Creates the maps if necessary.
1.1507 - ///
1.1508 - /// Creates the maps if necessary.
1.1509 + ///Creates the maps if necessary.
1.1510 + ///\todo Better memory allocation (instead of new).
1.1511 void create_maps() {
1.1512 if(!_reached) {
1.1513 local_reached = true;
1.1514 @@ -1288,9 +1303,9 @@
1.1515 }
1.1516 };
1.1517 /// \brief \ref named-templ-param "Named parameter" for setting
1.1518 - /// ReachedMap type
1.1519 + /// ReachedMap type.
1.1520 ///
1.1521 - /// \ref named-templ-param "Named parameter" for setting ReachedMap type
1.1522 + /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
1.1523 template <class T>
1.1524 struct DefReachedMap : public DfsVisit< Digraph, Visitor,
1.1525 DefReachedMapTraits<T> > {
1.1526 @@ -1304,25 +1319,22 @@
1.1527 ///
1.1528 /// Constructor.
1.1529 ///
1.1530 - /// \param digraph the digraph the algorithm will run on.
1.1531 - /// \param visitor The visitor of the algorithm.
1.1532 - ///
1.1533 + /// \param digraph The digraph the algorithm runs on.
1.1534 + /// \param visitor The visitor object of the algorithm.
1.1535 DfsVisit(const Digraph& digraph, Visitor& visitor)
1.1536 : _digraph(&digraph), _visitor(&visitor),
1.1537 _reached(0), local_reached(false) {}
1.1538
1.1539 /// \brief Destructor.
1.1540 - ///
1.1541 - /// Destructor.
1.1542 ~DfsVisit() {
1.1543 if(local_reached) delete _reached;
1.1544 }
1.1545
1.1546 - /// \brief Sets the map indicating if a node is reached.
1.1547 + /// \brief Sets the map that indicates which nodes are reached.
1.1548 ///
1.1549 - /// Sets the map indicating if a node is reached.
1.1550 + /// Sets the map that indicates which nodes are reached.
1.1551 /// If you don't use this function before calling \ref run(),
1.1552 - /// it will allocate one. The destuctor deallocates this
1.1553 + /// it will allocate one. The destructor deallocates this
1.1554 /// automatically allocated map, of course.
1.1555 /// \return <tt> (*this) </tt>
1.1556 DfsVisit &reachedMap(ReachedMap &m) {
1.1557 @@ -1335,21 +1347,23 @@
1.1558 }
1.1559
1.1560 public:
1.1561 +
1.1562 /// \name Execution control
1.1563 /// The simplest way to execute the algorithm is to use
1.1564 - /// one of the member functions called \c run(...).
1.1565 + /// one of the member functions called \ref lemon::DfsVisit::run()
1.1566 + /// "run()".
1.1567 /// \n
1.1568 - /// If you need more control on the execution,
1.1569 - /// first you must call \ref init(), then you can adda source node
1.1570 - /// with \ref addSource().
1.1571 - /// Finally \ref start() will perform the actual path
1.1572 - /// computation.
1.1573 + /// If you need more control on the execution, first you must call
1.1574 + /// \ref lemon::DfsVisit::init() "init()", then you can add several
1.1575 + /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
1.1576 + /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
1.1577 + /// actual path computation.
1.1578
1.1579 /// @{
1.1580 +
1.1581 /// \brief Initializes the internal data structures.
1.1582 ///
1.1583 /// Initializes the internal data structures.
1.1584 - ///
1.1585 void init() {
1.1586 create_maps();
1.1587 _stack.resize(countNodes(*_digraph));
1.1588 @@ -1359,10 +1373,18 @@
1.1589 }
1.1590 }
1.1591
1.1592 - /// \brief Adds a new source node.
1.1593 + ///Adds a new source node.
1.1594 +
1.1595 + ///Adds a new source node to the set of nodes to be processed.
1.1596 ///
1.1597 - /// Adds a new source node to the set of nodes to be processed.
1.1598 - void addSource(Node s) {
1.1599 + ///\pre The stack must be empty. (Otherwise the algorithm gives
1.1600 + ///false results.)
1.1601 + ///
1.1602 + ///\warning Distances will be wrong (or at least strange) in case of
1.1603 + ///multiple sources.
1.1604 + void addSource(Node s)
1.1605 + {
1.1606 + LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
1.1607 if(!(*_reached)[s]) {
1.1608 _reached->set(s,true);
1.1609 _visitor->start(s);
1.1610 @@ -1383,7 +1405,7 @@
1.1611 ///
1.1612 /// \return The processed arc.
1.1613 ///
1.1614 - /// \pre The stack must not be empty!
1.1615 + /// \pre The stack must not be empty.
1.1616 Arc processNextArc() {
1.1617 Arc e = _stack[_stack_head];
1.1618 Node m = _digraph->target(e);
1.1619 @@ -1417,37 +1439,58 @@
1.1620 ///
1.1621 /// \return The next arc to be processed or INVALID if the stack is
1.1622 /// empty.
1.1623 - Arc nextArc() {
1.1624 + Arc nextArc() const {
1.1625 return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
1.1626 }
1.1627
1.1628 /// \brief Returns \c false if there are nodes
1.1629 - /// to be processed in the queue
1.1630 + /// to be processed.
1.1631 ///
1.1632 /// Returns \c false if there are nodes
1.1633 - /// to be processed in the queue
1.1634 - bool emptyQueue() { return _stack_head < 0; }
1.1635 + /// to be processed in the queue (stack).
1.1636 + bool emptyQueue() const { return _stack_head < 0; }
1.1637
1.1638 /// \brief Returns the number of the nodes to be processed.
1.1639 ///
1.1640 - /// Returns the number of the nodes to be processed in the queue.
1.1641 - int queueSize() { return _stack_head + 1; }
1.1642 + /// Returns the number of the nodes to be processed in the queue (stack).
1.1643 + int queueSize() const { return _stack_head + 1; }
1.1644
1.1645 /// \brief Executes the algorithm.
1.1646 ///
1.1647 /// Executes the algorithm.
1.1648 ///
1.1649 - /// \pre init() must be called and at least one node should be added
1.1650 - /// with addSource() before using this function.
1.1651 + /// This method runs the %DFS algorithm from the root node
1.1652 + /// in order to compute the %DFS path to each node.
1.1653 + ///
1.1654 + /// The algorithm computes
1.1655 + /// - the %DFS tree,
1.1656 + /// - the distance of each node from the root in the %DFS tree.
1.1657 + ///
1.1658 + /// \pre init() must be called and a root node should be
1.1659 + /// added with addSource() before using this function.
1.1660 + ///
1.1661 + /// \note <tt>d.start()</tt> is just a shortcut of the following code.
1.1662 + /// \code
1.1663 + /// while ( !d.emptyQueue() ) {
1.1664 + /// d.processNextArc();
1.1665 + /// }
1.1666 + /// \endcode
1.1667 void start() {
1.1668 while ( !emptyQueue() ) processNextArc();
1.1669 }
1.1670
1.1671 - /// \brief Executes the algorithm until \c dest is reached.
1.1672 + /// \brief Executes the algorithm until the given target node is reached.
1.1673 ///
1.1674 - /// Executes the algorithm until \c dest is reached.
1.1675 + /// Executes the algorithm until the given target node is reached.
1.1676 ///
1.1677 - /// \pre init() must be called and at least one node should be added
1.1678 + /// This method runs the %DFS algorithm from the root node
1.1679 + /// in order to compute the DFS path to \c dest.
1.1680 + ///
1.1681 + /// The algorithm computes
1.1682 + /// - the %DFS path to \c dest,
1.1683 + /// - the distance of \c dest from the root in the %DFS tree.
1.1684 + ///
1.1685 + /// \pre init() must be called and a root node should be added
1.1686 /// with addSource() before using this function.
1.1687 void start(Node dest) {
1.1688 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest )
1.1689 @@ -1458,28 +1501,37 @@
1.1690 ///
1.1691 /// Executes the algorithm until a condition is met.
1.1692 ///
1.1693 - /// \pre init() must be called and at least one node should be added
1.1694 + /// This method runs the %DFS algorithm from the root node
1.1695 + /// until an arc \c a with <tt>am[a]</tt> true is found.
1.1696 + ///
1.1697 + /// \param am A \c bool (or convertible) arc map. The algorithm
1.1698 + /// will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
1.1699 + ///
1.1700 + /// \return The reached arc \c a with <tt>am[a]</tt> true or
1.1701 + /// \c INVALID if no such arc was found.
1.1702 + ///
1.1703 + /// \pre init() must be called and a root node should be added
1.1704 /// with addSource() before using this function.
1.1705 ///
1.1706 - /// \param em must be a bool (or convertible) arc map. The algorithm
1.1707 - /// will stop when it reaches an arc \c e with <tt>em[e]</tt> true.
1.1708 - ///
1.1709 - ///\return The reached arc \c e with <tt>em[e]</tt> true or
1.1710 - ///\c INVALID if no such arc was found.
1.1711 - ///
1.1712 - /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map,
1.1713 + /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
1.1714 /// not a node map.
1.1715 - template <typename EM>
1.1716 - Arc start(const EM &em) {
1.1717 - while ( !emptyQueue() && !em[_stack[_stack_head]] )
1.1718 + template <typename AM>
1.1719 + Arc start(const AM &am) {
1.1720 + while ( !emptyQueue() && !am[_stack[_stack_head]] )
1.1721 processNextArc();
1.1722 return emptyQueue() ? INVALID : _stack[_stack_head];
1.1723 }
1.1724
1.1725 - /// \brief Runs %DFSVisit algorithm from node \c s.
1.1726 + /// \brief Runs the algorithm from the given node.
1.1727 ///
1.1728 - /// This method runs the %DFS algorithm from a root node \c s.
1.1729 - /// \note d.run(s) is just a shortcut of the following code.
1.1730 + /// This method runs the %DFS algorithm from node \c s.
1.1731 + /// in order to compute the DFS path to each node.
1.1732 + ///
1.1733 + /// The algorithm computes
1.1734 + /// - the %DFS tree,
1.1735 + /// - the distance of each node from the root in the %DFS tree.
1.1736 + ///
1.1737 + /// \note <tt>d.run(s)</tt> is just a shortcut of the following code.
1.1738 ///\code
1.1739 /// d.init();
1.1740 /// d.addSource(s);
1.1741 @@ -1491,22 +1543,46 @@
1.1742 start();
1.1743 }
1.1744
1.1745 - /// \brief Runs %DFSVisit algorithm to visit all nodes in the digraph.
1.1746 + /// \brief Finds the %DFS path between \c s and \c t.
1.1747 +
1.1748 + /// This method runs the %DFS algorithm from node \c s
1.1749 + /// in order to compute the DFS path to \c t.
1.1750 + ///
1.1751 + /// \return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
1.1752 + /// if \c t is reachable form \c s, \c 0 otherwise.
1.1753 + ///
1.1754 + /// \note Apart from the return value, <tt>d.run(s,t)</tt> is
1.1755 + /// just a shortcut of the following code.
1.1756 + ///\code
1.1757 + /// d.init();
1.1758 + /// d.addSource(s);
1.1759 + /// d.start(t);
1.1760 + ///\endcode
1.1761 + int run(Node s,Node t) {
1.1762 + init();
1.1763 + addSource(s);
1.1764 + start(t);
1.1765 + return reached(t)?_stack_head+1:0;
1.1766 + }
1.1767 +
1.1768 + /// \brief Runs the algorithm to visit all nodes in the digraph.
1.1769
1.1770 /// This method runs the %DFS algorithm in order to
1.1771 - /// compute the %DFS path to each node. The algorithm computes
1.1772 - /// - The %DFS tree.
1.1773 - /// - The distance of each node from the root in the %DFS tree.
1.1774 + /// compute the %DFS path to each node.
1.1775 ///
1.1776 - ///\note d.run() is just a shortcut of the following code.
1.1777 + /// The algorithm computes
1.1778 + /// - the %DFS tree,
1.1779 + /// - the distance of each node from the root in the %DFS tree.
1.1780 + ///
1.1781 + /// \note <tt>d.run()</tt> is just a shortcut of the following code.
1.1782 ///\code
1.1783 - /// d.init();
1.1784 - /// for (NodeIt it(digraph); it != INVALID; ++it) {
1.1785 - /// if (!d.reached(it)) {
1.1786 - /// d.addSource(it);
1.1787 - /// d.start();
1.1788 - /// }
1.1789 - /// }
1.1790 + /// d.init();
1.1791 + /// for (NodeIt n(digraph); n != INVALID; ++n) {
1.1792 + /// if (!d.reached(n)) {
1.1793 + /// d.addSource(n);
1.1794 + /// d.start();
1.1795 + /// }
1.1796 + /// }
1.1797 ///\endcode
1.1798 void run() {
1.1799 init();
1.1800 @@ -1517,27 +1593,28 @@
1.1801 }
1.1802 }
1.1803 }
1.1804 +
1.1805 ///@}
1.1806
1.1807 /// \name Query Functions
1.1808 /// The result of the %DFS algorithm can be obtained using these
1.1809 /// functions.\n
1.1810 - /// Before the use of these functions,
1.1811 - /// either run() or start() must be called.
1.1812 + /// Either \ref lemon::DfsVisit::run() "run()" or
1.1813 + /// \ref lemon::DfsVisit::start() "start()" must be called before
1.1814 + /// using them.
1.1815 ///@{
1.1816 - /// \brief Checks if a node is reachable from the root.
1.1817 +
1.1818 + /// \brief Checks if a node is reachable from the root(s).
1.1819 ///
1.1820 /// Returns \c true if \c v is reachable from the root(s).
1.1821 - /// \warning The source nodes are inditated as unreachable.
1.1822 /// \pre Either \ref run() or \ref start()
1.1823 /// must be called before using this function.
1.1824 - ///
1.1825 bool reached(Node v) { return (*_reached)[v]; }
1.1826 +
1.1827 ///@}
1.1828 +
1.1829 };
1.1830
1.1831 -
1.1832 } //END OF NAMESPACE LEMON
1.1833
1.1834 #endif
1.1835 -