lemon/dfs.h
author Balazs Dezso <deba@inf.elte.hu>
Wed, 23 Jul 2008 19:32:48 +0200
changeset 233 28239207a8a3
parent 210 81cfc04531e8
child 247 f1158744a112
permissions -rw-r--r--
Unify DynArcLookUp interface (ticket #127)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     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/bits/path_dump.h>
    28 #include <lemon/core.h>
    29 #include <lemon/error.h>
    30 #include <lemon/maps.h>
    31 
    32 #include <lemon/concept_check.h>
    33 
    34 namespace lemon {
    35 
    36 
    37   ///Default traits class of Dfs class.
    38 
    39   ///Default traits class of Dfs class.
    40   ///\tparam GR Digraph type.
    41   template<class GR>
    42   struct DfsDefaultTraits
    43   {
    44     ///The digraph type the algorithm runs on.
    45     typedef GR Digraph;
    46     ///\brief The type of the map that stores the last
    47     ///arcs of the %DFS paths.
    48     ///
    49     ///The type of the map that stores the last
    50     ///arcs of the %DFS paths.
    51     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    52     ///
    53     typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
    54     ///Instantiates a PredMap.
    55 
    56     ///This function instantiates a \ref PredMap.
    57     ///\param G is the digraph, to which we would like to define the PredMap.
    58     ///\todo The digraph alone may be insufficient to initialize
    59     static PredMap *createPredMap(const GR &G)
    60     {
    61       return new PredMap(G);
    62     }
    63 
    64     ///The type of the map that indicates which nodes are processed.
    65 
    66     ///The type of the map that indicates which nodes are processed.
    67     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    68     ///\todo named parameter to set this type, function to read and write.
    69     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    70     ///Instantiates a ProcessedMap.
    71 
    72     ///This function instantiates a \ref ProcessedMap.
    73     ///\param g is the digraph, to which
    74     ///we would like to define the \ref ProcessedMap
    75 #ifdef DOXYGEN
    76     static ProcessedMap *createProcessedMap(const GR &g)
    77 #else
    78     static ProcessedMap *createProcessedMap(const GR &)
    79 #endif
    80     {
    81       return new ProcessedMap();
    82     }
    83     ///The type of the map that indicates which nodes are reached.
    84 
    85     ///The type of the map that indicates which nodes are reached.
    86     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    87     ///\todo named parameter to set this type, function to read and write.
    88     typedef typename Digraph::template NodeMap<bool> ReachedMap;
    89     ///Instantiates a ReachedMap.
    90 
    91     ///This function instantiates a \ref ReachedMap.
    92     ///\param G is the digraph, to which
    93     ///we would like to define the \ref ReachedMap.
    94     static ReachedMap *createReachedMap(const GR &G)
    95     {
    96       return new ReachedMap(G);
    97     }
    98     ///The type of the map that stores the dists of the nodes.
    99 
   100     ///The type of the map that stores the dists of the nodes.
   101     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   102     ///
   103     typedef typename Digraph::template NodeMap<int> DistMap;
   104     ///Instantiates a DistMap.
   105 
   106     ///This function instantiates a \ref DistMap.
   107     ///\param G is the digraph, to which we would like to define
   108     ///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
   812     ///the \ref DistMap
   813 #ifdef DOXYGEN
   814     static DistMap *createDistMap(const GR &g)
   815 #else
   816     static DistMap *createDistMap(const GR &)
   817 #endif
   818     {
   819       return new DistMap();
   820     }
   821   };
   822 
   823   /// Default traits used by \ref DfsWizard
   824 
   825   /// To make it easier to use Dfs algorithm
   826   ///we have created a wizard class.
   827   /// This \ref DfsWizard class needs default traits,
   828   ///as well as the \ref Dfs class.
   829   /// The \ref DfsWizardBase is a class to be the default traits of the
   830   /// \ref DfsWizard class.
   831   template<class GR>
   832   class DfsWizardBase : public DfsWizardDefaultTraits<GR>
   833   {
   834 
   835     typedef DfsWizardDefaultTraits<GR> Base;
   836   protected:
   837     /// Type of the nodes in the digraph.
   838     typedef typename Base::Digraph::Node Node;
   839 
   840     /// Pointer to the underlying digraph.
   841     void *_g;
   842     ///Pointer to the map of reached nodes.
   843     void *_reached;
   844     ///Pointer to the map of processed nodes.
   845     void *_processed;
   846     ///Pointer to the map of predecessors arcs.
   847     void *_pred;
   848     ///Pointer to the map of distances.
   849     void *_dist;
   850     ///Pointer to the source node.
   851     Node _source;
   852 
   853     public:
   854     /// Constructor.
   855 
   856     /// This constructor does not require parameters, therefore it initiates
   857     /// all of the attributes to default values (0, INVALID).
   858     DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
   859                            _dist(0), _source(INVALID) {}
   860 
   861     /// Constructor.
   862 
   863     /// This constructor requires some parameters,
   864     /// listed in the parameters list.
   865     /// Others are initiated to 0.
   866     /// \param g is the initial value of  \ref _g
   867     /// \param s is the initial value of  \ref _source
   868     DfsWizardBase(const GR &g, Node s=INVALID) :
   869       _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
   870       _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
   871 
   872   };
   873 
   874   /// A class to make the usage of the Dfs algorithm easier
   875 
   876   /// This class is created to make it easier to use the Dfs algorithm.
   877   /// It uses the functions and features of the plain \ref Dfs,
   878   /// but it is much simpler to use it.
   879   ///
   880   /// Simplicity means that the way to change the types defined
   881   /// in the traits class is based on functions that returns the new class
   882   /// and not on templatable built-in classes.
   883   /// When using the plain \ref Dfs
   884   /// the new class with the modified type comes from
   885   /// the original class by using the ::
   886   /// operator. In the case of \ref DfsWizard only
   887   /// a function have to be called and it will
   888   /// return the needed class.
   889   ///
   890   /// It does not have own \ref run method. When its \ref run method is called
   891   /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run
   892   /// method of it.
   893   template<class TR>
   894   class DfsWizard : public TR
   895   {
   896     typedef TR Base;
   897 
   898     ///The type of the underlying digraph.
   899     typedef typename TR::Digraph Digraph;
   900     //\e
   901     typedef typename Digraph::Node Node;
   902     //\e
   903     typedef typename Digraph::NodeIt NodeIt;
   904     //\e
   905     typedef typename Digraph::Arc Arc;
   906     //\e
   907     typedef typename Digraph::OutArcIt OutArcIt;
   908 
   909     ///\brief The type of the map that stores
   910     ///the reached nodes
   911     typedef typename TR::ReachedMap ReachedMap;
   912     ///\brief The type of the map that stores
   913     ///the processed nodes
   914     typedef typename TR::ProcessedMap ProcessedMap;
   915     ///\brief The type of the map that stores the last
   916     ///arcs of the %DFS paths.
   917     typedef typename TR::PredMap PredMap;
   918     ///The type of the map that stores the distances of the nodes.
   919     typedef typename TR::DistMap DistMap;
   920 
   921   public:
   922     /// Constructor.
   923     DfsWizard() : TR() {}
   924 
   925     /// Constructor that requires parameters.
   926 
   927     /// Constructor that requires parameters.
   928     /// These parameters will be the default values for the traits class.
   929     DfsWizard(const Digraph &g, Node s=INVALID) :
   930       TR(g,s) {}
   931 
   932     ///Copy constructor
   933     DfsWizard(const TR &b) : TR(b) {}
   934 
   935     ~DfsWizard() {}
   936 
   937     ///Runs Dfs algorithm from a given node.
   938 
   939     ///Runs Dfs algorithm from a given node.
   940     ///The node can be given by the \ref source function.
   941     void run()
   942     {
   943       if(Base::_source==INVALID) throw UninitializedParameter();
   944       Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
   945       if(Base::_reached)
   946         alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
   947       if(Base::_processed)
   948         alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
   949       if(Base::_pred)
   950         alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
   951       if(Base::_dist)
   952         alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
   953       alg.run(Base::_source);
   954     }
   955 
   956     ///Runs Dfs algorithm from the given node.
   957 
   958     ///Runs Dfs algorithm from the given node.
   959     ///\param s is the given source.
   960     void run(Node s)
   961     {
   962       Base::_source=s;
   963       run();
   964     }
   965 
   966     template<class T>
   967     struct DefPredMapBase : public Base {
   968       typedef T PredMap;
   969       static PredMap *createPredMap(const Digraph &) { return 0; };
   970       DefPredMapBase(const TR &b) : TR(b) {}
   971     };
   972 
   973     ///\brief \ref named-templ-param "Named parameter"
   974     ///function for setting PredMap type
   975     ///
   976     /// \ref named-templ-param "Named parameter"
   977     ///function for setting PredMap type
   978     ///
   979     template<class T>
   980     DfsWizard<DefPredMapBase<T> > predMap(const T &t)
   981     {
   982       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
   983       return DfsWizard<DefPredMapBase<T> >(*this);
   984     }
   985 
   986 
   987     template<class T>
   988     struct DefReachedMapBase : public Base {
   989       typedef T ReachedMap;
   990       static ReachedMap *createReachedMap(const Digraph &) { return 0; };
   991       DefReachedMapBase(const TR &b) : TR(b) {}
   992     };
   993 
   994     ///\brief \ref named-templ-param "Named parameter"
   995     ///function for setting ReachedMap
   996     ///
   997     /// \ref named-templ-param "Named parameter"
   998     ///function for setting ReachedMap
   999     ///
  1000     template<class T>
  1001     DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
  1002     {
  1003       Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
  1004       return DfsWizard<DefReachedMapBase<T> >(*this);
  1005     }
  1006 
  1007 
  1008     template<class T>
  1009     struct DefProcessedMapBase : public Base {
  1010       typedef T ProcessedMap;
  1011       static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
  1012       DefProcessedMapBase(const TR &b) : TR(b) {}
  1013     };
  1014 
  1015     ///\brief \ref named-templ-param "Named parameter"
  1016     ///function for setting ProcessedMap
  1017     ///
  1018     /// \ref named-templ-param "Named parameter"
  1019     ///function for setting ProcessedMap
  1020     ///
  1021     template<class T>
  1022     DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
  1023     {
  1024       Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
  1025       return DfsWizard<DefProcessedMapBase<T> >(*this);
  1026     }
  1027 
  1028     template<class T>
  1029     struct DefDistMapBase : public Base {
  1030       typedef T DistMap;
  1031       static DistMap *createDistMap(const Digraph &) { return 0; };
  1032       DefDistMapBase(const TR &b) : TR(b) {}
  1033     };
  1034 
  1035     ///\brief \ref named-templ-param "Named parameter"
  1036     ///function for setting DistMap type
  1037     ///
  1038     /// \ref named-templ-param "Named parameter"
  1039     ///function for setting DistMap type
  1040     ///
  1041     template<class T>
  1042     DfsWizard<DefDistMapBase<T> > distMap(const T &t)
  1043     {
  1044       Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
  1045       return DfsWizard<DefDistMapBase<T> >(*this);
  1046     }
  1047 
  1048     /// Sets the source node, from which the Dfs algorithm runs.
  1049 
  1050     /// Sets the source node, from which the Dfs algorithm runs.
  1051     /// \param s is the source node.
  1052     DfsWizard<TR> &source(Node s)
  1053     {
  1054       Base::_source=s;
  1055       return *this;
  1056     }
  1057 
  1058   };
  1059 
  1060   ///Function type interface for Dfs algorithm.
  1061 
  1062   ///\ingroup search
  1063   ///Function type interface for Dfs algorithm.
  1064   ///
  1065   ///This function also has several
  1066   ///\ref named-templ-func-param "named parameters",
  1067   ///they are declared as the members of class \ref DfsWizard.
  1068   ///The following
  1069   ///example shows how to use these parameters.
  1070   ///\code
  1071   ///  dfs(g,source).predMap(preds).run();
  1072   ///\endcode
  1073   ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
  1074   ///to the end of the parameter list.
  1075   ///\sa DfsWizard
  1076   ///\sa Dfs
  1077   template<class GR>
  1078   DfsWizard<DfsWizardBase<GR> >
  1079   dfs(const GR &g,typename GR::Node s=INVALID)
  1080   {
  1081     return DfsWizard<DfsWizardBase<GR> >(g,s);
  1082   }
  1083 
  1084 #ifdef DOXYGEN
  1085   /// \brief Visitor class for dfs.
  1086   ///
  1087   /// It gives a simple interface for a functional interface for dfs
  1088   /// traversal. The traversal on a linear data structure.
  1089   template <typename _Digraph>
  1090   struct DfsVisitor {
  1091     typedef _Digraph Digraph;
  1092     typedef typename Digraph::Arc Arc;
  1093     typedef typename Digraph::Node Node;
  1094     /// \brief Called when the arc reach a node.
  1095     ///
  1096     /// It is called when the dfs find an arc which target is not
  1097     /// reached yet.
  1098     void discover(const Arc& arc) {}
  1099     /// \brief Called when the node reached first time.
  1100     ///
  1101     /// It is Called when the node reached first time.
  1102     void reach(const Node& node) {}
  1103     /// \brief Called when we step back on an arc.
  1104     ///
  1105     /// It is called when the dfs should step back on the arc.
  1106     void backtrack(const Arc& arc) {}
  1107     /// \brief Called when we step back from the node.
  1108     ///
  1109     /// It is called when we step back from the node.
  1110     void leave(const Node& node) {}
  1111     /// \brief Called when the arc examined but target of the arc
  1112     /// already discovered.
  1113     ///
  1114     /// It called when the arc examined but the target of the arc
  1115     /// already discovered.
  1116     void examine(const Arc& arc) {}
  1117     /// \brief Called for the source node of the dfs.
  1118     ///
  1119     /// It is called for the source node of the dfs.
  1120     void start(const Node& node) {}
  1121     /// \brief Called when we leave the source node of the dfs.
  1122     ///
  1123     /// It is called when we leave the source node of the dfs.
  1124     void stop(const Node& node) {}
  1125 
  1126   };
  1127 #else
  1128   template <typename _Digraph>
  1129   struct DfsVisitor {
  1130     typedef _Digraph Digraph;
  1131     typedef typename Digraph::Arc Arc;
  1132     typedef typename Digraph::Node Node;
  1133     void discover(const Arc&) {}
  1134     void reach(const Node&) {}
  1135     void backtrack(const Arc&) {}
  1136     void leave(const Node&) {}
  1137     void examine(const Arc&) {}
  1138     void start(const Node&) {}
  1139     void stop(const Node&) {}
  1140 
  1141     template <typename _Visitor>
  1142     struct Constraints {
  1143       void constraints() {
  1144         Arc arc;
  1145         Node node;
  1146         visitor.discover(arc);
  1147         visitor.reach(node);
  1148         visitor.backtrack(arc);
  1149         visitor.leave(node);
  1150         visitor.examine(arc);
  1151         visitor.start(node);
  1152         visitor.stop(arc);
  1153       }
  1154       _Visitor& visitor;
  1155     };
  1156   };
  1157 #endif
  1158 
  1159   /// \brief Default traits class of DfsVisit class.
  1160   ///
  1161   /// Default traits class of DfsVisit class.
  1162   /// \tparam _Digraph Digraph type.
  1163   template<class _Digraph>
  1164   struct DfsVisitDefaultTraits {
  1165 
  1166     /// \brief The digraph type the algorithm runs on.
  1167     typedef _Digraph Digraph;
  1168 
  1169     /// \brief The type of the map that indicates which nodes are reached.
  1170     ///
  1171     /// The type of the map that indicates which nodes are reached.
  1172     /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
  1173     /// \todo named parameter to set this type, function to read and write.
  1174     typedef typename Digraph::template NodeMap<bool> ReachedMap;
  1175 
  1176     /// \brief Instantiates a ReachedMap.
  1177     ///
  1178     /// This function instantiates a \ref ReachedMap.
  1179     /// \param digraph is the digraph, to which
  1180     /// we would like to define the \ref ReachedMap.
  1181     static ReachedMap *createReachedMap(const Digraph &digraph) {
  1182       return new ReachedMap(digraph);
  1183     }
  1184 
  1185   };
  1186 
  1187   /// %DFS Visit algorithm class.
  1188 
  1189   /// \ingroup search
  1190   /// This class provides an efficient implementation of the %DFS algorithm
  1191   /// with visitor interface.
  1192   ///
  1193   /// The %DfsVisit class provides an alternative interface to the Dfs
  1194   /// class. It works with callback mechanism, the DfsVisit object calls
  1195   /// on every dfs event the \c Visitor class member functions.
  1196   ///
  1197   /// \tparam _Digraph The digraph type the algorithm runs on.
  1198   /// 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   /// \tparam _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   /// \tparam _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