lemon/dfs.h
author Peter Kovacs <kpeter@inf.elte.hu>
Wed, 08 Oct 2008 12:20:09 +0200
changeset 300 8c05947fc107
parent 290 f6899946c1ac
parent 288 47b3a3b67837
child 301 9db8964f0cf6
permissions -rw-r--r--
Revert faulty changes of [dc9e8d2c0df9]
     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/assert.h>
    31 #include <lemon/maps.h>
    32 #include <lemon/path.h>
    33 
    34 namespace lemon {
    35 
    36   ///Default traits class of Dfs class.
    37 
    38   ///Default traits class of Dfs class.
    39   ///\tparam GR Digraph type.
    40   template<class GR>
    41   struct DfsDefaultTraits
    42   {
    43     ///The type of the digraph the algorithm runs on.
    44     typedef GR Digraph;
    45 
    46     ///\brief The type of the map that stores the predecessor
    47     ///arcs of the %DFS paths.
    48     ///
    49     ///The type of the map that stores the predecessor
    50     ///arcs of the %DFS paths.
    51     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    52     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
    53     ///Instantiates a \ref PredMap.
    54 
    55     ///This function instantiates a \ref PredMap.
    56     ///\param g is the digraph, to which we would like to define the
    57     ///\ref PredMap.
    58     static PredMap *createPredMap(const Digraph &g)
    59     {
    60       return new PredMap(g);
    61     }
    62 
    63     ///The type of the map that indicates which nodes are processed.
    64 
    65     ///The type of the map that indicates which nodes are processed.
    66     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    67     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    68     ///Instantiates a \ref 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 meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    86     typedef typename Digraph::template NodeMap<bool> ReachedMap;
    87     ///Instantiates a \ref ReachedMap.
    88 
    89     ///This function instantiates a \ref ReachedMap.
    90     ///\param g is the digraph, to which
    91     ///we would like to define the \ref ReachedMap.
    92     static ReachedMap *createReachedMap(const Digraph &g)
    93     {
    94       return new ReachedMap(g);
    95     }
    96 
    97     ///The type of the map that stores the distances of the nodes.
    98 
    99     ///The type of the map that stores the distances of the nodes.
   100     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   101     typedef typename Digraph::template NodeMap<int> DistMap;
   102     ///Instantiates a \ref DistMap.
   103 
   104     ///This function instantiates a \ref DistMap.
   105     ///\param g is the digraph, to which we would like to define the
   106     ///\ref DistMap.
   107     static DistMap *createDistMap(const Digraph &g)
   108     {
   109       return new DistMap(g);
   110     }
   111   };
   112 
   113   ///%DFS algorithm class.
   114 
   115   ///\ingroup search
   116   ///This class provides an efficient implementation of the %DFS algorithm.
   117   ///
   118   ///There is also a \ref dfs() "function-type interface" for the DFS
   119   ///algorithm, which is convenient in the simplier cases and it can be
   120   ///used easier.
   121   ///
   122   ///\tparam GR The type of the digraph the algorithm runs on.
   123   ///The default value is \ref ListDigraph. The value of GR is not used
   124   ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
   125   ///\tparam TR Traits class to set various data types used by the algorithm.
   126   ///The default traits class is
   127   ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
   128   ///See \ref DfsDefaultTraits for the documentation of
   129   ///a Dfs traits class.
   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 traits class.
   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     ///\ref PredMap type.
   231     ///
   232     ///\ref named-templ-param "Named parameter" for setting
   233     ///\ref PredMap type.
   234     template <class T>
   235     struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
   236       typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
   237     };
   238 
   239     template <class T>
   240     struct SetDistMapTraits : public Traits {
   241       typedef T DistMap;
   242       static DistMap *createDistMap(const Digraph &)
   243       {
   244         LEMON_ASSERT(false, "DistMap is not initialized");
   245         return 0; // ignore warnings
   246       }
   247     };
   248     ///\brief \ref named-templ-param "Named parameter" for setting
   249     ///\ref DistMap type.
   250     ///
   251     ///\ref named-templ-param "Named parameter" for setting
   252     ///\ref DistMap type.
   253     template <class T>
   254     struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
   255       typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
   256     };
   257 
   258     template <class T>
   259     struct SetReachedMapTraits : public Traits {
   260       typedef T ReachedMap;
   261       static ReachedMap *createReachedMap(const Digraph &)
   262       {
   263         LEMON_ASSERT(false, "ReachedMap is not initialized");
   264         return 0; // ignore warnings
   265       }
   266     };
   267     ///\brief \ref named-templ-param "Named parameter" for setting
   268     ///\ref ReachedMap type.
   269     ///
   270     ///\ref named-templ-param "Named parameter" for setting
   271     ///\ref ReachedMap type.
   272     template <class T>
   273     struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
   274       typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
   275     };
   276 
   277     template <class T>
   278     struct SetProcessedMapTraits : public Traits {
   279       typedef T ProcessedMap;
   280       static ProcessedMap *createProcessedMap(const Digraph &)
   281       {
   282         LEMON_ASSERT(false, "ProcessedMap is not initialized");
   283         return 0; // ignore warnings
   284       }
   285     };
   286     ///\brief \ref named-templ-param "Named parameter" for setting
   287     ///\ref ProcessedMap type.
   288     ///
   289     ///\ref named-templ-param "Named parameter" for setting
   290     ///\ref ProcessedMap type.
   291     template <class T>
   292     struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
   293       typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
   294     };
   295 
   296     struct SetStandardProcessedMapTraits : public Traits {
   297       typedef typename Digraph::template NodeMap<bool> ProcessedMap;
   298       static ProcessedMap *createProcessedMap(const Digraph &g)
   299       {
   300         return new ProcessedMap(g);
   301       }
   302     };
   303     ///\brief \ref named-templ-param "Named parameter" for setting
   304     ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   305     ///
   306     ///\ref named-templ-param "Named parameter" for setting
   307     ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
   308     ///If you don't set it explicitly, it will be automatically allocated.
   309     struct SetStandardProcessedMap :
   310       public Dfs< Digraph, SetStandardProcessedMapTraits > {
   311       typedef Dfs< Digraph, SetStandardProcessedMapTraits > Create;
   312     };
   313 
   314     ///@}
   315 
   316   public:
   317 
   318     ///Constructor.
   319 
   320     ///Constructor.
   321     ///\param g The digraph the algorithm runs on.
   322     Dfs(const Digraph &g) :
   323       G(&g),
   324       _pred(NULL), local_pred(false),
   325       _dist(NULL), local_dist(false),
   326       _reached(NULL), local_reached(false),
   327       _processed(NULL), local_processed(false)
   328     { }
   329 
   330     ///Destructor.
   331     ~Dfs()
   332     {
   333       if(local_pred) delete _pred;
   334       if(local_dist) delete _dist;
   335       if(local_reached) delete _reached;
   336       if(local_processed) delete _processed;
   337     }
   338 
   339     ///Sets the map that stores the predecessor arcs.
   340 
   341     ///Sets the map that stores the predecessor arcs.
   342     ///If you don't use this function before calling \ref run(),
   343     ///it will allocate one. The destructor deallocates this
   344     ///automatically allocated map, of course.
   345     ///\return <tt> (*this) </tt>
   346     Dfs &predMap(PredMap &m)
   347     {
   348       if(local_pred) {
   349         delete _pred;
   350         local_pred=false;
   351       }
   352       _pred = &m;
   353       return *this;
   354     }
   355 
   356     ///Sets the map that indicates which nodes are reached.
   357 
   358     ///Sets the map that indicates which nodes are reached.
   359     ///If you don't use this function before calling \ref run(),
   360     ///it will allocate one. The destructor deallocates this
   361     ///automatically allocated map, of course.
   362     ///\return <tt> (*this) </tt>
   363     Dfs &reachedMap(ReachedMap &m)
   364     {
   365       if(local_reached) {
   366         delete _reached;
   367         local_reached=false;
   368       }
   369       _reached = &m;
   370       return *this;
   371     }
   372 
   373     ///Sets the map that indicates which nodes are processed.
   374 
   375     ///Sets the map that indicates which nodes are processed.
   376     ///If you don't use this function before calling \ref run(),
   377     ///it will allocate one. The destructor deallocates this
   378     ///automatically allocated map, of course.
   379     ///\return <tt> (*this) </tt>
   380     Dfs &processedMap(ProcessedMap &m)
   381     {
   382       if(local_processed) {
   383         delete _processed;
   384         local_processed=false;
   385       }
   386       _processed = &m;
   387       return *this;
   388     }
   389 
   390     ///Sets the map that stores the distances of the nodes.
   391 
   392     ///Sets the map that stores the distances of the nodes calculated by
   393     ///the algorithm.
   394     ///If you don't use this function before calling \ref run(),
   395     ///it will allocate one. The destructor deallocates this
   396     ///automatically allocated map, of course.
   397     ///\return <tt> (*this) </tt>
   398     Dfs &distMap(DistMap &m)
   399     {
   400       if(local_dist) {
   401         delete _dist;
   402         local_dist=false;
   403       }
   404       _dist = &m;
   405       return *this;
   406     }
   407 
   408   public:
   409 
   410     ///\name Execution control
   411     ///The simplest way to execute the algorithm is to use
   412     ///one of the member functions called \ref lemon::Dfs::run() "run()".
   413     ///\n
   414     ///If you need more control on the execution, first you must call
   415     ///\ref lemon::Dfs::init() "init()", then you can add a source node
   416     ///with \ref lemon::Dfs::addSource() "addSource()".
   417     ///Finally \ref lemon::Dfs::start() "start()" will perform the
   418     ///actual path computation.
   419 
   420     ///@{
   421 
   422     ///Initializes the internal data structures.
   423 
   424     ///Initializes the internal data structures.
   425     ///
   426     void init()
   427     {
   428       create_maps();
   429       _stack.resize(countNodes(*G));
   430       _stack_head=-1;
   431       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
   432         _pred->set(u,INVALID);
   433         _reached->set(u,false);
   434         _processed->set(u,false);
   435       }
   436     }
   437 
   438     ///Adds a new source node.
   439 
   440     ///Adds a new source node to the set of nodes to be processed.
   441     ///
   442     ///\pre The stack must be empty. (Otherwise the algorithm gives
   443     ///false results.)
   444     ///
   445     ///\warning Distances will be wrong (or at least strange) in case of
   446     ///multiple sources.
   447     void addSource(Node s)
   448     {
   449       LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
   450       if(!(*_reached)[s])
   451         {
   452           _reached->set(s,true);
   453           _pred->set(s,INVALID);
   454           OutArcIt e(*G,s);
   455           if(e!=INVALID) {
   456             _stack[++_stack_head]=e;
   457             _dist->set(s,_stack_head);
   458           }
   459           else {
   460             _processed->set(s,true);
   461             _dist->set(s,0);
   462           }
   463         }
   464     }
   465 
   466     ///Processes the next arc.
   467 
   468     ///Processes the next arc.
   469     ///
   470     ///\return The processed arc.
   471     ///
   472     ///\pre The stack must not be empty.
   473     Arc processNextArc()
   474     {
   475       Node m;
   476       Arc e=_stack[_stack_head];
   477       if(!(*_reached)[m=G->target(e)]) {
   478         _pred->set(m,e);
   479         _reached->set(m,true);
   480         ++_stack_head;
   481         _stack[_stack_head] = OutArcIt(*G, m);
   482         _dist->set(m,_stack_head);
   483       }
   484       else {
   485         m=G->source(e);
   486         ++_stack[_stack_head];
   487       }
   488       while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
   489         _processed->set(m,true);
   490         --_stack_head;
   491         if(_stack_head>=0) {
   492           m=G->source(_stack[_stack_head]);
   493           ++_stack[_stack_head];
   494         }
   495       }
   496       return e;
   497     }
   498 
   499     ///Next arc to be processed.
   500 
   501     ///Next arc to be processed.
   502     ///
   503     ///\return The next arc to be processed or \c INVALID if the stack
   504     ///is empty.
   505     OutArcIt nextArc() const
   506     {
   507       return _stack_head>=0?_stack[_stack_head]:INVALID;
   508     }
   509 
   510     ///\brief Returns \c false if there are nodes
   511     ///to be processed.
   512     ///
   513     ///Returns \c false if there are nodes
   514     ///to be processed in the queue (stack).
   515     bool emptyQueue() const { return _stack_head<0; }
   516 
   517     ///Returns the number of the nodes to be processed.
   518 
   519     ///Returns the number of the nodes to be processed in the queue (stack).
   520     int queueSize() const { return _stack_head+1; }
   521 
   522     ///Executes the algorithm.
   523 
   524     ///Executes the algorithm.
   525     ///
   526     ///This method runs the %DFS algorithm from the root node
   527     ///in order to compute the DFS path to each node.
   528     ///
   529     /// The algorithm computes
   530     ///- the %DFS tree,
   531     ///- the distance of each node from the root in the %DFS tree.
   532     ///
   533     ///\pre init() must be called and a root node should be
   534     ///added with addSource() before using this function.
   535     ///
   536     ///\note <tt>d.start()</tt> is just a shortcut of the following code.
   537     ///\code
   538     ///  while ( !d.emptyQueue() ) {
   539     ///    d.processNextArc();
   540     ///  }
   541     ///\endcode
   542     void start()
   543     {
   544       while ( !emptyQueue() ) processNextArc();
   545     }
   546 
   547     ///Executes the algorithm until the given target node is reached.
   548 
   549     ///Executes the algorithm until the given target node is reached.
   550     ///
   551     ///This method runs the %DFS algorithm from the root node
   552     ///in order to compute the DFS path to \c t.
   553     ///
   554     ///The algorithm computes
   555     ///- the %DFS path to \c t,
   556     ///- the distance of \c t from the root in the %DFS tree.
   557     ///
   558     ///\pre init() must be called and a root node should be
   559     ///added with addSource() before using this function.
   560     void start(Node t)
   561     {
   562       while ( !emptyQueue() && G->target(_stack[_stack_head])!=t )
   563         processNextArc();
   564     }
   565 
   566     ///Executes the algorithm until a condition is met.
   567 
   568     ///Executes the algorithm until a condition is met.
   569     ///
   570     ///This method runs the %DFS algorithm from the root node
   571     ///until an arc \c a with <tt>am[a]</tt> true is found.
   572     ///
   573     ///\param am A \c bool (or convertible) arc map. The algorithm
   574     ///will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
   575     ///
   576     ///\return The reached arc \c a with <tt>am[a]</tt> true or
   577     ///\c INVALID if no such arc was found.
   578     ///
   579     ///\pre init() must be called and a root node should be
   580     ///added with addSource() before using this function.
   581     ///
   582     ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
   583     ///not a node map.
   584     template<class ArcBoolMap>
   585     Arc start(const ArcBoolMap &am)
   586     {
   587       while ( !emptyQueue() && !am[_stack[_stack_head]] )
   588         processNextArc();
   589       return emptyQueue() ? INVALID : _stack[_stack_head];
   590     }
   591 
   592     ///Runs the algorithm from the given source node.
   593 
   594     ///This method runs the %DFS algorithm from node \c s
   595     ///in order to compute the DFS path to each node.
   596     ///
   597     ///The algorithm computes
   598     ///- the %DFS tree,
   599     ///- the distance of each node from the root in the %DFS tree.
   600     ///
   601     ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
   602     ///\code
   603     ///  d.init();
   604     ///  d.addSource(s);
   605     ///  d.start();
   606     ///\endcode
   607     void run(Node s) {
   608       init();
   609       addSource(s);
   610       start();
   611     }
   612 
   613     ///Finds the %DFS path between \c s and \c t.
   614 
   615     ///This method runs the %DFS algorithm from node \c s
   616     ///in order to compute the DFS path to node \c t
   617     ///(it stops searching when \c t is processed)
   618     ///
   619     ///\return \c true if \c t is reachable form \c s.
   620     ///
   621     ///\note Apart from the return value, <tt>d.run(s,t)</tt> is
   622     ///just a shortcut of the following code.
   623     ///\code
   624     ///  d.init();
   625     ///  d.addSource(s);
   626     ///  d.start(t);
   627     ///\endcode
   628     bool run(Node s,Node t) {
   629       init();
   630       addSource(s);
   631       start(t);
   632       return reached(t);
   633     }
   634 
   635     ///Runs the algorithm to visit all nodes in the digraph.
   636 
   637     ///This method runs the %DFS algorithm in order to compute the
   638     ///%DFS path to each node.
   639     ///
   640     ///The algorithm computes
   641     ///- the %DFS tree,
   642     ///- the distance of each node from the root in the %DFS tree.
   643     ///
   644     ///\note <tt>d.run()</tt> is just a shortcut of the following code.
   645     ///\code
   646     ///  d.init();
   647     ///  for (NodeIt n(digraph); n != INVALID; ++n) {
   648     ///    if (!d.reached(n)) {
   649     ///      d.addSource(n);
   650     ///      d.start();
   651     ///    }
   652     ///  }
   653     ///\endcode
   654     void run() {
   655       init();
   656       for (NodeIt it(*G); it != INVALID; ++it) {
   657         if (!reached(it)) {
   658           addSource(it);
   659           start();
   660         }
   661       }
   662     }
   663 
   664     ///@}
   665 
   666     ///\name Query Functions
   667     ///The result of the %DFS algorithm can be obtained using these
   668     ///functions.\n
   669     ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
   670     ///"start()" must be called before using them.
   671 
   672     ///@{
   673 
   674     ///The DFS path to a node.
   675 
   676     ///Returns the DFS path to a node.
   677     ///
   678     ///\warning \c t should be reachable from the root.
   679     ///
   680     ///\pre Either \ref run() or \ref start() must be called before
   681     ///using this function.
   682     Path path(Node t) const { return Path(*G, *_pred, t); }
   683 
   684     ///The distance of a node from the root.
   685 
   686     ///Returns the distance of a node from the root.
   687     ///
   688     ///\warning If node \c v is not reachable from the root, then
   689     ///the return value of this function is undefined.
   690     ///
   691     ///\pre Either \ref run() or \ref start() must be called before
   692     ///using this function.
   693     int dist(Node v) const { return (*_dist)[v]; }
   694 
   695     ///Returns the 'previous arc' of the %DFS tree for a node.
   696 
   697     ///This function returns the 'previous arc' of the %DFS tree for the
   698     ///node \c v, i.e. it returns the last arc of a %DFS path from the
   699     ///root to \c v. It is \c INVALID
   700     ///if \c v is not reachable from the root(s) or if \c v is a root.
   701     ///
   702     ///The %DFS tree used here is equal to the %DFS tree used in
   703     ///\ref predNode().
   704     ///
   705     ///\pre Either \ref run() or \ref start() must be called before using
   706     ///this function.
   707     Arc predArc(Node v) const { return (*_pred)[v];}
   708 
   709     ///Returns the 'previous node' of the %DFS tree.
   710 
   711     ///This function returns the 'previous node' of the %DFS
   712     ///tree for the node \c v, i.e. it returns the last but one node
   713     ///from a %DFS path from the root to \c v. It is \c INVALID
   714     ///if \c v is not reachable from the root(s) or if \c v is a root.
   715     ///
   716     ///The %DFS tree used here is equal to the %DFS tree used in
   717     ///\ref predArc().
   718     ///
   719     ///\pre Either \ref run() or \ref start() must be called before
   720     ///using this function.
   721     Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
   722                                   G->source((*_pred)[v]); }
   723 
   724     ///\brief Returns a const reference to the node map that stores the
   725     ///distances of the nodes.
   726     ///
   727     ///Returns a const reference to the node map that stores the
   728     ///distances of the nodes calculated by the algorithm.
   729     ///
   730     ///\pre Either \ref run() or \ref init()
   731     ///must be called before using this function.
   732     const DistMap &distMap() const { return *_dist;}
   733 
   734     ///\brief Returns a const reference to the node map that stores the
   735     ///predecessor arcs.
   736     ///
   737     ///Returns a const reference to the node map that stores the predecessor
   738     ///arcs, which form the DFS tree.
   739     ///
   740     ///\pre Either \ref run() or \ref init()
   741     ///must be called before using this function.
   742     const PredMap &predMap() const { return *_pred;}
   743 
   744     ///Checks if a node is reachable from the root(s).
   745 
   746     ///Returns \c true if \c v is reachable from the root(s).
   747     ///\pre Either \ref run() or \ref start()
   748     ///must be called before using this function.
   749     bool reached(Node v) const { return (*_reached)[v]; }
   750 
   751     ///@}
   752   };
   753 
   754   ///Default traits class of dfs() function.
   755 
   756   ///Default traits class of dfs() function.
   757   ///\tparam GR Digraph type.
   758   template<class GR>
   759   struct DfsWizardDefaultTraits
   760   {
   761     ///The type of the digraph the algorithm runs on.
   762     typedef GR Digraph;
   763 
   764     ///\brief The type of the map that stores the predecessor
   765     ///arcs of the %DFS paths.
   766     ///
   767     ///The type of the map that stores the predecessor
   768     ///arcs of the %DFS paths.
   769     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   770     typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
   771     ///Instantiates a \ref PredMap.
   772 
   773     ///This function instantiates a \ref PredMap.
   774     ///\param g is the digraph, to which we would like to define the
   775     ///\ref PredMap.
   776     static PredMap *createPredMap(const Digraph &g)
   777     {
   778       return new PredMap(g);
   779     }
   780 
   781     ///The type of the map that indicates which nodes are processed.
   782 
   783     ///The type of the map that indicates which nodes are processed.
   784     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   785     ///By default it is a NullMap.
   786     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
   787     ///Instantiates a \ref ProcessedMap.
   788 
   789     ///This function instantiates a \ref ProcessedMap.
   790     ///\param g is the digraph, to which
   791     ///we would like to define the \ref ProcessedMap.
   792 #ifdef DOXYGEN
   793     static ProcessedMap *createProcessedMap(const Digraph &g)
   794 #else
   795     static ProcessedMap *createProcessedMap(const Digraph &)
   796 #endif
   797     {
   798       return new ProcessedMap();
   799     }
   800 
   801     ///The type of the map that indicates which nodes are reached.
   802 
   803     ///The type of the map that indicates which nodes are reached.
   804     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
   805     typedef typename Digraph::template NodeMap<bool> ReachedMap;
   806     ///Instantiates a \ref ReachedMap.
   807 
   808     ///This function instantiates a \ref ReachedMap.
   809     ///\param g is the digraph, to which
   810     ///we would like to define the \ref ReachedMap.
   811     static ReachedMap *createReachedMap(const Digraph &g)
   812     {
   813       return new ReachedMap(g);
   814     }
   815 
   816     ///The type of the map that stores the distances of the nodes.
   817 
   818     ///The type of the map that stores the distances of the nodes.
   819     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   820     typedef typename Digraph::template NodeMap<int> DistMap;
   821     ///Instantiates a \ref DistMap.
   822 
   823     ///This function instantiates a \ref DistMap.
   824     ///\param g is the digraph, to which we would like to define
   825     ///the \ref DistMap
   826     static DistMap *createDistMap(const Digraph &g)
   827     {
   828       return new DistMap(g);
   829     }
   830 
   831     ///The type of the DFS paths.
   832 
   833     ///The type of the DFS paths.
   834     ///It must meet the \ref concepts::Path "Path" concept.
   835     typedef lemon::Path<Digraph> Path;
   836   };
   837 
   838   /// Default traits class used by \ref DfsWizard
   839 
   840   /// To make it easier to use Dfs algorithm
   841   /// we have created a wizard class.
   842   /// This \ref DfsWizard class needs default traits,
   843   /// as well as the \ref Dfs class.
   844   /// The \ref DfsWizardBase is a class to be the default traits of the
   845   /// \ref DfsWizard class.
   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, therefore 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() method, it uses the functions
   894   /// 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   template<class TR>
   899   class DfsWizard : public TR
   900   {
   901     typedef TR Base;
   902 
   903     ///The type of the digraph the algorithm runs on.
   904     typedef typename TR::Digraph Digraph;
   905 
   906     typedef typename Digraph::Node Node;
   907     typedef typename Digraph::NodeIt NodeIt;
   908     typedef typename Digraph::Arc Arc;
   909     typedef typename Digraph::OutArcIt OutArcIt;
   910 
   911     ///\brief The type of the map that stores the predecessor
   912     ///arcs of the DFS paths.
   913     typedef typename TR::PredMap PredMap;
   914     ///\brief The type of the map that stores the distances of the nodes.
   915     typedef typename TR::DistMap DistMap;
   916     ///\brief The type of the map that indicates which nodes are reached.
   917     typedef typename TR::ReachedMap ReachedMap;
   918     ///\brief The type of the map that indicates which nodes are processed.
   919     typedef typename TR::ProcessedMap ProcessedMap;
   920     ///The type of the DFS paths
   921     typedef typename TR::Path Path;
   922 
   923   public:
   924 
   925     /// Constructor.
   926     DfsWizard() : TR() {}
   927 
   928     /// Constructor that requires parameters.
   929 
   930     /// Constructor that requires parameters.
   931     /// These parameters will be the default values for the traits class.
   932     /// \param g The digraph the algorithm runs on.
   933     DfsWizard(const Digraph &g) :
   934       TR(g) {}
   935 
   936     ///Copy constructor
   937     DfsWizard(const TR &b) : TR(b) {}
   938 
   939     ~DfsWizard() {}
   940 
   941     ///Runs DFS algorithm from the given source node.
   942 
   943     ///This method runs DFS algorithm from node \c s
   944     ///in order to compute the DFS path to each node.
   945     void run(Node s)
   946     {
   947       Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
   948       if (Base::_pred)
   949         alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
   950       if (Base::_dist)
   951         alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
   952       if (Base::_reached)
   953         alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
   954       if (Base::_processed)
   955         alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
   956       if (s!=INVALID)
   957         alg.run(s);
   958       else
   959         alg.run();
   960     }
   961 
   962     ///Finds the DFS path between \c s and \c t.
   963 
   964     ///This method runs DFS algorithm from node \c s
   965     ///in order to compute the DFS path to node \c t
   966     ///(it stops searching when \c t is processed).
   967     ///
   968     ///\return \c true if \c t is reachable form \c s.
   969     bool run(Node s, Node t)
   970     {
   971       Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
   972       if (Base::_pred)
   973         alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
   974       if (Base::_dist)
   975         alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
   976       if (Base::_reached)
   977         alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
   978       if (Base::_processed)
   979         alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
   980       alg.run(s,t);
   981       if (Base::_path)
   982         *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
   983       if (Base::_di)
   984         *Base::_di = alg.dist(t);
   985       return alg.reached(t);
   986       }
   987 
   988     ///Runs DFS algorithm to visit all nodes in the digraph.
   989 
   990     ///This method runs DFS algorithm in order to compute
   991     ///the DFS path to each node.
   992     void run()
   993     {
   994       run(INVALID);
   995     }
   996 
   997     template<class T>
   998     struct SetPredMapBase : public Base {
   999       typedef T PredMap;
  1000       static PredMap *createPredMap(const Digraph &) { return 0; };
  1001       SetPredMapBase(const TR &b) : TR(b) {}
  1002     };
  1003     ///\brief \ref named-func-param "Named parameter"
  1004     ///for setting \ref PredMap object.
  1005     ///
  1006     ///\ref named-func-param "Named parameter"
  1007     ///for setting \ref PredMap object.
  1008     template<class T>
  1009     DfsWizard<SetPredMapBase<T> > predMap(const T &t)
  1010     {
  1011       Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  1012       return DfsWizard<SetPredMapBase<T> >(*this);
  1013     }
  1014 
  1015     template<class T>
  1016     struct SetReachedMapBase : public Base {
  1017       typedef T ReachedMap;
  1018       static ReachedMap *createReachedMap(const Digraph &) { return 0; };
  1019       SetReachedMapBase(const TR &b) : TR(b) {}
  1020     };
  1021     ///\brief \ref named-func-param "Named parameter"
  1022     ///for setting \ref ReachedMap object.
  1023     ///
  1024     /// \ref named-func-param "Named parameter"
  1025     ///for setting \ref ReachedMap object.
  1026     template<class T>
  1027     DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
  1028     {
  1029       Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
  1030       return DfsWizard<SetReachedMapBase<T> >(*this);
  1031     }
  1032 
  1033     template<class T>
  1034     struct SetDistMapBase : public Base {
  1035       typedef T DistMap;
  1036       static DistMap *createDistMap(const Digraph &) { return 0; };
  1037       SetDistMapBase(const TR &b) : TR(b) {}
  1038     };
  1039     ///\brief \ref named-func-param "Named parameter"
  1040     ///for setting \ref DistMap object.
  1041     ///
  1042     /// \ref named-func-param "Named parameter"
  1043     ///for setting \ref DistMap object.
  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     ///\brief \ref named-func-param "Named parameter"
  1058     ///for setting \ref ProcessedMap object.
  1059     ///
  1060     /// \ref named-func-param "Named parameter"
  1061     ///for setting \ref ProcessedMap object.
  1062     template<class T>
  1063     DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
  1064     {
  1065       Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
  1066       return DfsWizard<SetProcessedMapBase<T> >(*this);
  1067     }
  1068 
  1069     template<class T>
  1070     struct SetPathBase : public Base {
  1071       typedef T Path;
  1072       SetPathBase(const TR &b) : TR(b) {}
  1073     };
  1074     ///\brief \ref named-func-param "Named parameter"
  1075     ///for getting the DFS path to the target node.
  1076     ///
  1077     ///\ref named-func-param "Named parameter"
  1078     ///for getting the DFS path to the target node.
  1079     template<class T>
  1080     DfsWizard<SetPathBase<T> > path(const T &t)
  1081     {
  1082       Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
  1083       return DfsWizard<SetPathBase<T> >(*this);
  1084     }
  1085 
  1086     ///\brief \ref named-func-param "Named parameter"
  1087     ///for getting the distance of the target node.
  1088     ///
  1089     ///\ref named-func-param "Named parameter"
  1090     ///for getting the distance of the target node.
  1091     DfsWizard dist(const int &d)
  1092     {
  1093       Base::_di=const_cast<int*>(&d);
  1094       return *this;
  1095     }
  1096 
  1097   };
  1098 
  1099   ///Function-type interface for DFS algorithm.
  1100 
  1101   ///\ingroup search
  1102   ///Function-type interface for DFS algorithm.
  1103   ///
  1104   ///This function also has several \ref named-func-param "named parameters",
  1105   ///they are declared as the members of class \ref DfsWizard.
  1106   ///The following examples show how to use these parameters.
  1107   ///\code
  1108   ///  // Compute the DFS tree
  1109   ///  dfs(g).predMap(preds).distMap(dists).run(s);
  1110   ///
  1111   ///  // Compute the DFS path from s to t
  1112   ///  bool reached = dfs(g).path(p).dist(d).run(s,t);
  1113   ///\endcode
  1114 
  1115   ///\warning Don't forget to put the \ref DfsWizard::run() "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 _Digraph>
  1132   struct DfsVisitor {
  1133     typedef _Digraph 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 _Digraph>
  1170   struct DfsVisitor {
  1171     typedef _Digraph 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 _Digraph>
  1205   struct DfsVisitDefaultTraits {
  1206 
  1207     /// \brief The type of the digraph the algorithm runs on.
  1208     typedef _Digraph 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 meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
  1214     typedef typename Digraph::template NodeMap<bool> ReachedMap;
  1215 
  1216     /// \brief Instantiates a \ref ReachedMap.
  1217     ///
  1218     /// This function instantiates a \ref ReachedMap.
  1219     /// \param digraph is the digraph, to which
  1220     /// we would like to define the \ref ReachedMap.
  1221     static ReachedMap *createReachedMap(const Digraph &digraph) {
  1222       return new ReachedMap(digraph);
  1223     }
  1224 
  1225   };
  1226 
  1227   /// \ingroup search
  1228   ///
  1229   /// \brief %DFS algorithm class with visitor interface.
  1230   ///
  1231   /// This class provides an efficient implementation of the %DFS algorithm
  1232   /// with visitor interface.
  1233   ///
  1234   /// The %DfsVisit class provides an alternative interface to the Dfs
  1235   /// class. It works with callback mechanism, the DfsVisit object calls
  1236   /// the member functions of the \c Visitor class on every DFS event.
  1237   ///
  1238   /// This interface of the DFS algorithm should be used in special cases
  1239   /// when extra actions have to be performed in connection with certain
  1240   /// events of the DFS algorithm. Otherwise consider to use Dfs or dfs()
  1241   /// instead.
  1242   ///
  1243   /// \tparam _Digraph The type of the digraph the algorithm runs on.
  1244   /// The default value is
  1245   /// \ref ListDigraph. The value of _Digraph is not used directly by
  1246   /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
  1247   /// \tparam _Visitor The Visitor type that is used by the algorithm.
  1248   /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
  1249   /// does not observe the DFS events. If you want to observe the DFS
  1250   /// events, you should implement your own visitor class.
  1251   /// \tparam _Traits Traits class to set various data types used by the
  1252   /// algorithm. The default traits class is
  1253   /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
  1254   /// See \ref DfsVisitDefaultTraits for the documentation of
  1255   /// a DFS visit traits class.
  1256 #ifdef DOXYGEN
  1257   template <typename _Digraph, typename _Visitor, typename _Traits>
  1258 #else
  1259   template <typename _Digraph = ListDigraph,
  1260             typename _Visitor = DfsVisitor<_Digraph>,
  1261             typename _Traits = DfsVisitDefaultTraits<_Digraph> >
  1262 #endif
  1263   class DfsVisit {
  1264   public:
  1265 
  1266     ///The traits class.
  1267     typedef _Traits Traits;
  1268 
  1269     ///The type of the digraph the algorithm runs on.
  1270     typedef typename Traits::Digraph Digraph;
  1271 
  1272     ///The visitor type used by the algorithm.
  1273     typedef _Visitor Visitor;
  1274 
  1275     ///The type of the map that indicates which nodes are reached.
  1276     typedef typename Traits::ReachedMap ReachedMap;
  1277 
  1278   private:
  1279 
  1280     typedef typename Digraph::Node Node;
  1281     typedef typename Digraph::NodeIt NodeIt;
  1282     typedef typename Digraph::Arc Arc;
  1283     typedef typename Digraph::OutArcIt OutArcIt;
  1284 
  1285     //Pointer to the underlying digraph.
  1286     const Digraph *_digraph;
  1287     //Pointer to the visitor object.
  1288     Visitor *_visitor;
  1289     //Pointer to the map of reached status of the nodes.
  1290     ReachedMap *_reached;
  1291     //Indicates if _reached is locally allocated (true) or not.
  1292     bool local_reached;
  1293 
  1294     std::vector<typename Digraph::Arc> _stack;
  1295     int _stack_head;
  1296 
  1297     //Creates the maps if necessary.
  1298     void create_maps() {
  1299       if(!_reached) {
  1300         local_reached = true;
  1301         _reached = Traits::createReachedMap(*_digraph);
  1302       }
  1303     }
  1304 
  1305   protected:
  1306 
  1307     DfsVisit() {}
  1308 
  1309   public:
  1310 
  1311     typedef DfsVisit Create;
  1312 
  1313     /// \name Named template parameters
  1314 
  1315     ///@{
  1316     template <class T>
  1317     struct SetReachedMapTraits : public Traits {
  1318       typedef T ReachedMap;
  1319       static ReachedMap *createReachedMap(const Digraph &digraph) {
  1320         LEMON_ASSERT(false, "ReachedMap is not initialized");
  1321         return 0; // ignore warnings
  1322       }
  1323     };
  1324     /// \brief \ref named-templ-param "Named parameter" for setting
  1325     /// ReachedMap type.
  1326     ///
  1327     /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
  1328     template <class T>
  1329     struct SetReachedMap : public DfsVisit< Digraph, Visitor,
  1330                                             SetReachedMapTraits<T> > {
  1331       typedef DfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
  1332     };
  1333     ///@}
  1334 
  1335   public:
  1336 
  1337     /// \brief Constructor.
  1338     ///
  1339     /// Constructor.
  1340     ///
  1341     /// \param digraph The digraph the algorithm runs on.
  1342     /// \param visitor The visitor object of the algorithm.
  1343     DfsVisit(const Digraph& digraph, Visitor& visitor)
  1344       : _digraph(&digraph), _visitor(&visitor),
  1345         _reached(0), local_reached(false) {}
  1346 
  1347     /// \brief Destructor.
  1348     ~DfsVisit() {
  1349       if(local_reached) delete _reached;
  1350     }
  1351 
  1352     /// \brief Sets the map that indicates which nodes are reached.
  1353     ///
  1354     /// Sets the map that indicates which nodes are reached.
  1355     /// If you don't use this function before calling \ref run(),
  1356     /// it will allocate one. The destructor deallocates this
  1357     /// automatically allocated map, of course.
  1358     /// \return <tt> (*this) </tt>
  1359     DfsVisit &reachedMap(ReachedMap &m) {
  1360       if(local_reached) {
  1361         delete _reached;
  1362         local_reached=false;
  1363       }
  1364       _reached = &m;
  1365       return *this;
  1366     }
  1367 
  1368   public:
  1369 
  1370     /// \name Execution control
  1371     /// The simplest way to execute the algorithm is to use
  1372     /// one of the member functions called \ref lemon::DfsVisit::run()
  1373     /// "run()".
  1374     /// \n
  1375     /// If you need more control on the execution, first you must call
  1376     /// \ref lemon::DfsVisit::init() "init()", then you can add several
  1377     /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
  1378     /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
  1379     /// actual path computation.
  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     ///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     ///false results.)
  1401     ///
  1402     ///\warning Distances will be wrong (or at least strange) in case of
  1403     ///multiple sources.
  1404     void addSource(Node s)
  1405     {
  1406       LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
  1407       if(!(*_reached)[s]) {
  1408           _reached->set(s,true);
  1409           _visitor->start(s);
  1410           _visitor->reach(s);
  1411           Arc e;
  1412           _digraph->firstOut(e, s);
  1413           if (e != INVALID) {
  1414             _stack[++_stack_head] = e;
  1415           } else {
  1416             _visitor->leave(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() && _digraph->target(_stack[_stack_head]) != 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
  1590     /// compute the %DFS path to each node.
  1591     ///
  1592     /// The algorithm computes
  1593     /// - the %DFS tree,
  1594     /// - the distance of each node from the root in the %DFS tree.
  1595     ///
  1596     /// \note <tt>d.run()</tt> is just a shortcut of the following code.
  1597     ///\code
  1598     ///   d.init();
  1599     ///   for (NodeIt n(digraph); n != INVALID; ++n) {
  1600     ///     if (!d.reached(n)) {
  1601     ///       d.addSource(n);
  1602     ///       d.start();
  1603     ///     }
  1604     ///   }
  1605     ///\endcode
  1606     void run() {
  1607       init();
  1608       for (NodeIt it(*_digraph); it != INVALID; ++it) {
  1609         if (!reached(it)) {
  1610           addSource(it);
  1611           start();
  1612         }
  1613       }
  1614     }
  1615 
  1616     ///@}
  1617 
  1618     /// \name Query Functions
  1619     /// The result of the %DFS algorithm can be obtained using these
  1620     /// functions.\n
  1621     /// Either \ref lemon::DfsVisit::run() "run()" or
  1622     /// \ref lemon::DfsVisit::start() "start()" must be called before
  1623     /// using them.
  1624     ///@{
  1625 
  1626     /// \brief Checks if a node is reachable from the root(s).
  1627     ///
  1628     /// Returns \c true if \c v is reachable from the root(s).
  1629     /// \pre Either \ref run() or \ref start()
  1630     /// must be called before using this function.
  1631     bool reached(Node v) { return (*_reached)[v]; }
  1632 
  1633     ///@}
  1634 
  1635   };
  1636 
  1637 } //END OF NAMESPACE LEMON
  1638 
  1639 #endif