1.1 --- a/src/lemon/dfs.h Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,1136 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/lemon/dfs.h - Part of LEMON, a generic C++ optimization library
1.6 - *
1.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 - * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.9 - *
1.10 - * Permission to use, modify and distribute this software is granted
1.11 - * provided that this copyright notice appears in all copies. For
1.12 - * precise terms see the accompanying LICENSE file.
1.13 - *
1.14 - * This software is provided "AS IS" with no warranty of any kind,
1.15 - * express or implied, and with no claim as to its suitability for any
1.16 - * purpose.
1.17 - *
1.18 - */
1.19 -
1.20 -#ifndef LEMON_DFS_H
1.21 -#define LEMON_DFS_H
1.22 -
1.23 -///\ingroup flowalgs
1.24 -///\file
1.25 -///\brief Dfs algorithm.
1.26 -
1.27 -#include <lemon/list_graph.h>
1.28 -#include <lemon/graph_utils.h>
1.29 -#include <lemon/invalid.h>
1.30 -#include <lemon/error.h>
1.31 -#include <lemon/maps.h>
1.32 -
1.33 -namespace lemon {
1.34 -
1.35 -
1.36 -
1.37 - ///Default traits class of Dfs class.
1.38 -
1.39 - ///Default traits class of Dfs class.
1.40 - ///\param GR Graph type.
1.41 - template<class GR>
1.42 - struct DfsDefaultTraits
1.43 - {
1.44 - ///The graph type the algorithm runs on.
1.45 - typedef GR Graph;
1.46 - ///\brief The type of the map that stores the last
1.47 - ///edges of the %DFS paths.
1.48 - ///
1.49 - ///The type of the map that stores the last
1.50 - ///edges of the %DFS paths.
1.51 - ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.52 - ///
1.53 - typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
1.54 - ///Instantiates a PredMap.
1.55 -
1.56 - ///This function instantiates a \ref PredMap.
1.57 - ///\param G is the graph, to which we would like to define the PredMap.
1.58 - ///\todo The graph alone may be insufficient to initialize
1.59 - static PredMap *createPredMap(const GR &G)
1.60 - {
1.61 - return new PredMap(G);
1.62 - }
1.63 -// ///\brief The type of the map that stores the last but one
1.64 -// ///nodes of the %DFS paths.
1.65 -// ///
1.66 -// ///The type of the map that stores the last but one
1.67 -// ///nodes of the %DFS paths.
1.68 -// ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.69 -// ///
1.70 -// typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
1.71 -// ///Instantiates a PredNodeMap.
1.72 -
1.73 -// ///This function instantiates a \ref PredNodeMap.
1.74 -// ///\param G is the graph, to which
1.75 -// ///we would like to define the \ref PredNodeMap
1.76 -// static PredNodeMap *createPredNodeMap(const GR &G)
1.77 -// {
1.78 -// return new PredNodeMap();
1.79 -// }
1.80 -
1.81 - ///The type of the map that indicates which nodes are processed.
1.82 -
1.83 - ///The type of the map that indicates which nodes are processed.
1.84 - ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.85 - ///\todo named parameter to set this type, function to read and write.
1.86 - typedef NullMap<typename Graph::Node,bool> ProcessedMap;
1.87 - ///Instantiates a ProcessedMap.
1.88 -
1.89 - ///This function instantiates a \ref ProcessedMap.
1.90 - ///\param G is the graph, to which
1.91 - ///we would like to define the \ref ProcessedMap
1.92 - static ProcessedMap *createProcessedMap(const GR &)
1.93 - {
1.94 - return new ProcessedMap();
1.95 - }
1.96 - ///The type of the map that indicates which nodes are reached.
1.97 -
1.98 - ///The type of the map that indicates which nodes are reached.
1.99 - ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.100 - ///\todo named parameter to set this type, function to read and write.
1.101 - typedef typename Graph::template NodeMap<bool> ReachedMap;
1.102 - ///Instantiates a ReachedMap.
1.103 -
1.104 - ///This function instantiates a \ref ReachedMap.
1.105 - ///\param G is the graph, to which
1.106 - ///we would like to define the \ref ReachedMap.
1.107 - static ReachedMap *createReachedMap(const GR &G)
1.108 - {
1.109 - return new ReachedMap(G);
1.110 - }
1.111 - ///The type of the map that stores the dists of the nodes.
1.112 -
1.113 - ///The type of the map that stores the dists of the nodes.
1.114 - ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.115 - ///
1.116 - typedef typename Graph::template NodeMap<int> DistMap;
1.117 - ///Instantiates a DistMap.
1.118 -
1.119 - ///This function instantiates a \ref DistMap.
1.120 - ///\param G is the graph, to which we would like to define the \ref DistMap
1.121 - static DistMap *createDistMap(const GR &G)
1.122 - {
1.123 - return new DistMap(G);
1.124 - }
1.125 - };
1.126 -
1.127 - ///%DFS algorithm class.
1.128 -
1.129 - ///\ingroup flowalgs
1.130 - ///This class provides an efficient implementation of the %DFS algorithm.
1.131 - ///
1.132 - ///\param GR The graph type the algorithm runs on. The default value is
1.133 - ///\ref ListGraph. The value of GR is not used directly by Dfs, it
1.134 - ///is only passed to \ref DfsDefaultTraits.
1.135 - ///\param TR Traits class to set various data types used by the algorithm.
1.136 - ///The default traits class is
1.137 - ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
1.138 - ///See \ref DfsDefaultTraits for the documentation of
1.139 - ///a Dfs traits class.
1.140 - ///
1.141 - ///\author Jacint Szabo and Alpar Juttner
1.142 - ///\todo A compare object would be nice.
1.143 -
1.144 -#ifdef DOXYGEN
1.145 - template <typename GR,
1.146 - typename TR>
1.147 -#else
1.148 - template <typename GR=ListGraph,
1.149 - typename TR=DfsDefaultTraits<GR> >
1.150 -#endif
1.151 - class Dfs {
1.152 - public:
1.153 - /**
1.154 - * \brief \ref Exception for uninitialized parameters.
1.155 - *
1.156 - * This error represents problems in the initialization
1.157 - * of the parameters of the algorithms.
1.158 - */
1.159 - class UninitializedParameter : public lemon::UninitializedParameter {
1.160 - public:
1.161 - virtual const char* exceptionName() const {
1.162 - return "lemon::Dfs::UninitializedParameter";
1.163 - }
1.164 - };
1.165 -
1.166 - typedef TR Traits;
1.167 - ///The type of the underlying graph.
1.168 - typedef typename TR::Graph Graph;
1.169 - ///\e
1.170 - typedef typename Graph::Node Node;
1.171 - ///\e
1.172 - typedef typename Graph::NodeIt NodeIt;
1.173 - ///\e
1.174 - typedef typename Graph::Edge Edge;
1.175 - ///\e
1.176 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.177 -
1.178 - ///\brief The type of the map that stores the last
1.179 - ///edges of the %DFS paths.
1.180 - typedef typename TR::PredMap PredMap;
1.181 -// ///\brief The type of the map that stores the last but one
1.182 -// ///nodes of the %DFS paths.
1.183 -// typedef typename TR::PredNodeMap PredNodeMap;
1.184 - ///The type of the map indicating which nodes are reached.
1.185 - typedef typename TR::ReachedMap ReachedMap;
1.186 - ///The type of the map indicating which nodes are processed.
1.187 - typedef typename TR::ProcessedMap ProcessedMap;
1.188 - ///The type of the map that stores the dists of the nodes.
1.189 - typedef typename TR::DistMap DistMap;
1.190 - private:
1.191 - /// Pointer to the underlying graph.
1.192 - const Graph *G;
1.193 - ///Pointer to the map of predecessors edges.
1.194 - PredMap *_pred;
1.195 - ///Indicates if \ref _pred is locally allocated (\c true) or not.
1.196 - bool local_pred;
1.197 -// ///Pointer to the map of predecessors nodes.
1.198 -// PredNodeMap *_predNode;
1.199 -// ///Indicates if \ref _predNode is locally allocated (\c true) or not.
1.200 -// bool local_predNode;
1.201 - ///Pointer to the map of distances.
1.202 - DistMap *_dist;
1.203 - ///Indicates if \ref _dist is locally allocated (\c true) or not.
1.204 - bool local_dist;
1.205 - ///Pointer to the map of reached status of the nodes.
1.206 - ReachedMap *_reached;
1.207 - ///Indicates if \ref _reached is locally allocated (\c true) or not.
1.208 - bool local_reached;
1.209 - ///Pointer to the map of processed status of the nodes.
1.210 - ProcessedMap *_processed;
1.211 - ///Indicates if \ref _processed is locally allocated (\c true) or not.
1.212 - bool local_processed;
1.213 -
1.214 - std::vector<typename Graph::OutEdgeIt> _stack;
1.215 - int _stack_head;
1.216 -// ///The source node of the last execution.
1.217 -// Node source;
1.218 -
1.219 - ///Creates the maps if necessary.
1.220 -
1.221 - ///\todo Error if \c G are \c NULL.
1.222 - ///\todo Better memory allocation (instead of new).
1.223 - void create_maps()
1.224 - {
1.225 - if(!_pred) {
1.226 - local_pred = true;
1.227 - _pred = Traits::createPredMap(*G);
1.228 - }
1.229 -// if(!_predNode) {
1.230 -// local_predNode = true;
1.231 -// _predNode = Traits::createPredNodeMap(*G);
1.232 -// }
1.233 - if(!_dist) {
1.234 - local_dist = true;
1.235 - _dist = Traits::createDistMap(*G);
1.236 - }
1.237 - if(!_reached) {
1.238 - local_reached = true;
1.239 - _reached = Traits::createReachedMap(*G);
1.240 - }
1.241 - if(!_processed) {
1.242 - local_processed = true;
1.243 - _processed = Traits::createProcessedMap(*G);
1.244 - }
1.245 - }
1.246 -
1.247 - public :
1.248 -
1.249 - ///\name Named template parameters
1.250 -
1.251 - ///@{
1.252 -
1.253 - template <class T>
1.254 - struct DefPredMapTraits : public Traits {
1.255 - typedef T PredMap;
1.256 - static PredMap *createPredMap(const Graph &G)
1.257 - {
1.258 - throw UninitializedParameter();
1.259 - }
1.260 - };
1.261 - ///\ref named-templ-param "Named parameter" for setting PredMap type
1.262 -
1.263 - ///\ref named-templ-param "Named parameter" for setting PredMap type
1.264 - ///
1.265 - template <class T>
1.266 - class DefPredMap : public Dfs< Graph,
1.267 - DefPredMapTraits<T> > { };
1.268 -
1.269 -// template <class T>
1.270 -// struct DefPredNodeMapTraits : public Traits {
1.271 -// typedef T PredNodeMap;
1.272 -// static PredNodeMap *createPredNodeMap(const Graph &G)
1.273 -// {
1.274 -// throw UninitializedParameter();
1.275 -// }
1.276 -// };
1.277 -// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
1.278 -
1.279 -// ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
1.280 -// ///
1.281 -// template <class T>
1.282 -// class DefPredNodeMap : public Dfs< Graph,
1.283 -// LengthMap,
1.284 -// DefPredNodeMapTraits<T> > { };
1.285 -
1.286 - template <class T>
1.287 - struct DefDistMapTraits : public Traits {
1.288 - typedef T DistMap;
1.289 - static DistMap *createDistMap(const Graph &G)
1.290 - {
1.291 - throw UninitializedParameter();
1.292 - }
1.293 - };
1.294 - ///\ref named-templ-param "Named parameter" for setting DistMap type
1.295 -
1.296 - ///\ref named-templ-param "Named parameter" for setting DistMap type
1.297 - ///
1.298 - template <class T>
1.299 - class DefDistMap : public Dfs< Graph,
1.300 - DefDistMapTraits<T> > { };
1.301 -
1.302 - template <class T>
1.303 - struct DefReachedMapTraits : public Traits {
1.304 - typedef T ReachedMap;
1.305 - static ReachedMap *createReachedMap(const Graph &G)
1.306 - {
1.307 - throw UninitializedParameter();
1.308 - }
1.309 - };
1.310 - ///\ref named-templ-param "Named parameter" for setting ReachedMap type
1.311 -
1.312 - ///\ref named-templ-param "Named parameter" for setting ReachedMap type
1.313 - ///
1.314 - template <class T>
1.315 - class DefReachedMap : public Dfs< Graph,
1.316 - DefReachedMapTraits<T> > { };
1.317 -
1.318 - struct DefGraphReachedMapTraits : public Traits {
1.319 - typedef typename Graph::template NodeMap<bool> ReachedMap;
1.320 - static ReachedMap *createReachedMap(const Graph &G)
1.321 - {
1.322 - return new ReachedMap(G);
1.323 - }
1.324 - };
1.325 - template <class T>
1.326 - struct DefProcessedMapTraits : public Traits {
1.327 - typedef T ProcessedMap;
1.328 - static ProcessedMap *createProcessedMap(const Graph &G)
1.329 - {
1.330 - throw UninitializedParameter();
1.331 - }
1.332 - };
1.333 - ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
1.334 -
1.335 - ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
1.336 - ///
1.337 - template <class T>
1.338 - class DefProcessedMap : public Dfs< Graph,
1.339 - DefProcessedMapTraits<T> > { };
1.340 -
1.341 - struct DefGraphProcessedMapTraits : public Traits {
1.342 - typedef typename Graph::template NodeMap<bool> ProcessedMap;
1.343 - static ProcessedMap *createProcessedMap(const Graph &G)
1.344 - {
1.345 - return new ProcessedMap(G);
1.346 - }
1.347 - };
1.348 - ///\brief \ref named-templ-param "Named parameter"
1.349 - ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
1.350 - ///
1.351 - ///\ref named-templ-param "Named parameter"
1.352 - ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
1.353 - ///If you don't set it explicitely, it will be automatically allocated.
1.354 - template <class T>
1.355 - class DefProcessedMapToBeDefaultMap :
1.356 - public Dfs< Graph,
1.357 - DefGraphProcessedMapTraits> { };
1.358 -
1.359 - ///@}
1.360 -
1.361 - public:
1.362 -
1.363 - ///Constructor.
1.364 -
1.365 - ///\param _G the graph the algorithm will run on.
1.366 - ///
1.367 - Dfs(const Graph& _G) :
1.368 - G(&_G),
1.369 - _pred(NULL), local_pred(false),
1.370 -// _predNode(NULL), local_predNode(false),
1.371 - _dist(NULL), local_dist(false),
1.372 - _reached(NULL), local_reached(false),
1.373 - _processed(NULL), local_processed(false)
1.374 - { }
1.375 -
1.376 - ///Destructor.
1.377 - ~Dfs()
1.378 - {
1.379 - if(local_pred) delete _pred;
1.380 -// if(local_predNode) delete _predNode;
1.381 - if(local_dist) delete _dist;
1.382 - if(local_reached) delete _reached;
1.383 - if(local_processed) delete _processed;
1.384 - }
1.385 -
1.386 - ///Sets the map storing the predecessor edges.
1.387 -
1.388 - ///Sets the map storing the predecessor edges.
1.389 - ///If you don't use this function before calling \ref run(),
1.390 - ///it will allocate one. The destuctor deallocates this
1.391 - ///automatically allocated map, of course.
1.392 - ///\return <tt> (*this) </tt>
1.393 - Dfs &predMap(PredMap &m)
1.394 - {
1.395 - if(local_pred) {
1.396 - delete _pred;
1.397 - local_pred=false;
1.398 - }
1.399 - _pred = &m;
1.400 - return *this;
1.401 - }
1.402 -
1.403 -// ///Sets the map storing the predecessor nodes.
1.404 -
1.405 -// ///Sets the map storing the predecessor nodes.
1.406 -// ///If you don't use this function before calling \ref run(),
1.407 -// ///it will allocate one. The destuctor deallocates this
1.408 -// ///automatically allocated map, of course.
1.409 -// ///\return <tt> (*this) </tt>
1.410 -// Dfs &predNodeMap(PredNodeMap &m)
1.411 -// {
1.412 -// if(local_predNode) {
1.413 -// delete _predNode;
1.414 -// local_predNode=false;
1.415 -// }
1.416 -// _predNode = &m;
1.417 -// return *this;
1.418 -// }
1.419 -
1.420 - ///Sets the map storing the distances calculated by the algorithm.
1.421 -
1.422 - ///Sets the map storing the distances calculated by the algorithm.
1.423 - ///If you don't use this function before calling \ref run(),
1.424 - ///it will allocate one. The destuctor deallocates this
1.425 - ///automatically allocated map, of course.
1.426 - ///\return <tt> (*this) </tt>
1.427 - Dfs &distMap(DistMap &m)
1.428 - {
1.429 - if(local_dist) {
1.430 - delete _dist;
1.431 - local_dist=false;
1.432 - }
1.433 - _dist = &m;
1.434 - return *this;
1.435 - }
1.436 -
1.437 - ///Sets the map indicating if a node is reached.
1.438 -
1.439 - ///Sets the map indicating if a node is reached.
1.440 - ///If you don't use this function before calling \ref run(),
1.441 - ///it will allocate one. The destuctor deallocates this
1.442 - ///automatically allocated map, of course.
1.443 - ///\return <tt> (*this) </tt>
1.444 - Dfs &reachedMap(ReachedMap &m)
1.445 - {
1.446 - if(local_reached) {
1.447 - delete _reached;
1.448 - local_reached=false;
1.449 - }
1.450 - _reached = &m;
1.451 - return *this;
1.452 - }
1.453 -
1.454 - ///Sets the map indicating if a node is processed.
1.455 -
1.456 - ///Sets the map indicating if a node is processed.
1.457 - ///If you don't use this function before calling \ref run(),
1.458 - ///it will allocate one. The destuctor deallocates this
1.459 - ///automatically allocated map, of course.
1.460 - ///\return <tt> (*this) </tt>
1.461 - Dfs &processedMap(ProcessedMap &m)
1.462 - {
1.463 - if(local_processed) {
1.464 - delete _processed;
1.465 - local_processed=false;
1.466 - }
1.467 - _processed = &m;
1.468 - return *this;
1.469 - }
1.470 -
1.471 - public:
1.472 - ///\name Execution control
1.473 - ///The simplest way to execute the algorithm is to use
1.474 - ///one of the member functions called \c run(...).
1.475 - ///\n
1.476 - ///If you need more control on the execution,
1.477 - ///first you must call \ref init(), then you can add several source nodes
1.478 - ///with \ref addSource().
1.479 - ///Finally \ref start() will perform the actual path
1.480 - ///computation.
1.481 -
1.482 - ///@{
1.483 -
1.484 - ///Initializes the internal data structures.
1.485 -
1.486 - ///Initializes the internal data structures.
1.487 - ///
1.488 - void init()
1.489 - {
1.490 - create_maps();
1.491 - _stack.resize(countNodes(*G));
1.492 - _stack_head=-1;
1.493 - for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
1.494 - _pred->set(u,INVALID);
1.495 - // _predNode->set(u,INVALID);
1.496 - _reached->set(u,false);
1.497 - _processed->set(u,false);
1.498 - }
1.499 - }
1.500 -
1.501 - ///Adds a new source node.
1.502 -
1.503 - ///Adds a new source node to the set of nodes to be processed.
1.504 - ///
1.505 - ///\bug dist's are wrong (or at least strange) in case of multiple sources.
1.506 - void addSource(Node s)
1.507 - {
1.508 - if(!(*_reached)[s])
1.509 - {
1.510 - _reached->set(s,true);
1.511 - _pred->set(s,INVALID);
1.512 - // _predNode->set(u,INVALID);
1.513 - _stack[++_stack_head]=OutEdgeIt(*G,s);
1.514 - _dist->set(s,_stack_head);
1.515 - }
1.516 - }
1.517 -
1.518 - ///Processes the next node.
1.519 -
1.520 - ///Processes the next node.
1.521 - ///
1.522 - ///\warning The stack must not be empty!
1.523 - void processNextEdge()
1.524 - {
1.525 - Node m;
1.526 - Edge e=_stack[_stack_head];
1.527 - if(!(*_reached)[m=G->target(e)]) {
1.528 - _pred->set(m,e);
1.529 - _reached->set(m,true);
1.530 - // _pred_node->set(m,G->source(e));
1.531 - ++_stack_head;
1.532 - _stack[_stack_head] = OutEdgeIt(*G, m);
1.533 - _dist->set(m,_stack_head);
1.534 - }
1.535 - else {
1.536 - Node n;
1.537 - while(_stack_head>=0 &&
1.538 - (n=G->source(_stack[_stack_head]),
1.539 - ++_stack[_stack_head]==INVALID))
1.540 - {
1.541 - _processed->set(n,true);
1.542 - --_stack_head;
1.543 - }
1.544 - }
1.545 - }
1.546 -
1.547 - ///\brief Returns \c false if there are nodes
1.548 - ///to be processed in the queue
1.549 - ///
1.550 - ///Returns \c false if there are nodes
1.551 - ///to be processed in the queue
1.552 - bool emptyQueue() { return _stack_head<0; }
1.553 - ///Returns the number of the nodes to be processed.
1.554 -
1.555 - ///Returns the number of the nodes to be processed in the queue.
1.556 - ///
1.557 - int queueSize() { return _stack_head+1; }
1.558 -
1.559 - ///Executes the algorithm.
1.560 -
1.561 - ///Executes the algorithm.
1.562 - ///
1.563 - ///\pre init() must be called and at least one node should be added
1.564 - ///with addSource() before using this function.
1.565 - ///
1.566 - ///This method runs the %DFS algorithm from the root node(s)
1.567 - ///in order to
1.568 - ///compute the
1.569 - ///%DFS path to each node. The algorithm computes
1.570 - ///- The %DFS tree.
1.571 - ///- The distance of each node from the root(s).
1.572 - ///
1.573 - void start()
1.574 - {
1.575 - while ( !emptyQueue() ) processNextEdge();
1.576 - }
1.577 -
1.578 - ///Executes the algorithm until \c dest is reached.
1.579 -
1.580 - ///Executes the algorithm until \c dest is reached.
1.581 - ///
1.582 - ///\pre init() must be called and at least one node should be added
1.583 - ///with addSource() before using this function.
1.584 - ///
1.585 - ///This method runs the %DFS algorithm from the root node(s)
1.586 - ///in order to
1.587 - ///compute the
1.588 - ///%DFS path to \c dest. The algorithm computes
1.589 - ///- The %DFS path to \c dest.
1.590 - ///- The distance of \c dest from the root(s).
1.591 - ///
1.592 - void start(Node dest)
1.593 - {
1.594 - while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
1.595 - processNextEdge();
1.596 - }
1.597 -
1.598 - ///Executes the algorithm until a condition is met.
1.599 -
1.600 - ///Executes the algorithm until a condition is met.
1.601 - ///
1.602 - ///\pre init() must be called and at least one node should be added
1.603 - ///with addSource() before using this function.
1.604 - ///
1.605 - ///\param nm must be a bool (or convertible) edge map. The algorithm
1.606 - ///will stop when it reaches a edge \c v with <tt>nm[v]==true</tt>.
1.607 - ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c mn is an edge map,
1.608 - ///not a node map.
1.609 - template<class NM>
1.610 - void start(const NM &nm)
1.611 - {
1.612 - while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge();
1.613 - }
1.614 -
1.615 - ///Runs %DFS algorithm from node \c s.
1.616 -
1.617 - ///This method runs the %DFS algorithm from a root node \c s
1.618 - ///in order to
1.619 - ///compute the
1.620 - ///%DFS path to each node. The algorithm computes
1.621 - ///- The %DFS tree.
1.622 - ///- The distance of each node from the root.
1.623 - ///
1.624 - ///\note d.run(s) is just a shortcut of the following code.
1.625 - ///\code
1.626 - /// d.init();
1.627 - /// d.addSource(s);
1.628 - /// d.start();
1.629 - ///\endcode
1.630 - void run(Node s) {
1.631 - init();
1.632 - addSource(s);
1.633 - start();
1.634 - }
1.635 -
1.636 - ///Finds the %DFS path between \c s and \c t.
1.637 -
1.638 - ///Finds the %DFS path between \c s and \c t.
1.639 - ///
1.640 - ///\return The length of the %DFS s---t path if there exists one,
1.641 - ///0 otherwise.
1.642 - ///\note Apart from the return value, d.run(s) is
1.643 - ///just a shortcut of the following code.
1.644 - ///\code
1.645 - /// d.init();
1.646 - /// d.addSource(s);
1.647 - /// d.start(t);
1.648 - ///\endcode
1.649 - int run(Node s,Node t) {
1.650 - init();
1.651 - addSource(s);
1.652 - start(t);
1.653 - return reached(t)?_stack_head+1:0;
1.654 - }
1.655 -
1.656 - ///@}
1.657 -
1.658 - ///\name Query Functions
1.659 - ///The result of the %DFS algorithm can be obtained using these
1.660 - ///functions.\n
1.661 - ///Before the use of these functions,
1.662 - ///either run() or start() must be called.
1.663 -
1.664 - ///@{
1.665 -
1.666 - ///Copies the path to \c t on the DFS tree into \c p
1.667 -
1.668 - ///This function copies the path on the DFS tree to \c t into \c p.
1.669 - ///If it \c \t is a source itself or unreachable, then it does not
1.670 - ///alter \c p.
1.671 - ///\todo Is it the right way to handle unreachable nodes?
1.672 - ///\return Returns \c true if a path to \c t was actually copied to \c p,
1.673 - ///\c false otherwise.
1.674 - ///\sa DirPath
1.675 - template<class P>
1.676 - bool getPath(P &p,Node t)
1.677 - {
1.678 - if(reached(t)) {
1.679 - p.clear();
1.680 - typename P::Builder b(p);
1.681 - for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
1.682 - b.pushFront(pred(t));
1.683 - b.commit();
1.684 - return true;
1.685 - }
1.686 - return false;
1.687 - }
1.688 -
1.689 - ///The distance of a node from the root(s).
1.690 -
1.691 - ///Returns the distance of a node from the root(s).
1.692 - ///\pre \ref run() must be called before using this function.
1.693 - ///\warning If node \c v in unreachable from the root(s) the return value
1.694 - ///of this funcion is undefined.
1.695 - int dist(Node v) const { return (*_dist)[v]; }
1.696 -
1.697 - ///Returns the 'previous edge' of the %DFS tree.
1.698 -
1.699 - ///For a node \c v it returns the 'previous edge'
1.700 - ///of the %DFS path,
1.701 - ///i.e. it returns the last edge of a %DFS path from the root(s) to \c
1.702 - ///v. It is \ref INVALID
1.703 - ///if \c v is unreachable from the root(s) or \c v is a root. The
1.704 - ///%DFS tree used here is equal to the %DFS tree used in
1.705 - ///\ref predNode(Node v).
1.706 - ///\pre Either \ref run() or \ref start() must be called before using
1.707 - ///this function.
1.708 - ///\todo predEdge could be a better name.
1.709 - Edge pred(Node v) const { return (*_pred)[v];}
1.710 -
1.711 - ///Returns the 'previous node' of the %DFS tree.
1.712 -
1.713 - ///For a node \c v it returns the 'previous node'
1.714 - ///of the %DFS tree,
1.715 - ///i.e. it returns the last but one node from a %DFS path from the
1.716 - ///root(a) to \c /v.
1.717 - ///It is INVALID if \c v is unreachable from the root(s) or
1.718 - ///if \c v itself a root.
1.719 - ///The %DFS tree used here is equal to the %DFS
1.720 - ///tree used in \ref pred(Node v).
1.721 - ///\pre Either \ref run() or \ref start() must be called before
1.722 - ///using this function.
1.723 - Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
1.724 - G->source((*_pred)[v]); }
1.725 -
1.726 - ///Returns a reference to the NodeMap of distances.
1.727 -
1.728 - ///Returns a reference to the NodeMap of distances.
1.729 - ///\pre Either \ref run() or \ref init() must
1.730 - ///be called before using this function.
1.731 - const DistMap &distMap() const { return *_dist;}
1.732 -
1.733 - ///Returns a reference to the %DFS edge-tree map.
1.734 -
1.735 - ///Returns a reference to the NodeMap of the edges of the
1.736 - ///%DFS tree.
1.737 - ///\pre Either \ref run() or \ref init()
1.738 - ///must be called before using this function.
1.739 - const PredMap &predMap() const { return *_pred;}
1.740 -
1.741 -// ///Returns a reference to the map of nodes of %DFS paths.
1.742 -
1.743 -// ///Returns a reference to the NodeMap of the last but one nodes of the
1.744 -// ///%DFS tree.
1.745 -// ///\pre \ref run() must be called before using this function.
1.746 -// const PredNodeMap &predNodeMap() const { return *_predNode;}
1.747 -
1.748 - ///Checks if a node is reachable from the root.
1.749 -
1.750 - ///Returns \c true if \c v is reachable from the root.
1.751 - ///\warning The source nodes are inditated as unreached.
1.752 - ///\pre Either \ref run() or \ref start()
1.753 - ///must be called before using this function.
1.754 - ///
1.755 - bool reached(Node v) { return (*_reached)[v]; }
1.756 -
1.757 - ///@}
1.758 - };
1.759 -
1.760 - ///Default traits class of Dfs function.
1.761 -
1.762 - ///Default traits class of Dfs function.
1.763 - ///\param GR Graph type.
1.764 - template<class GR>
1.765 - struct DfsWizardDefaultTraits
1.766 - {
1.767 - ///The graph type the algorithm runs on.
1.768 - typedef GR Graph;
1.769 - ///\brief The type of the map that stores the last
1.770 - ///edges of the %DFS paths.
1.771 - ///
1.772 - ///The type of the map that stores the last
1.773 - ///edges of the %DFS paths.
1.774 - ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.775 - ///
1.776 - typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
1.777 - ///Instantiates a PredMap.
1.778 -
1.779 - ///This function instantiates a \ref PredMap.
1.780 - ///\param G is the graph, to which we would like to define the PredMap.
1.781 - ///\todo The graph alone may be insufficient to initialize
1.782 - static PredMap *createPredMap(const GR &)
1.783 - {
1.784 - return new PredMap();
1.785 - }
1.786 -// ///\brief The type of the map that stores the last but one
1.787 -// ///nodes of the %DFS paths.
1.788 -// ///
1.789 -// ///The type of the map that stores the last but one
1.790 -// ///nodes of the %DFS paths.
1.791 -// ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.792 -// ///
1.793 -// typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
1.794 -// ///Instantiates a PredNodeMap.
1.795 -
1.796 -// ///This function instantiates a \ref PredNodeMap.
1.797 -// ///\param G is the graph, to which
1.798 -// ///we would like to define the \ref PredNodeMap
1.799 -// static PredNodeMap *createPredNodeMap(const GR &G)
1.800 -// {
1.801 -// return new PredNodeMap();
1.802 -// }
1.803 -
1.804 - ///The type of the map that indicates which nodes are processed.
1.805 -
1.806 - ///The type of the map that indicates which nodes are processed.
1.807 - ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.808 - ///\todo named parameter to set this type, function to read and write.
1.809 - typedef NullMap<typename Graph::Node,bool> ProcessedMap;
1.810 - ///Instantiates a ProcessedMap.
1.811 -
1.812 - ///This function instantiates a \ref ProcessedMap.
1.813 - ///\param G is the graph, to which
1.814 - ///we would like to define the \ref ProcessedMap
1.815 - static ProcessedMap *createProcessedMap(const GR &)
1.816 - {
1.817 - return new ProcessedMap();
1.818 - }
1.819 - ///The type of the map that indicates which nodes are reached.
1.820 -
1.821 - ///The type of the map that indicates which nodes are reached.
1.822 - ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.823 - ///\todo named parameter to set this type, function to read and write.
1.824 - typedef typename Graph::template NodeMap<bool> ReachedMap;
1.825 - ///Instantiates a ReachedMap.
1.826 -
1.827 - ///This function instantiates a \ref ReachedMap.
1.828 - ///\param G is the graph, to which
1.829 - ///we would like to define the \ref ReachedMap.
1.830 - static ReachedMap *createReachedMap(const GR &G)
1.831 - {
1.832 - return new ReachedMap(G);
1.833 - }
1.834 - ///The type of the map that stores the dists of the nodes.
1.835 -
1.836 - ///The type of the map that stores the dists of the nodes.
1.837 - ///It must meet the \ref concept::WriteMap "WriteMap" concept.
1.838 - ///
1.839 - typedef NullMap<typename Graph::Node,int> DistMap;
1.840 - ///Instantiates a DistMap.
1.841 -
1.842 - ///This function instantiates a \ref DistMap.
1.843 - ///\param G is the graph, to which we would like to define the \ref DistMap
1.844 - static DistMap *createDistMap(const GR &)
1.845 - {
1.846 - return new DistMap();
1.847 - }
1.848 - };
1.849 -
1.850 - /// Default traits used by \ref DfsWizard
1.851 -
1.852 - /// To make it easier to use Dfs algorithm
1.853 - ///we have created a wizard class.
1.854 - /// This \ref DfsWizard class needs default traits,
1.855 - ///as well as the \ref Dfs class.
1.856 - /// The \ref DfsWizardBase is a class to be the default traits of the
1.857 - /// \ref DfsWizard class.
1.858 - template<class GR>
1.859 - class DfsWizardBase : public DfsWizardDefaultTraits<GR>
1.860 - {
1.861 -
1.862 - typedef DfsWizardDefaultTraits<GR> Base;
1.863 - protected:
1.864 - /// Type of the nodes in the graph.
1.865 - typedef typename Base::Graph::Node Node;
1.866 -
1.867 - /// Pointer to the underlying graph.
1.868 - void *_g;
1.869 - ///Pointer to the map of reached nodes.
1.870 - void *_reached;
1.871 - ///Pointer to the map of processed nodes.
1.872 - void *_processed;
1.873 - ///Pointer to the map of predecessors edges.
1.874 - void *_pred;
1.875 -// ///Pointer to the map of predecessors nodes.
1.876 -// void *_predNode;
1.877 - ///Pointer to the map of distances.
1.878 - void *_dist;
1.879 - ///Pointer to the source node.
1.880 - Node _source;
1.881 -
1.882 - public:
1.883 - /// Constructor.
1.884 -
1.885 - /// This constructor does not require parameters, therefore it initiates
1.886 - /// all of the attributes to default values (0, INVALID).
1.887 - DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
1.888 -// _predNode(0),
1.889 - _dist(0), _source(INVALID) {}
1.890 -
1.891 - /// Constructor.
1.892 -
1.893 - /// This constructor requires some parameters,
1.894 - /// listed in the parameters list.
1.895 - /// Others are initiated to 0.
1.896 - /// \param g is the initial value of \ref _g
1.897 - /// \param s is the initial value of \ref _source
1.898 - DfsWizardBase(const GR &g, Node s=INVALID) :
1.899 - _g((void *)&g), _reached(0), _processed(0), _pred(0),
1.900 -// _predNode(0),
1.901 - _dist(0), _source(s) {}
1.902 -
1.903 - };
1.904 -
1.905 - /// A class to make the usage of Dfs algorithm easier
1.906 -
1.907 - /// This class is created to make it easier to use Dfs algorithm.
1.908 - /// It uses the functions and features of the plain \ref Dfs,
1.909 - /// but it is much simpler to use it.
1.910 - ///
1.911 - /// Simplicity means that the way to change the types defined
1.912 - /// in the traits class is based on functions that returns the new class
1.913 - /// and not on templatable built-in classes.
1.914 - /// When using the plain \ref Dfs
1.915 - /// the new class with the modified type comes from
1.916 - /// the original class by using the ::
1.917 - /// operator. In the case of \ref DfsWizard only
1.918 - /// a function have to be called and it will
1.919 - /// return the needed class.
1.920 - ///
1.921 - /// It does not have own \ref run method. When its \ref run method is called
1.922 - /// it initiates a plain \ref Dfs class, and calls the \ref Dfs::run
1.923 - /// method of it.
1.924 - template<class TR>
1.925 - class DfsWizard : public TR
1.926 - {
1.927 - typedef TR Base;
1.928 -
1.929 - ///The type of the underlying graph.
1.930 - typedef typename TR::Graph Graph;
1.931 - //\e
1.932 - typedef typename Graph::Node Node;
1.933 - //\e
1.934 - typedef typename Graph::NodeIt NodeIt;
1.935 - //\e
1.936 - typedef typename Graph::Edge Edge;
1.937 - //\e
1.938 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.939 -
1.940 - ///\brief The type of the map that stores
1.941 - ///the reached nodes
1.942 - typedef typename TR::ReachedMap ReachedMap;
1.943 - ///\brief The type of the map that stores
1.944 - ///the processed nodes
1.945 - typedef typename TR::ProcessedMap ProcessedMap;
1.946 - ///\brief The type of the map that stores the last
1.947 - ///edges of the %DFS paths.
1.948 - typedef typename TR::PredMap PredMap;
1.949 -// ///\brief The type of the map that stores the last but one
1.950 -// ///nodes of the %DFS paths.
1.951 -// typedef typename TR::PredNodeMap PredNodeMap;
1.952 - ///The type of the map that stores the dists of the nodes.
1.953 - typedef typename TR::DistMap DistMap;
1.954 -
1.955 -public:
1.956 - /// Constructor.
1.957 - DfsWizard() : TR() {}
1.958 -
1.959 - /// Constructor that requires parameters.
1.960 -
1.961 - /// Constructor that requires parameters.
1.962 - /// These parameters will be the default values for the traits class.
1.963 - DfsWizard(const Graph &g, Node s=INVALID) :
1.964 - TR(g,s) {}
1.965 -
1.966 - ///Copy constructor
1.967 - DfsWizard(const TR &b) : TR(b) {}
1.968 -
1.969 - ~DfsWizard() {}
1.970 -
1.971 - ///Runs Dfs algorithm from a given node.
1.972 -
1.973 - ///Runs Dfs algorithm from a given node.
1.974 - ///The node can be given by the \ref source function.
1.975 - void run()
1.976 - {
1.977 - if(Base::_source==INVALID) throw UninitializedParameter();
1.978 - Dfs<Graph,TR> alg(*(Graph*)Base::_g);
1.979 - if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached);
1.980 - if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
1.981 - if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
1.982 -// if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
1.983 - if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
1.984 - alg.run(Base::_source);
1.985 - }
1.986 -
1.987 - ///Runs Dfs algorithm from the given node.
1.988 -
1.989 - ///Runs Dfs algorithm from the given node.
1.990 - ///\param s is the given source.
1.991 - void run(Node s)
1.992 - {
1.993 - Base::_source=s;
1.994 - run();
1.995 - }
1.996 -
1.997 - template<class T>
1.998 - struct DefPredMapBase : public Base {
1.999 - typedef T PredMap;
1.1000 - static PredMap *createPredMap(const Graph &) { return 0; };
1.1001 - DefPredMapBase(const TR &b) : TR(b) {}
1.1002 - };
1.1003 -
1.1004 - ///\brief \ref named-templ-param "Named parameter"
1.1005 - ///function for setting PredMap type
1.1006 - ///
1.1007 - /// \ref named-templ-param "Named parameter"
1.1008 - ///function for setting PredMap type
1.1009 - ///
1.1010 - template<class T>
1.1011 - DfsWizard<DefPredMapBase<T> > predMap(const T &t)
1.1012 - {
1.1013 - Base::_pred=(void *)&t;
1.1014 - return DfsWizard<DefPredMapBase<T> >(*this);
1.1015 - }
1.1016 -
1.1017 -
1.1018 - template<class T>
1.1019 - struct DefReachedMapBase : public Base {
1.1020 - typedef T ReachedMap;
1.1021 - static ReachedMap *createReachedMap(const Graph &) { return 0; };
1.1022 - DefReachedMapBase(const TR &b) : TR(b) {}
1.1023 - };
1.1024 -
1.1025 - ///\brief \ref named-templ-param "Named parameter"
1.1026 - ///function for setting ReachedMap
1.1027 - ///
1.1028 - /// \ref named-templ-param "Named parameter"
1.1029 - ///function for setting ReachedMap
1.1030 - ///
1.1031 - template<class T>
1.1032 - DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1.1033 - {
1.1034 - Base::_pred=(void *)&t;
1.1035 - return DfsWizard<DefReachedMapBase<T> >(*this);
1.1036 - }
1.1037 -
1.1038 -
1.1039 - template<class T>
1.1040 - struct DefProcessedMapBase : public Base {
1.1041 - typedef T ProcessedMap;
1.1042 - static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
1.1043 - DefProcessedMapBase(const TR &b) : TR(b) {}
1.1044 - };
1.1045 -
1.1046 - ///\brief \ref named-templ-param "Named parameter"
1.1047 - ///function for setting ProcessedMap
1.1048 - ///
1.1049 - /// \ref named-templ-param "Named parameter"
1.1050 - ///function for setting ProcessedMap
1.1051 - ///
1.1052 - template<class T>
1.1053 - DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1.1054 - {
1.1055 - Base::_pred=(void *)&t;
1.1056 - return DfsWizard<DefProcessedMapBase<T> >(*this);
1.1057 - }
1.1058 -
1.1059 -
1.1060 -// template<class T>
1.1061 -// struct DefPredNodeMapBase : public Base {
1.1062 -// typedef T PredNodeMap;
1.1063 -// static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
1.1064 -// DefPredNodeMapBase(const TR &b) : TR(b) {}
1.1065 -// };
1.1066 -
1.1067 -// ///\brief \ref named-templ-param "Named parameter"
1.1068 -// ///function for setting PredNodeMap type
1.1069 -// ///
1.1070 -// /// \ref named-templ-param "Named parameter"
1.1071 -// ///function for setting PredNodeMap type
1.1072 -// ///
1.1073 -// template<class T>
1.1074 -// DfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1.1075 -// {
1.1076 -// Base::_predNode=(void *)&t;
1.1077 -// return DfsWizard<DefPredNodeMapBase<T> >(*this);
1.1078 -// }
1.1079 -
1.1080 - template<class T>
1.1081 - struct DefDistMapBase : public Base {
1.1082 - typedef T DistMap;
1.1083 - static DistMap *createDistMap(const Graph &) { return 0; };
1.1084 - DefDistMapBase(const TR &b) : TR(b) {}
1.1085 - };
1.1086 -
1.1087 - ///\brief \ref named-templ-param "Named parameter"
1.1088 - ///function for setting DistMap type
1.1089 - ///
1.1090 - /// \ref named-templ-param "Named parameter"
1.1091 - ///function for setting DistMap type
1.1092 - ///
1.1093 - template<class T>
1.1094 - DfsWizard<DefDistMapBase<T> > distMap(const T &t)
1.1095 - {
1.1096 - Base::_dist=(void *)&t;
1.1097 - return DfsWizard<DefDistMapBase<T> >(*this);
1.1098 - }
1.1099 -
1.1100 - /// Sets the source node, from which the Dfs algorithm runs.
1.1101 -
1.1102 - /// Sets the source node, from which the Dfs algorithm runs.
1.1103 - /// \param s is the source node.
1.1104 - DfsWizard<TR> &source(Node s)
1.1105 - {
1.1106 - Base::_source=s;
1.1107 - return *this;
1.1108 - }
1.1109 -
1.1110 - };
1.1111 -
1.1112 - ///Function type interface for Dfs algorithm.
1.1113 -
1.1114 - /// \ingroup flowalgs
1.1115 - ///Function type interface for Dfs algorithm.
1.1116 - ///
1.1117 - ///This function also has several
1.1118 - ///\ref named-templ-func-param "named parameters",
1.1119 - ///they are declared as the members of class \ref DfsWizard.
1.1120 - ///The following
1.1121 - ///example shows how to use these parameters.
1.1122 - ///\code
1.1123 - /// dfs(g,source).predMap(preds).run();
1.1124 - ///\endcode
1.1125 - ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
1.1126 - ///to the end of the parameter list.
1.1127 - ///\sa DfsWizard
1.1128 - ///\sa Dfs
1.1129 - template<class GR>
1.1130 - DfsWizard<DfsWizardBase<GR> >
1.1131 - dfs(const GR &g,typename GR::Node s=INVALID)
1.1132 - {
1.1133 - return DfsWizard<DfsWizardBase<GR> >(g,s);
1.1134 - }
1.1135 -
1.1136 -} //END OF NAMESPACE LEMON
1.1137 -
1.1138 -#endif
1.1139 -