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