1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/dfs.h Mon May 23 04:48:14 2005 +0000
1.3 @@ -0,0 +1,1136 @@
1.4 +/* -*- C++ -*-
1.5 + * 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 +