lemon/dfs.h
changeset 108 889d0c289d19
child 157 2ccc1afc2c52
equal deleted inserted replaced
-1:000000000000 0:ddca76e38c87
       
     1 /* -*- C++ -*-
       
     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   ///\param 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 the \ref DistMap
       
   109     static DistMap *createDistMap(const GR &G)
       
   110     {
       
   111       return new DistMap(G);
       
   112     }
       
   113   };
       
   114   
       
   115   ///%DFS algorithm class.
       
   116   
       
   117   ///\ingroup search
       
   118   ///This class provides an efficient implementation of the %DFS algorithm.
       
   119   ///
       
   120   ///\param GR The digraph type the algorithm runs on. The default value is
       
   121   ///\ref ListDigraph. The value of GR is not used directly by Dfs, it
       
   122   ///is only passed to \ref DfsDefaultTraits.
       
   123   ///\param TR Traits class to set various data types used by the algorithm.
       
   124   ///The default traits class is
       
   125   ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
       
   126   ///See \ref DfsDefaultTraits for the documentation of
       
   127   ///a Dfs traits class.
       
   128   ///
       
   129   ///\author Jacint Szabo and Alpar Juttner
       
   130 #ifdef DOXYGEN
       
   131   template <typename GR,
       
   132 	    typename TR>
       
   133 #else
       
   134   template <typename GR=ListDigraph,
       
   135 	    typename TR=DfsDefaultTraits<GR> >
       
   136 #endif
       
   137   class Dfs {
       
   138   public:
       
   139     /**
       
   140      * \brief \ref Exception for uninitialized parameters.
       
   141      *
       
   142      * This error represents problems in the initialization
       
   143      * of the parameters of the algorithms.
       
   144      */
       
   145     class UninitializedParameter : public lemon::UninitializedParameter {
       
   146     public:
       
   147       virtual const char* what() const throw() {
       
   148 	return "lemon::Dfs::UninitializedParameter";
       
   149       }
       
   150     };
       
   151 
       
   152     typedef TR Traits;
       
   153     ///The type of the underlying digraph.
       
   154     typedef typename TR::Digraph Digraph;
       
   155     ///\e
       
   156     typedef typename Digraph::Node Node;
       
   157     ///\e
       
   158     typedef typename Digraph::NodeIt NodeIt;
       
   159     ///\e
       
   160     typedef typename Digraph::Arc Arc;
       
   161     ///\e
       
   162     typedef typename Digraph::OutArcIt OutArcIt;
       
   163     
       
   164     ///\brief The type of the map that stores the last
       
   165     ///arcs of the %DFS paths.
       
   166     typedef typename TR::PredMap PredMap;
       
   167     ///The type of the map indicating which nodes are reached.
       
   168     typedef typename TR::ReachedMap ReachedMap;
       
   169     ///The type of the map indicating which nodes are processed.
       
   170     typedef typename TR::ProcessedMap ProcessedMap;
       
   171     ///The type of the map that stores the dists of the nodes.
       
   172     typedef typename TR::DistMap DistMap;
       
   173   private:
       
   174     /// Pointer to the underlying digraph.
       
   175     const Digraph *G;
       
   176     ///Pointer to the map of predecessors arcs.
       
   177     PredMap *_pred;
       
   178     ///Indicates if \ref _pred is locally allocated (\c true) or not.
       
   179     bool local_pred;
       
   180     ///Pointer to the map of distances.
       
   181     DistMap *_dist;
       
   182     ///Indicates if \ref _dist is locally allocated (\c true) or not.
       
   183     bool local_dist;
       
   184     ///Pointer to the map of reached status of the nodes.
       
   185     ReachedMap *_reached;
       
   186     ///Indicates if \ref _reached is locally allocated (\c true) or not.
       
   187     bool local_reached;
       
   188     ///Pointer to the map of processed status of the nodes.
       
   189     ProcessedMap *_processed;
       
   190     ///Indicates if \ref _processed is locally allocated (\c true) or not.
       
   191     bool local_processed;
       
   192 
       
   193     std::vector<typename Digraph::OutArcIt> _stack;
       
   194     int _stack_head;
       
   195 
       
   196     ///Creates the maps if necessary.
       
   197     
       
   198     ///\todo Better memory allocation (instead of new).
       
   199     void create_maps() 
       
   200     {
       
   201       if(!_pred) {
       
   202 	local_pred = true;
       
   203 	_pred = Traits::createPredMap(*G);
       
   204       }
       
   205       if(!_dist) {
       
   206 	local_dist = true;
       
   207 	_dist = Traits::createDistMap(*G);
       
   208       }
       
   209       if(!_reached) {
       
   210 	local_reached = true;
       
   211 	_reached = Traits::createReachedMap(*G);
       
   212       }
       
   213       if(!_processed) {
       
   214 	local_processed = true;
       
   215 	_processed = Traits::createProcessedMap(*G);
       
   216       }
       
   217     }
       
   218 
       
   219   protected:
       
   220 
       
   221     Dfs() {}
       
   222     
       
   223   public:
       
   224 
       
   225     typedef Dfs Create;
       
   226 
       
   227     ///\name Named template parameters
       
   228 
       
   229     ///@{
       
   230 
       
   231     template <class T>
       
   232     struct DefPredMapTraits : public Traits {
       
   233       typedef T PredMap;
       
   234       static PredMap *createPredMap(const Digraph &G) 
       
   235       {
       
   236 	throw UninitializedParameter();
       
   237       }
       
   238     };
       
   239     ///\brief \ref named-templ-param "Named parameter" for setting
       
   240     ///PredMap type
       
   241     ///
       
   242     ///\ref named-templ-param "Named parameter" for setting PredMap type
       
   243     ///
       
   244     template <class T>
       
   245     struct DefPredMap : public Dfs<Digraph, DefPredMapTraits<T> > {
       
   246       typedef Dfs<Digraph, DefPredMapTraits<T> > Create;
       
   247     };
       
   248     
       
   249     
       
   250     template <class T>
       
   251     struct DefDistMapTraits : public Traits {
       
   252       typedef T DistMap;
       
   253       static DistMap *createDistMap(const Digraph &) 
       
   254       {
       
   255 	throw UninitializedParameter();
       
   256       }
       
   257     };
       
   258     ///\brief \ref named-templ-param "Named parameter" for setting
       
   259     ///DistMap type
       
   260     ///
       
   261     ///\ref named-templ-param "Named parameter" for setting DistMap
       
   262     ///type
       
   263     template <class T>
       
   264     struct DefDistMap {
       
   265       typedef Dfs<Digraph, DefDistMapTraits<T> > Create;
       
   266     };
       
   267     
       
   268     template <class T>
       
   269     struct DefReachedMapTraits : public Traits {
       
   270       typedef T ReachedMap;
       
   271       static ReachedMap *createReachedMap(const Digraph &) 
       
   272       {
       
   273 	throw UninitializedParameter();
       
   274       }
       
   275     };
       
   276     ///\brief \ref named-templ-param "Named parameter" for setting
       
   277     ///ReachedMap type
       
   278     ///
       
   279     ///\ref named-templ-param "Named parameter" for setting ReachedMap type
       
   280     ///
       
   281     template <class T>
       
   282     struct DefReachedMap : public Dfs< Digraph, DefReachedMapTraits<T> > {
       
   283       typedef Dfs< Digraph, DefReachedMapTraits<T> > Create;
       
   284     };
       
   285 
       
   286     template <class T>
       
   287     struct DefProcessedMapTraits : public Traits {
       
   288       typedef T ProcessedMap;
       
   289       static ProcessedMap *createProcessedMap(const Digraph &) 
       
   290       {
       
   291 	throw UninitializedParameter();
       
   292       }
       
   293     };
       
   294     ///\brief \ref named-templ-param "Named parameter" for setting
       
   295     ///ProcessedMap type
       
   296     ///
       
   297     ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
       
   298     ///
       
   299     template <class T>
       
   300     struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > { 
       
   301       typedef Dfs< Digraph, DefProcessedMapTraits<T> > Create;
       
   302     };
       
   303     
       
   304     struct DefDigraphProcessedMapTraits : public Traits {
       
   305       typedef typename Digraph::template NodeMap<bool> ProcessedMap;
       
   306       static ProcessedMap *createProcessedMap(const Digraph &G) 
       
   307       {
       
   308 	return new ProcessedMap(G);
       
   309       }
       
   310     };
       
   311     ///\brief \ref named-templ-param "Named parameter"
       
   312     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
       
   313     ///
       
   314     ///\ref named-templ-param "Named parameter"
       
   315     ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
       
   316     ///If you don't set it explicitely, it will be automatically allocated.
       
   317     template <class T>
       
   318     class DefProcessedMapToBeDefaultMap :
       
   319       public Dfs< Digraph, DefDigraphProcessedMapTraits> { 
       
   320       typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create;
       
   321     };
       
   322     
       
   323     ///@}
       
   324 
       
   325   public:      
       
   326     
       
   327     ///Constructor.
       
   328     
       
   329     ///\param _G the digraph the algorithm will run on.
       
   330     ///
       
   331     Dfs(const Digraph& _G) :
       
   332       G(&_G),
       
   333       _pred(NULL), local_pred(false),
       
   334       _dist(NULL), local_dist(false),
       
   335       _reached(NULL), local_reached(false),
       
   336       _processed(NULL), local_processed(false)
       
   337     { }
       
   338     
       
   339     ///Destructor.
       
   340     ~Dfs() 
       
   341     {
       
   342       if(local_pred) delete _pred;
       
   343       if(local_dist) delete _dist;
       
   344       if(local_reached) delete _reached;
       
   345       if(local_processed) delete _processed;
       
   346     }
       
   347 
       
   348     ///Sets the map storing the predecessor arcs.
       
   349 
       
   350     ///Sets the map storing the predecessor arcs.
       
   351     ///If you don't use this function before calling \ref run(),
       
   352     ///it will allocate one. The destuctor deallocates this
       
   353     ///automatically allocated map, of course.
       
   354     ///\return <tt> (*this) </tt>
       
   355     Dfs &predMap(PredMap &m) 
       
   356     {
       
   357       if(local_pred) {
       
   358 	delete _pred;
       
   359 	local_pred=false;
       
   360       }
       
   361       _pred = &m;
       
   362       return *this;
       
   363     }
       
   364 
       
   365     ///Sets the map storing the distances calculated by the algorithm.
       
   366 
       
   367     ///Sets the map storing the distances calculated by the algorithm.
       
   368     ///If you don't use this function before calling \ref run(),
       
   369     ///it will allocate one. The destuctor deallocates this
       
   370     ///automatically allocated map, of course.
       
   371     ///\return <tt> (*this) </tt>
       
   372     Dfs &distMap(DistMap &m) 
       
   373     {
       
   374       if(local_dist) {
       
   375 	delete _dist;
       
   376 	local_dist=false;
       
   377       }
       
   378       _dist = &m;
       
   379       return *this;
       
   380     }
       
   381 
       
   382     ///Sets the map indicating if a node is reached.
       
   383 
       
   384     ///Sets the map indicating if a node is reached.
       
   385     ///If you don't use this function before calling \ref run(),
       
   386     ///it will allocate one. The destuctor deallocates this
       
   387     ///automatically allocated map, of course.
       
   388     ///\return <tt> (*this) </tt>
       
   389     Dfs &reachedMap(ReachedMap &m) 
       
   390     {
       
   391       if(local_reached) {
       
   392 	delete _reached;
       
   393 	local_reached=false;
       
   394       }
       
   395       _reached = &m;
       
   396       return *this;
       
   397     }
       
   398 
       
   399     ///Sets the map indicating if a node is processed.
       
   400 
       
   401     ///Sets the map indicating if a node is processed.
       
   402     ///If you don't use this function before calling \ref run(),
       
   403     ///it will allocate one. The destuctor deallocates this
       
   404     ///automatically allocated map, of course.
       
   405     ///\return <tt> (*this) </tt>
       
   406     Dfs &processedMap(ProcessedMap &m) 
       
   407     {
       
   408       if(local_processed) {
       
   409 	delete _processed;
       
   410 	local_processed=false;
       
   411       }
       
   412       _processed = &m;
       
   413       return *this;
       
   414     }
       
   415 
       
   416   public:
       
   417     ///\name Execution control
       
   418     ///The simplest way to execute the algorithm is to use
       
   419     ///one of the member functions called \c run(...).
       
   420     ///\n
       
   421     ///If you need more control on the execution,
       
   422     ///first you must call \ref init(), then you can add a source node
       
   423     ///with \ref addSource().
       
   424     ///Finally \ref start() will perform the actual path
       
   425     ///computation.
       
   426 
       
   427     ///@{
       
   428 
       
   429     ///Initializes the internal data structures.
       
   430 
       
   431     ///Initializes the internal data structures.
       
   432     ///
       
   433     void init()
       
   434     {
       
   435       create_maps();
       
   436       _stack.resize(countNodes(*G));
       
   437       _stack_head=-1;
       
   438       for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
       
   439 	_pred->set(u,INVALID);
       
   440 	// _predNode->set(u,INVALID);
       
   441 	_reached->set(u,false);
       
   442 	_processed->set(u,false);
       
   443       }
       
   444     }
       
   445     
       
   446     ///Adds a new source node.
       
   447 
       
   448     ///Adds a new source node to the set of nodes to be processed.
       
   449     ///
       
   450     ///\warning dists are wrong (or at least strange)
       
   451     ///in case of multiple sources.
       
   452     void addSource(Node s)
       
   453     {
       
   454       if(!(*_reached)[s])
       
   455 	{
       
   456 	  _reached->set(s,true);
       
   457 	  _pred->set(s,INVALID);
       
   458 	  OutArcIt e(*G,s);
       
   459 	  if(e!=INVALID) {
       
   460 	    _stack[++_stack_head]=e;
       
   461 	    _dist->set(s,_stack_head);
       
   462 	  }
       
   463 	  else {
       
   464 	    _processed->set(s,true);
       
   465 	    _dist->set(s,0);
       
   466 	  }
       
   467 	}
       
   468     }
       
   469     
       
   470     ///Processes the next arc.
       
   471 
       
   472     ///Processes the next arc.
       
   473     ///
       
   474     ///\return The processed arc.
       
   475     ///
       
   476     ///\pre The stack must not be empty!
       
   477     Arc processNextArc()
       
   478     { 
       
   479       Node m;
       
   480       Arc e=_stack[_stack_head];
       
   481       if(!(*_reached)[m=G->target(e)]) {
       
   482 	_pred->set(m,e);
       
   483 	_reached->set(m,true);
       
   484 	++_stack_head;
       
   485 	_stack[_stack_head] = OutArcIt(*G, m);
       
   486 	_dist->set(m,_stack_head);
       
   487       }
       
   488       else {
       
   489 	m=G->source(e);
       
   490 	++_stack[_stack_head];
       
   491       }
       
   492       while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
       
   493 	_processed->set(m,true);
       
   494 	--_stack_head;
       
   495 	if(_stack_head>=0) {
       
   496 	  m=G->source(_stack[_stack_head]);
       
   497 	  ++_stack[_stack_head];
       
   498 	}
       
   499       }
       
   500       return e;
       
   501     }
       
   502     ///Next arc to be processed.
       
   503 
       
   504     ///Next arc to be processed.
       
   505     ///
       
   506     ///\return The next arc to be processed or INVALID if the stack is
       
   507     /// empty.
       
   508     OutArcIt nextArc()
       
   509     { 
       
   510       return _stack_head>=0?_stack[_stack_head]:INVALID;
       
   511     }
       
   512 
       
   513     ///\brief Returns \c false if there are nodes
       
   514     ///to be processed in the queue
       
   515     ///
       
   516     ///Returns \c false if there are nodes
       
   517     ///to be processed in the queue
       
   518     bool emptyQueue() { return _stack_head<0; }
       
   519     ///Returns the number of the nodes to be processed.
       
   520     
       
   521     ///Returns the number of the nodes to be processed in the queue.
       
   522     int queueSize() { return _stack_head+1; }
       
   523     
       
   524     ///Executes the algorithm.
       
   525 
       
   526     ///Executes the algorithm.
       
   527     ///
       
   528     ///\pre init() must be called and at least one node should be added
       
   529     ///with addSource() before using this function.
       
   530     ///
       
   531     ///This method runs the %DFS algorithm from the root node(s)
       
   532     ///in order to
       
   533     ///compute the
       
   534     ///%DFS path to each node. The algorithm computes
       
   535     ///- The %DFS tree.
       
   536     ///- The distance of each node from the root(s) in the %DFS tree.
       
   537     ///
       
   538     void start()
       
   539     {
       
   540       while ( !emptyQueue() ) processNextArc();
       
   541     }
       
   542     
       
   543     ///Executes the algorithm until \c dest is reached.
       
   544 
       
   545     ///Executes the algorithm until \c dest is reached.
       
   546     ///
       
   547     ///\pre init() must be called and at least one node should be added
       
   548     ///with addSource() before using this function.
       
   549     ///
       
   550     ///This method runs the %DFS algorithm from the root node(s)
       
   551     ///in order to
       
   552     ///compute the
       
   553     ///%DFS path to \c dest. The algorithm computes
       
   554     ///- The %DFS path to \c  dest.
       
   555     ///- The distance of \c dest from the root(s) in the %DFS tree.
       
   556     ///
       
   557     void start(Node dest)
       
   558     {
       
   559       while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest ) 
       
   560 	processNextArc();
       
   561     }
       
   562     
       
   563     ///Executes the algorithm until a condition is met.
       
   564 
       
   565     ///Executes the algorithm until a condition is met.
       
   566     ///
       
   567     ///\pre init() must be called and at least one node should be added
       
   568     ///with addSource() before using this function.
       
   569     ///
       
   570     ///\param em must be a bool (or convertible) arc map. The algorithm
       
   571     ///will stop when it reaches an arc \c e with <tt>em[e]</tt> true.
       
   572     ///
       
   573     ///\return The reached arc \c e with <tt>em[e]</tt> true or
       
   574     ///\c INVALID if no such arc was found.
       
   575     ///
       
   576     ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map,
       
   577     ///not a node map.
       
   578     template<class EM>
       
   579     Arc start(const EM &em)
       
   580     {
       
   581       while ( !emptyQueue() && !em[_stack[_stack_head]] )
       
   582         processNextArc();
       
   583       return emptyQueue() ? INVALID : _stack[_stack_head];
       
   584     }
       
   585 
       
   586     ///Runs %DFS algorithm to visit all nodes in the digraph.
       
   587     
       
   588     ///This method runs the %DFS algorithm in order to
       
   589     ///compute the
       
   590     ///%DFS path to each node. The algorithm computes
       
   591     ///- The %DFS tree.
       
   592     ///- The distance of each node from the root in the %DFS tree.
       
   593     ///
       
   594     ///\note d.run() is just a shortcut of the following code.
       
   595     ///\code
       
   596     ///  d.init();
       
   597     ///  for (NodeIt it(digraph); it != INVALID; ++it) {
       
   598     ///    if (!d.reached(it)) {
       
   599     ///      d.addSource(it);
       
   600     ///      d.start();
       
   601     ///    }
       
   602     ///  }
       
   603     ///\endcode
       
   604     void run() {
       
   605       init();
       
   606       for (NodeIt it(*G); it != INVALID; ++it) {
       
   607         if (!reached(it)) {
       
   608           addSource(it);
       
   609           start();
       
   610         }
       
   611       }
       
   612     }
       
   613 
       
   614     ///Runs %DFS algorithm from node \c s.
       
   615     
       
   616     ///This method runs the %DFS algorithm from a root node \c s
       
   617     ///in order to
       
   618     ///compute the
       
   619     ///%DFS path to each node. The algorithm computes
       
   620     ///- The %DFS tree.
       
   621     ///- The distance of each node from the root in the %DFS tree.
       
   622     ///
       
   623     ///\note d.run(s) is just a shortcut of the following code.
       
   624     ///\code
       
   625     ///  d.init();
       
   626     ///  d.addSource(s);
       
   627     ///  d.start();
       
   628     ///\endcode
       
   629     void run(Node s) {
       
   630       init();
       
   631       addSource(s);
       
   632       start();
       
   633     }
       
   634     
       
   635     ///Finds the %DFS path between \c s and \c t.
       
   636     
       
   637     ///Finds the %DFS path between \c s and \c t.
       
   638     ///
       
   639     ///\return The length of the %DFS s---t path if there exists one,
       
   640     ///0 otherwise.
       
   641     ///\note Apart from the return value, d.run(s,t) is
       
   642     ///just a shortcut of the following code.
       
   643     ///\code
       
   644     ///  d.init();
       
   645     ///  d.addSource(s);
       
   646     ///  d.start(t);
       
   647     ///\endcode
       
   648     int run(Node s,Node t) {
       
   649       init();
       
   650       addSource(s);
       
   651       start(t);
       
   652       return reached(t)?_stack_head+1:0;
       
   653     }
       
   654     
       
   655     ///@}
       
   656 
       
   657     ///\name Query Functions
       
   658     ///The result of the %DFS algorithm can be obtained using these
       
   659     ///functions.\n
       
   660     ///Before the use of these functions,
       
   661     ///either run() or start() must be called.
       
   662     
       
   663     ///@{
       
   664 
       
   665     typedef PredMapPath<Digraph, PredMap> Path;
       
   666 
       
   667     ///Gives back the shortest path.
       
   668     
       
   669     ///Gives back the shortest path.
       
   670     ///\pre The \c t should be reachable from the source.
       
   671     Path path(Node t) 
       
   672     {
       
   673       return Path(*G, *_pred, t);
       
   674     }
       
   675 
       
   676     ///The distance of a node from the root(s).
       
   677 
       
   678     ///Returns the distance of a node from the root(s).
       
   679     ///\pre \ref run() must be called before using this function.
       
   680     ///\warning If node \c v is unreachable from the root(s) then the return 
       
   681     ///value of this funcion is undefined.
       
   682     int dist(Node v) const { return (*_dist)[v]; }
       
   683 
       
   684     ///Returns the 'previous arc' of the %DFS tree.
       
   685 
       
   686     ///For a node \c v it returns the 'previous arc'
       
   687     ///of the %DFS path,
       
   688     ///i.e. it returns the last arc of a %DFS path from the root(s) to \c
       
   689     ///v. It is \ref INVALID
       
   690     ///if \c v is unreachable from the root(s) or \c v is a root. The
       
   691     ///%DFS tree used here is equal to the %DFS tree used in
       
   692     ///\ref predNode().
       
   693     ///\pre Either \ref run() or \ref start() must be called before using
       
   694     ///this function.
       
   695     Arc predArc(Node v) const { return (*_pred)[v];}
       
   696 
       
   697     ///Returns the 'previous node' of the %DFS tree.
       
   698 
       
   699     ///For a node \c v it returns the 'previous node'
       
   700     ///of the %DFS tree,
       
   701     ///i.e. it returns the last but one node from a %DFS path from the
       
   702     ///root(s) to \c v.
       
   703     ///It is INVALID if \c v is unreachable from the root(s) or
       
   704     ///if \c v itself a root.
       
   705     ///The %DFS tree used here is equal to the %DFS
       
   706     ///tree used in \ref predArc().
       
   707     ///\pre Either \ref run() or \ref start() must be called before
       
   708     ///using this function.
       
   709     Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
       
   710 				  G->source((*_pred)[v]); }
       
   711     
       
   712     ///Returns a reference to the NodeMap of distances.
       
   713 
       
   714     ///Returns a reference to the NodeMap of distances.
       
   715     ///\pre Either \ref run() or \ref init() must
       
   716     ///be called before using this function.
       
   717     const DistMap &distMap() const { return *_dist;}
       
   718  
       
   719     ///Returns a reference to the %DFS arc-tree map.
       
   720 
       
   721     ///Returns a reference to the NodeMap of the arcs of the
       
   722     ///%DFS tree.
       
   723     ///\pre Either \ref run() or \ref init()
       
   724     ///must be called before using this function.
       
   725     const PredMap &predMap() const { return *_pred;}
       
   726  
       
   727     ///Checks if a node is reachable from the root.
       
   728 
       
   729     ///Returns \c true if \c v is reachable from the root(s).
       
   730     ///\warning The source nodes are inditated as unreachable.
       
   731     ///\pre Either \ref run() or \ref start()
       
   732     ///must be called before using this function.
       
   733     ///
       
   734     bool reached(Node v) { return (*_reached)[v]; }
       
   735     
       
   736     ///@}
       
   737   };
       
   738 
       
   739   ///Default traits class of Dfs function.
       
   740 
       
   741   ///Default traits class of Dfs function.
       
   742   ///\param GR Digraph type.
       
   743   template<class GR>
       
   744   struct DfsWizardDefaultTraits
       
   745   {
       
   746     ///The digraph type the algorithm runs on. 
       
   747     typedef GR Digraph;
       
   748     ///\brief The type of the map that stores the last
       
   749     ///arcs of the %DFS paths.
       
   750     /// 
       
   751     ///The type of the map that stores the last
       
   752     ///arcs of the %DFS paths.
       
   753     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
       
   754     ///
       
   755     typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
       
   756     ///Instantiates a PredMap.
       
   757  
       
   758     ///This function instantiates a \ref PredMap. 
       
   759     ///\param g is the digraph, to which we would like to define the PredMap.
       
   760     ///\todo The digraph alone may be insufficient to initialize
       
   761 #ifdef DOXYGEN
       
   762     static PredMap *createPredMap(const GR &g) 
       
   763 #else
       
   764     static PredMap *createPredMap(const GR &) 
       
   765 #endif
       
   766     {
       
   767       return new PredMap();
       
   768     }
       
   769 
       
   770     ///The type of the map that indicates which nodes are processed.
       
   771  
       
   772     ///The type of the map that indicates which nodes are processed.
       
   773     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
       
   774     ///\todo named parameter to set this type, function to read and write.
       
   775     typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
       
   776     ///Instantiates a ProcessedMap.
       
   777  
       
   778     ///This function instantiates a \ref ProcessedMap. 
       
   779     ///\param g is the digraph, to which
       
   780     ///we would like to define the \ref ProcessedMap
       
   781 #ifdef DOXYGEN
       
   782     static ProcessedMap *createProcessedMap(const GR &g)
       
   783 #else
       
   784     static ProcessedMap *createProcessedMap(const GR &)
       
   785 #endif
       
   786     {
       
   787       return new ProcessedMap();
       
   788     }
       
   789     ///The type of the map that indicates which nodes are reached.
       
   790  
       
   791     ///The type of the map that indicates which nodes are reached.
       
   792     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
       
   793     ///\todo named parameter to set this type, function to read and write.
       
   794     typedef typename Digraph::template NodeMap<bool> ReachedMap;
       
   795     ///Instantiates a ReachedMap.
       
   796  
       
   797     ///This function instantiates a \ref ReachedMap. 
       
   798     ///\param G is the digraph, to which
       
   799     ///we would like to define the \ref ReachedMap.
       
   800     static ReachedMap *createReachedMap(const GR &G)
       
   801     {
       
   802       return new ReachedMap(G);
       
   803     }
       
   804     ///The type of the map that stores the dists of the nodes.
       
   805  
       
   806     ///The type of the map that stores the dists of the nodes.
       
   807     ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
       
   808     ///
       
   809     typedef NullMap<typename Digraph::Node,int> DistMap;
       
   810     ///Instantiates a DistMap.
       
   811  
       
   812     ///This function instantiates a \ref DistMap. 
       
   813     ///\param g is the digraph, to which we would like to define 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::_pred=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::_pred=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   /// \param _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   /// \param _Digraph The digraph type the algorithm runs on. The default value is
       
  1199   /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it
       
  1200   /// is only passed to \ref DfsDefaultTraits.
       
  1201   /// \param _Visitor The Visitor object for the algorithm. The 
       
  1202   /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitor which
       
  1203   /// does not observe the Dfs events. If you want to observe the dfs
       
  1204   /// events you should implement your own Visitor class.
       
  1205   /// \param _Traits Traits class to set various data types used by the 
       
  1206   /// algorithm. The default traits class is
       
  1207   /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
       
  1208   /// See \ref DfsVisitDefaultTraits for the documentation of
       
  1209   /// a Dfs visit traits class.
       
  1210   ///
       
  1211   /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
       
  1212 #ifdef DOXYGEN
       
  1213   template <typename _Digraph, typename _Visitor, typename _Traits>
       
  1214 #else
       
  1215   template <typename _Digraph = ListDigraph,
       
  1216 	    typename _Visitor = DfsVisitor<_Digraph>,
       
  1217 	    typename _Traits = DfsDefaultTraits<_Digraph> >
       
  1218 #endif
       
  1219   class DfsVisit {
       
  1220   public:
       
  1221     
       
  1222     /// \brief \ref Exception for uninitialized parameters.
       
  1223     ///
       
  1224     /// This error represents problems in the initialization
       
  1225     /// of the parameters of the algorithms.
       
  1226     class UninitializedParameter : public lemon::UninitializedParameter {
       
  1227     public:
       
  1228       virtual const char* what() const throw() 
       
  1229       {
       
  1230 	return "lemon::DfsVisit::UninitializedParameter";
       
  1231       }
       
  1232     };
       
  1233 
       
  1234     typedef _Traits Traits;
       
  1235 
       
  1236     typedef typename Traits::Digraph Digraph;
       
  1237 
       
  1238     typedef _Visitor Visitor;
       
  1239 
       
  1240     ///The type of the map indicating which nodes are reached.
       
  1241     typedef typename Traits::ReachedMap ReachedMap;
       
  1242 
       
  1243   private:
       
  1244 
       
  1245     typedef typename Digraph::Node Node;
       
  1246     typedef typename Digraph::NodeIt NodeIt;
       
  1247     typedef typename Digraph::Arc Arc;
       
  1248     typedef typename Digraph::OutArcIt OutArcIt;
       
  1249 
       
  1250     /// Pointer to the underlying digraph.
       
  1251     const Digraph *_digraph;
       
  1252     /// Pointer to the visitor object.
       
  1253     Visitor *_visitor;
       
  1254     ///Pointer to the map of reached status of the nodes.
       
  1255     ReachedMap *_reached;
       
  1256     ///Indicates if \ref _reached is locally allocated (\c true) or not.
       
  1257     bool local_reached;
       
  1258 
       
  1259     std::vector<typename Digraph::Arc> _stack;
       
  1260     int _stack_head;
       
  1261 
       
  1262     /// \brief Creates the maps if necessary.
       
  1263     ///
       
  1264     /// Creates the maps if necessary.
       
  1265     void create_maps() {
       
  1266       if(!_reached) {
       
  1267 	local_reached = true;
       
  1268 	_reached = Traits::createReachedMap(*_digraph);
       
  1269       }
       
  1270     }
       
  1271 
       
  1272   protected:
       
  1273 
       
  1274     DfsVisit() {}
       
  1275     
       
  1276   public:
       
  1277 
       
  1278     typedef DfsVisit Create;
       
  1279 
       
  1280     /// \name Named template parameters
       
  1281 
       
  1282     ///@{
       
  1283     template <class T>
       
  1284     struct DefReachedMapTraits : public Traits {
       
  1285       typedef T ReachedMap;
       
  1286       static ReachedMap *createReachedMap(const Digraph &digraph) {
       
  1287 	throw UninitializedParameter();
       
  1288       }
       
  1289     };
       
  1290     /// \brief \ref named-templ-param "Named parameter" for setting 
       
  1291     /// ReachedMap type
       
  1292     ///
       
  1293     /// \ref named-templ-param "Named parameter" for setting ReachedMap type
       
  1294     template <class T>
       
  1295     struct DefReachedMap : public DfsVisit< Digraph, Visitor,
       
  1296 					    DefReachedMapTraits<T> > {
       
  1297       typedef DfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
       
  1298     };
       
  1299     ///@}
       
  1300 
       
  1301   public:      
       
  1302     
       
  1303     /// \brief Constructor.
       
  1304     ///
       
  1305     /// Constructor.
       
  1306     ///
       
  1307     /// \param digraph the digraph the algorithm will run on.
       
  1308     /// \param visitor The visitor of the algorithm.
       
  1309     ///
       
  1310     DfsVisit(const Digraph& digraph, Visitor& visitor) 
       
  1311       : _digraph(&digraph), _visitor(&visitor),
       
  1312 	_reached(0), local_reached(false) {}
       
  1313     
       
  1314     /// \brief Destructor.
       
  1315     ///
       
  1316     /// Destructor.
       
  1317     ~DfsVisit() {
       
  1318       if(local_reached) delete _reached;
       
  1319     }
       
  1320 
       
  1321     /// \brief Sets the map indicating if a node is reached.
       
  1322     ///
       
  1323     /// Sets the map indicating if a node is reached.
       
  1324     /// If you don't use this function before calling \ref run(),
       
  1325     /// it will allocate one. The destuctor deallocates this
       
  1326     /// automatically allocated map, of course.
       
  1327     /// \return <tt> (*this) </tt>
       
  1328     DfsVisit &reachedMap(ReachedMap &m) {
       
  1329       if(local_reached) {
       
  1330 	delete _reached;
       
  1331 	local_reached=false;
       
  1332       }
       
  1333       _reached = &m;
       
  1334       return *this;
       
  1335     }
       
  1336 
       
  1337   public:
       
  1338     /// \name Execution control
       
  1339     /// The simplest way to execute the algorithm is to use
       
  1340     /// one of the member functions called \c run(...).
       
  1341     /// \n
       
  1342     /// If you need more control on the execution,
       
  1343     /// first you must call \ref init(), then you can adda source node
       
  1344     /// with \ref addSource().
       
  1345     /// Finally \ref start() will perform the actual path
       
  1346     /// computation.
       
  1347 
       
  1348     /// @{
       
  1349     /// \brief Initializes the internal data structures.
       
  1350     ///
       
  1351     /// Initializes the internal data structures.
       
  1352     ///
       
  1353     void init() {
       
  1354       create_maps();
       
  1355       _stack.resize(countNodes(*_digraph));
       
  1356       _stack_head = -1;
       
  1357       for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
       
  1358 	_reached->set(u, false);
       
  1359       }
       
  1360     }
       
  1361     
       
  1362     /// \brief Adds a new source node.
       
  1363     ///
       
  1364     /// Adds a new source node to the set of nodes to be processed.
       
  1365     void addSource(Node s) {
       
  1366       if(!(*_reached)[s]) {
       
  1367 	  _reached->set(s,true);
       
  1368 	  _visitor->start(s);
       
  1369 	  _visitor->reach(s);
       
  1370 	  Arc e; 
       
  1371 	  _digraph->firstOut(e, s);
       
  1372 	  if (e != INVALID) {
       
  1373 	    _stack[++_stack_head] = e;
       
  1374 	  } else {
       
  1375 	    _visitor->leave(s);
       
  1376 	  }
       
  1377 	}
       
  1378     }
       
  1379     
       
  1380     /// \brief Processes the next arc.
       
  1381     ///
       
  1382     /// Processes the next arc.
       
  1383     ///
       
  1384     /// \return The processed arc.
       
  1385     ///
       
  1386     /// \pre The stack must not be empty!
       
  1387     Arc processNextArc() { 
       
  1388       Arc e = _stack[_stack_head];
       
  1389       Node m = _digraph->target(e);
       
  1390       if(!(*_reached)[m]) {
       
  1391 	_visitor->discover(e);
       
  1392 	_visitor->reach(m);
       
  1393 	_reached->set(m, true);
       
  1394 	_digraph->firstOut(_stack[++_stack_head], m);
       
  1395       } else {
       
  1396 	_visitor->examine(e);
       
  1397 	m = _digraph->source(e);
       
  1398 	_digraph->nextOut(_stack[_stack_head]);
       
  1399       }
       
  1400       while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
       
  1401 	_visitor->leave(m);
       
  1402 	--_stack_head;
       
  1403 	if (_stack_head >= 0) {
       
  1404 	  _visitor->backtrack(_stack[_stack_head]);
       
  1405 	  m = _digraph->source(_stack[_stack_head]);
       
  1406 	  _digraph->nextOut(_stack[_stack_head]);
       
  1407 	} else {
       
  1408 	  _visitor->stop(m);	  
       
  1409 	}
       
  1410       }
       
  1411       return e;
       
  1412     }
       
  1413 
       
  1414     /// \brief Next arc to be processed.
       
  1415     ///
       
  1416     /// Next arc to be processed.
       
  1417     ///
       
  1418     /// \return The next arc to be processed or INVALID if the stack is
       
  1419     /// empty.
       
  1420     Arc nextArc() { 
       
  1421       return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
       
  1422     }
       
  1423 
       
  1424     /// \brief Returns \c false if there are nodes
       
  1425     /// to be processed in the queue
       
  1426     ///
       
  1427     /// Returns \c false if there are nodes
       
  1428     /// to be processed in the queue
       
  1429     bool emptyQueue() { return _stack_head < 0; }
       
  1430 
       
  1431     /// \brief Returns the number of the nodes to be processed.
       
  1432     ///
       
  1433     /// Returns the number of the nodes to be processed in the queue.
       
  1434     int queueSize() { return _stack_head + 1; }
       
  1435     
       
  1436     /// \brief Executes the algorithm.
       
  1437     ///
       
  1438     /// Executes the algorithm.
       
  1439     ///
       
  1440     /// \pre init() must be called and at least one node should be added
       
  1441     /// with addSource() before using this function.
       
  1442     void start() {
       
  1443       while ( !emptyQueue() ) processNextArc();
       
  1444     }
       
  1445     
       
  1446     /// \brief Executes the algorithm until \c dest is reached.
       
  1447     ///
       
  1448     /// Executes the algorithm until \c dest is reached.
       
  1449     ///
       
  1450     /// \pre init() must be called and at least one node should be added
       
  1451     /// with addSource() before using this function.
       
  1452     void start(Node dest) {
       
  1453       while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest ) 
       
  1454 	processNextArc();
       
  1455     }
       
  1456     
       
  1457     /// \brief Executes the algorithm until a condition is met.
       
  1458     ///
       
  1459     /// Executes the algorithm until a condition is met.
       
  1460     ///
       
  1461     /// \pre init() must be called and at least one node should be added
       
  1462     /// with addSource() before using this function.
       
  1463     ///
       
  1464     /// \param em must be a bool (or convertible) arc map. The algorithm
       
  1465     /// will stop when it reaches an arc \c e with <tt>em[e]</tt> true.
       
  1466     ///
       
  1467     ///\return The reached arc \c e with <tt>em[e]</tt> true or
       
  1468     ///\c INVALID if no such arc was found.
       
  1469     ///
       
  1470     /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map,
       
  1471     /// not a node map.
       
  1472     template <typename EM>
       
  1473     Arc start(const EM &em) {
       
  1474       while ( !emptyQueue() && !em[_stack[_stack_head]] )
       
  1475         processNextArc();
       
  1476       return emptyQueue() ? INVALID : _stack[_stack_head];
       
  1477     }
       
  1478 
       
  1479     /// \brief Runs %DFSVisit algorithm from node \c s.
       
  1480     ///
       
  1481     /// This method runs the %DFS algorithm from a root node \c s.
       
  1482     /// \note d.run(s) is just a shortcut of the following code.
       
  1483     ///\code
       
  1484     ///   d.init();
       
  1485     ///   d.addSource(s);
       
  1486     ///   d.start();
       
  1487     ///\endcode
       
  1488     void run(Node s) {
       
  1489       init();
       
  1490       addSource(s);
       
  1491       start();
       
  1492     }
       
  1493 
       
  1494     /// \brief Runs %DFSVisit algorithm to visit all nodes in the digraph.
       
  1495     
       
  1496     /// This method runs the %DFS algorithm in order to
       
  1497     /// compute the %DFS path to each node. The algorithm computes
       
  1498     /// - The %DFS tree.
       
  1499     /// - The distance of each node from the root in the %DFS tree.
       
  1500     ///
       
  1501     ///\note d.run() is just a shortcut of the following code.
       
  1502     ///\code
       
  1503     ///  d.init();
       
  1504     ///  for (NodeIt it(digraph); it != INVALID; ++it) {
       
  1505     ///    if (!d.reached(it)) {
       
  1506     ///      d.addSource(it);
       
  1507     ///      d.start();
       
  1508     ///    }
       
  1509     ///  }
       
  1510     ///\endcode
       
  1511     void run() {
       
  1512       init();
       
  1513       for (NodeIt it(*_digraph); it != INVALID; ++it) {
       
  1514         if (!reached(it)) {
       
  1515           addSource(it);
       
  1516           start();
       
  1517         }
       
  1518       }
       
  1519     }
       
  1520     ///@}
       
  1521 
       
  1522     /// \name Query Functions
       
  1523     /// The result of the %DFS algorithm can be obtained using these
       
  1524     /// functions.\n
       
  1525     /// Before the use of these functions,
       
  1526     /// either run() or start() must be called.
       
  1527     ///@{
       
  1528     /// \brief Checks if a node is reachable from the root.
       
  1529     ///
       
  1530     /// Returns \c true if \c v is reachable from the root(s).
       
  1531     /// \warning The source nodes are inditated as unreachable.
       
  1532     /// \pre Either \ref run() or \ref start()
       
  1533     /// must be called before using this function.
       
  1534     ///
       
  1535     bool reached(Node v) { return (*_reached)[v]; }
       
  1536     ///@}
       
  1537   };
       
  1538 
       
  1539 
       
  1540 } //END OF NAMESPACE LEMON
       
  1541 
       
  1542 #endif
       
  1543