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