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