lemon/dfs.h
author deba
Thu, 10 Nov 2005 12:40:58 +0000
changeset 1785 606178a14011
parent 1765 f15b3c09481c
child 1799 990ef198f64d
permissions -rw-r--r--
Assertion with own exception throwing
     1 /* -*- C++ -*-
     2  * lemon/dfs.h - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 #ifndef LEMON_DFS_H
    18 #define LEMON_DFS_H
    19 
    20 ///\ingroup flowalgs
    21 ///\file
    22 ///\brief Dfs algorithm.
    23 
    24 #include <lemon/list_graph.h>
    25 #include <lemon/graph_utils.h>
    26 #include <lemon/invalid.h>
    27 #include <lemon/error.h>
    28 #include <lemon/maps.h>
    29 
    30 #include <lemon/concept_check.h>
    31 
    32 namespace lemon {
    33 
    34   
    35   ///Default traits class of Dfs class.
    36 
    37   ///Default traits class of Dfs class.
    38   ///\param GR Graph type.
    39   template<class GR>
    40   struct DfsDefaultTraits
    41   {
    42     ///The graph type the algorithm runs on. 
    43     typedef GR Graph;
    44     ///\brief The type of the map that stores the last
    45     ///edges of the %DFS paths.
    46     /// 
    47     ///The type of the map that stores the last
    48     ///edges of the %DFS paths.
    49     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
    50     ///
    51     typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
    52     ///Instantiates a PredMap.
    53  
    54     ///This function instantiates a \ref PredMap. 
    55     ///\param G is the graph, to which we would like to define the PredMap.
    56     ///\todo The graph alone may be insufficient to initialize
    57     static PredMap *createPredMap(const GR &G) 
    58     {
    59       return new PredMap(G);
    60     }
    61 
    62     ///The type of the map that indicates which nodes are processed.
    63  
    64     ///The type of the map that indicates which nodes are processed.
    65     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
    66     ///\todo named parameter to set this type, function to read and write.
    67     typedef NullMap<typename Graph::Node,bool> ProcessedMap;
    68     ///Instantiates a ProcessedMap.
    69  
    70     ///This function instantiates a \ref ProcessedMap. 
    71     ///\param g is the graph, to which
    72     ///we would like to define the \ref ProcessedMap
    73 #ifdef DOXYGEN
    74     static ProcessedMap *createProcessedMap(const GR &g)
    75 #else
    76     static ProcessedMap *createProcessedMap(const GR &)
    77 #endif
    78     {
    79       return new ProcessedMap();
    80     }
    81     ///The type of the map that indicates which nodes are reached.
    82  
    83     ///The type of the map that indicates which nodes are reached.
    84     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
    85     ///\todo named parameter to set this type, function to read and write.
    86     typedef typename Graph::template NodeMap<bool> ReachedMap;
    87     ///Instantiates a ReachedMap.
    88  
    89     ///This function instantiates a \ref ReachedMap. 
    90     ///\param G is the graph, to which
    91     ///we would like to define the \ref ReachedMap.
    92     static ReachedMap *createReachedMap(const GR &G)
    93     {
    94       return new ReachedMap(G);
    95     }
    96     ///The type of the map that stores the dists of the nodes.
    97  
    98     ///The type of the map that stores the dists of the nodes.
    99     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
   100     ///
   101     typedef typename Graph::template NodeMap<int> DistMap;
   102     ///Instantiates a DistMap.
   103  
   104     ///This function instantiates a \ref DistMap. 
   105     ///\param G is the graph, to which we would like to define the \ref DistMap
   106     static DistMap *createDistMap(const GR &G)
   107     {
   108       return new DistMap(G);
   109     }
   110   };
   111   
   112   ///%DFS algorithm class.
   113   
   114   ///\ingroup flowalgs
   115   ///This class provides an efficient implementation of the %DFS algorithm.
   116   ///
   117   ///\param GR The graph type the algorithm runs on. The default value is
   118   ///\ref ListGraph. The value of GR is not used directly by Dfs, it
   119   ///is only passed to \ref DfsDefaultTraits.
   120   ///\param TR Traits class to set various data types used by the algorithm.
   121   ///The default traits class is
   122   ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
   123   ///See \ref DfsDefaultTraits for the documentation of
   124   ///a Dfs traits class.
   125   ///
   126   ///\author Jacint Szabo and Alpar Juttner
   127 #ifdef DOXYGEN
   128   template <typename GR,
   129 	    typename TR>
   130 #else
   131   template <typename GR=ListGraph,
   132 	    typename TR=DfsDefaultTraits<GR> >
   133 #endif
   134   class Dfs {
   135   public:
   136     /**
   137      * \brief \ref Exception for uninitialized parameters.
   138      *
   139      * This error represents problems in the initialization
   140      * of the parameters of the algorithms.
   141      */
   142     class UninitializedParameter : public lemon::UninitializedParameter {
   143     public:
   144       virtual const char* exceptionName() const {
   145 	return "lemon::Dfs::UninitializedParameter";
   146       }
   147     };
   148 
   149     typedef TR Traits;
   150     ///The type of the underlying graph.
   151     typedef typename TR::Graph Graph;
   152     ///\e
   153     typedef typename Graph::Node Node;
   154     ///\e
   155     typedef typename Graph::NodeIt NodeIt;
   156     ///\e
   157     typedef typename Graph::Edge Edge;
   158     ///\e
   159     typedef typename Graph::OutEdgeIt OutEdgeIt;
   160     
   161     ///\brief The type of the map that stores the last
   162     ///edges of the %DFS paths.
   163     typedef typename TR::PredMap PredMap;
   164     ///The type of the map indicating which nodes are reached.
   165     typedef typename TR::ReachedMap ReachedMap;
   166     ///The type of the map indicating which nodes are processed.
   167     typedef typename TR::ProcessedMap ProcessedMap;
   168     ///The type of the map that stores the dists of the nodes.
   169     typedef typename TR::DistMap DistMap;
   170   private:
   171     /// Pointer to the underlying graph.
   172     const Graph *G;
   173     ///Pointer to the map of predecessors edges.
   174     PredMap *_pred;
   175     ///Indicates if \ref _pred is locally allocated (\c true) or not.
   176     bool local_pred;
   177     ///Pointer to the map of distances.
   178     DistMap *_dist;
   179     ///Indicates if \ref _dist is locally allocated (\c true) or not.
   180     bool local_dist;
   181     ///Pointer to the map of reached status of the nodes.
   182     ReachedMap *_reached;
   183     ///Indicates if \ref _reached is locally allocated (\c true) or not.
   184     bool local_reached;
   185     ///Pointer to the map of processed status of the nodes.
   186     ProcessedMap *_processed;
   187     ///Indicates if \ref _processed is locally allocated (\c true) or not.
   188     bool local_processed;
   189 
   190     std::vector<typename Graph::OutEdgeIt> _stack;
   191     int _stack_head;
   192 
   193     ///Creates the maps if necessary.
   194     
   195     ///\todo Better memory allocation (instead of new).
   196     void create_maps() 
   197     {
   198       if(!_pred) {
   199 	local_pred = true;
   200 	_pred = Traits::createPredMap(*G);
   201       }
   202       if(!_dist) {
   203 	local_dist = true;
   204 	_dist = Traits::createDistMap(*G);
   205       }
   206       if(!_reached) {
   207 	local_reached = true;
   208 	_reached = Traits::createReachedMap(*G);
   209       }
   210       if(!_processed) {
   211 	local_processed = true;
   212 	_processed = Traits::createProcessedMap(*G);
   213       }
   214     }
   215 
   216   protected:
   217 
   218     Dfs() {}
   219     
   220   public:
   221 
   222     typedef Dfs Create;
   223 
   224     ///\name Named template parameters
   225 
   226     ///@{
   227 
   228     template <class T>
   229     struct DefPredMapTraits : public Traits {
   230       typedef T PredMap;
   231       static PredMap *createPredMap(const Graph &G) 
   232       {
   233 	throw UninitializedParameter();
   234       }
   235     };
   236     ///\ref named-templ-param "Named parameter" for setting PredMap type
   237 
   238     ///\ref named-templ-param "Named parameter" for setting PredMap type
   239     ///
   240     template <class T>
   241     struct DefPredMap : public Dfs<Graph, DefPredMapTraits<T> > {
   242       typedef Dfs<Graph, DefPredMapTraits<T> > Create;
   243     };
   244     
   245     
   246     template <class T>
   247     struct DefDistMapTraits : public Traits {
   248       typedef T DistMap;
   249       static DistMap *createDistMap(const Graph &G) 
   250       {
   251 	throw UninitializedParameter();
   252       }
   253     };
   254     ///\ref named-templ-param "Named parameter" for setting DistMap type
   255 
   256     ///\ref named-templ-param "Named parameter" for setting DistMap type
   257     ///
   258     template <class T>
   259     struct DefDistMap {
   260       typedef Dfs<Graph, DefDistMapTraits<T> > Create;
   261     };
   262     
   263     template <class T>
   264     struct DefReachedMapTraits : public Traits {
   265       typedef T ReachedMap;
   266       static ReachedMap *createReachedMap(const Graph &G) 
   267       {
   268 	throw UninitializedParameter();
   269       }
   270     };
   271     ///\ref named-templ-param "Named parameter" for setting ReachedMap type
   272 
   273     ///\ref named-templ-param "Named parameter" for setting ReachedMap type
   274     ///
   275     template <class T>
   276     struct DefReachedMap : public Dfs< Graph, DefReachedMapTraits<T> > {
   277       typedef Dfs< Graph, DefReachedMapTraits<T> > Create;
   278     };
   279 
   280     template <class T>
   281     struct DefProcessedMapTraits : public Traits {
   282       typedef T ProcessedMap;
   283       static ProcessedMap *createProcessedMap(const Graph &G) 
   284       {
   285 	throw UninitializedParameter();
   286       }
   287     };
   288     ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
   289 
   290     ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
   291     ///
   292     template <class T>
   293     struct DefProcessedMap : public Dfs< Graph, DefProcessedMapTraits<T> > { 
   294       typedef Dfs< Graph, DefProcessedMapTraits<T> > Create;
   295     };
   296     
   297     struct DefGraphProcessedMapTraits : public Traits {
   298       typedef typename Graph::template NodeMap<bool> ProcessedMap;
   299       static ProcessedMap *createProcessedMap(const Graph &G) 
   300       {
   301 	return new ProcessedMap(G);
   302       }
   303     };
   304     ///\brief \ref named-templ-param "Named parameter"
   305     ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
   306     ///
   307     ///\ref named-templ-param "Named parameter"
   308     ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
   309     ///If you don't set it explicitely, it will be automatically allocated.
   310     template <class T>
   311     class DefProcessedMapToBeDefaultMap :
   312       public Dfs< Graph, DefGraphProcessedMapTraits> { 
   313       typedef Dfs< Graph, DefGraphProcessedMapTraits> Create;
   314     };
   315     
   316     ///@}
   317 
   318   public:      
   319     
   320     ///Constructor.
   321     
   322     ///\param _G the graph the algorithm will run on.
   323     ///
   324     Dfs(const Graph& _G) :
   325       G(&_G),
   326       _pred(NULL), local_pred(false),
   327       _dist(NULL), local_dist(false),
   328       _reached(NULL), local_reached(false),
   329       _processed(NULL), local_processed(false)
   330     { }
   331     
   332     ///Destructor.
   333     ~Dfs() 
   334     {
   335       if(local_pred) delete _pred;
   336       if(local_dist) delete _dist;
   337       if(local_reached) delete _reached;
   338       if(local_processed) delete _processed;
   339     }
   340 
   341     ///Sets the map storing the predecessor edges.
   342 
   343     ///Sets the map storing the predecessor edges.
   344     ///If you don't use this function before calling \ref run(),
   345     ///it will allocate one. The destuctor deallocates this
   346     ///automatically allocated map, of course.
   347     ///\return <tt> (*this) </tt>
   348     Dfs &predMap(PredMap &m) 
   349     {
   350       if(local_pred) {
   351 	delete _pred;
   352 	local_pred=false;
   353       }
   354       _pred = &m;
   355       return *this;
   356     }
   357 
   358     ///Sets the map storing the distances calculated by the algorithm.
   359 
   360     ///Sets the map storing the distances calculated by the algorithm.
   361     ///If you don't use this function before calling \ref run(),
   362     ///it will allocate one. The destuctor deallocates this
   363     ///automatically allocated map, of course.
   364     ///\return <tt> (*this) </tt>
   365     Dfs &distMap(DistMap &m) 
   366     {
   367       if(local_dist) {
   368 	delete _dist;
   369 	local_dist=false;
   370       }
   371       _dist = &m;
   372       return *this;
   373     }
   374 
   375     ///Sets the map indicating if a node is reached.
   376 
   377     ///Sets the map indicating if a node is reached.
   378     ///If you don't use this function before calling \ref run(),
   379     ///it will allocate one. The destuctor deallocates this
   380     ///automatically allocated map, of course.
   381     ///\return <tt> (*this) </tt>
   382     Dfs &reachedMap(ReachedMap &m) 
   383     {
   384       if(local_reached) {
   385 	delete _reached;
   386 	local_reached=false;
   387       }
   388       _reached = &m;
   389       return *this;
   390     }
   391 
   392     ///Sets the map indicating if a node is processed.
   393 
   394     ///Sets the map indicating if a node is processed.
   395     ///If you don't use this function before calling \ref run(),
   396     ///it will allocate one. The destuctor deallocates this
   397     ///automatically allocated map, of course.
   398     ///\return <tt> (*this) </tt>
   399     Dfs &processedMap(ProcessedMap &m) 
   400     {
   401       if(local_processed) {
   402 	delete _processed;
   403 	local_processed=false;
   404       }
   405       _processed = &m;
   406       return *this;
   407     }
   408 
   409   public:
   410     ///\name Execution control
   411     ///The simplest way to execute the algorithm is to use
   412     ///one of the member functions called \c run(...).
   413     ///\n
   414     ///If you need more control on the execution,
   415     ///first you must call \ref init(), then you can add a source node
   416     ///with \ref addSource().
   417     ///Finally \ref start() will perform the actual path
   418     ///computation.
   419 
   420     ///@{
   421 
   422     ///Initializes the internal data structures.
   423 
   424     ///Initializes the internal data structures.
   425     ///
   426     void init()
   427     {
   428       create_maps();
   429       _stack.resize(countNodes(*G));
   430       _stack_head=-1;
   431       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
   432 	_pred->set(u,INVALID);
   433 	// _predNode->set(u,INVALID);
   434 	_reached->set(u,false);
   435 	_processed->set(u,false);
   436       }
   437     }
   438     
   439     ///Adds a new source node.
   440 
   441     ///Adds a new source node to the set of nodes to be processed.
   442     ///
   443     ///\bug dists are wrong (or at least strange) in case of multiple sources.
   444     void addSource(Node s)
   445     {
   446       if(!(*_reached)[s])
   447 	{
   448 	  _reached->set(s,true);
   449 	  _pred->set(s,INVALID);
   450 	  OutEdgeIt e(*G,s);
   451 	  if(e!=INVALID) {
   452 	    _stack[++_stack_head]=e;
   453 	    _dist->set(s,_stack_head);
   454 	  }
   455 	  else {
   456 	    _processed->set(s,true);
   457 	    _dist->set(s,0);
   458 	  }
   459 	}
   460     }
   461     
   462     ///Processes the next edge.
   463 
   464     ///Processes the next edge.
   465     ///
   466     ///\return The processed edge.
   467     ///
   468     ///\pre The stack must not be empty!
   469     Edge processNextEdge()
   470     { 
   471       Node m;
   472       Edge e=_stack[_stack_head];
   473       if(!(*_reached)[m=G->target(e)]) {
   474 	_pred->set(m,e);
   475 	_reached->set(m,true);
   476 	++_stack_head;
   477 	_stack[_stack_head] = OutEdgeIt(*G, m);
   478 	_dist->set(m,_stack_head);
   479       }
   480       else {
   481 	m=G->source(e);
   482 	++_stack[_stack_head];
   483       }
   484       while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
   485 	_processed->set(m,true);
   486 	--_stack_head;
   487 	if(_stack_head>=0) {
   488 	  m=G->source(_stack[_stack_head]);
   489 	  ++_stack[_stack_head];
   490 	}
   491       }
   492       return e;
   493     }
   494     ///Next edge to be processed.
   495 
   496     ///Next edge to be processed.
   497     ///
   498     ///\return The next edge to be processed or INVALID if the stack is
   499     /// empty.
   500     OutEdgeIt nextEdge()
   501     { 
   502       return _stack_head>=0?_stack[_stack_head]:INVALID;
   503     }
   504 
   505     ///\brief Returns \c false if there are nodes
   506     ///to be processed in the queue
   507     ///
   508     ///Returns \c false if there are nodes
   509     ///to be processed in the queue
   510     bool emptyQueue() { return _stack_head<0; }
   511     ///Returns the number of the nodes to be processed.
   512     
   513     ///Returns the number of the nodes to be processed in the queue.
   514     int queueSize() { return _stack_head+1; }
   515     
   516     ///Executes the algorithm.
   517 
   518     ///Executes the algorithm.
   519     ///
   520     ///\pre init() must be called and at least one node should be added
   521     ///with addSource() before using this function.
   522     ///
   523     ///This method runs the %DFS algorithm from the root node(s)
   524     ///in order to
   525     ///compute the
   526     ///%DFS path to each node. The algorithm computes
   527     ///- The %DFS tree.
   528     ///- The distance of each node from the root(s) in the %DFS tree.
   529     ///
   530     void start()
   531     {
   532       while ( !emptyQueue() ) processNextEdge();
   533     }
   534     
   535     ///Executes the algorithm until \c dest is reached.
   536 
   537     ///Executes the algorithm until \c dest is reached.
   538     ///
   539     ///\pre init() must be called and at least one node should be added
   540     ///with addSource() before using this function.
   541     ///
   542     ///This method runs the %DFS algorithm from the root node(s)
   543     ///in order to
   544     ///compute the
   545     ///%DFS path to \c dest. The algorithm computes
   546     ///- The %DFS path to \c  dest.
   547     ///- The distance of \c dest from the root(s) in the %DFS tree.
   548     ///
   549     void start(Node dest)
   550     {
   551       while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest ) 
   552 	processNextEdge();
   553     }
   554     
   555     ///Executes the algorithm until a condition is met.
   556 
   557     ///Executes the algorithm until a condition is met.
   558     ///
   559     ///\pre init() must be called and at least one node should be added
   560     ///with addSource() before using this function.
   561     ///
   562     ///\param nm must be a bool (or convertible) edge map. The algorithm
   563     ///will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>.
   564     ///
   565     ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c em is an edge map,
   566     ///not a node map.
   567     template<class EM>
   568     void start(const EM &em)
   569     {
   570       while ( !emptyQueue() && !em[_stack[_stack_head]] ) processNextEdge();
   571     }
   572 
   573     ///Runs %DFS algorithm from node \c s.
   574     
   575     ///This method runs the %DFS algorithm from a root node \c s
   576     ///in order to
   577     ///compute the
   578     ///%DFS path to each node. The algorithm computes
   579     ///- The %DFS tree.
   580     ///- The distance of each node from the root in the %DFS tree.
   581     ///
   582     ///\note d.run(s) is just a shortcut of the following code.
   583     ///\code
   584     ///  d.init();
   585     ///  d.addSource(s);
   586     ///  d.start();
   587     ///\endcode
   588     void run(Node s) {
   589       init();
   590       addSource(s);
   591       start();
   592     }
   593     
   594     ///Finds the %DFS path between \c s and \c t.
   595     
   596     ///Finds the %DFS path between \c s and \c t.
   597     ///
   598     ///\return The length of the %DFS s---t path if there exists one,
   599     ///0 otherwise.
   600     ///\note Apart from the return value, d.run(s,t) is
   601     ///just a shortcut of the following code.
   602     ///\code
   603     ///  d.init();
   604     ///  d.addSource(s);
   605     ///  d.start(t);
   606     ///\endcode
   607     int run(Node s,Node t) {
   608       init();
   609       addSource(s);
   610       start(t);
   611       return reached(t)?_stack_head+1:0;
   612     }
   613     
   614     ///@}
   615 
   616     ///\name Query Functions
   617     ///The result of the %DFS algorithm can be obtained using these
   618     ///functions.\n
   619     ///Before the use of these functions,
   620     ///either run() or start() must be called.
   621     
   622     ///@{
   623 
   624     ///Copies the path to \c t on the DFS tree into \c p
   625     
   626     ///This function copies the path to \c t on the DFS tree  into \c p.
   627     ///If \c t is a source itself or unreachable, then it does not
   628     ///alter \c p.
   629     ///
   630     ///\return Returns \c true if a path to \c t was actually copied to \c p,
   631     ///\c false otherwise.
   632     ///\sa DirPath
   633     template<class P>
   634     bool getPath(P &p,Node t) 
   635     {
   636       if(reached(t)) {
   637 	p.clear();
   638 	typename P::Builder b(p);
   639 	for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
   640 	  b.pushFront(predEdge(t));
   641 	b.commit();
   642 	return true;
   643       }
   644       return false;
   645     }
   646 
   647     ///The distance of a node from the root(s).
   648 
   649     ///Returns the distance of a node from the root(s).
   650     ///\pre \ref run() must be called before using this function.
   651     ///\warning If node \c v is unreachable from the root(s) then the return value
   652     ///of this funcion is undefined.
   653     int dist(Node v) const { return (*_dist)[v]; }
   654 
   655     ///Returns the 'previous edge' of the %DFS tree.
   656 
   657     ///For a node \c v it returns the 'previous edge'
   658     ///of the %DFS path,
   659     ///i.e. it returns the last edge of a %DFS path from the root(s) to \c
   660     ///v. It is \ref INVALID
   661     ///if \c v is unreachable from the root(s) or \c v is a root. The
   662     ///%DFS tree used here is equal to the %DFS tree used in
   663     ///\ref predNode().
   664     ///\pre Either \ref run() or \ref start() must be called before using
   665     ///this function.
   666     Edge predEdge(Node v) const { return (*_pred)[v];}
   667 
   668     ///Returns the 'previous node' of the %DFS tree.
   669 
   670     ///For a node \c v it returns the 'previous node'
   671     ///of the %DFS tree,
   672     ///i.e. it returns the last but one node from a %DFS path from the
   673     ///root(a) to \c /v.
   674     ///It is INVALID if \c v is unreachable from the root(s) or
   675     ///if \c v itself a root.
   676     ///The %DFS tree used here is equal to the %DFS
   677     ///tree used in \ref predEdge().
   678     ///\pre Either \ref run() or \ref start() must be called before
   679     ///using this function.
   680     Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
   681 				  G->source((*_pred)[v]); }
   682     
   683     ///Returns a reference to the NodeMap of distances.
   684 
   685     ///Returns a reference to the NodeMap of distances.
   686     ///\pre Either \ref run() or \ref init() must
   687     ///be called before using this function.
   688     const DistMap &distMap() const { return *_dist;}
   689  
   690     ///Returns a reference to the %DFS edge-tree map.
   691 
   692     ///Returns a reference to the NodeMap of the edges of the
   693     ///%DFS tree.
   694     ///\pre Either \ref run() or \ref init()
   695     ///must be called before using this function.
   696     const PredMap &predMap() const { return *_pred;}
   697  
   698     ///Checks if a node is reachable from the root.
   699 
   700     ///Returns \c true if \c v is reachable from the root(s).
   701     ///\warning The source nodes are inditated as unreachable.
   702     ///\pre Either \ref run() or \ref start()
   703     ///must be called before using this function.
   704     ///
   705     bool reached(Node v) { return (*_reached)[v]; }
   706     
   707     ///@}
   708   };
   709 
   710   ///Default traits class of Dfs function.
   711 
   712   ///Default traits class of Dfs function.
   713   ///\param GR Graph type.
   714   template<class GR>
   715   struct DfsWizardDefaultTraits
   716   {
   717     ///The graph type the algorithm runs on. 
   718     typedef GR Graph;
   719     ///\brief The type of the map that stores the last
   720     ///edges of the %DFS paths.
   721     /// 
   722     ///The type of the map that stores the last
   723     ///edges of the %DFS paths.
   724     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
   725     ///
   726     typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
   727     ///Instantiates a PredMap.
   728  
   729     ///This function instantiates a \ref PredMap. 
   730     ///\param g is the graph, to which we would like to define the PredMap.
   731     ///\todo The graph alone may be insufficient to initialize
   732 #ifdef DOXYGEN
   733     static PredMap *createPredMap(const GR &g) 
   734 #else
   735     static PredMap *createPredMap(const GR &) 
   736 #endif
   737     {
   738       return new PredMap();
   739     }
   740 
   741     ///The type of the map that indicates which nodes are processed.
   742  
   743     ///The type of the map that indicates which nodes are processed.
   744     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
   745     ///\todo named parameter to set this type, function to read and write.
   746     typedef NullMap<typename Graph::Node,bool> ProcessedMap;
   747     ///Instantiates a ProcessedMap.
   748  
   749     ///This function instantiates a \ref ProcessedMap. 
   750     ///\param g is the graph, to which
   751     ///we would like to define the \ref ProcessedMap
   752 #ifdef DOXYGEN
   753     static ProcessedMap *createProcessedMap(const GR &g)
   754 #else
   755     static ProcessedMap *createProcessedMap(const GR &)
   756 #endif
   757     {
   758       return new ProcessedMap();
   759     }
   760     ///The type of the map that indicates which nodes are reached.
   761  
   762     ///The type of the map that indicates which nodes are reached.
   763     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
   764     ///\todo named parameter to set this type, function to read and write.
   765     typedef typename Graph::template NodeMap<bool> ReachedMap;
   766     ///Instantiates a ReachedMap.
   767  
   768     ///This function instantiates a \ref ReachedMap. 
   769     ///\param G is the graph, to which
   770     ///we would like to define the \ref ReachedMap.
   771     static ReachedMap *createReachedMap(const GR &G)
   772     {
   773       return new ReachedMap(G);
   774     }
   775     ///The type of the map that stores the dists of the nodes.
   776  
   777     ///The type of the map that stores the dists of the nodes.
   778     ///It must meet the \ref concept::WriteMap "WriteMap" concept.
   779     ///
   780     typedef NullMap<typename Graph::Node,int> DistMap;
   781     ///Instantiates a DistMap.
   782  
   783     ///This function instantiates a \ref DistMap. 
   784     ///\param g is the graph, to which we would like to define the \ref DistMap
   785 #ifdef DOXYGEN
   786     static DistMap *createDistMap(const GR &g)
   787 #else
   788     static DistMap *createDistMap(const GR &)
   789 #endif
   790     {
   791       return new DistMap();
   792     }
   793   };
   794   
   795   /// Default traits used by \ref DfsWizard
   796 
   797   /// To make it easier to use Dfs algorithm
   798   ///we have created a wizard class.
   799   /// This \ref DfsWizard class needs default traits,
   800   ///as well as the \ref Dfs class.
   801   /// The \ref DfsWizardBase is a class to be the default traits of the
   802   /// \ref DfsWizard class.
   803   template<class GR>
   804   class DfsWizardBase : public DfsWizardDefaultTraits<GR>
   805   {
   806 
   807     typedef DfsWizardDefaultTraits<GR> Base;
   808   protected:
   809     /// Type of the nodes in the graph.
   810     typedef typename Base::Graph::Node Node;
   811 
   812     /// Pointer to the underlying graph.
   813     void *_g;
   814     ///Pointer to the map of reached nodes.
   815     void *_reached;
   816     ///Pointer to the map of processed nodes.
   817     void *_processed;
   818     ///Pointer to the map of predecessors edges.
   819     void *_pred;
   820     ///Pointer to the map of distances.
   821     void *_dist;
   822     ///Pointer to the source node.
   823     Node _source;
   824     
   825     public:
   826     /// Constructor.
   827     
   828     /// This constructor does not require parameters, therefore it initiates
   829     /// all of the attributes to default values (0, INVALID).
   830     DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
   831 			   _dist(0), _source(INVALID) {}
   832 
   833     /// Constructor.
   834     
   835     /// This constructor requires some parameters,
   836     /// listed in the parameters list.
   837     /// Others are initiated to 0.
   838     /// \param g is the initial value of  \ref _g
   839     /// \param s is the initial value of  \ref _source
   840     DfsWizardBase(const GR &g, Node s=INVALID) :
   841       _g((void *)&g), _reached(0), _processed(0), _pred(0),
   842       _dist(0), _source(s) {}
   843 
   844   };
   845   
   846   /// A class to make the usage of the Dfs algorithm easier
   847 
   848   /// This class is created to make it easier to use the Dfs algorithm.
   849   /// It uses the functions and features of the plain \ref Dfs,
   850   /// but it is much simpler to use it.
   851   ///
   852   /// Simplicity means that the way to change the types defined
   853   /// in the traits class is based on functions that returns the new class
   854   /// and not on templatable built-in classes.
   855   /// When using the plain \ref Dfs
   856   /// the new class with the modified type comes from
   857   /// the original class by using the ::
   858   /// operator. In the case of \ref DfsWizard only
   859   /// a function have to be called and it will
   860   /// return the needed class.
   861   ///
   862   /// It does not have own \ref run method. When its \ref run method is called
   863   /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run
   864   /// method of it.
   865   template<class TR>
   866   class DfsWizard : public TR
   867   {
   868     typedef TR Base;
   869 
   870     ///The type of the underlying graph.
   871     typedef typename TR::Graph Graph;
   872     //\e
   873     typedef typename Graph::Node Node;
   874     //\e
   875     typedef typename Graph::NodeIt NodeIt;
   876     //\e
   877     typedef typename Graph::Edge Edge;
   878     //\e
   879     typedef typename Graph::OutEdgeIt OutEdgeIt;
   880     
   881     ///\brief The type of the map that stores
   882     ///the reached nodes
   883     typedef typename TR::ReachedMap ReachedMap;
   884     ///\brief The type of the map that stores
   885     ///the processed nodes
   886     typedef typename TR::ProcessedMap ProcessedMap;
   887     ///\brief The type of the map that stores the last
   888     ///edges of the %DFS paths.
   889     typedef typename TR::PredMap PredMap;
   890     ///The type of the map that stores the distances of the nodes.
   891     typedef typename TR::DistMap DistMap;
   892 
   893 public:
   894     /// Constructor.
   895     DfsWizard() : TR() {}
   896 
   897     /// Constructor that requires parameters.
   898 
   899     /// Constructor that requires parameters.
   900     /// These parameters will be the default values for the traits class.
   901     DfsWizard(const Graph &g, Node s=INVALID) :
   902       TR(g,s) {}
   903 
   904     ///Copy constructor
   905     DfsWizard(const TR &b) : TR(b) {}
   906 
   907     ~DfsWizard() {}
   908 
   909     ///Runs Dfs algorithm from a given node.
   910     
   911     ///Runs Dfs algorithm from a given node.
   912     ///The node can be given by the \ref source function.
   913     void run()
   914     {
   915       if(Base::_source==INVALID) throw UninitializedParameter();
   916       Dfs<Graph,TR> alg(*(Graph*)Base::_g);
   917       if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached);
   918       if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
   919       if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
   920       if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
   921       alg.run(Base::_source);
   922     }
   923 
   924     ///Runs Dfs algorithm from the given node.
   925 
   926     ///Runs Dfs algorithm from the given node.
   927     ///\param s is the given source.
   928     void run(Node s)
   929     {
   930       Base::_source=s;
   931       run();
   932     }
   933 
   934     template<class T>
   935     struct DefPredMapBase : public Base {
   936       typedef T PredMap;
   937       static PredMap *createPredMap(const Graph &) { return 0; };
   938       DefPredMapBase(const TR &b) : TR(b) {}
   939     };
   940     
   941     ///\brief \ref named-templ-param "Named parameter"
   942     ///function for setting PredMap type
   943     ///
   944     /// \ref named-templ-param "Named parameter"
   945     ///function for setting PredMap type
   946     ///
   947     template<class T>
   948     DfsWizard<DefPredMapBase<T> > predMap(const T &t) 
   949     {
   950       Base::_pred=(void *)&t;
   951       return DfsWizard<DefPredMapBase<T> >(*this);
   952     }
   953     
   954  
   955     template<class T>
   956     struct DefReachedMapBase : public Base {
   957       typedef T ReachedMap;
   958       static ReachedMap *createReachedMap(const Graph &) { return 0; };
   959       DefReachedMapBase(const TR &b) : TR(b) {}
   960     };
   961     
   962     ///\brief \ref named-templ-param "Named parameter"
   963     ///function for setting ReachedMap
   964     ///
   965     /// \ref named-templ-param "Named parameter"
   966     ///function for setting ReachedMap
   967     ///
   968     template<class T>
   969     DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) 
   970     {
   971       Base::_pred=(void *)&t;
   972       return DfsWizard<DefReachedMapBase<T> >(*this);
   973     }
   974     
   975 
   976     template<class T>
   977     struct DefProcessedMapBase : public Base {
   978       typedef T ProcessedMap;
   979       static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
   980       DefProcessedMapBase(const TR &b) : TR(b) {}
   981     };
   982     
   983     ///\brief \ref named-templ-param "Named parameter"
   984     ///function for setting ProcessedMap
   985     ///
   986     /// \ref named-templ-param "Named parameter"
   987     ///function for setting ProcessedMap
   988     ///
   989     template<class T>
   990     DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) 
   991     {
   992       Base::_pred=(void *)&t;
   993       return DfsWizard<DefProcessedMapBase<T> >(*this);
   994     }
   995     
   996     template<class T>
   997     struct DefDistMapBase : public Base {
   998       typedef T DistMap;
   999       static DistMap *createDistMap(const Graph &) { return 0; };
  1000       DefDistMapBase(const TR &b) : TR(b) {}
  1001     };
  1002     
  1003     ///\brief \ref named-templ-param "Named parameter"
  1004     ///function for setting DistMap type
  1005     ///
  1006     /// \ref named-templ-param "Named parameter"
  1007     ///function for setting DistMap type
  1008     ///
  1009     template<class T>
  1010     DfsWizard<DefDistMapBase<T> > distMap(const T &t) 
  1011     {
  1012       Base::_dist=(void *)&t;
  1013       return DfsWizard<DefDistMapBase<T> >(*this);
  1014     }
  1015     
  1016     /// Sets the source node, from which the Dfs algorithm runs.
  1017 
  1018     /// Sets the source node, from which the Dfs algorithm runs.
  1019     /// \param s is the source node.
  1020     DfsWizard<TR> &source(Node s) 
  1021     {
  1022       Base::_source=s;
  1023       return *this;
  1024     }
  1025     
  1026   };
  1027   
  1028   ///Function type interface for Dfs algorithm.
  1029 
  1030   /// \ingroup flowalgs
  1031   ///Function type interface for Dfs algorithm.
  1032   ///
  1033   ///This function also has several
  1034   ///\ref named-templ-func-param "named parameters",
  1035   ///they are declared as the members of class \ref DfsWizard.
  1036   ///The following
  1037   ///example shows how to use these parameters.
  1038   ///\code
  1039   ///  dfs(g,source).predMap(preds).run();
  1040   ///\endcode
  1041   ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
  1042   ///to the end of the parameter list.
  1043   ///\sa DfsWizard
  1044   ///\sa Dfs
  1045   template<class GR>
  1046   DfsWizard<DfsWizardBase<GR> >
  1047   dfs(const GR &g,typename GR::Node s=INVALID)
  1048   {
  1049     return DfsWizard<DfsWizardBase<GR> >(g,s);
  1050   }
  1051 
  1052   /// \brief Visitor class for dfs.
  1053   ///  
  1054   /// It gives a simple interface for a functional interface for dfs 
  1055   /// traversal. The traversal on a linear data structure. 
  1056   template <typename _Graph>
  1057   struct DfsVisitor {
  1058     typedef _Graph Graph;
  1059     typedef typename Graph::Edge Edge;
  1060     typedef typename Graph::Node Node;
  1061     /// \brief Called when the edge reach a node.
  1062     /// 
  1063     /// It is called when the dfs find an edge which target is not
  1064     /// reached yet.
  1065     void discover(const Edge& edge) {}
  1066     /// \brief Called when the node reached first time.
  1067     /// 
  1068     /// It is Called when the node reached first time.
  1069     void reach(const Node& node) {}
  1070     /// \brief Called when we step back on an edge.
  1071     /// 
  1072     /// It is called when the dfs should step back on the edge.
  1073     void backtrack(const Edge& edge) {}
  1074     /// \brief Called when we step back from the node.
  1075     /// 
  1076     /// It is called when we step back from the node.
  1077     void leave(const Node& node) {}
  1078     /// \brief Called when the edge examined but target of the edge 
  1079     /// already discovered.
  1080     /// 
  1081     /// It called when the edge examined but the target of the edge 
  1082     /// already discovered.
  1083     void examine(const Edge& edge) {}
  1084     /// \brief Called for the source node of the dfs.
  1085     /// 
  1086     /// It is called for the source node of the dfs.
  1087     void start(const Node&) {}
  1088     /// \brief Called when we leave the source node of the dfs.
  1089     /// 
  1090     /// It is called when we leave the source node of the dfs.
  1091     void stop(const Node&) {}
  1092 
  1093     template <typename _Visitor>
  1094     struct Constraints {
  1095       void constraints() {
  1096 	Edge edge;
  1097 	Node node;
  1098 	visitor.discover(edge);
  1099 	visitor.reach(node);
  1100 	visitor.backtrack(edge);
  1101 	visitor.leave(node);
  1102 	visitor.examine(edge);
  1103 	visitor.start(node);
  1104 	visitor.stop(edge);
  1105       }
  1106       _Visitor& visitor;
  1107     };
  1108   };
  1109 
  1110   /// \brief Default traits class of DfsVisit class.
  1111   ///
  1112   /// Default traits class of DfsVisit class.
  1113   /// \param _Graph Graph type.
  1114   template<class _Graph>
  1115   struct DfsVisitDefaultTraits {
  1116 
  1117     /// \brief The graph type the algorithm runs on. 
  1118     typedef _Graph Graph;
  1119 
  1120     /// \brief The type of the map that indicates which nodes are reached.
  1121     /// 
  1122     /// The type of the map that indicates which nodes are reached.
  1123     /// It must meet the \ref concept::WriteMap "WriteMap" concept.
  1124     /// \todo named parameter to set this type, function to read and write.
  1125     typedef typename Graph::template NodeMap<bool> ReachedMap;
  1126 
  1127     /// \brief Instantiates a ReachedMap.
  1128     ///
  1129     /// This function instantiates a \ref ReachedMap. 
  1130     /// \param G is the graph, to which
  1131     /// we would like to define the \ref ReachedMap.
  1132     static ReachedMap *createReachedMap(const Graph &graph) {
  1133       return new ReachedMap(graph);
  1134     }
  1135 
  1136   };
  1137   
  1138   /// %DFS Visit algorithm class.
  1139   
  1140   /// \ingroup flowalgs
  1141   /// This class provides an efficient implementation of the %DFS algorithm
  1142   /// with visitor interface.
  1143   ///
  1144   /// The %DfsVisit class provides an alternative interface to the Dfs
  1145   /// class. It works with callback mechanism, the DfsVisit object calls
  1146   /// on every dfs event the \c Visitor class member functions. 
  1147   ///
  1148   /// \param _Graph The graph type the algorithm runs on. The default value is
  1149   /// \ref ListGraph. The value of _Graph is not used directly by Dfs, it
  1150   /// is only passed to \ref DfsDefaultTraits.
  1151   /// \param _Visitor The Visitor object for the algorithm. The 
  1152   /// \ref DfsVisitor "DfsVisitor<_Graph>" is an empty Visitor which
  1153   /// does not observe the Dfs events. If you want to observe the dfs
  1154   /// events you should implement your own Visitor class.
  1155   /// \param _Traits Traits class to set various data types used by the 
  1156   /// algorithm. The default traits class is
  1157   /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Graph>".
  1158   /// See \ref DfsVisitDefaultTraits for the documentation of
  1159   /// a Dfs visit traits class.
  1160   ///
  1161   /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
  1162 #ifdef DOXYGEN
  1163   template <typename _Graph, typename _Visitor, typename _Traits>
  1164 #else
  1165   template <typename _Graph = ListGraph,
  1166 	    typename _Visitor = DfsVisitor<_Graph>,
  1167 	    typename _Traits = DfsDefaultTraits<_Graph> >
  1168 #endif
  1169   class DfsVisit {
  1170   public:
  1171     
  1172     /// \brief \ref Exception for uninitialized parameters.
  1173     ///
  1174     /// This error represents problems in the initialization
  1175     /// of the parameters of the algorithms.
  1176     class UninitializedParameter : public lemon::UninitializedParameter {
  1177     public:
  1178       virtual const char* exceptionName() const {
  1179 	return "lemon::DfsVisit::UninitializedParameter";
  1180       }
  1181     };
  1182 
  1183     typedef _Traits Traits;
  1184 
  1185     typedef typename Traits::Graph Graph;
  1186 
  1187     typedef _Visitor Visitor;
  1188 
  1189     ///The type of the map indicating which nodes are reached.
  1190     typedef typename Traits::ReachedMap ReachedMap;
  1191 
  1192   private:
  1193 
  1194     typedef typename Graph::Node Node;
  1195     typedef typename Graph::NodeIt NodeIt;
  1196     typedef typename Graph::Edge Edge;
  1197     typedef typename Graph::OutEdgeIt OutEdgeIt;
  1198 
  1199     /// Pointer to the underlying graph.
  1200     const Graph *_graph;
  1201     /// Pointer to the visitor object.
  1202     Visitor *_visitor;
  1203     ///Pointer to the map of reached status of the nodes.
  1204     ReachedMap *_reached;
  1205     ///Indicates if \ref _reached is locally allocated (\c true) or not.
  1206     bool local_reached;
  1207 
  1208     std::vector<typename Graph::Edge> _stack;
  1209     int _stack_head;
  1210 
  1211     /// \brief Creates the maps if necessary.
  1212     ///
  1213     /// Creates the maps if necessary.
  1214     void create_maps() {
  1215       if(!_reached) {
  1216 	local_reached = true;
  1217 	_reached = Traits::createReachedMap(*_graph);
  1218       }
  1219     }
  1220 
  1221   protected:
  1222 
  1223     DfsVisit() {}
  1224     
  1225   public:
  1226 
  1227     typedef DfsVisit Create;
  1228 
  1229     /// \name Named template parameters
  1230 
  1231     ///@{
  1232     template <class T>
  1233     struct DefReachedMapTraits : public Traits {
  1234       typedef T ReachedMap;
  1235       static ReachedMap *createReachedMap(const Graph &graph) {
  1236 	throw UninitializedParameter();
  1237       }
  1238     };
  1239     /// \brief \ref named-templ-param "Named parameter" for setting 
  1240     /// ReachedMap type
  1241     ///
  1242     /// \ref named-templ-param "Named parameter" for setting ReachedMap type
  1243     template <class T>
  1244     struct DefReachedMap : public DfsVisit< Graph, Visitor,
  1245 					    DefReachedMapTraits<T> > {
  1246       typedef DfsVisit< Graph, Visitor, DefReachedMapTraits<T> > Create;
  1247     };
  1248     ///@}
  1249 
  1250   public:      
  1251     
  1252     /// \brief Constructor.
  1253     ///
  1254     /// Constructor.
  1255     ///
  1256     /// \param graph the graph the algorithm will run on.
  1257     /// \param visitor The visitor of the algorithm.
  1258     ///
  1259     DfsVisit(const Graph& graph, Visitor& visitor) 
  1260       : _graph(&graph), _visitor(&visitor),
  1261 	_reached(0), local_reached(false) {}
  1262     
  1263     /// \brief Destructor.
  1264     ///
  1265     /// Destructor.
  1266     ~DfsVisit() {
  1267       if(local_reached) delete _reached;
  1268     }
  1269 
  1270     /// \brief Sets the map indicating if a node is reached.
  1271     ///
  1272     /// Sets the map indicating if a node is reached.
  1273     /// If you don't use this function before calling \ref run(),
  1274     /// it will allocate one. The destuctor deallocates this
  1275     /// automatically allocated map, of course.
  1276     /// \return <tt> (*this) </tt>
  1277     DfsVisit &reachedMap(ReachedMap &m) {
  1278       if(local_reached) {
  1279 	delete _reached;
  1280 	local_reached=false;
  1281       }
  1282       _reached = &m;
  1283       return *this;
  1284     }
  1285 
  1286   public:
  1287     /// \name Execution control
  1288     /// The simplest way to execute the algorithm is to use
  1289     /// one of the member functions called \c run(...).
  1290     /// \n
  1291     /// If you need more control on the execution,
  1292     /// first you must call \ref init(), then you can adda source node
  1293     /// with \ref addSource().
  1294     /// Finally \ref start() will perform the actual path
  1295     /// computation.
  1296 
  1297     /// @{
  1298     /// \brief Initializes the internal data structures.
  1299     ///
  1300     /// Initializes the internal data structures.
  1301     ///
  1302     void init() {
  1303       create_maps();
  1304       _stack.resize(countNodes(*_graph));
  1305       _stack_head = -1;
  1306       for (NodeIt u(*_graph) ; u != INVALID ; ++u) {
  1307 	_reached->set(u, false);
  1308       }
  1309     }
  1310     
  1311     /// \brief Adds a new source node.
  1312     ///
  1313     /// Adds a new source node to the set of nodes to be processed.
  1314     void addSource(Node s) {
  1315       if(!(*_reached)[s]) {
  1316 	  _reached->set(s,true);
  1317 	  _visitor->start(s);
  1318 	  _visitor->reach(s);
  1319 	  Edge e; 
  1320 	  _graph->firstOut(e, s);
  1321 	  if (e != INVALID) {
  1322 	    _stack[++_stack_head] = e;
  1323 	  } else {
  1324 	    _visitor->leave(s);
  1325 	  }
  1326 	}
  1327     }
  1328     
  1329     /// \brief Processes the next edge.
  1330     ///
  1331     /// Processes the next edge.
  1332     ///
  1333     /// \return The processed edge.
  1334     ///
  1335     /// \pre The stack must not be empty!
  1336     Edge processNextEdge() { 
  1337       Edge e = _stack[_stack_head];
  1338       Node m = _graph->target(e);
  1339       if(!(*_reached)[m]) {
  1340 	_visitor->discover(e);
  1341 	_visitor->reach(m);
  1342 	_reached->set(m, true);
  1343 	_graph->firstOut(_stack[++_stack_head], m);
  1344       } else {
  1345 	_visitor->examine(e);
  1346 	m = _graph->source(e);
  1347 	_graph->nextOut(_stack[_stack_head]);
  1348       }
  1349       while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
  1350 	_visitor->leave(m);
  1351 	--_stack_head;
  1352 	if (_stack_head >= 0) {
  1353 	  _visitor->backtrack(_stack[_stack_head]);
  1354 	  m = _graph->source(_stack[_stack_head]);
  1355 	  _graph->nextOut(_stack[_stack_head]);
  1356 	} else {
  1357 	  _visitor->stop(m);	  
  1358 	}
  1359       }
  1360       return e;
  1361     }
  1362 
  1363     /// \brief Next edge to be processed.
  1364     ///
  1365     /// Next edge to be processed.
  1366     ///
  1367     /// \return The next edge to be processed or INVALID if the stack is
  1368     /// empty.
  1369     Edge nextEdge() { 
  1370       return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
  1371     }
  1372 
  1373     /// \brief Returns \c false if there are nodes
  1374     /// to be processed in the queue
  1375     ///
  1376     /// Returns \c false if there are nodes
  1377     /// to be processed in the queue
  1378     bool emptyQueue() { return _stack_head < 0; }
  1379 
  1380     /// \brief Returns the number of the nodes to be processed.
  1381     ///
  1382     /// Returns the number of the nodes to be processed in the queue.
  1383     int queueSize() { return _stack_head + 1; }
  1384     
  1385     /// \brief Executes the algorithm.
  1386     ///
  1387     /// Executes the algorithm.
  1388     ///
  1389     /// \pre init() must be called and at least one node should be added
  1390     /// with addSource() before using this function.
  1391     void start() {
  1392       while ( !emptyQueue() ) processNextEdge();
  1393     }
  1394     
  1395     /// \brief Executes the algorithm until \c dest is reached.
  1396     ///
  1397     /// Executes the algorithm until \c dest is reached.
  1398     ///
  1399     /// \pre init() must be called and at least one node should be added
  1400     /// with addSource() before using this function.
  1401     void start(Node dest) {
  1402       while ( !emptyQueue() && _graph->target(_stack[_stack_head]) != dest) 
  1403 	processNextEdge();
  1404     }
  1405     
  1406     /// \brief Executes the algorithm until a condition is met.
  1407     ///
  1408     /// Executes the algorithm until a condition is met.
  1409     ///
  1410     /// \pre init() must be called and at least one node should be added
  1411     /// with addSource() before using this function.
  1412     ///
  1413     /// \param nm must be a bool (or convertible) edge map. The algorithm
  1414     /// will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>.
  1415     ///
  1416     /// \warning Contrary to \ref Dfs and \ref Dijkstra, \c em is an edge map,
  1417     /// not a node map.
  1418     template <typename EM>
  1419     void start(const EM &em) {
  1420       while (!emptyQueue() && !em[_stack[_stack_head]]) processNextEdge();
  1421     }
  1422 
  1423     /// \brief Runs %DFS algorithm from node \c s.
  1424     ///
  1425     /// This method runs the %DFS algorithm from a root node \c s.
  1426     /// \note d.run(s) is just a shortcut of the following code.
  1427     /// \code
  1428     ///   d.init();
  1429     ///   d.addSource(s);
  1430     ///   d.start();
  1431     /// \endcode
  1432     void run(Node s) {
  1433       init();
  1434       addSource(s);
  1435       start();
  1436     }
  1437     ///@}
  1438 
  1439     /// \name Query Functions
  1440     /// The result of the %DFS algorithm can be obtained using these
  1441     /// functions.\n
  1442     /// Before the use of these functions,
  1443     /// either run() or start() must be called.
  1444     ///@{
  1445     /// \brief Checks if a node is reachable from the root.
  1446     ///
  1447     /// Returns \c true if \c v is reachable from the root(s).
  1448     /// \warning The source nodes are inditated as unreachable.
  1449     /// \pre Either \ref run() or \ref start()
  1450     /// must be called before using this function.
  1451     ///
  1452     bool reached(Node v) { return (*_reached)[v]; }
  1453     ///@}
  1454   };
  1455 
  1456 
  1457 } //END OF NAMESPACE LEMON
  1458 
  1459 #endif
  1460