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