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