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