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