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