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