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