1.1 --- a/lemon/dfs.h Wed Nov 02 12:44:50 2005 +0000
1.2 +++ b/lemon/dfs.h Wed Nov 02 15:22:28 2005 +0000
1.3 @@ -27,9 +27,10 @@
1.4 #include <lemon/error.h>
1.5 #include <lemon/maps.h>
1.6
1.7 +#include <lemon/concept_check.h>
1.8 +
1.9 namespace lemon {
1.10
1.11 -
1.12
1.13 ///Default traits class of Dfs class.
1.14
1.15 @@ -123,8 +124,6 @@
1.16 ///a Dfs traits class.
1.17 ///
1.18 ///\author Jacint Szabo and Alpar Juttner
1.19 - ///\todo A compare object would be nice.
1.20 -
1.21 #ifdef DOXYGEN
1.22 template <typename GR,
1.23 typename TR>
1.24 @@ -275,7 +274,7 @@
1.25 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
1.26 ///
1.27 template <class T>
1.28 - struct DefReachedMap {
1.29 + struct DefReachedMap : public Dfs< Graph, DefReachedMapTraits<T> > {
1.30 typedef Dfs< Graph, DefReachedMapTraits<T> > Create;
1.31 };
1.32
1.33 @@ -326,7 +325,6 @@
1.34 Dfs(const Graph& _G) :
1.35 G(&_G),
1.36 _pred(NULL), local_pred(false),
1.37 -// _predNode(NULL), local_predNode(false),
1.38 _dist(NULL), local_dist(false),
1.39 _reached(NULL), local_reached(false),
1.40 _processed(NULL), local_processed(false)
1.41 @@ -336,7 +334,6 @@
1.42 ~Dfs()
1.43 {
1.44 if(local_pred) delete _pred;
1.45 -// if(local_predNode) delete _predNode;
1.46 if(local_dist) delete _dist;
1.47 if(local_reached) delete _reached;
1.48 if(local_processed) delete _processed;
1.49 @@ -359,23 +356,6 @@
1.50 return *this;
1.51 }
1.52
1.53 -// ///Sets the map storing the predecessor nodes.
1.54 -
1.55 -// ///Sets the map storing the predecessor nodes.
1.56 -// ///If you don't use this function before calling \ref run(),
1.57 -// ///it will allocate one. The destuctor deallocates this
1.58 -// ///automatically allocated map, of course.
1.59 -// ///\return <tt> (*this) </tt>
1.60 -// Dfs &predNodeMap(PredNodeMap &m)
1.61 -// {
1.62 -// if(local_predNode) {
1.63 -// delete _predNode;
1.64 -// local_predNode=false;
1.65 -// }
1.66 -// _predNode = &m;
1.67 -// return *this;
1.68 -// }
1.69 -
1.70 ///Sets the map storing the distances calculated by the algorithm.
1.71
1.72 ///Sets the map storing the distances calculated by the algorithm.
1.73 @@ -468,7 +448,6 @@
1.74 {
1.75 _reached->set(s,true);
1.76 _pred->set(s,INVALID);
1.77 - // _predNode->set(u,INVALID);
1.78 OutEdgeIt e(*G,s);
1.79 if(e!=INVALID) {
1.80 _stack[++_stack_head]=e;
1.81 @@ -495,7 +474,6 @@
1.82 if(!(*_reached)[m=G->target(e)]) {
1.83 _pred->set(m,e);
1.84 _reached->set(m,true);
1.85 - // _pred_node->set(m,G->source(e));
1.86 ++_stack_head;
1.87 _stack[_stack_head] = OutEdgeIt(*G, m);
1.88 _dist->set(m,_stack_head);
1.89 @@ -504,7 +482,6 @@
1.90 m=G->source(e);
1.91 ++_stack[_stack_head];
1.92 }
1.93 - //'m' is now the (original) source of the _stack[_stack_head]
1.94 while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
1.95 _processed->set(m,true);
1.96 --_stack_head;
1.97 @@ -590,14 +567,14 @@
1.98 ///\param nm must be a bool (or convertible) edge map. The algorithm
1.99 ///will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>.
1.100 ///
1.101 - ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c nm is an edge map,
1.102 + ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c em is an edge map,
1.103 ///not a node map.
1.104 - template<class NM>
1.105 - void start(const NM &nm)
1.106 - {
1.107 - while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge();
1.108 - }
1.109 -
1.110 + template<class EM>
1.111 + void start(const EM &em)
1.112 + {
1.113 + while ( !emptyQueue() && !em[_stack[_stack_head]] ) processNextEdge();
1.114 + }
1.115 +
1.116 ///Runs %DFS algorithm from node \c s.
1.117
1.118 ///This method runs the %DFS algorithm from a root node \c s
1.119 @@ -725,13 +702,6 @@
1.120 ///must be called before using this function.
1.121 const PredMap &predMap() const { return *_pred;}
1.122
1.123 -// ///Returns a reference to the map of nodes of %DFS paths.
1.124 -
1.125 -// ///Returns a reference to the NodeMap of the last but one nodes of the
1.126 -// ///%DFS tree.
1.127 -// ///\pre \ref run() must be called before using this function.
1.128 -// const PredNodeMap &predNodeMap() const { return *_predNode;}
1.129 -
1.130 ///Checks if a node is reachable from the root.
1.131
1.132 ///Returns \c true if \c v is reachable from the root(s).
1.133 @@ -774,23 +744,6 @@
1.134 {
1.135 return new PredMap();
1.136 }
1.137 -// ///\brief The type of the map that stores the last but one
1.138 -// ///nodes of the %DFS paths.
1.139 -// ///
1.140 -// ///The type of the map that stores the last but one
1.141 -// ///nodes of the %DFS paths.
1.142 -// ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.143 -// ///
1.144 -// typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
1.145 -// ///Instantiates a PredNodeMap.
1.146 -
1.147 -// ///This function instantiates a \ref PredNodeMap.
1.148 -// ///\param G is the graph, to which
1.149 -// ///we would like to define the \ref PredNodeMap
1.150 -// static PredNodeMap *createPredNodeMap(const GR &G)
1.151 -// {
1.152 -// return new PredNodeMap();
1.153 -// }
1.154
1.155 ///The type of the map that indicates which nodes are processed.
1.156
1.157 @@ -871,8 +824,6 @@
1.158 void *_processed;
1.159 ///Pointer to the map of predecessors edges.
1.160 void *_pred;
1.161 -// ///Pointer to the map of predecessors nodes.
1.162 -// void *_predNode;
1.163 ///Pointer to the map of distances.
1.164 void *_dist;
1.165 ///Pointer to the source node.
1.166 @@ -884,7 +835,6 @@
1.167 /// This constructor does not require parameters, therefore it initiates
1.168 /// all of the attributes to default values (0, INVALID).
1.169 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
1.170 -// _predNode(0),
1.171 _dist(0), _source(INVALID) {}
1.172
1.173 /// Constructor.
1.174 @@ -896,7 +846,6 @@
1.175 /// \param s is the initial value of \ref _source
1.176 DfsWizardBase(const GR &g, Node s=INVALID) :
1.177 _g((void *)&g), _reached(0), _processed(0), _pred(0),
1.178 -// _predNode(0),
1.179 _dist(0), _source(s) {}
1.180
1.181 };
1.182 @@ -945,9 +894,6 @@
1.183 ///\brief The type of the map that stores the last
1.184 ///edges of the %DFS paths.
1.185 typedef typename TR::PredMap PredMap;
1.186 -// ///\brief The type of the map that stores the last but one
1.187 -// ///nodes of the %DFS paths.
1.188 -// typedef typename TR::PredNodeMap PredNodeMap;
1.189 ///The type of the map that stores the distances of the nodes.
1.190 typedef typename TR::DistMap DistMap;
1.191
1.192 @@ -978,7 +924,6 @@
1.193 if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached);
1.194 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
1.195 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
1.196 -// if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
1.197 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
1.198 alg.run(Base::_source);
1.199 }
1.200 @@ -1055,27 +1000,6 @@
1.201 return DfsWizard<DefProcessedMapBase<T> >(*this);
1.202 }
1.203
1.204 -
1.205 -// template<class T>
1.206 -// struct DefPredNodeMapBase : public Base {
1.207 -// typedef T PredNodeMap;
1.208 -// static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
1.209 -// DefPredNodeMapBase(const TR &b) : TR(b) {}
1.210 -// };
1.211 -
1.212 -// ///\brief \ref named-templ-param "Named parameter"
1.213 -// ///function for setting PredNodeMap type
1.214 -// ///
1.215 -// /// \ref named-templ-param "Named parameter"
1.216 -// ///function for setting PredNodeMap type
1.217 -// ///
1.218 -// template<class T>
1.219 -// DfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1.220 -// {
1.221 -// Base::_predNode=(void *)&t;
1.222 -// return DfsWizard<DefPredNodeMapBase<T> >(*this);
1.223 -// }
1.224 -
1.225 template<class T>
1.226 struct DefDistMapBase : public Base {
1.227 typedef T DistMap;
1.228 @@ -1132,6 +1056,414 @@
1.229 return DfsWizard<DfsWizardBase<GR> >(g,s);
1.230 }
1.231
1.232 + /// \brief Visitor class for dfs.
1.233 + ///
1.234 + /// It gives a simple interface for a functional interface for dfs
1.235 + /// traversal. The traversal on a linear data structure.
1.236 + template <typename _Graph>
1.237 + struct DfsVisitor {
1.238 + typedef _Graph Graph;
1.239 + typedef typename Graph::Edge Edge;
1.240 + typedef typename Graph::Node Node;
1.241 + /// \brief Called when the edge reach a node.
1.242 + ///
1.243 + /// It is called when the dfs find an edge which target is not
1.244 + /// reached yet.
1.245 + void discover(const Edge& edge) {}
1.246 + /// \brief Called when the node reached first time.
1.247 + ///
1.248 + /// It is Called when the node reached first time.
1.249 + void reach(const Node& node) {}
1.250 + /// \brief Called when we step back on an edge.
1.251 + ///
1.252 + /// It is called when the dfs should step back on the edge.
1.253 + void backtrack(const Edge& edge) {}
1.254 + /// \brief Called when we step back from the node.
1.255 + ///
1.256 + /// It is called when we step back from the node.
1.257 + void leave(const Node& node) {}
1.258 + /// \brief Called when the edge examined but target of the edge
1.259 + /// already discovered.
1.260 + ///
1.261 + /// It called when the edge examined but the target of the edge
1.262 + /// already discovered.
1.263 + void examine(const Edge& edge) {}
1.264 + /// \brief Called for the source node of the dfs.
1.265 + ///
1.266 + /// It is called for the source node of the dfs.
1.267 + void start(const Node&) {}
1.268 + /// \brief Called when we leave the source node of the dfs.
1.269 + ///
1.270 + /// It is called when we leave the source node of the dfs.
1.271 + void stop(const Node&) {}
1.272 +
1.273 + template <typename _Visitor>
1.274 + struct Constraints {
1.275 + void constraints() {
1.276 + Edge edge;
1.277 + Node node;
1.278 + visitor.discover(edge);
1.279 + visitor.reach(node);
1.280 + visitor.backtrack(edge);
1.281 + visitor.leave(node);
1.282 + visitor.examine(edge);
1.283 + visitor.start(node);
1.284 + visitor.stop(edge);
1.285 + }
1.286 + _Visitor& visitor;
1.287 + };
1.288 + };
1.289 +
1.290 + /// \brief Default traits class of DfsVisit class.
1.291 + ///
1.292 + /// Default traits class of DfsVisit class.
1.293 + /// \param _Graph Graph type.
1.294 + template<class _Graph>
1.295 + struct DfsVisitDefaultTraits {
1.296 +
1.297 + /// \brief The graph type the algorithm runs on.
1.298 + typedef _Graph Graph;
1.299 +
1.300 + /// \brief The type of the map that indicates which nodes are reached.
1.301 + ///
1.302 + /// The type of the map that indicates which nodes are reached.
1.303 + /// It must meet the \ref concept::WriteMap "WriteMap" concept.
1.304 + /// \todo named parameter to set this type, function to read and write.
1.305 + typedef typename Graph::template NodeMap<bool> ReachedMap;
1.306 +
1.307 + /// \brief Instantiates a ReachedMap.
1.308 + ///
1.309 + /// This function instantiates a \ref ReachedMap.
1.310 + /// \param G is the graph, to which
1.311 + /// we would like to define the \ref ReachedMap.
1.312 + static ReachedMap *createReachedMap(const Graph &graph) {
1.313 + return new ReachedMap(graph);
1.314 + }
1.315 +
1.316 + };
1.317 +
1.318 + /// %DFS Visit algorithm class.
1.319 +
1.320 + /// \ingroup flowalgs
1.321 + /// This class provides an efficient implementation of the %DFS algorithm
1.322 + /// with visitor interface.
1.323 + ///
1.324 + /// The %DfsVisit class provides an alternative interface to the Dfs
1.325 + /// class. It works with callback mechanism, the DfsVisit object calls
1.326 + /// on every dfs event the \c Visitor class member functions.
1.327 + ///
1.328 + /// \param _Graph The graph type the algorithm runs on. The default value is
1.329 + /// \ref ListGraph. The value of _Graph is not used directly by Dfs, it
1.330 + /// is only passed to \ref DfsDefaultTraits.
1.331 + /// \param _Visitor The Visitor object for the algorithm. The
1.332 + /// \ref DfsVisitor "DfsVisitor<_Graph>" is an empty Visitor which
1.333 + /// does not observe the Dfs events. If you want to observe the dfs
1.334 + /// events you should implement your own Visitor class.
1.335 + /// \param _Traits Traits class to set various data types used by the
1.336 + /// algorithm. The default traits class is
1.337 + /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Graph>".
1.338 + /// See \ref DfsVisitDefaultTraits for the documentation of
1.339 + /// a Dfs visit traits class.
1.340 + ///
1.341 + /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
1.342 +#ifdef DOXYGEN
1.343 + template <typename _Graph, typename _Visitor, typename _Traits>
1.344 +#else
1.345 + template <typename _Graph = ListGraph,
1.346 + typename _Visitor = DfsVisitor<_Graph>,
1.347 + typename _Traits = DfsDefaultTraits<_Graph> >
1.348 +#endif
1.349 + class DfsVisit {
1.350 + public:
1.351 +
1.352 + /// \brief \ref Exception for uninitialized parameters.
1.353 + ///
1.354 + /// This error represents problems in the initialization
1.355 + /// of the parameters of the algorithms.
1.356 + class UninitializedParameter : public lemon::UninitializedParameter {
1.357 + public:
1.358 + virtual const char* exceptionName() const {
1.359 + return "lemon::DfsVisit::UninitializedParameter";
1.360 + }
1.361 + };
1.362 +
1.363 + typedef _Traits Traits;
1.364 +
1.365 + typedef typename Traits::Graph Graph;
1.366 +
1.367 + typedef _Visitor Visitor;
1.368 +
1.369 + ///The type of the map indicating which nodes are reached.
1.370 + typedef typename Traits::ReachedMap ReachedMap;
1.371 +
1.372 + private:
1.373 +
1.374 + typedef typename Graph::Node Node;
1.375 + typedef typename Graph::NodeIt NodeIt;
1.376 + typedef typename Graph::Edge Edge;
1.377 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.378 +
1.379 + /// Pointer to the underlying graph.
1.380 + const Graph *_graph;
1.381 + /// Pointer to the visitor object.
1.382 + Visitor *_visitor;
1.383 + ///Pointer to the map of reached status of the nodes.
1.384 + ReachedMap *_reached;
1.385 + ///Indicates if \ref _reached is locally allocated (\c true) or not.
1.386 + bool local_reached;
1.387 +
1.388 + std::vector<typename Graph::Edge> _stack;
1.389 + int _stack_head;
1.390 +
1.391 + /// \brief Creates the maps if necessary.
1.392 + ///
1.393 + /// Creates the maps if necessary.
1.394 + void create_maps() {
1.395 + if(!_reached) {
1.396 + local_reached = true;
1.397 + _reached = Traits::createReachedMap(*_graph);
1.398 + }
1.399 + }
1.400 +
1.401 + protected:
1.402 +
1.403 + DfsVisit() {}
1.404 +
1.405 + public:
1.406 +
1.407 + typedef DfsVisit Create;
1.408 +
1.409 + /// \name Named template parameters
1.410 +
1.411 + ///@{
1.412 + template <class T>
1.413 + struct DefReachedMapTraits : public Traits {
1.414 + typedef T ReachedMap;
1.415 + static ReachedMap *createReachedMap(const Graph &graph) {
1.416 + throw UninitializedParameter();
1.417 + }
1.418 + };
1.419 + /// \brief \ref named-templ-param "Named parameter" for setting
1.420 + /// ReachedMap type
1.421 + ///
1.422 + /// \ref named-templ-param "Named parameter" for setting ReachedMap type
1.423 + template <class T>
1.424 + struct DefReachedMap : public Dfs< Graph, DefReachedMapTraits<T> > {
1.425 + typedef Dfs< Graph, DefReachedMapTraits<T> > Create;
1.426 + };
1.427 + ///@}
1.428 +
1.429 + public:
1.430 +
1.431 + /// \brief Constructor.
1.432 + ///
1.433 + /// Constructor.
1.434 + ///
1.435 + /// \param graph the graph the algorithm will run on.
1.436 + /// \param visitor The visitor of the algorithm.
1.437 + ///
1.438 + DfsVisit(const Graph& graph, Visitor& visitor)
1.439 + : _graph(&graph), _visitor(&visitor),
1.440 + _reached(0), local_reached(false) {}
1.441 +
1.442 + /// \brief Destructor.
1.443 + ///
1.444 + /// Destructor.
1.445 + ~DfsVisit() {
1.446 + if(local_reached) delete _reached;
1.447 + }
1.448 +
1.449 + /// \brief Sets the map indicating if a node is reached.
1.450 + ///
1.451 + /// Sets the map indicating if a node is reached.
1.452 + /// If you don't use this function before calling \ref run(),
1.453 + /// it will allocate one. The destuctor deallocates this
1.454 + /// automatically allocated map, of course.
1.455 + /// \return <tt> (*this) </tt>
1.456 + DfsVisit &reachedMap(ReachedMap &m) {
1.457 + if(local_reached) {
1.458 + delete _reached;
1.459 + local_reached=false;
1.460 + }
1.461 + _reached = &m;
1.462 + return *this;
1.463 + }
1.464 +
1.465 + public:
1.466 + /// \name Execution control
1.467 + /// The simplest way to execute the algorithm is to use
1.468 + /// one of the member functions called \c run(...).
1.469 + /// \n
1.470 + /// If you need more control on the execution,
1.471 + /// first you must call \ref init(), then you can add several source nodes
1.472 + /// with \ref addSource().
1.473 + /// Finally \ref start() will perform the actual path
1.474 + /// computation.
1.475 +
1.476 + /// @{
1.477 + /// \brief Initializes the internal data structures.
1.478 + ///
1.479 + /// Initializes the internal data structures.
1.480 + ///
1.481 + void init() {
1.482 + create_maps();
1.483 + _stack.resize(countNodes(*_graph));
1.484 + _stack_head = -1;
1.485 + for (NodeIt u(*_graph) ; u != INVALID ; ++u) {
1.486 + _reached->set(u, false);
1.487 + }
1.488 + }
1.489 +
1.490 + /// \brief Adds a new source node.
1.491 + ///
1.492 + /// Adds a new source node to the set of nodes to be processed.
1.493 + void addSource(Node s) {
1.494 + if(!(*_reached)[s]) {
1.495 + _reached->set(s,true);
1.496 + _visitor->start(s);
1.497 + _visitor->reach(s);
1.498 + Edge e;
1.499 + _graph->firstOut(e, s);
1.500 + if (e != INVALID) {
1.501 + _stack[++_stack_head] = e;
1.502 + } else {
1.503 + _visitor->leave(s);
1.504 + }
1.505 + }
1.506 + }
1.507 +
1.508 + /// \brief Processes the next edge.
1.509 + ///
1.510 + /// Processes the next edge.
1.511 + ///
1.512 + /// \return The processed edge.
1.513 + ///
1.514 + /// \pre The stack must not be empty!
1.515 + Edge processNextEdge() {
1.516 + Edge e = _stack[_stack_head];
1.517 + Node m = _graph->target(e);
1.518 + if(!(*_reached)[m]) {
1.519 + _visitor->discover(e);
1.520 + _visitor->reach(m);
1.521 + _reached->set(m, true);
1.522 + _graph->firstOut(_stack[++_stack_head], m);
1.523 + } else {
1.524 + _visitor->examine(e);
1.525 + m = _graph->source(e);
1.526 + _graph->nextOut(_stack[_stack_head]);
1.527 + }
1.528 + while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
1.529 + _visitor->leave(m);
1.530 + --_stack_head;
1.531 + if (_stack_head >= 0) {
1.532 + _visitor->backtrack(_stack[_stack_head]);
1.533 + m = _graph->source(_stack[_stack_head]);
1.534 + _graph->nextOut(_stack[_stack_head]);
1.535 + } else {
1.536 + _visitor->stop(m);
1.537 + }
1.538 + }
1.539 + return e;
1.540 + }
1.541 +
1.542 + /// \brief Next edge to be processed.
1.543 + ///
1.544 + /// Next edge to be processed.
1.545 + ///
1.546 + /// \return The next edge to be processed or INVALID if the stack is
1.547 + /// empty.
1.548 + Edge nextEdge() {
1.549 + return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
1.550 + }
1.551 +
1.552 + /// \brief Returns \c false if there are nodes
1.553 + /// to be processed in the queue
1.554 + ///
1.555 + /// Returns \c false if there are nodes
1.556 + /// to be processed in the queue
1.557 + ///
1.558 + /// \todo This should be called emptyStack() or some "neutral" name.
1.559 + bool emptyQueue() { return _stack_head < 0; }
1.560 +
1.561 + /// \brief Returns the number of the nodes to be processed.
1.562 + ///
1.563 + /// Returns the number of the nodes to be processed in the queue.
1.564 + ///
1.565 + ///\todo This should be called stackSize() or some "neutral" name.
1.566 + int queueSize() { return _stack_head + 1; }
1.567 +
1.568 + /// \brief Executes the algorithm.
1.569 + ///
1.570 + /// Executes the algorithm.
1.571 + ///
1.572 + /// \pre init() must be called and at least one node should be added
1.573 + /// with addSource() before using this function.
1.574 + void start() {
1.575 + while ( !emptyQueue() ) processNextEdge();
1.576 + }
1.577 +
1.578 + /// \brief Executes the algorithm until \c dest is reached.
1.579 + ///
1.580 + /// Executes the algorithm until \c dest is reached.
1.581 + ///
1.582 + /// \pre init() must be called and at least one node should be added
1.583 + /// with addSource() before using this function.
1.584 + void start(Node dest) {
1.585 + while ( !emptyQueue() && _graph->target(_stack[_stack_head]) != dest)
1.586 + processNextEdge();
1.587 + }
1.588 +
1.589 + /// \brief Executes the algorithm until a condition is met.
1.590 + ///
1.591 + /// Executes the algorithm until a condition is met.
1.592 + ///
1.593 + /// \pre init() must be called and at least one node should be added
1.594 + /// with addSource() before using this function.
1.595 + ///
1.596 + /// \param nm must be a bool (or convertible) edge map. The algorithm
1.597 + /// will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>.
1.598 + ///
1.599 + /// \warning Contrary to \ref Dfs and \ref Dijkstra, \c em is an edge map,
1.600 + /// not a node map.
1.601 + template <typename EM>
1.602 + void start(const EM &em) {
1.603 + while (!emptyQueue() && !em[_stack[_stack_head]]) processNextEdge();
1.604 + }
1.605 +
1.606 + /// \brief Runs %DFS algorithm from node \c s.
1.607 + ///
1.608 + /// This method runs the %DFS algorithm from a root node \c s.
1.609 + /// \note d.run(s) is just a shortcut of the following code.
1.610 + /// \code
1.611 + /// d.init();
1.612 + /// d.addSource(s);
1.613 + /// d.start();
1.614 + /// \endcode
1.615 + void run(Node s) {
1.616 + init();
1.617 + addSource(s);
1.618 + start();
1.619 + }
1.620 + ///@}
1.621 +
1.622 + /// \name Query Functions
1.623 + /// The result of the %DFS algorithm can be obtained using these
1.624 + /// functions.\n
1.625 + /// Before the use of these functions,
1.626 + /// either run() or start() must be called.
1.627 + ///@{
1.628 + /// \brief Checks if a node is reachable from the root.
1.629 + ///
1.630 + /// Returns \c true if \c v is reachable from the root(s).
1.631 + /// \warning The source nodes are inditated as unreachable.
1.632 + /// \pre Either \ref run() or \ref start()
1.633 + /// must be called before using this function.
1.634 + ///
1.635 + bool reached(Node v) { return (*_reached)[v]; }
1.636 + ///@}
1.637 + };
1.638 +
1.639 +
1.640 } //END OF NAMESPACE LEMON
1.641
1.642 #endif