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