1.1 --- a/lemon/dfs.h Sun Jul 13 16:46:56 2008 +0100
1.2 +++ b/lemon/dfs.h Sun Jul 13 19:51:02 2008 +0100
1.3 @@ -1,6 +1,6 @@
1.4 -/* -*- C++ -*-
1.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.6 *
1.7 - * This file is a part of LEMON, a generic C++ optimization library
1.8 + * This file is a part of LEMON, a generic C++ optimization library.
1.9 *
1.10 * Copyright (C) 2003-2008
1.11 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.12 @@ -34,7 +34,7 @@
1.13
1.14 namespace lemon {
1.15
1.16 -
1.17 +
1.18 ///Default traits class of Dfs class.
1.19
1.20 ///Default traits class of Dfs class.
1.21 @@ -42,35 +42,35 @@
1.22 template<class GR>
1.23 struct DfsDefaultTraits
1.24 {
1.25 - ///The digraph type the algorithm runs on.
1.26 + ///The digraph type the algorithm runs on.
1.27 typedef GR Digraph;
1.28 ///\brief The type of the map that stores the last
1.29 ///arcs of the %DFS paths.
1.30 - ///
1.31 + ///
1.32 ///The type of the map that stores the last
1.33 ///arcs of the %DFS paths.
1.34 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.35 ///
1.36 typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
1.37 ///Instantiates a PredMap.
1.38 -
1.39 - ///This function instantiates a \ref PredMap.
1.40 +
1.41 + ///This function instantiates a \ref PredMap.
1.42 ///\param G is the digraph, to which we would like to define the PredMap.
1.43 ///\todo The digraph alone may be insufficient to initialize
1.44 - static PredMap *createPredMap(const GR &G)
1.45 + static PredMap *createPredMap(const GR &G)
1.46 {
1.47 return new PredMap(G);
1.48 }
1.49
1.50 ///The type of the map that indicates which nodes are processed.
1.51 -
1.52 +
1.53 ///The type of the map that indicates which nodes are processed.
1.54 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.55 ///\todo named parameter to set this type, function to read and write.
1.56 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.57 ///Instantiates a ProcessedMap.
1.58 -
1.59 - ///This function instantiates a \ref ProcessedMap.
1.60 +
1.61 + ///This function instantiates a \ref ProcessedMap.
1.62 ///\param g is the digraph, to which
1.63 ///we would like to define the \ref ProcessedMap
1.64 #ifdef DOXYGEN
1.65 @@ -82,14 +82,14 @@
1.66 return new ProcessedMap();
1.67 }
1.68 ///The type of the map that indicates which nodes are reached.
1.69 -
1.70 +
1.71 ///The type of the map that indicates which nodes are reached.
1.72 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.73 ///\todo named parameter to set this type, function to read and write.
1.74 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.75 ///Instantiates a ReachedMap.
1.76 -
1.77 - ///This function instantiates a \ref ReachedMap.
1.78 +
1.79 + ///This function instantiates a \ref ReachedMap.
1.80 ///\param G is the digraph, to which
1.81 ///we would like to define the \ref ReachedMap.
1.82 static ReachedMap *createReachedMap(const GR &G)
1.83 @@ -97,23 +97,23 @@
1.84 return new ReachedMap(G);
1.85 }
1.86 ///The type of the map that stores the dists of the nodes.
1.87 -
1.88 +
1.89 ///The type of the map that stores the dists of the nodes.
1.90 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.91 ///
1.92 typedef typename Digraph::template NodeMap<int> DistMap;
1.93 ///Instantiates a DistMap.
1.94 -
1.95 - ///This function instantiates a \ref DistMap.
1.96 +
1.97 + ///This function instantiates a \ref DistMap.
1.98 ///\param G is the digraph, to which we would like to define the \ref DistMap
1.99 static DistMap *createDistMap(const GR &G)
1.100 {
1.101 return new DistMap(G);
1.102 }
1.103 };
1.104 -
1.105 +
1.106 ///%DFS algorithm class.
1.107 -
1.108 +
1.109 ///\ingroup search
1.110 ///This class provides an efficient implementation of the %DFS algorithm.
1.111 ///
1.112 @@ -127,10 +127,10 @@
1.113 ///a Dfs traits class.
1.114 #ifdef DOXYGEN
1.115 template <typename GR,
1.116 - typename TR>
1.117 + typename TR>
1.118 #else
1.119 template <typename GR=ListDigraph,
1.120 - typename TR=DfsDefaultTraits<GR> >
1.121 + typename TR=DfsDefaultTraits<GR> >
1.122 #endif
1.123 class Dfs {
1.124 public:
1.125 @@ -143,7 +143,7 @@
1.126 class UninitializedParameter : public lemon::UninitializedParameter {
1.127 public:
1.128 virtual const char* what() const throw() {
1.129 - return "lemon::Dfs::UninitializedParameter";
1.130 + return "lemon::Dfs::UninitializedParameter";
1.131 }
1.132 };
1.133
1.134 @@ -158,7 +158,7 @@
1.135 typedef typename Digraph::Arc Arc;
1.136 ///\e
1.137 typedef typename Digraph::OutArcIt OutArcIt;
1.138 -
1.139 +
1.140 ///\brief The type of the map that stores the last
1.141 ///arcs of the %DFS paths.
1.142 typedef typename TR::PredMap PredMap;
1.143 @@ -192,32 +192,32 @@
1.144 int _stack_head;
1.145
1.146 ///Creates the maps if necessary.
1.147 -
1.148 +
1.149 ///\todo Better memory allocation (instead of new).
1.150 - void create_maps()
1.151 + void create_maps()
1.152 {
1.153 if(!_pred) {
1.154 - local_pred = true;
1.155 - _pred = Traits::createPredMap(*G);
1.156 + local_pred = true;
1.157 + _pred = Traits::createPredMap(*G);
1.158 }
1.159 if(!_dist) {
1.160 - local_dist = true;
1.161 - _dist = Traits::createDistMap(*G);
1.162 + local_dist = true;
1.163 + _dist = Traits::createDistMap(*G);
1.164 }
1.165 if(!_reached) {
1.166 - local_reached = true;
1.167 - _reached = Traits::createReachedMap(*G);
1.168 + local_reached = true;
1.169 + _reached = Traits::createReachedMap(*G);
1.170 }
1.171 if(!_processed) {
1.172 - local_processed = true;
1.173 - _processed = Traits::createProcessedMap(*G);
1.174 + local_processed = true;
1.175 + _processed = Traits::createProcessedMap(*G);
1.176 }
1.177 }
1.178
1.179 protected:
1.180
1.181 Dfs() {}
1.182 -
1.183 +
1.184 public:
1.185
1.186 typedef Dfs Create;
1.187 @@ -229,9 +229,9 @@
1.188 template <class T>
1.189 struct DefPredMapTraits : public Traits {
1.190 typedef T PredMap;
1.191 - static PredMap *createPredMap(const Digraph &G)
1.192 + static PredMap *createPredMap(const Digraph &G)
1.193 {
1.194 - throw UninitializedParameter();
1.195 + throw UninitializedParameter();
1.196 }
1.197 };
1.198 ///\brief \ref named-templ-param "Named parameter" for setting
1.199 @@ -243,14 +243,14 @@
1.200 struct DefPredMap : public Dfs<Digraph, DefPredMapTraits<T> > {
1.201 typedef Dfs<Digraph, DefPredMapTraits<T> > Create;
1.202 };
1.203 -
1.204 -
1.205 +
1.206 +
1.207 template <class T>
1.208 struct DefDistMapTraits : public Traits {
1.209 typedef T DistMap;
1.210 - static DistMap *createDistMap(const Digraph &)
1.211 + static DistMap *createDistMap(const Digraph &)
1.212 {
1.213 - throw UninitializedParameter();
1.214 + throw UninitializedParameter();
1.215 }
1.216 };
1.217 ///\brief \ref named-templ-param "Named parameter" for setting
1.218 @@ -262,13 +262,13 @@
1.219 struct DefDistMap {
1.220 typedef Dfs<Digraph, DefDistMapTraits<T> > Create;
1.221 };
1.222 -
1.223 +
1.224 template <class T>
1.225 struct DefReachedMapTraits : public Traits {
1.226 typedef T ReachedMap;
1.227 - static ReachedMap *createReachedMap(const Digraph &)
1.228 + static ReachedMap *createReachedMap(const Digraph &)
1.229 {
1.230 - throw UninitializedParameter();
1.231 + throw UninitializedParameter();
1.232 }
1.233 };
1.234 ///\brief \ref named-templ-param "Named parameter" for setting
1.235 @@ -284,9 +284,9 @@
1.236 template <class T>
1.237 struct DefProcessedMapTraits : public Traits {
1.238 typedef T ProcessedMap;
1.239 - static ProcessedMap *createProcessedMap(const Digraph &)
1.240 + static ProcessedMap *createProcessedMap(const Digraph &)
1.241 {
1.242 - throw UninitializedParameter();
1.243 + throw UninitializedParameter();
1.244 }
1.245 };
1.246 ///\brief \ref named-templ-param "Named parameter" for setting
1.247 @@ -295,15 +295,15 @@
1.248 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
1.249 ///
1.250 template <class T>
1.251 - struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > {
1.252 + struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > {
1.253 typedef Dfs< Digraph, DefProcessedMapTraits<T> > Create;
1.254 };
1.255 -
1.256 +
1.257 struct DefDigraphProcessedMapTraits : public Traits {
1.258 typedef typename Digraph::template NodeMap<bool> ProcessedMap;
1.259 - static ProcessedMap *createProcessedMap(const Digraph &G)
1.260 + static ProcessedMap *createProcessedMap(const Digraph &G)
1.261 {
1.262 - return new ProcessedMap(G);
1.263 + return new ProcessedMap(G);
1.264 }
1.265 };
1.266 ///\brief \ref named-templ-param "Named parameter"
1.267 @@ -314,16 +314,16 @@
1.268 ///If you don't set it explicitely, it will be automatically allocated.
1.269 template <class T>
1.270 class DefProcessedMapToBeDefaultMap :
1.271 - public Dfs< Digraph, DefDigraphProcessedMapTraits> {
1.272 + public Dfs< Digraph, DefDigraphProcessedMapTraits> {
1.273 typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create;
1.274 };
1.275 -
1.276 +
1.277 ///@}
1.278
1.279 - public:
1.280 -
1.281 + public:
1.282 +
1.283 ///Constructor.
1.284 -
1.285 +
1.286 ///\param _G the digraph the algorithm will run on.
1.287 ///
1.288 Dfs(const Digraph& _G) :
1.289 @@ -333,9 +333,9 @@
1.290 _reached(NULL), local_reached(false),
1.291 _processed(NULL), local_processed(false)
1.292 { }
1.293 -
1.294 +
1.295 ///Destructor.
1.296 - ~Dfs()
1.297 + ~Dfs()
1.298 {
1.299 if(local_pred) delete _pred;
1.300 if(local_dist) delete _dist;
1.301 @@ -350,11 +350,11 @@
1.302 ///it will allocate one. The destuctor deallocates this
1.303 ///automatically allocated map, of course.
1.304 ///\return <tt> (*this) </tt>
1.305 - Dfs &predMap(PredMap &m)
1.306 + Dfs &predMap(PredMap &m)
1.307 {
1.308 if(local_pred) {
1.309 - delete _pred;
1.310 - local_pred=false;
1.311 + delete _pred;
1.312 + local_pred=false;
1.313 }
1.314 _pred = &m;
1.315 return *this;
1.316 @@ -367,11 +367,11 @@
1.317 ///it will allocate one. The destuctor deallocates this
1.318 ///automatically allocated map, of course.
1.319 ///\return <tt> (*this) </tt>
1.320 - Dfs &distMap(DistMap &m)
1.321 + Dfs &distMap(DistMap &m)
1.322 {
1.323 if(local_dist) {
1.324 - delete _dist;
1.325 - local_dist=false;
1.326 + delete _dist;
1.327 + local_dist=false;
1.328 }
1.329 _dist = &m;
1.330 return *this;
1.331 @@ -384,11 +384,11 @@
1.332 ///it will allocate one. The destuctor deallocates this
1.333 ///automatically allocated map, of course.
1.334 ///\return <tt> (*this) </tt>
1.335 - Dfs &reachedMap(ReachedMap &m)
1.336 + Dfs &reachedMap(ReachedMap &m)
1.337 {
1.338 if(local_reached) {
1.339 - delete _reached;
1.340 - local_reached=false;
1.341 + delete _reached;
1.342 + local_reached=false;
1.343 }
1.344 _reached = &m;
1.345 return *this;
1.346 @@ -401,11 +401,11 @@
1.347 ///it will allocate one. The destuctor deallocates this
1.348 ///automatically allocated map, of course.
1.349 ///\return <tt> (*this) </tt>
1.350 - Dfs &processedMap(ProcessedMap &m)
1.351 + Dfs &processedMap(ProcessedMap &m)
1.352 {
1.353 if(local_processed) {
1.354 - delete _processed;
1.355 - local_processed=false;
1.356 + delete _processed;
1.357 + local_processed=false;
1.358 }
1.359 _processed = &m;
1.360 return *this;
1.361 @@ -434,13 +434,13 @@
1.362 _stack.resize(countNodes(*G));
1.363 _stack_head=-1;
1.364 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
1.365 - _pred->set(u,INVALID);
1.366 - // _predNode->set(u,INVALID);
1.367 - _reached->set(u,false);
1.368 - _processed->set(u,false);
1.369 + _pred->set(u,INVALID);
1.370 + // _predNode->set(u,INVALID);
1.371 + _reached->set(u,false);
1.372 + _processed->set(u,false);
1.373 }
1.374 }
1.375 -
1.376 +
1.377 ///Adds a new source node.
1.378
1.379 ///Adds a new source node to the set of nodes to be processed.
1.380 @@ -450,21 +450,21 @@
1.381 void addSource(Node s)
1.382 {
1.383 if(!(*_reached)[s])
1.384 - {
1.385 - _reached->set(s,true);
1.386 - _pred->set(s,INVALID);
1.387 - OutArcIt e(*G,s);
1.388 - if(e!=INVALID) {
1.389 - _stack[++_stack_head]=e;
1.390 - _dist->set(s,_stack_head);
1.391 - }
1.392 - else {
1.393 - _processed->set(s,true);
1.394 - _dist->set(s,0);
1.395 - }
1.396 - }
1.397 + {
1.398 + _reached->set(s,true);
1.399 + _pred->set(s,INVALID);
1.400 + OutArcIt e(*G,s);
1.401 + if(e!=INVALID) {
1.402 + _stack[++_stack_head]=e;
1.403 + _dist->set(s,_stack_head);
1.404 + }
1.405 + else {
1.406 + _processed->set(s,true);
1.407 + _dist->set(s,0);
1.408 + }
1.409 + }
1.410 }
1.411 -
1.412 +
1.413 ///Processes the next arc.
1.414
1.415 ///Processes the next arc.
1.416 @@ -473,27 +473,27 @@
1.417 ///
1.418 ///\pre The stack must not be empty!
1.419 Arc processNextArc()
1.420 - {
1.421 + {
1.422 Node m;
1.423 Arc e=_stack[_stack_head];
1.424 if(!(*_reached)[m=G->target(e)]) {
1.425 - _pred->set(m,e);
1.426 - _reached->set(m,true);
1.427 - ++_stack_head;
1.428 - _stack[_stack_head] = OutArcIt(*G, m);
1.429 - _dist->set(m,_stack_head);
1.430 + _pred->set(m,e);
1.431 + _reached->set(m,true);
1.432 + ++_stack_head;
1.433 + _stack[_stack_head] = OutArcIt(*G, m);
1.434 + _dist->set(m,_stack_head);
1.435 }
1.436 else {
1.437 - m=G->source(e);
1.438 - ++_stack[_stack_head];
1.439 + m=G->source(e);
1.440 + ++_stack[_stack_head];
1.441 }
1.442 while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
1.443 - _processed->set(m,true);
1.444 - --_stack_head;
1.445 - if(_stack_head>=0) {
1.446 - m=G->source(_stack[_stack_head]);
1.447 - ++_stack[_stack_head];
1.448 - }
1.449 + _processed->set(m,true);
1.450 + --_stack_head;
1.451 + if(_stack_head>=0) {
1.452 + m=G->source(_stack[_stack_head]);
1.453 + ++_stack[_stack_head];
1.454 + }
1.455 }
1.456 return e;
1.457 }
1.458 @@ -504,7 +504,7 @@
1.459 ///\return The next arc to be processed or INVALID if the stack is
1.460 /// empty.
1.461 OutArcIt nextArc()
1.462 - {
1.463 + {
1.464 return _stack_head>=0?_stack[_stack_head]:INVALID;
1.465 }
1.466
1.467 @@ -515,10 +515,10 @@
1.468 ///to be processed in the queue
1.469 bool emptyQueue() { return _stack_head<0; }
1.470 ///Returns the number of the nodes to be processed.
1.471 -
1.472 +
1.473 ///Returns the number of the nodes to be processed in the queue.
1.474 int queueSize() { return _stack_head+1; }
1.475 -
1.476 +
1.477 ///Executes the algorithm.
1.478
1.479 ///Executes the algorithm.
1.480 @@ -537,7 +537,7 @@
1.481 {
1.482 while ( !emptyQueue() ) processNextArc();
1.483 }
1.484 -
1.485 +
1.486 ///Executes the algorithm until \c dest is reached.
1.487
1.488 ///Executes the algorithm until \c dest is reached.
1.489 @@ -554,10 +554,10 @@
1.490 ///
1.491 void start(Node dest)
1.492 {
1.493 - while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
1.494 - processNextArc();
1.495 + while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
1.496 + processNextArc();
1.497 }
1.498 -
1.499 +
1.500 ///Executes the algorithm until a condition is met.
1.501
1.502 ///Executes the algorithm until a condition is met.
1.503 @@ -582,7 +582,7 @@
1.504 }
1.505
1.506 ///Runs %DFS algorithm to visit all nodes in the digraph.
1.507 -
1.508 +
1.509 ///This method runs the %DFS algorithm in order to
1.510 ///compute the
1.511 ///%DFS path to each node. The algorithm computes
1.512 @@ -610,7 +610,7 @@
1.513 }
1.514
1.515 ///Runs %DFS algorithm from node \c s.
1.516 -
1.517 +
1.518 ///This method runs the %DFS algorithm from a root node \c s
1.519 ///in order to
1.520 ///compute the
1.521 @@ -629,9 +629,9 @@
1.522 addSource(s);
1.523 start();
1.524 }
1.525 -
1.526 +
1.527 ///Finds the %DFS path between \c s and \c t.
1.528 -
1.529 +
1.530 ///Finds the %DFS path between \c s and \c t.
1.531 ///
1.532 ///\return The length of the %DFS s---t path if there exists one,
1.533 @@ -649,7 +649,7 @@
1.534 start(t);
1.535 return reached(t)?_stack_head+1:0;
1.536 }
1.537 -
1.538 +
1.539 ///@}
1.540
1.541 ///\name Query Functions
1.542 @@ -657,16 +657,16 @@
1.543 ///functions.\n
1.544 ///Before the use of these functions,
1.545 ///either run() or start() must be called.
1.546 -
1.547 +
1.548 ///@{
1.549
1.550 typedef PredMapPath<Digraph, PredMap> Path;
1.551
1.552 ///Gives back the shortest path.
1.553 -
1.554 +
1.555 ///Gives back the shortest path.
1.556 ///\pre The \c t should be reachable from the source.
1.557 - Path path(Node t)
1.558 + Path path(Node t)
1.559 {
1.560 return Path(*G, *_pred, t);
1.561 }
1.562 @@ -675,7 +675,7 @@
1.563
1.564 ///Returns the distance of a node from the root(s).
1.565 ///\pre \ref run() must be called before using this function.
1.566 - ///\warning If node \c v is unreachable from the root(s) then the return
1.567 + ///\warning If node \c v is unreachable from the root(s) then the return
1.568 ///value of this funcion is undefined.
1.569 int dist(Node v) const { return (*_dist)[v]; }
1.570
1.571 @@ -705,15 +705,15 @@
1.572 ///\pre Either \ref run() or \ref start() must be called before
1.573 ///using this function.
1.574 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
1.575 - G->source((*_pred)[v]); }
1.576 -
1.577 + G->source((*_pred)[v]); }
1.578 +
1.579 ///Returns a reference to the NodeMap of distances.
1.580
1.581 ///Returns a reference to the NodeMap of distances.
1.582 ///\pre Either \ref run() or \ref init() must
1.583 ///be called before using this function.
1.584 const DistMap &distMap() const { return *_dist;}
1.585 -
1.586 +
1.587 ///Returns a reference to the %DFS arc-tree map.
1.588
1.589 ///Returns a reference to the NodeMap of the arcs of the
1.590 @@ -721,7 +721,7 @@
1.591 ///\pre Either \ref run() or \ref init()
1.592 ///must be called before using this function.
1.593 const PredMap &predMap() const { return *_pred;}
1.594 -
1.595 +
1.596 ///Checks if a node is reachable from the root.
1.597
1.598 ///Returns \c true if \c v is reachable from the root(s).
1.599 @@ -730,7 +730,7 @@
1.600 ///must be called before using this function.
1.601 ///
1.602 bool reached(Node v) { return (*_reached)[v]; }
1.603 -
1.604 +
1.605 ///@}
1.606 };
1.607
1.608 @@ -741,39 +741,39 @@
1.609 template<class GR>
1.610 struct DfsWizardDefaultTraits
1.611 {
1.612 - ///The digraph type the algorithm runs on.
1.613 + ///The digraph type the algorithm runs on.
1.614 typedef GR Digraph;
1.615 ///\brief The type of the map that stores the last
1.616 ///arcs of the %DFS paths.
1.617 - ///
1.618 + ///
1.619 ///The type of the map that stores the last
1.620 ///arcs of the %DFS paths.
1.621 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.622 ///
1.623 typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
1.624 ///Instantiates a PredMap.
1.625 -
1.626 - ///This function instantiates a \ref PredMap.
1.627 +
1.628 + ///This function instantiates a \ref PredMap.
1.629 ///\param g is the digraph, to which we would like to define the PredMap.
1.630 ///\todo The digraph alone may be insufficient to initialize
1.631 #ifdef DOXYGEN
1.632 - static PredMap *createPredMap(const GR &g)
1.633 + static PredMap *createPredMap(const GR &g)
1.634 #else
1.635 - static PredMap *createPredMap(const GR &)
1.636 + static PredMap *createPredMap(const GR &)
1.637 #endif
1.638 {
1.639 return new PredMap();
1.640 }
1.641
1.642 ///The type of the map that indicates which nodes are processed.
1.643 -
1.644 +
1.645 ///The type of the map that indicates which nodes are processed.
1.646 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.647 ///\todo named parameter to set this type, function to read and write.
1.648 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.649 ///Instantiates a ProcessedMap.
1.650 -
1.651 - ///This function instantiates a \ref ProcessedMap.
1.652 +
1.653 + ///This function instantiates a \ref ProcessedMap.
1.654 ///\param g is the digraph, to which
1.655 ///we would like to define the \ref ProcessedMap
1.656 #ifdef DOXYGEN
1.657 @@ -785,14 +785,14 @@
1.658 return new ProcessedMap();
1.659 }
1.660 ///The type of the map that indicates which nodes are reached.
1.661 -
1.662 +
1.663 ///The type of the map that indicates which nodes are reached.
1.664 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.665 ///\todo named parameter to set this type, function to read and write.
1.666 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.667 ///Instantiates a ReachedMap.
1.668 -
1.669 - ///This function instantiates a \ref ReachedMap.
1.670 +
1.671 + ///This function instantiates a \ref ReachedMap.
1.672 ///\param G is the digraph, to which
1.673 ///we would like to define the \ref ReachedMap.
1.674 static ReachedMap *createReachedMap(const GR &G)
1.675 @@ -800,14 +800,14 @@
1.676 return new ReachedMap(G);
1.677 }
1.678 ///The type of the map that stores the dists of the nodes.
1.679 -
1.680 +
1.681 ///The type of the map that stores the dists of the nodes.
1.682 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.683 ///
1.684 typedef NullMap<typename Digraph::Node,int> DistMap;
1.685 ///Instantiates a DistMap.
1.686 -
1.687 - ///This function instantiates a \ref DistMap.
1.688 +
1.689 + ///This function instantiates a \ref DistMap.
1.690 ///\param g is the digraph, to which we would like to define the \ref DistMap
1.691 #ifdef DOXYGEN
1.692 static DistMap *createDistMap(const GR &g)
1.693 @@ -818,7 +818,7 @@
1.694 return new DistMap();
1.695 }
1.696 };
1.697 -
1.698 +
1.699 /// Default traits used by \ref DfsWizard
1.700
1.701 /// To make it easier to use Dfs algorithm
1.702 @@ -848,28 +848,28 @@
1.703 void *_dist;
1.704 ///Pointer to the source node.
1.705 Node _source;
1.706 -
1.707 +
1.708 public:
1.709 /// Constructor.
1.710 -
1.711 +
1.712 /// This constructor does not require parameters, therefore it initiates
1.713 /// all of the attributes to default values (0, INVALID).
1.714 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
1.715 - _dist(0), _source(INVALID) {}
1.716 + _dist(0), _source(INVALID) {}
1.717
1.718 /// Constructor.
1.719 -
1.720 +
1.721 /// This constructor requires some parameters,
1.722 /// listed in the parameters list.
1.723 /// Others are initiated to 0.
1.724 /// \param g is the initial value of \ref _g
1.725 /// \param s is the initial value of \ref _source
1.726 DfsWizardBase(const GR &g, Node s=INVALID) :
1.727 - _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
1.728 + _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
1.729 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
1.730
1.731 };
1.732 -
1.733 +
1.734 /// A class to make the usage of the Dfs algorithm easier
1.735
1.736 /// This class is created to make it easier to use the Dfs algorithm.
1.737 @@ -904,7 +904,7 @@
1.738 typedef typename Digraph::Arc Arc;
1.739 //\e
1.740 typedef typename Digraph::OutArcIt OutArcIt;
1.741 -
1.742 +
1.743 ///\brief The type of the map that stores
1.744 ///the reached nodes
1.745 typedef typename TR::ReachedMap ReachedMap;
1.746 @@ -934,20 +934,20 @@
1.747 ~DfsWizard() {}
1.748
1.749 ///Runs Dfs algorithm from a given node.
1.750 -
1.751 +
1.752 ///Runs Dfs algorithm from a given node.
1.753 ///The node can be given by the \ref source function.
1.754 void run()
1.755 {
1.756 if(Base::_source==INVALID) throw UninitializedParameter();
1.757 Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
1.758 - if(Base::_reached)
1.759 + if(Base::_reached)
1.760 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
1.761 - if(Base::_processed)
1.762 + if(Base::_processed)
1.763 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1.764 - if(Base::_pred)
1.765 + if(Base::_pred)
1.766 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1.767 - if(Base::_dist)
1.768 + if(Base::_dist)
1.769 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1.770 alg.run(Base::_source);
1.771 }
1.772 @@ -968,7 +968,7 @@
1.773 static PredMap *createPredMap(const Digraph &) { return 0; };
1.774 DefPredMapBase(const TR &b) : TR(b) {}
1.775 };
1.776 -
1.777 +
1.778 ///\brief \ref named-templ-param "Named parameter"
1.779 ///function for setting PredMap type
1.780 ///
1.781 @@ -976,20 +976,20 @@
1.782 ///function for setting PredMap type
1.783 ///
1.784 template<class T>
1.785 - DfsWizard<DefPredMapBase<T> > predMap(const T &t)
1.786 + DfsWizard<DefPredMapBase<T> > predMap(const T &t)
1.787 {
1.788 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1.789 return DfsWizard<DefPredMapBase<T> >(*this);
1.790 }
1.791 -
1.792 -
1.793 +
1.794 +
1.795 template<class T>
1.796 struct DefReachedMapBase : public Base {
1.797 typedef T ReachedMap;
1.798 static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1.799 DefReachedMapBase(const TR &b) : TR(b) {}
1.800 };
1.801 -
1.802 +
1.803 ///\brief \ref named-templ-param "Named parameter"
1.804 ///function for setting ReachedMap
1.805 ///
1.806 @@ -997,12 +997,12 @@
1.807 ///function for setting ReachedMap
1.808 ///
1.809 template<class T>
1.810 - DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1.811 + DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1.812 {
1.813 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
1.814 return DfsWizard<DefReachedMapBase<T> >(*this);
1.815 }
1.816 -
1.817 +
1.818
1.819 template<class T>
1.820 struct DefProcessedMapBase : public Base {
1.821 @@ -1010,7 +1010,7 @@
1.822 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1.823 DefProcessedMapBase(const TR &b) : TR(b) {}
1.824 };
1.825 -
1.826 +
1.827 ///\brief \ref named-templ-param "Named parameter"
1.828 ///function for setting ProcessedMap
1.829 ///
1.830 @@ -1018,19 +1018,19 @@
1.831 ///function for setting ProcessedMap
1.832 ///
1.833 template<class T>
1.834 - DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1.835 + DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1.836 {
1.837 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
1.838 return DfsWizard<DefProcessedMapBase<T> >(*this);
1.839 }
1.840 -
1.841 +
1.842 template<class T>
1.843 struct DefDistMapBase : public Base {
1.844 typedef T DistMap;
1.845 static DistMap *createDistMap(const Digraph &) { return 0; };
1.846 DefDistMapBase(const TR &b) : TR(b) {}
1.847 };
1.848 -
1.849 +
1.850 ///\brief \ref named-templ-param "Named parameter"
1.851 ///function for setting DistMap type
1.852 ///
1.853 @@ -1038,24 +1038,24 @@
1.854 ///function for setting DistMap type
1.855 ///
1.856 template<class T>
1.857 - DfsWizard<DefDistMapBase<T> > distMap(const T &t)
1.858 + DfsWizard<DefDistMapBase<T> > distMap(const T &t)
1.859 {
1.860 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1.861 return DfsWizard<DefDistMapBase<T> >(*this);
1.862 }
1.863 -
1.864 +
1.865 /// Sets the source node, from which the Dfs algorithm runs.
1.866
1.867 /// Sets the source node, from which the Dfs algorithm runs.
1.868 /// \param s is the source node.
1.869 - DfsWizard<TR> &source(Node s)
1.870 + DfsWizard<TR> &source(Node s)
1.871 {
1.872 Base::_source=s;
1.873 return *this;
1.874 }
1.875 -
1.876 +
1.877 };
1.878 -
1.879 +
1.880 ///Function type interface for Dfs algorithm.
1.881
1.882 ///\ingroup search
1.883 @@ -1082,43 +1082,43 @@
1.884
1.885 #ifdef DOXYGEN
1.886 /// \brief Visitor class for dfs.
1.887 - ///
1.888 - /// It gives a simple interface for a functional interface for dfs
1.889 - /// traversal. The traversal on a linear data structure.
1.890 + ///
1.891 + /// It gives a simple interface for a functional interface for dfs
1.892 + /// traversal. The traversal on a linear data structure.
1.893 template <typename _Digraph>
1.894 struct DfsVisitor {
1.895 typedef _Digraph Digraph;
1.896 typedef typename Digraph::Arc Arc;
1.897 typedef typename Digraph::Node Node;
1.898 /// \brief Called when the arc reach a node.
1.899 - ///
1.900 + ///
1.901 /// It is called when the dfs find an arc which target is not
1.902 /// reached yet.
1.903 void discover(const Arc& arc) {}
1.904 /// \brief Called when the node reached first time.
1.905 - ///
1.906 + ///
1.907 /// It is Called when the node reached first time.
1.908 void reach(const Node& node) {}
1.909 /// \brief Called when we step back on an arc.
1.910 - ///
1.911 + ///
1.912 /// It is called when the dfs should step back on the arc.
1.913 void backtrack(const Arc& arc) {}
1.914 /// \brief Called when we step back from the node.
1.915 - ///
1.916 + ///
1.917 /// It is called when we step back from the node.
1.918 void leave(const Node& node) {}
1.919 - /// \brief Called when the arc examined but target of the arc
1.920 + /// \brief Called when the arc examined but target of the arc
1.921 /// already discovered.
1.922 - ///
1.923 - /// It called when the arc examined but the target of the arc
1.924 + ///
1.925 + /// It called when the arc examined but the target of the arc
1.926 /// already discovered.
1.927 void examine(const Arc& arc) {}
1.928 /// \brief Called for the source node of the dfs.
1.929 - ///
1.930 + ///
1.931 /// It is called for the source node of the dfs.
1.932 void start(const Node& node) {}
1.933 /// \brief Called when we leave the source node of the dfs.
1.934 - ///
1.935 + ///
1.936 /// It is called when we leave the source node of the dfs.
1.937 void stop(const Node& node) {}
1.938
1.939 @@ -1140,15 +1140,15 @@
1.940 template <typename _Visitor>
1.941 struct Constraints {
1.942 void constraints() {
1.943 - Arc arc;
1.944 - Node node;
1.945 - visitor.discover(arc);
1.946 - visitor.reach(node);
1.947 - visitor.backtrack(arc);
1.948 - visitor.leave(node);
1.949 - visitor.examine(arc);
1.950 - visitor.start(node);
1.951 - visitor.stop(arc);
1.952 + Arc arc;
1.953 + Node node;
1.954 + visitor.discover(arc);
1.955 + visitor.reach(node);
1.956 + visitor.backtrack(arc);
1.957 + visitor.leave(node);
1.958 + visitor.examine(arc);
1.959 + visitor.start(node);
1.960 + visitor.stop(arc);
1.961 }
1.962 _Visitor& visitor;
1.963 };
1.964 @@ -1162,11 +1162,11 @@
1.965 template<class _Digraph>
1.966 struct DfsVisitDefaultTraits {
1.967
1.968 - /// \brief The digraph type the algorithm runs on.
1.969 + /// \brief The digraph type the algorithm runs on.
1.970 typedef _Digraph Digraph;
1.971
1.972 /// \brief The type of the map that indicates which nodes are reached.
1.973 - ///
1.974 + ///
1.975 /// The type of the map that indicates which nodes are reached.
1.976 /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.977 /// \todo named parameter to set this type, function to read and write.
1.978 @@ -1174,7 +1174,7 @@
1.979
1.980 /// \brief Instantiates a ReachedMap.
1.981 ///
1.982 - /// This function instantiates a \ref ReachedMap.
1.983 + /// This function instantiates a \ref ReachedMap.
1.984 /// \param digraph is the digraph, to which
1.985 /// we would like to define the \ref ReachedMap.
1.986 static ReachedMap *createReachedMap(const Digraph &digraph) {
1.987 @@ -1182,25 +1182,25 @@
1.988 }
1.989
1.990 };
1.991 -
1.992 +
1.993 /// %DFS Visit algorithm class.
1.994 -
1.995 +
1.996 /// \ingroup search
1.997 /// This class provides an efficient implementation of the %DFS algorithm
1.998 /// with visitor interface.
1.999 ///
1.1000 /// The %DfsVisit class provides an alternative interface to the Dfs
1.1001 /// class. It works with callback mechanism, the DfsVisit object calls
1.1002 - /// on every dfs event the \c Visitor class member functions.
1.1003 + /// on every dfs event the \c Visitor class member functions.
1.1004 ///
1.1005 /// \tparam _Digraph The digraph type the algorithm runs on. The default value is
1.1006 /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it
1.1007 /// is only passed to \ref DfsDefaultTraits.
1.1008 - /// \tparam _Visitor The Visitor object for the algorithm. The
1.1009 + /// \tparam _Visitor The Visitor object for the algorithm. The
1.1010 /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitor which
1.1011 /// does not observe the Dfs events. If you want to observe the dfs
1.1012 /// events you should implement your own Visitor class.
1.1013 - /// \tparam _Traits Traits class to set various data types used by the
1.1014 + /// \tparam _Traits Traits class to set various data types used by the
1.1015 /// algorithm. The default traits class is
1.1016 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
1.1017 /// See \ref DfsVisitDefaultTraits for the documentation of
1.1018 @@ -1211,21 +1211,21 @@
1.1019 template <typename _Digraph, typename _Visitor, typename _Traits>
1.1020 #else
1.1021 template <typename _Digraph = ListDigraph,
1.1022 - typename _Visitor = DfsVisitor<_Digraph>,
1.1023 - typename _Traits = DfsDefaultTraits<_Digraph> >
1.1024 + typename _Visitor = DfsVisitor<_Digraph>,
1.1025 + typename _Traits = DfsDefaultTraits<_Digraph> >
1.1026 #endif
1.1027 class DfsVisit {
1.1028 public:
1.1029 -
1.1030 +
1.1031 /// \brief \ref Exception for uninitialized parameters.
1.1032 ///
1.1033 /// This error represents problems in the initialization
1.1034 /// of the parameters of the algorithms.
1.1035 class UninitializedParameter : public lemon::UninitializedParameter {
1.1036 public:
1.1037 - virtual const char* what() const throw()
1.1038 + virtual const char* what() const throw()
1.1039 {
1.1040 - return "lemon::DfsVisit::UninitializedParameter";
1.1041 + return "lemon::DfsVisit::UninitializedParameter";
1.1042 }
1.1043 };
1.1044
1.1045 @@ -1262,15 +1262,15 @@
1.1046 /// Creates the maps if necessary.
1.1047 void create_maps() {
1.1048 if(!_reached) {
1.1049 - local_reached = true;
1.1050 - _reached = Traits::createReachedMap(*_digraph);
1.1051 + local_reached = true;
1.1052 + _reached = Traits::createReachedMap(*_digraph);
1.1053 }
1.1054 }
1.1055
1.1056 protected:
1.1057
1.1058 DfsVisit() {}
1.1059 -
1.1060 +
1.1061 public:
1.1062
1.1063 typedef DfsVisit Create;
1.1064 @@ -1282,22 +1282,22 @@
1.1065 struct DefReachedMapTraits : public Traits {
1.1066 typedef T ReachedMap;
1.1067 static ReachedMap *createReachedMap(const Digraph &digraph) {
1.1068 - throw UninitializedParameter();
1.1069 + throw UninitializedParameter();
1.1070 }
1.1071 };
1.1072 - /// \brief \ref named-templ-param "Named parameter" for setting
1.1073 + /// \brief \ref named-templ-param "Named parameter" for setting
1.1074 /// ReachedMap type
1.1075 ///
1.1076 /// \ref named-templ-param "Named parameter" for setting ReachedMap type
1.1077 template <class T>
1.1078 struct DefReachedMap : public DfsVisit< Digraph, Visitor,
1.1079 - DefReachedMapTraits<T> > {
1.1080 + DefReachedMapTraits<T> > {
1.1081 typedef DfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
1.1082 };
1.1083 ///@}
1.1084
1.1085 - public:
1.1086 -
1.1087 + public:
1.1088 +
1.1089 /// \brief Constructor.
1.1090 ///
1.1091 /// Constructor.
1.1092 @@ -1305,10 +1305,10 @@
1.1093 /// \param digraph the digraph the algorithm will run on.
1.1094 /// \param visitor The visitor of the algorithm.
1.1095 ///
1.1096 - DfsVisit(const Digraph& digraph, Visitor& visitor)
1.1097 + DfsVisit(const Digraph& digraph, Visitor& visitor)
1.1098 : _digraph(&digraph), _visitor(&visitor),
1.1099 - _reached(0), local_reached(false) {}
1.1100 -
1.1101 + _reached(0), local_reached(false) {}
1.1102 +
1.1103 /// \brief Destructor.
1.1104 ///
1.1105 /// Destructor.
1.1106 @@ -1325,8 +1325,8 @@
1.1107 /// \return <tt> (*this) </tt>
1.1108 DfsVisit &reachedMap(ReachedMap &m) {
1.1109 if(local_reached) {
1.1110 - delete _reached;
1.1111 - local_reached=false;
1.1112 + delete _reached;
1.1113 + local_reached=false;
1.1114 }
1.1115 _reached = &m;
1.1116 return *this;
1.1117 @@ -1353,28 +1353,28 @@
1.1118 _stack.resize(countNodes(*_digraph));
1.1119 _stack_head = -1;
1.1120 for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
1.1121 - _reached->set(u, false);
1.1122 + _reached->set(u, false);
1.1123 }
1.1124 }
1.1125 -
1.1126 +
1.1127 /// \brief Adds a new source node.
1.1128 ///
1.1129 /// Adds a new source node to the set of nodes to be processed.
1.1130 void addSource(Node s) {
1.1131 if(!(*_reached)[s]) {
1.1132 - _reached->set(s,true);
1.1133 - _visitor->start(s);
1.1134 - _visitor->reach(s);
1.1135 - Arc e;
1.1136 - _digraph->firstOut(e, s);
1.1137 - if (e != INVALID) {
1.1138 - _stack[++_stack_head] = e;
1.1139 - } else {
1.1140 - _visitor->leave(s);
1.1141 - }
1.1142 - }
1.1143 + _reached->set(s,true);
1.1144 + _visitor->start(s);
1.1145 + _visitor->reach(s);
1.1146 + Arc e;
1.1147 + _digraph->firstOut(e, s);
1.1148 + if (e != INVALID) {
1.1149 + _stack[++_stack_head] = e;
1.1150 + } else {
1.1151 + _visitor->leave(s);
1.1152 + }
1.1153 + }
1.1154 }
1.1155 -
1.1156 +
1.1157 /// \brief Processes the next arc.
1.1158 ///
1.1159 /// Processes the next arc.
1.1160 @@ -1382,29 +1382,29 @@
1.1161 /// \return The processed arc.
1.1162 ///
1.1163 /// \pre The stack must not be empty!
1.1164 - Arc processNextArc() {
1.1165 + Arc processNextArc() {
1.1166 Arc e = _stack[_stack_head];
1.1167 Node m = _digraph->target(e);
1.1168 if(!(*_reached)[m]) {
1.1169 - _visitor->discover(e);
1.1170 - _visitor->reach(m);
1.1171 - _reached->set(m, true);
1.1172 - _digraph->firstOut(_stack[++_stack_head], m);
1.1173 + _visitor->discover(e);
1.1174 + _visitor->reach(m);
1.1175 + _reached->set(m, true);
1.1176 + _digraph->firstOut(_stack[++_stack_head], m);
1.1177 } else {
1.1178 - _visitor->examine(e);
1.1179 - m = _digraph->source(e);
1.1180 - _digraph->nextOut(_stack[_stack_head]);
1.1181 + _visitor->examine(e);
1.1182 + m = _digraph->source(e);
1.1183 + _digraph->nextOut(_stack[_stack_head]);
1.1184 }
1.1185 while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
1.1186 - _visitor->leave(m);
1.1187 - --_stack_head;
1.1188 - if (_stack_head >= 0) {
1.1189 - _visitor->backtrack(_stack[_stack_head]);
1.1190 - m = _digraph->source(_stack[_stack_head]);
1.1191 - _digraph->nextOut(_stack[_stack_head]);
1.1192 - } else {
1.1193 - _visitor->stop(m);
1.1194 - }
1.1195 + _visitor->leave(m);
1.1196 + --_stack_head;
1.1197 + if (_stack_head >= 0) {
1.1198 + _visitor->backtrack(_stack[_stack_head]);
1.1199 + m = _digraph->source(_stack[_stack_head]);
1.1200 + _digraph->nextOut(_stack[_stack_head]);
1.1201 + } else {
1.1202 + _visitor->stop(m);
1.1203 + }
1.1204 }
1.1205 return e;
1.1206 }
1.1207 @@ -1415,7 +1415,7 @@
1.1208 ///
1.1209 /// \return The next arc to be processed or INVALID if the stack is
1.1210 /// empty.
1.1211 - Arc nextArc() {
1.1212 + Arc nextArc() {
1.1213 return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
1.1214 }
1.1215
1.1216 @@ -1430,7 +1430,7 @@
1.1217 ///
1.1218 /// Returns the number of the nodes to be processed in the queue.
1.1219 int queueSize() { return _stack_head + 1; }
1.1220 -
1.1221 +
1.1222 /// \brief Executes the algorithm.
1.1223 ///
1.1224 /// Executes the algorithm.
1.1225 @@ -1440,7 +1440,7 @@
1.1226 void start() {
1.1227 while ( !emptyQueue() ) processNextArc();
1.1228 }
1.1229 -
1.1230 +
1.1231 /// \brief Executes the algorithm until \c dest is reached.
1.1232 ///
1.1233 /// Executes the algorithm until \c dest is reached.
1.1234 @@ -1448,10 +1448,10 @@
1.1235 /// \pre init() must be called and at least one node should be added
1.1236 /// with addSource() before using this function.
1.1237 void start(Node dest) {
1.1238 - while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest )
1.1239 - processNextArc();
1.1240 + while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest )
1.1241 + processNextArc();
1.1242 }
1.1243 -
1.1244 +
1.1245 /// \brief Executes the algorithm until a condition is met.
1.1246 ///
1.1247 /// Executes the algorithm until a condition is met.
1.1248 @@ -1490,7 +1490,7 @@
1.1249 }
1.1250
1.1251 /// \brief Runs %DFSVisit algorithm to visit all nodes in the digraph.
1.1252 -
1.1253 +
1.1254 /// This method runs the %DFS algorithm in order to
1.1255 /// compute the %DFS path to each node. The algorithm computes
1.1256 /// - The %DFS tree.