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