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