lemon/dfs.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sun, 30 Nov 2008 14:51:05 +0100
changeset 402 235be9d4b6ab
parent 313 64f8f7cc6168
child 405 6b9057cdcd8b
child 906 e24922c56bc2
permissions -rw-r--r--
Many doc improvements for Circulation (#175)

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