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 +