lemon/dfs.h
changeset 100 4f754b4cf82b
child 157 2ccc1afc2c52
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/lemon/dfs.h	Thu Feb 07 21:37:07 2008 +0000
     1.3 @@ -0,0 +1,1543 @@
     1.4 +/* -*- C++ -*-
     1.5 + *
     1.6 + * This file is a part of LEMON, a generic C++ optimization library
     1.7 + *
     1.8 + * Copyright (C) 2003-2008
     1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.11 + *
    1.12 + * Permission to use, modify and distribute this software is granted
    1.13 + * provided that this copyright notice appears in all copies. For
    1.14 + * precise terms see the accompanying LICENSE file.
    1.15 + *
    1.16 + * This software is provided "AS IS" with no warranty of any kind,
    1.17 + * express or implied, and with no claim as to its suitability for any
    1.18 + * purpose.
    1.19 + *
    1.20 + */
    1.21 +
    1.22 +#ifndef LEMON_DFS_H
    1.23 +#define LEMON_DFS_H
    1.24 +
    1.25 +///\ingroup search
    1.26 +///\file
    1.27 +///\brief Dfs algorithm.
    1.28 +
    1.29 +#include <lemon/list_graph.h>
    1.30 +#include <lemon/graph_utils.h>
    1.31 +#include <lemon/bits/path_dump.h>
    1.32 +#include <lemon/bits/invalid.h>
    1.33 +#include <lemon/error.h>
    1.34 +#include <lemon/maps.h>
    1.35 +
    1.36 +#include <lemon/concept_check.h>
    1.37 +
    1.38 +namespace lemon {
    1.39 +
    1.40 +  
    1.41 +  ///Default traits class of Dfs class.
    1.42 +
    1.43 +  ///Default traits class of Dfs class.
    1.44 +  ///\param GR Digraph type.
    1.45 +  template<class GR>
    1.46 +  struct DfsDefaultTraits
    1.47 +  {
    1.48 +    ///The digraph type the algorithm runs on. 
    1.49 +    typedef GR Digraph;
    1.50 +    ///\brief The type of the map that stores the last
    1.51 +    ///arcs of the %DFS paths.
    1.52 +    /// 
    1.53 +    ///The type of the map that stores the last
    1.54 +    ///arcs of the %DFS paths.
    1.55 +    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.56 +    ///
    1.57 +    typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
    1.58 +    ///Instantiates a PredMap.
    1.59 + 
    1.60 +    ///This function instantiates a \ref PredMap. 
    1.61 +    ///\param G is the digraph, to which we would like to define the PredMap.
    1.62 +    ///\todo The digraph alone may be insufficient to initialize
    1.63 +    static PredMap *createPredMap(const GR &G) 
    1.64 +    {
    1.65 +      return new PredMap(G);
    1.66 +    }
    1.67 +
    1.68 +    ///The type of the map that indicates which nodes are processed.
    1.69 + 
    1.70 +    ///The type of the map that indicates which nodes are processed.
    1.71 +    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.72 +    ///\todo named parameter to set this type, function to read and write.
    1.73 +    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    1.74 +    ///Instantiates a ProcessedMap.
    1.75 + 
    1.76 +    ///This function instantiates a \ref ProcessedMap. 
    1.77 +    ///\param g is the digraph, to which
    1.78 +    ///we would like to define the \ref ProcessedMap
    1.79 +#ifdef DOXYGEN
    1.80 +    static ProcessedMap *createProcessedMap(const GR &g)
    1.81 +#else
    1.82 +    static ProcessedMap *createProcessedMap(const GR &)
    1.83 +#endif
    1.84 +    {
    1.85 +      return new ProcessedMap();
    1.86 +    }
    1.87 +    ///The type of the map that indicates which nodes are reached.
    1.88 + 
    1.89 +    ///The type of the map that indicates which nodes are reached.
    1.90 +    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    1.91 +    ///\todo named parameter to set this type, function to read and write.
    1.92 +    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    1.93 +    ///Instantiates a ReachedMap.
    1.94 + 
    1.95 +    ///This function instantiates a \ref ReachedMap. 
    1.96 +    ///\param G is the digraph, to which
    1.97 +    ///we would like to define the \ref ReachedMap.
    1.98 +    static ReachedMap *createReachedMap(const GR &G)
    1.99 +    {
   1.100 +      return new ReachedMap(G);
   1.101 +    }
   1.102 +    ///The type of the map that stores the dists of the nodes.
   1.103 + 
   1.104 +    ///The type of the map that stores the dists of the nodes.
   1.105 +    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   1.106 +    ///
   1.107 +    typedef typename Digraph::template NodeMap<int> DistMap;
   1.108 +    ///Instantiates a DistMap.
   1.109 + 
   1.110 +    ///This function instantiates a \ref DistMap. 
   1.111 +    ///\param G is the digraph, to which we would like to define the \ref DistMap
   1.112 +    static DistMap *createDistMap(const GR &G)
   1.113 +    {
   1.114 +      return new DistMap(G);
   1.115 +    }
   1.116 +  };
   1.117 +  
   1.118 +  ///%DFS algorithm class.
   1.119 +  
   1.120 +  ///\ingroup search
   1.121 +  ///This class provides an efficient implementation of the %DFS algorithm.
   1.122 +  ///
   1.123 +  ///\param GR The digraph type the algorithm runs on. The default value is
   1.124 +  ///\ref ListDigraph. The value of GR is not used directly by Dfs, it
   1.125 +  ///is only passed to \ref DfsDefaultTraits.
   1.126 +  ///\param TR Traits class to set various data types used by the algorithm.
   1.127 +  ///The default traits class is
   1.128 +  ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
   1.129 +  ///See \ref DfsDefaultTraits for the documentation of
   1.130 +  ///a Dfs traits class.
   1.131 +  ///
   1.132 +  ///\author Jacint Szabo and Alpar Juttner
   1.133 +#ifdef DOXYGEN
   1.134 +  template <typename GR,
   1.135 +	    typename TR>
   1.136 +#else
   1.137 +  template <typename GR=ListDigraph,
   1.138 +	    typename TR=DfsDefaultTraits<GR> >
   1.139 +#endif
   1.140 +  class Dfs {
   1.141 +  public:
   1.142 +    /**
   1.143 +     * \brief \ref Exception for uninitialized parameters.
   1.144 +     *
   1.145 +     * This error represents problems in the initialization
   1.146 +     * of the parameters of the algorithms.
   1.147 +     */
   1.148 +    class UninitializedParameter : public lemon::UninitializedParameter {
   1.149 +    public:
   1.150 +      virtual const char* what() const throw() {
   1.151 +	return "lemon::Dfs::UninitializedParameter";
   1.152 +      }
   1.153 +    };
   1.154 +
   1.155 +    typedef TR Traits;
   1.156 +    ///The type of the underlying digraph.
   1.157 +    typedef typename TR::Digraph Digraph;
   1.158 +    ///\e
   1.159 +    typedef typename Digraph::Node Node;
   1.160 +    ///\e
   1.161 +    typedef typename Digraph::NodeIt NodeIt;
   1.162 +    ///\e
   1.163 +    typedef typename Digraph::Arc Arc;
   1.164 +    ///\e
   1.165 +    typedef typename Digraph::OutArcIt OutArcIt;
   1.166 +    
   1.167 +    ///\brief The type of the map that stores the last
   1.168 +    ///arcs of the %DFS paths.
   1.169 +    typedef typename TR::PredMap PredMap;
   1.170 +    ///The type of the map indicating which nodes are reached.
   1.171 +    typedef typename TR::ReachedMap ReachedMap;
   1.172 +    ///The type of the map indicating which nodes are processed.
   1.173 +    typedef typename TR::ProcessedMap ProcessedMap;
   1.174 +    ///The type of the map that stores the dists of the nodes.
   1.175 +    typedef typename TR::DistMap DistMap;
   1.176 +  private:
   1.177 +    /// Pointer to the underlying digraph.
   1.178 +    const Digraph *G;
   1.179 +    ///Pointer to the map of predecessors arcs.
   1.180 +    PredMap *_pred;
   1.181 +    ///Indicates if \ref _pred is locally allocated (\c true) or not.
   1.182 +    bool local_pred;
   1.183 +    ///Pointer to the map of distances.
   1.184 +    DistMap *_dist;
   1.185 +    ///Indicates if \ref _dist is locally allocated (\c true) or not.
   1.186 +    bool local_dist;
   1.187 +    ///Pointer to the map of reached status of the nodes.
   1.188 +    ReachedMap *_reached;
   1.189 +    ///Indicates if \ref _reached is locally allocated (\c true) or not.
   1.190 +    bool local_reached;
   1.191 +    ///Pointer to the map of processed status of the nodes.
   1.192 +    ProcessedMap *_processed;
   1.193 +    ///Indicates if \ref _processed is locally allocated (\c true) or not.
   1.194 +    bool local_processed;
   1.195 +
   1.196 +    std::vector<typename Digraph::OutArcIt> _stack;
   1.197 +    int _stack_head;
   1.198 +
   1.199 +    ///Creates the maps if necessary.
   1.200 +    
   1.201 +    ///\todo Better memory allocation (instead of new).
   1.202 +    void create_maps() 
   1.203 +    {
   1.204 +      if(!_pred) {
   1.205 +	local_pred = true;
   1.206 +	_pred = Traits::createPredMap(*G);
   1.207 +      }
   1.208 +      if(!_dist) {
   1.209 +	local_dist = true;
   1.210 +	_dist = Traits::createDistMap(*G);
   1.211 +      }
   1.212 +      if(!_reached) {
   1.213 +	local_reached = true;
   1.214 +	_reached = Traits::createReachedMap(*G);
   1.215 +      }
   1.216 +      if(!_processed) {
   1.217 +	local_processed = true;
   1.218 +	_processed = Traits::createProcessedMap(*G);
   1.219 +      }
   1.220 +    }
   1.221 +
   1.222 +  protected:
   1.223 +
   1.224 +    Dfs() {}
   1.225 +    
   1.226 +  public:
   1.227 +
   1.228 +    typedef Dfs Create;
   1.229 +
   1.230 +    ///\name Named template parameters
   1.231 +
   1.232 +    ///@{
   1.233 +
   1.234 +    template <class T>
   1.235 +    struct DefPredMapTraits : public Traits {
   1.236 +      typedef T PredMap;
   1.237 +      static PredMap *createPredMap(const Digraph &G) 
   1.238 +      {
   1.239 +	throw UninitializedParameter();
   1.240 +      }
   1.241 +    };
   1.242 +    ///\brief \ref named-templ-param "Named parameter" for setting
   1.243 +    ///PredMap type
   1.244 +    ///
   1.245 +    ///\ref named-templ-param "Named parameter" for setting PredMap type
   1.246 +    ///
   1.247 +    template <class T>
   1.248 +    struct DefPredMap : public Dfs<Digraph, DefPredMapTraits<T> > {
   1.249 +      typedef Dfs<Digraph, DefPredMapTraits<T> > Create;
   1.250 +    };
   1.251 +    
   1.252 +    
   1.253 +    template <class T>
   1.254 +    struct DefDistMapTraits : public Traits {
   1.255 +      typedef T DistMap;
   1.256 +      static DistMap *createDistMap(const Digraph &) 
   1.257 +      {
   1.258 +	throw UninitializedParameter();
   1.259 +      }
   1.260 +    };
   1.261 +    ///\brief \ref named-templ-param "Named parameter" for setting
   1.262 +    ///DistMap type
   1.263 +    ///
   1.264 +    ///\ref named-templ-param "Named parameter" for setting DistMap
   1.265 +    ///type
   1.266 +    template <class T>
   1.267 +    struct DefDistMap {
   1.268 +      typedef Dfs<Digraph, DefDistMapTraits<T> > Create;
   1.269 +    };
   1.270 +    
   1.271 +    template <class T>
   1.272 +    struct DefReachedMapTraits : public Traits {
   1.273 +      typedef T ReachedMap;
   1.274 +      static ReachedMap *createReachedMap(const Digraph &) 
   1.275 +      {
   1.276 +	throw UninitializedParameter();
   1.277 +      }
   1.278 +    };
   1.279 +    ///\brief \ref named-templ-param "Named parameter" for setting
   1.280 +    ///ReachedMap type
   1.281 +    ///
   1.282 +    ///\ref named-templ-param "Named parameter" for setting ReachedMap type
   1.283 +    ///
   1.284 +    template <class T>
   1.285 +    struct DefReachedMap : public Dfs< Digraph, DefReachedMapTraits<T> > {
   1.286 +      typedef Dfs< Digraph, DefReachedMapTraits<T> > Create;
   1.287 +    };
   1.288 +
   1.289 +    template <class T>
   1.290 +    struct DefProcessedMapTraits : public Traits {
   1.291 +      typedef T ProcessedMap;
   1.292 +      static ProcessedMap *createProcessedMap(const Digraph &) 
   1.293 +      {
   1.294 +	throw UninitializedParameter();
   1.295 +      }
   1.296 +    };
   1.297 +    ///\brief \ref named-templ-param "Named parameter" for setting
   1.298 +    ///ProcessedMap type
   1.299 +    ///
   1.300 +    ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
   1.301 +    ///
   1.302 +    template <class T>
   1.303 +    struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > { 
   1.304 +      typedef Dfs< Digraph, DefProcessedMapTraits<T> > Create;
   1.305 +    };
   1.306 +    
   1.307 +    struct DefDigraphProcessedMapTraits : public Traits {
   1.308 +      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
   1.309 +      static ProcessedMap *createProcessedMap(const Digraph &G) 
   1.310 +      {
   1.311 +	return new ProcessedMap(G);
   1.312 +      }
   1.313 +    };
   1.314 +    ///\brief \ref named-templ-param "Named parameter"
   1.315 +    ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
   1.316 +    ///
   1.317 +    ///\ref named-templ-param "Named parameter"
   1.318 +    ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
   1.319 +    ///If you don't set it explicitely, it will be automatically allocated.
   1.320 +    template <class T>
   1.321 +    class DefProcessedMapToBeDefaultMap :
   1.322 +      public Dfs< Digraph, DefDigraphProcessedMapTraits> { 
   1.323 +      typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create;
   1.324 +    };
   1.325 +    
   1.326 +    ///@}
   1.327 +
   1.328 +  public:      
   1.329 +    
   1.330 +    ///Constructor.
   1.331 +    
   1.332 +    ///\param _G the digraph the algorithm will run on.
   1.333 +    ///
   1.334 +    Dfs(const Digraph& _G) :
   1.335 +      G(&_G),
   1.336 +      _pred(NULL), local_pred(false),
   1.337 +      _dist(NULL), local_dist(false),
   1.338 +      _reached(NULL), local_reached(false),
   1.339 +      _processed(NULL), local_processed(false)
   1.340 +    { }
   1.341 +    
   1.342 +    ///Destructor.
   1.343 +    ~Dfs() 
   1.344 +    {
   1.345 +      if(local_pred) delete _pred;
   1.346 +      if(local_dist) delete _dist;
   1.347 +      if(local_reached) delete _reached;
   1.348 +      if(local_processed) delete _processed;
   1.349 +    }
   1.350 +
   1.351 +    ///Sets the map storing the predecessor arcs.
   1.352 +
   1.353 +    ///Sets the map storing the predecessor arcs.
   1.354 +    ///If you don't use this function before calling \ref run(),
   1.355 +    ///it will allocate one. The destuctor deallocates this
   1.356 +    ///automatically allocated map, of course.
   1.357 +    ///\return <tt> (*this) </tt>
   1.358 +    Dfs &predMap(PredMap &m) 
   1.359 +    {
   1.360 +      if(local_pred) {
   1.361 +	delete _pred;
   1.362 +	local_pred=false;
   1.363 +      }
   1.364 +      _pred = &m;
   1.365 +      return *this;
   1.366 +    }
   1.367 +
   1.368 +    ///Sets the map storing the distances calculated by the algorithm.
   1.369 +
   1.370 +    ///Sets the map storing the distances calculated by the algorithm.
   1.371 +    ///If you don't use this function before calling \ref run(),
   1.372 +    ///it will allocate one. The destuctor deallocates this
   1.373 +    ///automatically allocated map, of course.
   1.374 +    ///\return <tt> (*this) </tt>
   1.375 +    Dfs &distMap(DistMap &m) 
   1.376 +    {
   1.377 +      if(local_dist) {
   1.378 +	delete _dist;
   1.379 +	local_dist=false;
   1.380 +      }
   1.381 +      _dist = &m;
   1.382 +      return *this;
   1.383 +    }
   1.384 +
   1.385 +    ///Sets the map indicating if a node is reached.
   1.386 +
   1.387 +    ///Sets the map indicating if a node is reached.
   1.388 +    ///If you don't use this function before calling \ref run(),
   1.389 +    ///it will allocate one. The destuctor deallocates this
   1.390 +    ///automatically allocated map, of course.
   1.391 +    ///\return <tt> (*this) </tt>
   1.392 +    Dfs &reachedMap(ReachedMap &m) 
   1.393 +    {
   1.394 +      if(local_reached) {
   1.395 +	delete _reached;
   1.396 +	local_reached=false;
   1.397 +      }
   1.398 +      _reached = &m;
   1.399 +      return *this;
   1.400 +    }
   1.401 +
   1.402 +    ///Sets the map indicating if a node is processed.
   1.403 +
   1.404 +    ///Sets the map indicating if a node is processed.
   1.405 +    ///If you don't use this function before calling \ref run(),
   1.406 +    ///it will allocate one. The destuctor deallocates this
   1.407 +    ///automatically allocated map, of course.
   1.408 +    ///\return <tt> (*this) </tt>
   1.409 +    Dfs &processedMap(ProcessedMap &m) 
   1.410 +    {
   1.411 +      if(local_processed) {
   1.412 +	delete _processed;
   1.413 +	local_processed=false;
   1.414 +      }
   1.415 +      _processed = &m;
   1.416 +      return *this;
   1.417 +    }
   1.418 +
   1.419 +  public:
   1.420 +    ///\name Execution control
   1.421 +    ///The simplest way to execute the algorithm is to use
   1.422 +    ///one of the member functions called \c run(...).
   1.423 +    ///\n
   1.424 +    ///If you need more control on the execution,
   1.425 +    ///first you must call \ref init(), then you can add a source node
   1.426 +    ///with \ref addSource().
   1.427 +    ///Finally \ref start() will perform the actual path
   1.428 +    ///computation.
   1.429 +
   1.430 +    ///@{
   1.431 +
   1.432 +    ///Initializes the internal data structures.
   1.433 +
   1.434 +    ///Initializes the internal data structures.
   1.435 +    ///
   1.436 +    void init()
   1.437 +    {
   1.438 +      create_maps();
   1.439 +      _stack.resize(countNodes(*G));
   1.440 +      _stack_head=-1;
   1.441 +      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
   1.442 +	_pred->set(u,INVALID);
   1.443 +	// _predNode->set(u,INVALID);
   1.444 +	_reached->set(u,false);
   1.445 +	_processed->set(u,false);
   1.446 +      }
   1.447 +    }
   1.448 +    
   1.449 +    ///Adds a new source node.
   1.450 +
   1.451 +    ///Adds a new source node to the set of nodes to be processed.
   1.452 +    ///
   1.453 +    ///\warning dists are wrong (or at least strange)
   1.454 +    ///in case of multiple sources.
   1.455 +    void addSource(Node s)
   1.456 +    {
   1.457 +      if(!(*_reached)[s])
   1.458 +	{
   1.459 +	  _reached->set(s,true);
   1.460 +	  _pred->set(s,INVALID);
   1.461 +	  OutArcIt e(*G,s);
   1.462 +	  if(e!=INVALID) {
   1.463 +	    _stack[++_stack_head]=e;
   1.464 +	    _dist->set(s,_stack_head);
   1.465 +	  }
   1.466 +	  else {
   1.467 +	    _processed->set(s,true);
   1.468 +	    _dist->set(s,0);
   1.469 +	  }
   1.470 +	}
   1.471 +    }
   1.472 +    
   1.473 +    ///Processes the next arc.
   1.474 +
   1.475 +    ///Processes the next arc.
   1.476 +    ///
   1.477 +    ///\return The processed arc.
   1.478 +    ///
   1.479 +    ///\pre The stack must not be empty!
   1.480 +    Arc processNextArc()
   1.481 +    { 
   1.482 +      Node m;
   1.483 +      Arc e=_stack[_stack_head];
   1.484 +      if(!(*_reached)[m=G->target(e)]) {
   1.485 +	_pred->set(m,e);
   1.486 +	_reached->set(m,true);
   1.487 +	++_stack_head;
   1.488 +	_stack[_stack_head] = OutArcIt(*G, m);
   1.489 +	_dist->set(m,_stack_head);
   1.490 +      }
   1.491 +      else {
   1.492 +	m=G->source(e);
   1.493 +	++_stack[_stack_head];
   1.494 +      }
   1.495 +      while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
   1.496 +	_processed->set(m,true);
   1.497 +	--_stack_head;
   1.498 +	if(_stack_head>=0) {
   1.499 +	  m=G->source(_stack[_stack_head]);
   1.500 +	  ++_stack[_stack_head];
   1.501 +	}
   1.502 +      }
   1.503 +      return e;
   1.504 +    }
   1.505 +    ///Next arc to be processed.
   1.506 +
   1.507 +    ///Next arc to be processed.
   1.508 +    ///
   1.509 +    ///\return The next arc to be processed or INVALID if the stack is
   1.510 +    /// empty.
   1.511 +    OutArcIt nextArc()
   1.512 +    { 
   1.513 +      return _stack_head>=0?_stack[_stack_head]:INVALID;
   1.514 +    }
   1.515 +
   1.516 +    ///\brief Returns \c false if there are nodes
   1.517 +    ///to be processed in the queue
   1.518 +    ///
   1.519 +    ///Returns \c false if there are nodes
   1.520 +    ///to be processed in the queue
   1.521 +    bool emptyQueue() { return _stack_head<0; }
   1.522 +    ///Returns the number of the nodes to be processed.
   1.523 +    
   1.524 +    ///Returns the number of the nodes to be processed in the queue.
   1.525 +    int queueSize() { return _stack_head+1; }
   1.526 +    
   1.527 +    ///Executes the algorithm.
   1.528 +
   1.529 +    ///Executes the algorithm.
   1.530 +    ///
   1.531 +    ///\pre init() must be called and at least one node should be added
   1.532 +    ///with addSource() before using this function.
   1.533 +    ///
   1.534 +    ///This method runs the %DFS algorithm from the root node(s)
   1.535 +    ///in order to
   1.536 +    ///compute the
   1.537 +    ///%DFS path to each node. The algorithm computes
   1.538 +    ///- The %DFS tree.
   1.539 +    ///- The distance of each node from the root(s) in the %DFS tree.
   1.540 +    ///
   1.541 +    void start()
   1.542 +    {
   1.543 +      while ( !emptyQueue() ) processNextArc();
   1.544 +    }
   1.545 +    
   1.546 +    ///Executes the algorithm until \c dest is reached.
   1.547 +
   1.548 +    ///Executes the algorithm until \c dest is reached.
   1.549 +    ///
   1.550 +    ///\pre init() must be called and at least one node should be added
   1.551 +    ///with addSource() before using this function.
   1.552 +    ///
   1.553 +    ///This method runs the %DFS algorithm from the root node(s)
   1.554 +    ///in order to
   1.555 +    ///compute the
   1.556 +    ///%DFS path to \c dest. The algorithm computes
   1.557 +    ///- The %DFS path to \c  dest.
   1.558 +    ///- The distance of \c dest from the root(s) in the %DFS tree.
   1.559 +    ///
   1.560 +    void start(Node dest)
   1.561 +    {
   1.562 +      while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest ) 
   1.563 +	processNextArc();
   1.564 +    }
   1.565 +    
   1.566 +    ///Executes the algorithm until a condition is met.
   1.567 +
   1.568 +    ///Executes the algorithm until a condition is met.
   1.569 +    ///
   1.570 +    ///\pre init() must be called and at least one node should be added
   1.571 +    ///with addSource() before using this function.
   1.572 +    ///
   1.573 +    ///\param em must be a bool (or convertible) arc map. The algorithm
   1.574 +    ///will stop when it reaches an arc \c e with <tt>em[e]</tt> true.
   1.575 +    ///
   1.576 +    ///\return The reached arc \c e with <tt>em[e]</tt> true or
   1.577 +    ///\c INVALID if no such arc was found.
   1.578 +    ///
   1.579 +    ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map,
   1.580 +    ///not a node map.
   1.581 +    template<class EM>
   1.582 +    Arc start(const EM &em)
   1.583 +    {
   1.584 +      while ( !emptyQueue() && !em[_stack[_stack_head]] )
   1.585 +        processNextArc();
   1.586 +      return emptyQueue() ? INVALID : _stack[_stack_head];
   1.587 +    }
   1.588 +
   1.589 +    ///Runs %DFS algorithm to visit all nodes in the digraph.
   1.590 +    
   1.591 +    ///This method runs the %DFS algorithm in order to
   1.592 +    ///compute the
   1.593 +    ///%DFS path to each node. The algorithm computes
   1.594 +    ///- The %DFS tree.
   1.595 +    ///- The distance of each node from the root in the %DFS tree.
   1.596 +    ///
   1.597 +    ///\note d.run() is just a shortcut of the following code.
   1.598 +    ///\code
   1.599 +    ///  d.init();
   1.600 +    ///  for (NodeIt it(digraph); it != INVALID; ++it) {
   1.601 +    ///    if (!d.reached(it)) {
   1.602 +    ///      d.addSource(it);
   1.603 +    ///      d.start();
   1.604 +    ///    }
   1.605 +    ///  }
   1.606 +    ///\endcode
   1.607 +    void run() {
   1.608 +      init();
   1.609 +      for (NodeIt it(*G); it != INVALID; ++it) {
   1.610 +        if (!reached(it)) {
   1.611 +          addSource(it);
   1.612 +          start();
   1.613 +        }
   1.614 +      }
   1.615 +    }
   1.616 +
   1.617 +    ///Runs %DFS algorithm from node \c s.
   1.618 +    
   1.619 +    ///This method runs the %DFS algorithm from a root node \c s
   1.620 +    ///in order to
   1.621 +    ///compute the
   1.622 +    ///%DFS path to each node. The algorithm computes
   1.623 +    ///- The %DFS tree.
   1.624 +    ///- The distance of each node from the root in the %DFS tree.
   1.625 +    ///
   1.626 +    ///\note d.run(s) is just a shortcut of the following code.
   1.627 +    ///\code
   1.628 +    ///  d.init();
   1.629 +    ///  d.addSource(s);
   1.630 +    ///  d.start();
   1.631 +    ///\endcode
   1.632 +    void run(Node s) {
   1.633 +      init();
   1.634 +      addSource(s);
   1.635 +      start();
   1.636 +    }
   1.637 +    
   1.638 +    ///Finds the %DFS path between \c s and \c t.
   1.639 +    
   1.640 +    ///Finds the %DFS path between \c s and \c t.
   1.641 +    ///
   1.642 +    ///\return The length of the %DFS s---t path if there exists one,
   1.643 +    ///0 otherwise.
   1.644 +    ///\note Apart from the return value, d.run(s,t) is
   1.645 +    ///just a shortcut of the following code.
   1.646 +    ///\code
   1.647 +    ///  d.init();
   1.648 +    ///  d.addSource(s);
   1.649 +    ///  d.start(t);
   1.650 +    ///\endcode
   1.651 +    int run(Node s,Node t) {
   1.652 +      init();
   1.653 +      addSource(s);
   1.654 +      start(t);
   1.655 +      return reached(t)?_stack_head+1:0;
   1.656 +    }
   1.657 +    
   1.658 +    ///@}
   1.659 +
   1.660 +    ///\name Query Functions
   1.661 +    ///The result of the %DFS algorithm can be obtained using these
   1.662 +    ///functions.\n
   1.663 +    ///Before the use of these functions,
   1.664 +    ///either run() or start() must be called.
   1.665 +    
   1.666 +    ///@{
   1.667 +
   1.668 +    typedef PredMapPath<Digraph, PredMap> Path;
   1.669 +
   1.670 +    ///Gives back the shortest path.
   1.671 +    
   1.672 +    ///Gives back the shortest path.
   1.673 +    ///\pre The \c t should be reachable from the source.
   1.674 +    Path path(Node t) 
   1.675 +    {
   1.676 +      return Path(*G, *_pred, t);
   1.677 +    }
   1.678 +
   1.679 +    ///The distance of a node from the root(s).
   1.680 +
   1.681 +    ///Returns the distance of a node from the root(s).
   1.682 +    ///\pre \ref run() must be called before using this function.
   1.683 +    ///\warning If node \c v is unreachable from the root(s) then the return 
   1.684 +    ///value of this funcion is undefined.
   1.685 +    int dist(Node v) const { return (*_dist)[v]; }
   1.686 +
   1.687 +    ///Returns the 'previous arc' of the %DFS tree.
   1.688 +
   1.689 +    ///For a node \c v it returns the 'previous arc'
   1.690 +    ///of the %DFS path,
   1.691 +    ///i.e. it returns the last arc of a %DFS path from the root(s) to \c
   1.692 +    ///v. It is \ref INVALID
   1.693 +    ///if \c v is unreachable from the root(s) or \c v is a root. The
   1.694 +    ///%DFS tree used here is equal to the %DFS tree used in
   1.695 +    ///\ref predNode().
   1.696 +    ///\pre Either \ref run() or \ref start() must be called before using
   1.697 +    ///this function.
   1.698 +    Arc predArc(Node v) const { return (*_pred)[v];}
   1.699 +
   1.700 +    ///Returns the 'previous node' of the %DFS tree.
   1.701 +
   1.702 +    ///For a node \c v it returns the 'previous node'
   1.703 +    ///of the %DFS tree,
   1.704 +    ///i.e. it returns the last but one node from a %DFS path from the
   1.705 +    ///root(s) to \c v.
   1.706 +    ///It is INVALID if \c v is unreachable from the root(s) or
   1.707 +    ///if \c v itself a root.
   1.708 +    ///The %DFS tree used here is equal to the %DFS
   1.709 +    ///tree used in \ref predArc().
   1.710 +    ///\pre Either \ref run() or \ref start() must be called before
   1.711 +    ///using this function.
   1.712 +    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
   1.713 +				  G->source((*_pred)[v]); }
   1.714 +    
   1.715 +    ///Returns a reference to the NodeMap of distances.
   1.716 +
   1.717 +    ///Returns a reference to the NodeMap of distances.
   1.718 +    ///\pre Either \ref run() or \ref init() must
   1.719 +    ///be called before using this function.
   1.720 +    const DistMap &distMap() const { return *_dist;}
   1.721 + 
   1.722 +    ///Returns a reference to the %DFS arc-tree map.
   1.723 +
   1.724 +    ///Returns a reference to the NodeMap of the arcs of the
   1.725 +    ///%DFS tree.
   1.726 +    ///\pre Either \ref run() or \ref init()
   1.727 +    ///must be called before using this function.
   1.728 +    const PredMap &predMap() const { return *_pred;}
   1.729 + 
   1.730 +    ///Checks if a node is reachable from the root.
   1.731 +
   1.732 +    ///Returns \c true if \c v is reachable from the root(s).
   1.733 +    ///\warning The source nodes are inditated as unreachable.
   1.734 +    ///\pre Either \ref run() or \ref start()
   1.735 +    ///must be called before using this function.
   1.736 +    ///
   1.737 +    bool reached(Node v) { return (*_reached)[v]; }
   1.738 +    
   1.739 +    ///@}
   1.740 +  };
   1.741 +
   1.742 +  ///Default traits class of Dfs function.
   1.743 +
   1.744 +  ///Default traits class of Dfs function.
   1.745 +  ///\param GR Digraph type.
   1.746 +  template<class GR>
   1.747 +  struct DfsWizardDefaultTraits
   1.748 +  {
   1.749 +    ///The digraph type the algorithm runs on. 
   1.750 +    typedef GR Digraph;
   1.751 +    ///\brief The type of the map that stores the last
   1.752 +    ///arcs of the %DFS paths.
   1.753 +    /// 
   1.754 +    ///The type of the map that stores the last
   1.755 +    ///arcs of the %DFS paths.
   1.756 +    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   1.757 +    ///
   1.758 +    typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
   1.759 +    ///Instantiates a PredMap.
   1.760 + 
   1.761 +    ///This function instantiates a \ref PredMap. 
   1.762 +    ///\param g is the digraph, to which we would like to define the PredMap.
   1.763 +    ///\todo The digraph alone may be insufficient to initialize
   1.764 +#ifdef DOXYGEN
   1.765 +    static PredMap *createPredMap(const GR &g) 
   1.766 +#else
   1.767 +    static PredMap *createPredMap(const GR &) 
   1.768 +#endif
   1.769 +    {
   1.770 +      return new PredMap();
   1.771 +    }
   1.772 +
   1.773 +    ///The type of the map that indicates which nodes are processed.
   1.774 + 
   1.775 +    ///The type of the map that indicates which nodes are processed.
   1.776 +    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   1.777 +    ///\todo named parameter to set this type, function to read and write.
   1.778 +    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
   1.779 +    ///Instantiates a ProcessedMap.
   1.780 + 
   1.781 +    ///This function instantiates a \ref ProcessedMap. 
   1.782 +    ///\param g is the digraph, to which
   1.783 +    ///we would like to define the \ref ProcessedMap
   1.784 +#ifdef DOXYGEN
   1.785 +    static ProcessedMap *createProcessedMap(const GR &g)
   1.786 +#else
   1.787 +    static ProcessedMap *createProcessedMap(const GR &)
   1.788 +#endif
   1.789 +    {
   1.790 +      return new ProcessedMap();
   1.791 +    }
   1.792 +    ///The type of the map that indicates which nodes are reached.
   1.793 + 
   1.794 +    ///The type of the map that indicates which nodes are reached.
   1.795 +    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   1.796 +    ///\todo named parameter to set this type, function to read and write.
   1.797 +    typedef typename Digraph::template NodeMap<bool> ReachedMap;
   1.798 +    ///Instantiates a ReachedMap.
   1.799 + 
   1.800 +    ///This function instantiates a \ref ReachedMap. 
   1.801 +    ///\param G is the digraph, to which
   1.802 +    ///we would like to define the \ref ReachedMap.
   1.803 +    static ReachedMap *createReachedMap(const GR &G)
   1.804 +    {
   1.805 +      return new ReachedMap(G);
   1.806 +    }
   1.807 +    ///The type of the map that stores the dists of the nodes.
   1.808 + 
   1.809 +    ///The type of the map that stores the dists of the nodes.
   1.810 +    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
   1.811 +    ///
   1.812 +    typedef NullMap<typename Digraph::Node,int> DistMap;
   1.813 +    ///Instantiates a DistMap.
   1.814 + 
   1.815 +    ///This function instantiates a \ref DistMap. 
   1.816 +    ///\param g is the digraph, to which we would like to define the \ref DistMap
   1.817 +#ifdef DOXYGEN
   1.818 +    static DistMap *createDistMap(const GR &g)
   1.819 +#else
   1.820 +    static DistMap *createDistMap(const GR &)
   1.821 +#endif
   1.822 +    {
   1.823 +      return new DistMap();
   1.824 +    }
   1.825 +  };
   1.826 +  
   1.827 +  /// Default traits used by \ref DfsWizard
   1.828 +
   1.829 +  /// To make it easier to use Dfs algorithm
   1.830 +  ///we have created a wizard class.
   1.831 +  /// This \ref DfsWizard class needs default traits,
   1.832 +  ///as well as the \ref Dfs class.
   1.833 +  /// The \ref DfsWizardBase is a class to be the default traits of the
   1.834 +  /// \ref DfsWizard class.
   1.835 +  template<class GR>
   1.836 +  class DfsWizardBase : public DfsWizardDefaultTraits<GR>
   1.837 +  {
   1.838 +
   1.839 +    typedef DfsWizardDefaultTraits<GR> Base;
   1.840 +  protected:
   1.841 +    /// Type of the nodes in the digraph.
   1.842 +    typedef typename Base::Digraph::Node Node;
   1.843 +
   1.844 +    /// Pointer to the underlying digraph.
   1.845 +    void *_g;
   1.846 +    ///Pointer to the map of reached nodes.
   1.847 +    void *_reached;
   1.848 +    ///Pointer to the map of processed nodes.
   1.849 +    void *_processed;
   1.850 +    ///Pointer to the map of predecessors arcs.
   1.851 +    void *_pred;
   1.852 +    ///Pointer to the map of distances.
   1.853 +    void *_dist;
   1.854 +    ///Pointer to the source node.
   1.855 +    Node _source;
   1.856 +    
   1.857 +    public:
   1.858 +    /// Constructor.
   1.859 +    
   1.860 +    /// This constructor does not require parameters, therefore it initiates
   1.861 +    /// all of the attributes to default values (0, INVALID).
   1.862 +    DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
   1.863 +			   _dist(0), _source(INVALID) {}
   1.864 +
   1.865 +    /// Constructor.
   1.866 +    
   1.867 +    /// This constructor requires some parameters,
   1.868 +    /// listed in the parameters list.
   1.869 +    /// Others are initiated to 0.
   1.870 +    /// \param g is the initial value of  \ref _g
   1.871 +    /// \param s is the initial value of  \ref _source
   1.872 +    DfsWizardBase(const GR &g, Node s=INVALID) :
   1.873 +      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), 
   1.874 +      _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
   1.875 +
   1.876 +  };
   1.877 +  
   1.878 +  /// A class to make the usage of the Dfs algorithm easier
   1.879 +
   1.880 +  /// This class is created to make it easier to use the Dfs algorithm.
   1.881 +  /// It uses the functions and features of the plain \ref Dfs,
   1.882 +  /// but it is much simpler to use it.
   1.883 +  ///
   1.884 +  /// Simplicity means that the way to change the types defined
   1.885 +  /// in the traits class is based on functions that returns the new class
   1.886 +  /// and not on templatable built-in classes.
   1.887 +  /// When using the plain \ref Dfs
   1.888 +  /// the new class with the modified type comes from
   1.889 +  /// the original class by using the ::
   1.890 +  /// operator. In the case of \ref DfsWizard only
   1.891 +  /// a function have to be called and it will
   1.892 +  /// return the needed class.
   1.893 +  ///
   1.894 +  /// It does not have own \ref run method. When its \ref run method is called
   1.895 +  /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run
   1.896 +  /// method of it.
   1.897 +  template<class TR>
   1.898 +  class DfsWizard : public TR
   1.899 +  {
   1.900 +    typedef TR Base;
   1.901 +
   1.902 +    ///The type of the underlying digraph.
   1.903 +    typedef typename TR::Digraph Digraph;
   1.904 +    //\e
   1.905 +    typedef typename Digraph::Node Node;
   1.906 +    //\e
   1.907 +    typedef typename Digraph::NodeIt NodeIt;
   1.908 +    //\e
   1.909 +    typedef typename Digraph::Arc Arc;
   1.910 +    //\e
   1.911 +    typedef typename Digraph::OutArcIt OutArcIt;
   1.912 +    
   1.913 +    ///\brief The type of the map that stores
   1.914 +    ///the reached nodes
   1.915 +    typedef typename TR::ReachedMap ReachedMap;
   1.916 +    ///\brief The type of the map that stores
   1.917 +    ///the processed nodes
   1.918 +    typedef typename TR::ProcessedMap ProcessedMap;
   1.919 +    ///\brief The type of the map that stores the last
   1.920 +    ///arcs of the %DFS paths.
   1.921 +    typedef typename TR::PredMap PredMap;
   1.922 +    ///The type of the map that stores the distances of the nodes.
   1.923 +    typedef typename TR::DistMap DistMap;
   1.924 +
   1.925 +  public:
   1.926 +    /// Constructor.
   1.927 +    DfsWizard() : TR() {}
   1.928 +
   1.929 +    /// Constructor that requires parameters.
   1.930 +
   1.931 +    /// Constructor that requires parameters.
   1.932 +    /// These parameters will be the default values for the traits class.
   1.933 +    DfsWizard(const Digraph &g, Node s=INVALID) :
   1.934 +      TR(g,s) {}
   1.935 +
   1.936 +    ///Copy constructor
   1.937 +    DfsWizard(const TR &b) : TR(b) {}
   1.938 +
   1.939 +    ~DfsWizard() {}
   1.940 +
   1.941 +    ///Runs Dfs algorithm from a given node.
   1.942 +    
   1.943 +    ///Runs Dfs algorithm from a given node.
   1.944 +    ///The node can be given by the \ref source function.
   1.945 +    void run()
   1.946 +    {
   1.947 +      if(Base::_source==INVALID) throw UninitializedParameter();
   1.948 +      Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
   1.949 +      if(Base::_reached) 
   1.950 +        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
   1.951 +      if(Base::_processed) 
   1.952 +        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
   1.953 +      if(Base::_pred) 
   1.954 +        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
   1.955 +      if(Base::_dist) 
   1.956 +        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
   1.957 +      alg.run(Base::_source);
   1.958 +    }
   1.959 +
   1.960 +    ///Runs Dfs algorithm from the given node.
   1.961 +
   1.962 +    ///Runs Dfs algorithm from the given node.
   1.963 +    ///\param s is the given source.
   1.964 +    void run(Node s)
   1.965 +    {
   1.966 +      Base::_source=s;
   1.967 +      run();
   1.968 +    }
   1.969 +
   1.970 +    template<class T>
   1.971 +    struct DefPredMapBase : public Base {
   1.972 +      typedef T PredMap;
   1.973 +      static PredMap *createPredMap(const Digraph &) { return 0; };
   1.974 +      DefPredMapBase(const TR &b) : TR(b) {}
   1.975 +    };
   1.976 +    
   1.977 +    ///\brief \ref named-templ-param "Named parameter"
   1.978 +    ///function for setting PredMap type
   1.979 +    ///
   1.980 +    /// \ref named-templ-param "Named parameter"
   1.981 +    ///function for setting PredMap type
   1.982 +    ///
   1.983 +    template<class T>
   1.984 +    DfsWizard<DefPredMapBase<T> > predMap(const T &t) 
   1.985 +    {
   1.986 +      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
   1.987 +      return DfsWizard<DefPredMapBase<T> >(*this);
   1.988 +    }
   1.989 +    
   1.990 + 
   1.991 +    template<class T>
   1.992 +    struct DefReachedMapBase : public Base {
   1.993 +      typedef T ReachedMap;
   1.994 +      static ReachedMap *createReachedMap(const Digraph &) { return 0; };
   1.995 +      DefReachedMapBase(const TR &b) : TR(b) {}
   1.996 +    };
   1.997 +    
   1.998 +    ///\brief \ref named-templ-param "Named parameter"
   1.999 +    ///function for setting ReachedMap
  1.1000 +    ///
  1.1001 +    /// \ref named-templ-param "Named parameter"
  1.1002 +    ///function for setting ReachedMap
  1.1003 +    ///
  1.1004 +    template<class T>
  1.1005 +    DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) 
  1.1006 +    {
  1.1007 +      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  1.1008 +      return DfsWizard<DefReachedMapBase<T> >(*this);
  1.1009 +    }
  1.1010 +    
  1.1011 +
  1.1012 +    template<class T>
  1.1013 +    struct DefProcessedMapBase : public Base {
  1.1014 +      typedef T ProcessedMap;
  1.1015 +      static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
  1.1016 +      DefProcessedMapBase(const TR &b) : TR(b) {}
  1.1017 +    };
  1.1018 +    
  1.1019 +    ///\brief \ref named-templ-param "Named parameter"
  1.1020 +    ///function for setting ProcessedMap
  1.1021 +    ///
  1.1022 +    /// \ref named-templ-param "Named parameter"
  1.1023 +    ///function for setting ProcessedMap
  1.1024 +    ///
  1.1025 +    template<class T>
  1.1026 +    DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) 
  1.1027 +    {
  1.1028 +      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
  1.1029 +      return DfsWizard<DefProcessedMapBase<T> >(*this);
  1.1030 +    }
  1.1031 +    
  1.1032 +    template<class T>
  1.1033 +    struct DefDistMapBase : public Base {
  1.1034 +      typedef T DistMap;
  1.1035 +      static DistMap *createDistMap(const Digraph &) { return 0; };
  1.1036 +      DefDistMapBase(const TR &b) : TR(b) {}
  1.1037 +    };
  1.1038 +    
  1.1039 +    ///\brief \ref named-templ-param "Named parameter"
  1.1040 +    ///function for setting DistMap type
  1.1041 +    ///
  1.1042 +    /// \ref named-templ-param "Named parameter"
  1.1043 +    ///function for setting DistMap type
  1.1044 +    ///
  1.1045 +    template<class T>
  1.1046 +    DfsWizard<DefDistMapBase<T> > distMap(const T &t) 
  1.1047 +    {
  1.1048 +      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
  1.1049 +      return DfsWizard<DefDistMapBase<T> >(*this);
  1.1050 +    }
  1.1051 +    
  1.1052 +    /// Sets the source node, from which the Dfs algorithm runs.
  1.1053 +
  1.1054 +    /// Sets the source node, from which the Dfs algorithm runs.
  1.1055 +    /// \param s is the source node.
  1.1056 +    DfsWizard<TR> &source(Node s) 
  1.1057 +    {
  1.1058 +      Base::_source=s;
  1.1059 +      return *this;
  1.1060 +    }
  1.1061 +    
  1.1062 +  };
  1.1063 +  
  1.1064 +  ///Function type interface for Dfs algorithm.
  1.1065 +
  1.1066 +  ///\ingroup search
  1.1067 +  ///Function type interface for Dfs algorithm.
  1.1068 +  ///
  1.1069 +  ///This function also has several
  1.1070 +  ///\ref named-templ-func-param "named parameters",
  1.1071 +  ///they are declared as the members of class \ref DfsWizard.
  1.1072 +  ///The following
  1.1073 +  ///example shows how to use these parameters.
  1.1074 +  ///\code
  1.1075 +  ///  dfs(g,source).predMap(preds).run();
  1.1076 +  ///\endcode
  1.1077 +  ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
  1.1078 +  ///to the end of the parameter list.
  1.1079 +  ///\sa DfsWizard
  1.1080 +  ///\sa Dfs
  1.1081 +  template<class GR>
  1.1082 +  DfsWizard<DfsWizardBase<GR> >
  1.1083 +  dfs(const GR &g,typename GR::Node s=INVALID)
  1.1084 +  {
  1.1085 +    return DfsWizard<DfsWizardBase<GR> >(g,s);
  1.1086 +  }
  1.1087 +
  1.1088 +#ifdef DOXYGEN
  1.1089 +  /// \brief Visitor class for dfs.
  1.1090 +  ///  
  1.1091 +  /// It gives a simple interface for a functional interface for dfs 
  1.1092 +  /// traversal. The traversal on a linear data structure. 
  1.1093 +  template <typename _Digraph>
  1.1094 +  struct DfsVisitor {
  1.1095 +    typedef _Digraph Digraph;
  1.1096 +    typedef typename Digraph::Arc Arc;
  1.1097 +    typedef typename Digraph::Node Node;
  1.1098 +    /// \brief Called when the arc reach a node.
  1.1099 +    /// 
  1.1100 +    /// It is called when the dfs find an arc which target is not
  1.1101 +    /// reached yet.
  1.1102 +    void discover(const Arc& arc) {}
  1.1103 +    /// \brief Called when the node reached first time.
  1.1104 +    /// 
  1.1105 +    /// It is Called when the node reached first time.
  1.1106 +    void reach(const Node& node) {}
  1.1107 +    /// \brief Called when we step back on an arc.
  1.1108 +    /// 
  1.1109 +    /// It is called when the dfs should step back on the arc.
  1.1110 +    void backtrack(const Arc& arc) {}
  1.1111 +    /// \brief Called when we step back from the node.
  1.1112 +    /// 
  1.1113 +    /// It is called when we step back from the node.
  1.1114 +    void leave(const Node& node) {}
  1.1115 +    /// \brief Called when the arc examined but target of the arc 
  1.1116 +    /// already discovered.
  1.1117 +    /// 
  1.1118 +    /// It called when the arc examined but the target of the arc 
  1.1119 +    /// already discovered.
  1.1120 +    void examine(const Arc& arc) {}
  1.1121 +    /// \brief Called for the source node of the dfs.
  1.1122 +    /// 
  1.1123 +    /// It is called for the source node of the dfs.
  1.1124 +    void start(const Node& node) {}
  1.1125 +    /// \brief Called when we leave the source node of the dfs.
  1.1126 +    /// 
  1.1127 +    /// It is called when we leave the source node of the dfs.
  1.1128 +    void stop(const Node& node) {}
  1.1129 +
  1.1130 +  };
  1.1131 +#else
  1.1132 +  template <typename _Digraph>
  1.1133 +  struct DfsVisitor {
  1.1134 +    typedef _Digraph Digraph;
  1.1135 +    typedef typename Digraph::Arc Arc;
  1.1136 +    typedef typename Digraph::Node Node;
  1.1137 +    void discover(const Arc&) {}
  1.1138 +    void reach(const Node&) {}
  1.1139 +    void backtrack(const Arc&) {}
  1.1140 +    void leave(const Node&) {}
  1.1141 +    void examine(const Arc&) {}
  1.1142 +    void start(const Node&) {}
  1.1143 +    void stop(const Node&) {}
  1.1144 +
  1.1145 +    template <typename _Visitor>
  1.1146 +    struct Constraints {
  1.1147 +      void constraints() {
  1.1148 +	Arc arc;
  1.1149 +	Node node;
  1.1150 +	visitor.discover(arc);
  1.1151 +	visitor.reach(node);
  1.1152 +	visitor.backtrack(arc);
  1.1153 +	visitor.leave(node);
  1.1154 +	visitor.examine(arc);
  1.1155 +	visitor.start(node);
  1.1156 +	visitor.stop(arc);
  1.1157 +      }
  1.1158 +      _Visitor& visitor;
  1.1159 +    };
  1.1160 +  };
  1.1161 +#endif
  1.1162 +
  1.1163 +  /// \brief Default traits class of DfsVisit class.
  1.1164 +  ///
  1.1165 +  /// Default traits class of DfsVisit class.
  1.1166 +  /// \param _Digraph Digraph type.
  1.1167 +  template<class _Digraph>
  1.1168 +  struct DfsVisitDefaultTraits {
  1.1169 +
  1.1170 +    /// \brief The digraph type the algorithm runs on. 
  1.1171 +    typedef _Digraph Digraph;
  1.1172 +
  1.1173 +    /// \brief The type of the map that indicates which nodes are reached.
  1.1174 +    /// 
  1.1175 +    /// The type of the map that indicates which nodes are reached.
  1.1176 +    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
  1.1177 +    /// \todo named parameter to set this type, function to read and write.
  1.1178 +    typedef typename Digraph::template NodeMap<bool> ReachedMap;
  1.1179 +
  1.1180 +    /// \brief Instantiates a ReachedMap.
  1.1181 +    ///
  1.1182 +    /// This function instantiates a \ref ReachedMap. 
  1.1183 +    /// \param digraph is the digraph, to which
  1.1184 +    /// we would like to define the \ref ReachedMap.
  1.1185 +    static ReachedMap *createReachedMap(const Digraph &digraph) {
  1.1186 +      return new ReachedMap(digraph);
  1.1187 +    }
  1.1188 +
  1.1189 +  };
  1.1190 +  
  1.1191 +  /// %DFS Visit algorithm class.
  1.1192 +  
  1.1193 +  /// \ingroup search
  1.1194 +  /// This class provides an efficient implementation of the %DFS algorithm
  1.1195 +  /// with visitor interface.
  1.1196 +  ///
  1.1197 +  /// The %DfsVisit class provides an alternative interface to the Dfs
  1.1198 +  /// class. It works with callback mechanism, the DfsVisit object calls
  1.1199 +  /// on every dfs event the \c Visitor class member functions. 
  1.1200 +  ///
  1.1201 +  /// \param _Digraph The digraph type the algorithm runs on. The default value is
  1.1202 +  /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it
  1.1203 +  /// is only passed to \ref DfsDefaultTraits.
  1.1204 +  /// \param _Visitor The Visitor object for the algorithm. The 
  1.1205 +  /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitor which
  1.1206 +  /// does not observe the Dfs events. If you want to observe the dfs
  1.1207 +  /// events you should implement your own Visitor class.
  1.1208 +  /// \param _Traits Traits class to set various data types used by the 
  1.1209 +  /// algorithm. The default traits class is
  1.1210 +  /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
  1.1211 +  /// See \ref DfsVisitDefaultTraits for the documentation of
  1.1212 +  /// a Dfs visit traits class.
  1.1213 +  ///
  1.1214 +  /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
  1.1215 +#ifdef DOXYGEN
  1.1216 +  template <typename _Digraph, typename _Visitor, typename _Traits>
  1.1217 +#else
  1.1218 +  template <typename _Digraph = ListDigraph,
  1.1219 +	    typename _Visitor = DfsVisitor<_Digraph>,
  1.1220 +	    typename _Traits = DfsDefaultTraits<_Digraph> >
  1.1221 +#endif
  1.1222 +  class DfsVisit {
  1.1223 +  public:
  1.1224 +    
  1.1225 +    /// \brief \ref Exception for uninitialized parameters.
  1.1226 +    ///
  1.1227 +    /// This error represents problems in the initialization
  1.1228 +    /// of the parameters of the algorithms.
  1.1229 +    class UninitializedParameter : public lemon::UninitializedParameter {
  1.1230 +    public:
  1.1231 +      virtual const char* what() const throw() 
  1.1232 +      {
  1.1233 +	return "lemon::DfsVisit::UninitializedParameter";
  1.1234 +      }
  1.1235 +    };
  1.1236 +
  1.1237 +    typedef _Traits Traits;
  1.1238 +
  1.1239 +    typedef typename Traits::Digraph Digraph;
  1.1240 +
  1.1241 +    typedef _Visitor Visitor;
  1.1242 +
  1.1243 +    ///The type of the map indicating which nodes are reached.
  1.1244 +    typedef typename Traits::ReachedMap ReachedMap;
  1.1245 +
  1.1246 +  private:
  1.1247 +
  1.1248 +    typedef typename Digraph::Node Node;
  1.1249 +    typedef typename Digraph::NodeIt NodeIt;
  1.1250 +    typedef typename Digraph::Arc Arc;
  1.1251 +    typedef typename Digraph::OutArcIt OutArcIt;
  1.1252 +
  1.1253 +    /// Pointer to the underlying digraph.
  1.1254 +    const Digraph *_digraph;
  1.1255 +    /// Pointer to the visitor object.
  1.1256 +    Visitor *_visitor;
  1.1257 +    ///Pointer to the map of reached status of the nodes.
  1.1258 +    ReachedMap *_reached;
  1.1259 +    ///Indicates if \ref _reached is locally allocated (\c true) or not.
  1.1260 +    bool local_reached;
  1.1261 +
  1.1262 +    std::vector<typename Digraph::Arc> _stack;
  1.1263 +    int _stack_head;
  1.1264 +
  1.1265 +    /// \brief Creates the maps if necessary.
  1.1266 +    ///
  1.1267 +    /// Creates the maps if necessary.
  1.1268 +    void create_maps() {
  1.1269 +      if(!_reached) {
  1.1270 +	local_reached = true;
  1.1271 +	_reached = Traits::createReachedMap(*_digraph);
  1.1272 +      }
  1.1273 +    }
  1.1274 +
  1.1275 +  protected:
  1.1276 +
  1.1277 +    DfsVisit() {}
  1.1278 +    
  1.1279 +  public:
  1.1280 +
  1.1281 +    typedef DfsVisit Create;
  1.1282 +
  1.1283 +    /// \name Named template parameters
  1.1284 +
  1.1285 +    ///@{
  1.1286 +    template <class T>
  1.1287 +    struct DefReachedMapTraits : public Traits {
  1.1288 +      typedef T ReachedMap;
  1.1289 +      static ReachedMap *createReachedMap(const Digraph &digraph) {
  1.1290 +	throw UninitializedParameter();
  1.1291 +      }
  1.1292 +    };
  1.1293 +    /// \brief \ref named-templ-param "Named parameter" for setting 
  1.1294 +    /// ReachedMap type
  1.1295 +    ///
  1.1296 +    /// \ref named-templ-param "Named parameter" for setting ReachedMap type
  1.1297 +    template <class T>
  1.1298 +    struct DefReachedMap : public DfsVisit< Digraph, Visitor,
  1.1299 +					    DefReachedMapTraits<T> > {
  1.1300 +      typedef DfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
  1.1301 +    };
  1.1302 +    ///@}
  1.1303 +
  1.1304 +  public:      
  1.1305 +    
  1.1306 +    /// \brief Constructor.
  1.1307 +    ///
  1.1308 +    /// Constructor.
  1.1309 +    ///
  1.1310 +    /// \param digraph the digraph the algorithm will run on.
  1.1311 +    /// \param visitor The visitor of the algorithm.
  1.1312 +    ///
  1.1313 +    DfsVisit(const Digraph& digraph, Visitor& visitor) 
  1.1314 +      : _digraph(&digraph), _visitor(&visitor),
  1.1315 +	_reached(0), local_reached(false) {}
  1.1316 +    
  1.1317 +    /// \brief Destructor.
  1.1318 +    ///
  1.1319 +    /// Destructor.
  1.1320 +    ~DfsVisit() {
  1.1321 +      if(local_reached) delete _reached;
  1.1322 +    }
  1.1323 +
  1.1324 +    /// \brief Sets the map indicating if a node is reached.
  1.1325 +    ///
  1.1326 +    /// Sets the map indicating if a node is reached.
  1.1327 +    /// If you don't use this function before calling \ref run(),
  1.1328 +    /// it will allocate one. The destuctor deallocates this
  1.1329 +    /// automatically allocated map, of course.
  1.1330 +    /// \return <tt> (*this) </tt>
  1.1331 +    DfsVisit &reachedMap(ReachedMap &m) {
  1.1332 +      if(local_reached) {
  1.1333 +	delete _reached;
  1.1334 +	local_reached=false;
  1.1335 +      }
  1.1336 +      _reached = &m;
  1.1337 +      return *this;
  1.1338 +    }
  1.1339 +
  1.1340 +  public:
  1.1341 +    /// \name Execution control
  1.1342 +    /// The simplest way to execute the algorithm is to use
  1.1343 +    /// one of the member functions called \c run(...).
  1.1344 +    /// \n
  1.1345 +    /// If you need more control on the execution,
  1.1346 +    /// first you must call \ref init(), then you can adda source node
  1.1347 +    /// with \ref addSource().
  1.1348 +    /// Finally \ref start() will perform the actual path
  1.1349 +    /// computation.
  1.1350 +
  1.1351 +    /// @{
  1.1352 +    /// \brief Initializes the internal data structures.
  1.1353 +    ///
  1.1354 +    /// Initializes the internal data structures.
  1.1355 +    ///
  1.1356 +    void init() {
  1.1357 +      create_maps();
  1.1358 +      _stack.resize(countNodes(*_digraph));
  1.1359 +      _stack_head = -1;
  1.1360 +      for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
  1.1361 +	_reached->set(u, false);
  1.1362 +      }
  1.1363 +    }
  1.1364 +    
  1.1365 +    /// \brief Adds a new source node.
  1.1366 +    ///
  1.1367 +    /// Adds a new source node to the set of nodes to be processed.
  1.1368 +    void addSource(Node s) {
  1.1369 +      if(!(*_reached)[s]) {
  1.1370 +	  _reached->set(s,true);
  1.1371 +	  _visitor->start(s);
  1.1372 +	  _visitor->reach(s);
  1.1373 +	  Arc e; 
  1.1374 +	  _digraph->firstOut(e, s);
  1.1375 +	  if (e != INVALID) {
  1.1376 +	    _stack[++_stack_head] = e;
  1.1377 +	  } else {
  1.1378 +	    _visitor->leave(s);
  1.1379 +	  }
  1.1380 +	}
  1.1381 +    }
  1.1382 +    
  1.1383 +    /// \brief Processes the next arc.
  1.1384 +    ///
  1.1385 +    /// Processes the next arc.
  1.1386 +    ///
  1.1387 +    /// \return The processed arc.
  1.1388 +    ///
  1.1389 +    /// \pre The stack must not be empty!
  1.1390 +    Arc processNextArc() { 
  1.1391 +      Arc e = _stack[_stack_head];
  1.1392 +      Node m = _digraph->target(e);
  1.1393 +      if(!(*_reached)[m]) {
  1.1394 +	_visitor->discover(e);
  1.1395 +	_visitor->reach(m);
  1.1396 +	_reached->set(m, true);
  1.1397 +	_digraph->firstOut(_stack[++_stack_head], m);
  1.1398 +      } else {
  1.1399 +	_visitor->examine(e);
  1.1400 +	m = _digraph->source(e);
  1.1401 +	_digraph->nextOut(_stack[_stack_head]);
  1.1402 +      }
  1.1403 +      while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
  1.1404 +	_visitor->leave(m);
  1.1405 +	--_stack_head;
  1.1406 +	if (_stack_head >= 0) {
  1.1407 +	  _visitor->backtrack(_stack[_stack_head]);
  1.1408 +	  m = _digraph->source(_stack[_stack_head]);
  1.1409 +	  _digraph->nextOut(_stack[_stack_head]);
  1.1410 +	} else {
  1.1411 +	  _visitor->stop(m);	  
  1.1412 +	}
  1.1413 +      }
  1.1414 +      return e;
  1.1415 +    }
  1.1416 +
  1.1417 +    /// \brief Next arc to be processed.
  1.1418 +    ///
  1.1419 +    /// Next arc to be processed.
  1.1420 +    ///
  1.1421 +    /// \return The next arc to be processed or INVALID if the stack is
  1.1422 +    /// empty.
  1.1423 +    Arc nextArc() { 
  1.1424 +      return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
  1.1425 +    }
  1.1426 +
  1.1427 +    /// \brief Returns \c false if there are nodes
  1.1428 +    /// to be processed in the queue
  1.1429 +    ///
  1.1430 +    /// Returns \c false if there are nodes
  1.1431 +    /// to be processed in the queue
  1.1432 +    bool emptyQueue() { return _stack_head < 0; }
  1.1433 +
  1.1434 +    /// \brief Returns the number of the nodes to be processed.
  1.1435 +    ///
  1.1436 +    /// Returns the number of the nodes to be processed in the queue.
  1.1437 +    int queueSize() { return _stack_head + 1; }
  1.1438 +    
  1.1439 +    /// \brief Executes the algorithm.
  1.1440 +    ///
  1.1441 +    /// Executes the algorithm.
  1.1442 +    ///
  1.1443 +    /// \pre init() must be called and at least one node should be added
  1.1444 +    /// with addSource() before using this function.
  1.1445 +    void start() {
  1.1446 +      while ( !emptyQueue() ) processNextArc();
  1.1447 +    }
  1.1448 +    
  1.1449 +    /// \brief Executes the algorithm until \c dest is reached.
  1.1450 +    ///
  1.1451 +    /// Executes the algorithm until \c dest is reached.
  1.1452 +    ///
  1.1453 +    /// \pre init() must be called and at least one node should be added
  1.1454 +    /// with addSource() before using this function.
  1.1455 +    void start(Node dest) {
  1.1456 +      while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest ) 
  1.1457 +	processNextArc();
  1.1458 +    }
  1.1459 +    
  1.1460 +    /// \brief Executes the algorithm until a condition is met.
  1.1461 +    ///
  1.1462 +    /// Executes the algorithm until a condition is met.
  1.1463 +    ///
  1.1464 +    /// \pre init() must be called and at least one node should be added
  1.1465 +    /// with addSource() before using this function.
  1.1466 +    ///
  1.1467 +    /// \param em must be a bool (or convertible) arc map. The algorithm
  1.1468 +    /// will stop when it reaches an arc \c e with <tt>em[e]</tt> true.
  1.1469 +    ///
  1.1470 +    ///\return The reached arc \c e with <tt>em[e]</tt> true or
  1.1471 +    ///\c INVALID if no such arc was found.
  1.1472 +    ///
  1.1473 +    /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map,
  1.1474 +    /// not a node map.
  1.1475 +    template <typename EM>
  1.1476 +    Arc start(const EM &em) {
  1.1477 +      while ( !emptyQueue() && !em[_stack[_stack_head]] )
  1.1478 +        processNextArc();
  1.1479 +      return emptyQueue() ? INVALID : _stack[_stack_head];
  1.1480 +    }
  1.1481 +
  1.1482 +    /// \brief Runs %DFSVisit algorithm from node \c s.
  1.1483 +    ///
  1.1484 +    /// This method runs the %DFS algorithm from a root node \c s.
  1.1485 +    /// \note d.run(s) is just a shortcut of the following code.
  1.1486 +    ///\code
  1.1487 +    ///   d.init();
  1.1488 +    ///   d.addSource(s);
  1.1489 +    ///   d.start();
  1.1490 +    ///\endcode
  1.1491 +    void run(Node s) {
  1.1492 +      init();
  1.1493 +      addSource(s);
  1.1494 +      start();
  1.1495 +    }
  1.1496 +
  1.1497 +    /// \brief Runs %DFSVisit algorithm to visit all nodes in the digraph.
  1.1498 +    
  1.1499 +    /// This method runs the %DFS algorithm in order to
  1.1500 +    /// compute the %DFS path to each node. The algorithm computes
  1.1501 +    /// - The %DFS tree.
  1.1502 +    /// - The distance of each node from the root in the %DFS tree.
  1.1503 +    ///
  1.1504 +    ///\note d.run() is just a shortcut of the following code.
  1.1505 +    ///\code
  1.1506 +    ///  d.init();
  1.1507 +    ///  for (NodeIt it(digraph); it != INVALID; ++it) {
  1.1508 +    ///    if (!d.reached(it)) {
  1.1509 +    ///      d.addSource(it);
  1.1510 +    ///      d.start();
  1.1511 +    ///    }
  1.1512 +    ///  }
  1.1513 +    ///\endcode
  1.1514 +    void run() {
  1.1515 +      init();
  1.1516 +      for (NodeIt it(*_digraph); it != INVALID; ++it) {
  1.1517 +        if (!reached(it)) {
  1.1518 +          addSource(it);
  1.1519 +          start();
  1.1520 +        }
  1.1521 +      }
  1.1522 +    }
  1.1523 +    ///@}
  1.1524 +
  1.1525 +    /// \name Query Functions
  1.1526 +    /// The result of the %DFS algorithm can be obtained using these
  1.1527 +    /// functions.\n
  1.1528 +    /// Before the use of these functions,
  1.1529 +    /// either run() or start() must be called.
  1.1530 +    ///@{
  1.1531 +    /// \brief Checks if a node is reachable from the root.
  1.1532 +    ///
  1.1533 +    /// Returns \c true if \c v is reachable from the root(s).
  1.1534 +    /// \warning The source nodes are inditated as unreachable.
  1.1535 +    /// \pre Either \ref run() or \ref start()
  1.1536 +    /// must be called before using this function.
  1.1537 +    ///
  1.1538 +    bool reached(Node v) { return (*_reached)[v]; }
  1.1539 +    ///@}
  1.1540 +  };
  1.1541 +
  1.1542 +
  1.1543 +} //END OF NAMESPACE LEMON
  1.1544 +
  1.1545 +#endif
  1.1546 +