1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/bfs.h Thu Feb 07 21:37:07 2008 +0000
1.3 @@ -0,0 +1,1597 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_BFS_H
1.23 +#define LEMON_BFS_H
1.24 +
1.25 +///\ingroup search
1.26 +///\file
1.27 +///\brief Bfs algorithm.
1.28 +
1.29 +#include <lemon/list_graph.h>
1.30 +#include <lemon/graph_utils.h>
1.31 +#include <lemon/bits/path_dump.h>
1.32 +#include <lemon/bits/invalid.h>
1.33 +#include <lemon/error.h>
1.34 +#include <lemon/maps.h>
1.35 +
1.36 +namespace lemon {
1.37 +
1.38 +
1.39 +
1.40 + ///Default traits class of Bfs class.
1.41 +
1.42 + ///Default traits class of Bfs class.
1.43 + ///\param GR Digraph type.
1.44 + template<class GR>
1.45 + struct BfsDefaultTraits
1.46 + {
1.47 + ///The digraph type the algorithm runs on.
1.48 + typedef GR Digraph;
1.49 + ///\brief The type of the map that stores the last
1.50 + ///arcs of the shortest paths.
1.51 + ///
1.52 + ///The type of the map that stores the last
1.53 + ///arcs of the shortest paths.
1.54 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.55 + ///
1.56 + typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
1.57 + ///Instantiates a PredMap.
1.58 +
1.59 + ///This function instantiates a \ref PredMap.
1.60 + ///\param G is the digraph, to which we would like to define the PredMap.
1.61 + ///\todo The digraph alone may be insufficient to initialize
1.62 + static PredMap *createPredMap(const GR &G)
1.63 + {
1.64 + return new PredMap(G);
1.65 + }
1.66 + ///The type of the map that indicates which nodes are processed.
1.67 +
1.68 + ///The type of the map that indicates which nodes are processed.
1.69 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.70 + ///\todo named parameter to set this type, function to read and write.
1.71 + typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.72 + ///Instantiates a ProcessedMap.
1.73 +
1.74 + ///This function instantiates a \ref ProcessedMap.
1.75 + ///\param g is the digraph, to which
1.76 + ///we would like to define the \ref ProcessedMap
1.77 +#ifdef DOXYGEN
1.78 + static ProcessedMap *createProcessedMap(const GR &g)
1.79 +#else
1.80 + static ProcessedMap *createProcessedMap(const GR &)
1.81 +#endif
1.82 + {
1.83 + return new ProcessedMap();
1.84 + }
1.85 + ///The type of the map that indicates which nodes are reached.
1.86 +
1.87 + ///The type of the map that indicates which nodes are reached.
1.88 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.89 + ///\todo named parameter to set this type, function to read and write.
1.90 + typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.91 + ///Instantiates a ReachedMap.
1.92 +
1.93 + ///This function instantiates a \ref ReachedMap.
1.94 + ///\param G is the digraph, to which
1.95 + ///we would like to define the \ref ReachedMap.
1.96 + static ReachedMap *createReachedMap(const GR &G)
1.97 + {
1.98 + return new ReachedMap(G);
1.99 + }
1.100 + ///The type of the map that stores the dists of the nodes.
1.101 +
1.102 + ///The type of the map that stores the dists of the nodes.
1.103 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.104 + ///
1.105 + typedef typename Digraph::template NodeMap<int> DistMap;
1.106 + ///Instantiates a DistMap.
1.107 +
1.108 + ///This function instantiates a \ref DistMap.
1.109 + ///\param G is the digraph, to which we would like to define the \ref DistMap
1.110 + static DistMap *createDistMap(const GR &G)
1.111 + {
1.112 + return new DistMap(G);
1.113 + }
1.114 + };
1.115 +
1.116 + ///%BFS algorithm class.
1.117 +
1.118 + ///\ingroup search
1.119 + ///This class provides an efficient implementation of the %BFS algorithm.
1.120 + ///
1.121 + ///\param GR The digraph type the algorithm runs on. The default value is
1.122 + ///\ref ListDigraph. The value of GR is not used directly by Bfs, it
1.123 + ///is only passed to \ref BfsDefaultTraits.
1.124 + ///\param TR Traits class to set various data types used by the algorithm.
1.125 + ///The default traits class is
1.126 + ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
1.127 + ///See \ref BfsDefaultTraits for the documentation of
1.128 + ///a Bfs traits class.
1.129 + ///
1.130 + ///\author Alpar Juttner
1.131 +
1.132 +#ifdef DOXYGEN
1.133 + template <typename GR,
1.134 + typename TR>
1.135 +#else
1.136 + template <typename GR=ListDigraph,
1.137 + typename TR=BfsDefaultTraits<GR> >
1.138 +#endif
1.139 + class Bfs {
1.140 + public:
1.141 + /**
1.142 + * \brief \ref Exception for uninitialized parameters.
1.143 + *
1.144 + * This error represents problems in the initialization
1.145 + * of the parameters of the algorithms.
1.146 + */
1.147 + class UninitializedParameter : public lemon::UninitializedParameter {
1.148 + public:
1.149 + virtual const char* what() const throw() {
1.150 + return "lemon::Bfs::UninitializedParameter";
1.151 + }
1.152 + };
1.153 +
1.154 + typedef TR Traits;
1.155 + ///The type of the underlying digraph.
1.156 + typedef typename TR::Digraph Digraph;
1.157 +
1.158 + ///\brief The type of the map that stores the last
1.159 + ///arcs of the shortest paths.
1.160 + typedef typename TR::PredMap PredMap;
1.161 + ///The type of the map indicating which nodes are reached.
1.162 + typedef typename TR::ReachedMap ReachedMap;
1.163 + ///The type of the map indicating which nodes are processed.
1.164 + typedef typename TR::ProcessedMap ProcessedMap;
1.165 + ///The type of the map that stores the dists of the nodes.
1.166 + typedef typename TR::DistMap DistMap;
1.167 + private:
1.168 +
1.169 + typedef typename Digraph::Node Node;
1.170 + typedef typename Digraph::NodeIt NodeIt;
1.171 + typedef typename Digraph::Arc Arc;
1.172 + typedef typename Digraph::OutArcIt OutArcIt;
1.173 +
1.174 + /// Pointer to the underlying digraph.
1.175 + const Digraph *G;
1.176 + ///Pointer to the map of predecessors arcs.
1.177 + PredMap *_pred;
1.178 + ///Indicates if \ref _pred is locally allocated (\c true) or not.
1.179 + bool local_pred;
1.180 + ///Pointer to the map of distances.
1.181 + DistMap *_dist;
1.182 + ///Indicates if \ref _dist is locally allocated (\c true) or not.
1.183 + bool local_dist;
1.184 + ///Pointer to the map of reached status of the nodes.
1.185 + ReachedMap *_reached;
1.186 + ///Indicates if \ref _reached is locally allocated (\c true) or not.
1.187 + bool local_reached;
1.188 + ///Pointer to the map of processed status of the nodes.
1.189 + ProcessedMap *_processed;
1.190 + ///Indicates if \ref _processed is locally allocated (\c true) or not.
1.191 + bool local_processed;
1.192 +
1.193 + std::vector<typename Digraph::Node> _queue;
1.194 + int _queue_head,_queue_tail,_queue_next_dist;
1.195 + int _curr_dist;
1.196 +
1.197 + ///Creates the maps if necessary.
1.198 +
1.199 + ///\todo Better memory allocation (instead of new).
1.200 + void create_maps()
1.201 + {
1.202 + if(!_pred) {
1.203 + local_pred = true;
1.204 + _pred = Traits::createPredMap(*G);
1.205 + }
1.206 + if(!_dist) {
1.207 + local_dist = true;
1.208 + _dist = Traits::createDistMap(*G);
1.209 + }
1.210 + if(!_reached) {
1.211 + local_reached = true;
1.212 + _reached = Traits::createReachedMap(*G);
1.213 + }
1.214 + if(!_processed) {
1.215 + local_processed = true;
1.216 + _processed = Traits::createProcessedMap(*G);
1.217 + }
1.218 + }
1.219 +
1.220 + protected:
1.221 +
1.222 + Bfs() {}
1.223 +
1.224 + public:
1.225 +
1.226 + typedef Bfs Create;
1.227 +
1.228 + ///\name Named template parameters
1.229 +
1.230 + ///@{
1.231 +
1.232 + template <class T>
1.233 + struct DefPredMapTraits : public Traits {
1.234 + typedef T PredMap;
1.235 + static PredMap *createPredMap(const Digraph &)
1.236 + {
1.237 + throw UninitializedParameter();
1.238 + }
1.239 + };
1.240 + ///\brief \ref named-templ-param "Named parameter" for setting
1.241 + ///PredMap type
1.242 + ///
1.243 + ///\ref named-templ-param "Named parameter" for setting PredMap type
1.244 + ///
1.245 + template <class T>
1.246 + struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > {
1.247 + typedef Bfs< Digraph, DefPredMapTraits<T> > Create;
1.248 + };
1.249 +
1.250 + template <class T>
1.251 + struct DefDistMapTraits : public Traits {
1.252 + typedef T DistMap;
1.253 + static DistMap *createDistMap(const Digraph &)
1.254 + {
1.255 + throw UninitializedParameter();
1.256 + }
1.257 + };
1.258 + ///\brief \ref named-templ-param "Named parameter" for setting
1.259 + ///DistMap type
1.260 + ///
1.261 + ///\ref named-templ-param "Named parameter" for setting DistMap type
1.262 + ///
1.263 + template <class T>
1.264 + struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > {
1.265 + typedef Bfs< Digraph, DefDistMapTraits<T> > Create;
1.266 + };
1.267 +
1.268 + template <class T>
1.269 + struct DefReachedMapTraits : public Traits {
1.270 + typedef T ReachedMap;
1.271 + static ReachedMap *createReachedMap(const Digraph &)
1.272 + {
1.273 + throw UninitializedParameter();
1.274 + }
1.275 + };
1.276 + ///\brief \ref named-templ-param "Named parameter" for setting
1.277 + ///ReachedMap type
1.278 + ///
1.279 + ///\ref named-templ-param "Named parameter" for setting ReachedMap type
1.280 + ///
1.281 + template <class T>
1.282 + struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > {
1.283 + typedef Bfs< Digraph, DefReachedMapTraits<T> > Create;
1.284 + };
1.285 +
1.286 + template <class T>
1.287 + struct DefProcessedMapTraits : public Traits {
1.288 + typedef T ProcessedMap;
1.289 + static ProcessedMap *createProcessedMap(const Digraph &)
1.290 + {
1.291 + throw UninitializedParameter();
1.292 + }
1.293 + };
1.294 + ///\brief \ref named-templ-param "Named parameter" for setting
1.295 + ///ProcessedMap type
1.296 + ///
1.297 + ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
1.298 + ///
1.299 + template <class T>
1.300 + struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits<T> > {
1.301 + typedef Bfs< Digraph, DefProcessedMapTraits<T> > Create;
1.302 + };
1.303 +
1.304 + struct DefDigraphProcessedMapTraits : public Traits {
1.305 + typedef typename Digraph::template NodeMap<bool> ProcessedMap;
1.306 + static ProcessedMap *createProcessedMap(const Digraph &G)
1.307 + {
1.308 + return new ProcessedMap(G);
1.309 + }
1.310 + };
1.311 + ///\brief \ref named-templ-param "Named parameter"
1.312 + ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
1.313 + ///
1.314 + ///\ref named-templ-param "Named parameter"
1.315 + ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
1.316 + ///If you don't set it explicitly, it will be automatically allocated.
1.317 + template <class T>
1.318 + struct DefProcessedMapToBeDefaultMap :
1.319 + public Bfs< Digraph, DefDigraphProcessedMapTraits> {
1.320 + typedef Bfs< Digraph, DefDigraphProcessedMapTraits> Create;
1.321 + };
1.322 +
1.323 + ///@}
1.324 +
1.325 + public:
1.326 +
1.327 + ///Constructor.
1.328 +
1.329 + ///\param _G the digraph the algorithm will run on.
1.330 + ///
1.331 + Bfs(const Digraph& _G) :
1.332 + G(&_G),
1.333 + _pred(NULL), local_pred(false),
1.334 + _dist(NULL), local_dist(false),
1.335 + _reached(NULL), local_reached(false),
1.336 + _processed(NULL), local_processed(false)
1.337 + { }
1.338 +
1.339 + ///Destructor.
1.340 + ~Bfs()
1.341 + {
1.342 + if(local_pred) delete _pred;
1.343 + if(local_dist) delete _dist;
1.344 + if(local_reached) delete _reached;
1.345 + if(local_processed) delete _processed;
1.346 + }
1.347 +
1.348 + ///Sets the map storing the predecessor arcs.
1.349 +
1.350 + ///Sets the map storing the predecessor arcs.
1.351 + ///If you don't use this function before calling \ref run(),
1.352 + ///it will allocate one. The destructor deallocates this
1.353 + ///automatically allocated map, of course.
1.354 + ///\return <tt> (*this) </tt>
1.355 + Bfs &predMap(PredMap &m)
1.356 + {
1.357 + if(local_pred) {
1.358 + delete _pred;
1.359 + local_pred=false;
1.360 + }
1.361 + _pred = &m;
1.362 + return *this;
1.363 + }
1.364 +
1.365 + ///Sets the map indicating the reached nodes.
1.366 +
1.367 + ///Sets the map indicating the reached nodes.
1.368 + ///If you don't use this function before calling \ref run(),
1.369 + ///it will allocate one. The destructor deallocates this
1.370 + ///automatically allocated map, of course.
1.371 + ///\return <tt> (*this) </tt>
1.372 + Bfs &reachedMap(ReachedMap &m)
1.373 + {
1.374 + if(local_reached) {
1.375 + delete _reached;
1.376 + local_reached=false;
1.377 + }
1.378 + _reached = &m;
1.379 + return *this;
1.380 + }
1.381 +
1.382 + ///Sets the map indicating the processed nodes.
1.383 +
1.384 + ///Sets the map indicating the processed nodes.
1.385 + ///If you don't use this function before calling \ref run(),
1.386 + ///it will allocate one. The destructor deallocates this
1.387 + ///automatically allocated map, of course.
1.388 + ///\return <tt> (*this) </tt>
1.389 + Bfs &processedMap(ProcessedMap &m)
1.390 + {
1.391 + if(local_processed) {
1.392 + delete _processed;
1.393 + local_processed=false;
1.394 + }
1.395 + _processed = &m;
1.396 + return *this;
1.397 + }
1.398 +
1.399 + ///Sets the map storing the distances calculated by the algorithm.
1.400 +
1.401 + ///Sets the map storing the distances calculated by the algorithm.
1.402 + ///If you don't use this function before calling \ref run(),
1.403 + ///it will allocate one. The destructor deallocates this
1.404 + ///automatically allocated map, of course.
1.405 + ///\return <tt> (*this) </tt>
1.406 + Bfs &distMap(DistMap &m)
1.407 + {
1.408 + if(local_dist) {
1.409 + delete _dist;
1.410 + local_dist=false;
1.411 + }
1.412 + _dist = &m;
1.413 + return *this;
1.414 + }
1.415 +
1.416 + public:
1.417 + ///\name Execution control
1.418 + ///The simplest way to execute the algorithm is to use
1.419 + ///one of the member functions called \c run(...).
1.420 + ///\n
1.421 + ///If you need more control on the execution,
1.422 + ///first you must call \ref init(), then you can add several source nodes
1.423 + ///with \ref addSource().
1.424 + ///Finally \ref start() will perform the actual path
1.425 + ///computation.
1.426 +
1.427 + ///@{
1.428 +
1.429 + ///\brief Initializes the internal data structures.
1.430 + ///
1.431 + ///Initializes the internal data structures.
1.432 + ///
1.433 + void init()
1.434 + {
1.435 + create_maps();
1.436 + _queue.resize(countNodes(*G));
1.437 + _queue_head=_queue_tail=0;
1.438 + _curr_dist=1;
1.439 + for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
1.440 + _pred->set(u,INVALID);
1.441 + _reached->set(u,false);
1.442 + _processed->set(u,false);
1.443 + }
1.444 + }
1.445 +
1.446 + ///Adds a new source node.
1.447 +
1.448 + ///Adds a new source node to the set of nodes to be processed.
1.449 + ///
1.450 + void addSource(Node s)
1.451 + {
1.452 + if(!(*_reached)[s])
1.453 + {
1.454 + _reached->set(s,true);
1.455 + _pred->set(s,INVALID);
1.456 + _dist->set(s,0);
1.457 + _queue[_queue_head++]=s;
1.458 + _queue_next_dist=_queue_head;
1.459 + }
1.460 + }
1.461 +
1.462 + ///Processes the next node.
1.463 +
1.464 + ///Processes the next node.
1.465 + ///
1.466 + ///\return The processed node.
1.467 + ///
1.468 + ///\warning The queue must not be empty!
1.469 + Node processNextNode()
1.470 + {
1.471 + if(_queue_tail==_queue_next_dist) {
1.472 + _curr_dist++;
1.473 + _queue_next_dist=_queue_head;
1.474 + }
1.475 + Node n=_queue[_queue_tail++];
1.476 + _processed->set(n,true);
1.477 + Node m;
1.478 + for(OutArcIt e(*G,n);e!=INVALID;++e)
1.479 + if(!(*_reached)[m=G->target(e)]) {
1.480 + _queue[_queue_head++]=m;
1.481 + _reached->set(m,true);
1.482 + _pred->set(m,e);
1.483 + _dist->set(m,_curr_dist);
1.484 + }
1.485 + return n;
1.486 + }
1.487 +
1.488 + ///Processes the next node.
1.489 +
1.490 + ///Processes the next node. And checks that the given target node
1.491 + ///is reached. If the target node is reachable from the processed
1.492 + ///node then the reached parameter will be set true. The reached
1.493 + ///parameter should be initially false.
1.494 + ///
1.495 + ///\param target The target node.
1.496 + ///\retval reach Indicates that the target node is reached.
1.497 + ///\return The processed node.
1.498 + ///
1.499 + ///\warning The queue must not be empty!
1.500 + Node processNextNode(Node target, bool& reach)
1.501 + {
1.502 + if(_queue_tail==_queue_next_dist) {
1.503 + _curr_dist++;
1.504 + _queue_next_dist=_queue_head;
1.505 + }
1.506 + Node n=_queue[_queue_tail++];
1.507 + _processed->set(n,true);
1.508 + Node m;
1.509 + for(OutArcIt e(*G,n);e!=INVALID;++e)
1.510 + if(!(*_reached)[m=G->target(e)]) {
1.511 + _queue[_queue_head++]=m;
1.512 + _reached->set(m,true);
1.513 + _pred->set(m,e);
1.514 + _dist->set(m,_curr_dist);
1.515 + reach = reach || (target == m);
1.516 + }
1.517 + return n;
1.518 + }
1.519 +
1.520 + ///Processes the next node.
1.521 +
1.522 + ///Processes the next node. And checks that at least one of
1.523 + ///reached node has true value in the \c nm node map. If one node
1.524 + ///with true value is reachable from the processed node then the
1.525 + ///rnode parameter will be set to the first of such nodes.
1.526 + ///
1.527 + ///\param nm The node map of possible targets.
1.528 + ///\retval rnode The reached target node.
1.529 + ///\return The processed node.
1.530 + ///
1.531 + ///\warning The queue must not be empty!
1.532 + template<class NM>
1.533 + Node processNextNode(const NM& nm, Node& rnode)
1.534 + {
1.535 + if(_queue_tail==_queue_next_dist) {
1.536 + _curr_dist++;
1.537 + _queue_next_dist=_queue_head;
1.538 + }
1.539 + Node n=_queue[_queue_tail++];
1.540 + _processed->set(n,true);
1.541 + Node m;
1.542 + for(OutArcIt e(*G,n);e!=INVALID;++e)
1.543 + if(!(*_reached)[m=G->target(e)]) {
1.544 + _queue[_queue_head++]=m;
1.545 + _reached->set(m,true);
1.546 + _pred->set(m,e);
1.547 + _dist->set(m,_curr_dist);
1.548 + if (nm[m] && rnode == INVALID) rnode = m;
1.549 + }
1.550 + return n;
1.551 + }
1.552 +
1.553 + ///Next node to be processed.
1.554 +
1.555 + ///Next node to be processed.
1.556 + ///
1.557 + ///\return The next node to be processed or INVALID if the queue is
1.558 + /// empty.
1.559 + Node nextNode()
1.560 + {
1.561 + return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
1.562 + }
1.563 +
1.564 + ///\brief Returns \c false if there are nodes
1.565 + ///to be processed in the queue
1.566 + ///
1.567 + ///Returns \c false if there are nodes
1.568 + ///to be processed in the queue
1.569 + bool emptyQueue() { return _queue_tail==_queue_head; }
1.570 + ///Returns the number of the nodes to be processed.
1.571 +
1.572 + ///Returns the number of the nodes to be processed in the queue.
1.573 + int queueSize() { return _queue_head-_queue_tail; }
1.574 +
1.575 + ///Executes the algorithm.
1.576 +
1.577 + ///Executes the algorithm.
1.578 + ///
1.579 + ///\pre init() must be called and at least one node should be added
1.580 + ///with addSource() before using this function.
1.581 + ///
1.582 + ///This method runs the %BFS algorithm from the root node(s)
1.583 + ///in order to
1.584 + ///compute the
1.585 + ///shortest path to each node. The algorithm computes
1.586 + ///- The shortest path tree.
1.587 + ///- The distance of each node from the root(s).
1.588 + void start()
1.589 + {
1.590 + while ( !emptyQueue() ) processNextNode();
1.591 + }
1.592 +
1.593 + ///Executes the algorithm until \c dest is reached.
1.594 +
1.595 + ///Executes the algorithm until \c dest is reached.
1.596 + ///
1.597 + ///\pre init() must be called and at least one node should be added
1.598 + ///with addSource() before using this function.
1.599 + ///
1.600 + ///This method runs the %BFS algorithm from the root node(s)
1.601 + ///in order to compute the shortest path to \c dest.
1.602 + ///The algorithm computes
1.603 + ///- The shortest path to \c dest.
1.604 + ///- The distance of \c dest from the root(s).
1.605 + void start(Node dest)
1.606 + {
1.607 + bool reach = false;
1.608 + while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
1.609 + }
1.610 +
1.611 + ///Executes the algorithm until a condition is met.
1.612 +
1.613 + ///Executes the algorithm until a condition is met.
1.614 + ///
1.615 + ///\pre init() must be called and at least one node should be added
1.616 + ///with addSource() before using this function.
1.617 + ///
1.618 + ///\param nm must be a bool (or convertible) node map. The
1.619 + ///algorithm will stop when it reaches a node \c v with
1.620 + /// <tt>nm[v]</tt> true.
1.621 + ///
1.622 + ///\return The reached node \c v with <tt>nm[v]</tt> true or
1.623 + ///\c INVALID if no such node was found.
1.624 + template<class NM>
1.625 + Node start(const NM &nm)
1.626 + {
1.627 + Node rnode = INVALID;
1.628 + while ( !emptyQueue() && rnode == INVALID ) {
1.629 + processNextNode(nm, rnode);
1.630 + }
1.631 + return rnode;
1.632 + }
1.633 +
1.634 + ///Runs %BFS algorithm from node \c s.
1.635 +
1.636 + ///This method runs the %BFS algorithm from a root node \c s
1.637 + ///in order to
1.638 + ///compute the
1.639 + ///shortest path to each node. The algorithm computes
1.640 + ///- The shortest path tree.
1.641 + ///- The distance of each node from the root.
1.642 + ///
1.643 + ///\note b.run(s) is just a shortcut of the following code.
1.644 + ///\code
1.645 + /// b.init();
1.646 + /// b.addSource(s);
1.647 + /// b.start();
1.648 + ///\endcode
1.649 + void run(Node s) {
1.650 + init();
1.651 + addSource(s);
1.652 + start();
1.653 + }
1.654 +
1.655 + ///Finds the shortest path between \c s and \c t.
1.656 +
1.657 + ///Finds the shortest path between \c s and \c t.
1.658 + ///
1.659 + ///\return The length of the shortest s---t path if there exists one,
1.660 + ///0 otherwise.
1.661 + ///\note Apart from the return value, b.run(s) is
1.662 + ///just a shortcut of the following code.
1.663 + ///\code
1.664 + /// b.init();
1.665 + /// b.addSource(s);
1.666 + /// b.start(t);
1.667 + ///\endcode
1.668 + int run(Node s,Node t) {
1.669 + init();
1.670 + addSource(s);
1.671 + start(t);
1.672 + return reached(t) ? _curr_dist : 0;
1.673 + }
1.674 +
1.675 + ///@}
1.676 +
1.677 + ///\name Query Functions
1.678 + ///The result of the %BFS algorithm can be obtained using these
1.679 + ///functions.\n
1.680 + ///Before the use of these functions,
1.681 + ///either run() or start() must be calleb.
1.682 +
1.683 + ///@{
1.684 +
1.685 + typedef PredMapPath<Digraph, PredMap> Path;
1.686 +
1.687 + ///Gives back the shortest path.
1.688 +
1.689 + ///Gives back the shortest path.
1.690 + ///\pre The \c t should be reachable from the source.
1.691 + Path path(Node t)
1.692 + {
1.693 + return Path(*G, *_pred, t);
1.694 + }
1.695 +
1.696 + ///The distance of a node from the root(s).
1.697 +
1.698 + ///Returns the distance of a node from the root(s).
1.699 + ///\pre \ref run() must be called before using this function.
1.700 + ///\warning If node \c v in unreachable from the root(s) the return value
1.701 + ///of this function is undefined.
1.702 + int dist(Node v) const { return (*_dist)[v]; }
1.703 +
1.704 + ///Returns the 'previous arc' of the shortest path tree.
1.705 +
1.706 + ///For a node \c v it returns the 'previous arc'
1.707 + ///of the shortest path tree,
1.708 + ///i.e. it returns the last arc of a shortest path from the root(s) to \c
1.709 + ///v. It is \ref INVALID
1.710 + ///if \c v is unreachable from the root(s) or \c v is a root. The
1.711 + ///shortest path tree used here is equal to the shortest path tree used in
1.712 + ///\ref predNode().
1.713 + ///\pre Either \ref run() or \ref start() must be called before using
1.714 + ///this function.
1.715 + Arc predArc(Node v) const { return (*_pred)[v];}
1.716 +
1.717 + ///Returns the 'previous node' of the shortest path tree.
1.718 +
1.719 + ///For a node \c v it returns the 'previous node'
1.720 + ///of the shortest path tree,
1.721 + ///i.e. it returns the last but one node from a shortest path from the
1.722 + ///root(a) to \c /v.
1.723 + ///It is INVALID if \c v is unreachable from the root(s) or
1.724 + ///if \c v itself a root.
1.725 + ///The shortest path tree used here is equal to the shortest path
1.726 + ///tree used in \ref predArc().
1.727 + ///\pre Either \ref run() or \ref start() must be called before
1.728 + ///using this function.
1.729 + Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
1.730 + G->source((*_pred)[v]); }
1.731 +
1.732 + ///Returns a reference to the NodeMap of distances.
1.733 +
1.734 + ///Returns a reference to the NodeMap of distances.
1.735 + ///\pre Either \ref run() or \ref init() must
1.736 + ///be called before using this function.
1.737 + const DistMap &distMap() const { return *_dist;}
1.738 +
1.739 + ///Returns a reference to the shortest path tree map.
1.740 +
1.741 + ///Returns a reference to the NodeMap of the arcs of the
1.742 + ///shortest path tree.
1.743 + ///\pre Either \ref run() or \ref init()
1.744 + ///must be called before using this function.
1.745 + const PredMap &predMap() const { return *_pred;}
1.746 +
1.747 + ///Checks if a node is reachable from the root.
1.748 +
1.749 + ///Returns \c true if \c v is reachable from the root.
1.750 + ///\warning The source nodes are indicated as unreached.
1.751 + ///\pre Either \ref run() or \ref start()
1.752 + ///must be called before using this function.
1.753 + ///
1.754 + bool reached(Node v) { return (*_reached)[v]; }
1.755 +
1.756 + ///@}
1.757 + };
1.758 +
1.759 + ///Default traits class of Bfs function.
1.760 +
1.761 + ///Default traits class of Bfs function.
1.762 + ///\param GR Digraph type.
1.763 + template<class GR>
1.764 + struct BfsWizardDefaultTraits
1.765 + {
1.766 + ///The digraph type the algorithm runs on.
1.767 + typedef GR Digraph;
1.768 + ///\brief The type of the map that stores the last
1.769 + ///arcs of the shortest paths.
1.770 + ///
1.771 + ///The type of the map that stores the last
1.772 + ///arcs of the shortest paths.
1.773 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.774 + ///
1.775 + typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
1.776 + ///Instantiates a PredMap.
1.777 +
1.778 + ///This function instantiates a \ref PredMap.
1.779 + ///\param g is the digraph, to which we would like to define the PredMap.
1.780 + ///\todo The digraph alone may be insufficient to initialize
1.781 +#ifdef DOXYGEN
1.782 + static PredMap *createPredMap(const GR &g)
1.783 +#else
1.784 + static PredMap *createPredMap(const GR &)
1.785 +#endif
1.786 + {
1.787 + return new PredMap();
1.788 + }
1.789 +
1.790 + ///The type of the map that indicates which nodes are processed.
1.791 +
1.792 + ///The type of the map that indicates which nodes are processed.
1.793 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.794 + ///\todo named parameter to set this type, function to read and write.
1.795 + typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
1.796 + ///Instantiates a ProcessedMap.
1.797 +
1.798 + ///This function instantiates a \ref ProcessedMap.
1.799 + ///\param g is the digraph, to which
1.800 + ///we would like to define the \ref ProcessedMap
1.801 +#ifdef DOXYGEN
1.802 + static ProcessedMap *createProcessedMap(const GR &g)
1.803 +#else
1.804 + static ProcessedMap *createProcessedMap(const GR &)
1.805 +#endif
1.806 + {
1.807 + return new ProcessedMap();
1.808 + }
1.809 + ///The type of the map that indicates which nodes are reached.
1.810 +
1.811 + ///The type of the map that indicates which nodes are reached.
1.812 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.813 + ///\todo named parameter to set this type, function to read and write.
1.814 + typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.815 + ///Instantiates a ReachedMap.
1.816 +
1.817 + ///This function instantiates a \ref ReachedMap.
1.818 + ///\param G is the digraph, to which
1.819 + ///we would like to define the \ref ReachedMap.
1.820 + static ReachedMap *createReachedMap(const GR &G)
1.821 + {
1.822 + return new ReachedMap(G);
1.823 + }
1.824 + ///The type of the map that stores the dists of the nodes.
1.825 +
1.826 + ///The type of the map that stores the dists of the nodes.
1.827 + ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.828 + ///
1.829 + typedef NullMap<typename Digraph::Node,int> DistMap;
1.830 + ///Instantiates a DistMap.
1.831 +
1.832 + ///This function instantiates a \ref DistMap.
1.833 + ///\param g is the digraph, to which we would like to define the \ref DistMap
1.834 +#ifdef DOXYGEN
1.835 + static DistMap *createDistMap(const GR &g)
1.836 +#else
1.837 + static DistMap *createDistMap(const GR &)
1.838 +#endif
1.839 + {
1.840 + return new DistMap();
1.841 + }
1.842 + };
1.843 +
1.844 + /// Default traits used by \ref BfsWizard
1.845 +
1.846 + /// To make it easier to use Bfs algorithm
1.847 + ///we have created a wizard class.
1.848 + /// This \ref BfsWizard class needs default traits,
1.849 + ///as well as the \ref Bfs class.
1.850 + /// The \ref BfsWizardBase is a class to be the default traits of the
1.851 + /// \ref BfsWizard class.
1.852 + template<class GR>
1.853 + class BfsWizardBase : public BfsWizardDefaultTraits<GR>
1.854 + {
1.855 +
1.856 + typedef BfsWizardDefaultTraits<GR> Base;
1.857 + protected:
1.858 + /// Type of the nodes in the digraph.
1.859 + typedef typename Base::Digraph::Node Node;
1.860 +
1.861 + /// Pointer to the underlying digraph.
1.862 + void *_g;
1.863 + ///Pointer to the map of reached nodes.
1.864 + void *_reached;
1.865 + ///Pointer to the map of processed nodes.
1.866 + void *_processed;
1.867 + ///Pointer to the map of predecessors arcs.
1.868 + void *_pred;
1.869 + ///Pointer to the map of distances.
1.870 + void *_dist;
1.871 + ///Pointer to the source node.
1.872 + Node _source;
1.873 +
1.874 + public:
1.875 + /// Constructor.
1.876 +
1.877 + /// This constructor does not require parameters, therefore it initiates
1.878 + /// all of the attributes to default values (0, INVALID).
1.879 + BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
1.880 + _dist(0), _source(INVALID) {}
1.881 +
1.882 + /// Constructor.
1.883 +
1.884 + /// This constructor requires some parameters,
1.885 + /// listed in the parameters list.
1.886 + /// Others are initiated to 0.
1.887 + /// \param g is the initial value of \ref _g
1.888 + /// \param s is the initial value of \ref _source
1.889 + BfsWizardBase(const GR &g, Node s=INVALID) :
1.890 + _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
1.891 + _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
1.892 +
1.893 + };
1.894 +
1.895 + /// A class to make the usage of Bfs algorithm easier
1.896 +
1.897 + /// This class is created to make it easier to use Bfs algorithm.
1.898 + /// It uses the functions and features of the plain \ref Bfs,
1.899 + /// but it is much simpler to use it.
1.900 + ///
1.901 + /// Simplicity means that the way to change the types defined
1.902 + /// in the traits class is based on functions that returns the new class
1.903 + /// and not on templatable built-in classes.
1.904 + /// When using the plain \ref Bfs
1.905 + /// the new class with the modified type comes from
1.906 + /// the original class by using the ::
1.907 + /// operator. In the case of \ref BfsWizard only
1.908 + /// a function have to be called and it will
1.909 + /// return the needed class.
1.910 + ///
1.911 + /// It does not have own \ref run method. When its \ref run method is called
1.912 + /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run
1.913 + /// method of it.
1.914 + template<class TR>
1.915 + class BfsWizard : public TR
1.916 + {
1.917 + typedef TR Base;
1.918 +
1.919 + ///The type of the underlying digraph.
1.920 + typedef typename TR::Digraph Digraph;
1.921 + //\e
1.922 + typedef typename Digraph::Node Node;
1.923 + //\e
1.924 + typedef typename Digraph::NodeIt NodeIt;
1.925 + //\e
1.926 + typedef typename Digraph::Arc Arc;
1.927 + //\e
1.928 + typedef typename Digraph::OutArcIt OutArcIt;
1.929 +
1.930 + ///\brief The type of the map that stores
1.931 + ///the reached nodes
1.932 + typedef typename TR::ReachedMap ReachedMap;
1.933 + ///\brief The type of the map that stores
1.934 + ///the processed nodes
1.935 + typedef typename TR::ProcessedMap ProcessedMap;
1.936 + ///\brief The type of the map that stores the last
1.937 + ///arcs of the shortest paths.
1.938 + typedef typename TR::PredMap PredMap;
1.939 + ///The type of the map that stores the dists of the nodes.
1.940 + typedef typename TR::DistMap DistMap;
1.941 +
1.942 + public:
1.943 + /// Constructor.
1.944 + BfsWizard() : TR() {}
1.945 +
1.946 + /// Constructor that requires parameters.
1.947 +
1.948 + /// Constructor that requires parameters.
1.949 + /// These parameters will be the default values for the traits class.
1.950 + BfsWizard(const Digraph &g, Node s=INVALID) :
1.951 + TR(g,s) {}
1.952 +
1.953 + ///Copy constructor
1.954 + BfsWizard(const TR &b) : TR(b) {}
1.955 +
1.956 + ~BfsWizard() {}
1.957 +
1.958 + ///Runs Bfs algorithm from a given node.
1.959 +
1.960 + ///Runs Bfs algorithm from a given node.
1.961 + ///The node can be given by the \ref source function.
1.962 + void run()
1.963 + {
1.964 + if(Base::_source==INVALID) throw UninitializedParameter();
1.965 + Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
1.966 + if(Base::_reached)
1.967 + alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
1.968 + if(Base::_processed)
1.969 + alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1.970 + if(Base::_pred)
1.971 + alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1.972 + if(Base::_dist)
1.973 + alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1.974 + alg.run(Base::_source);
1.975 + }
1.976 +
1.977 + ///Runs Bfs algorithm from the given node.
1.978 +
1.979 + ///Runs Bfs algorithm from the given node.
1.980 + ///\param s is the given source.
1.981 + void run(Node s)
1.982 + {
1.983 + Base::_source=s;
1.984 + run();
1.985 + }
1.986 +
1.987 + template<class T>
1.988 + struct DefPredMapBase : public Base {
1.989 + typedef T PredMap;
1.990 + static PredMap *createPredMap(const Digraph &) { return 0; };
1.991 + DefPredMapBase(const TR &b) : TR(b) {}
1.992 + };
1.993 +
1.994 + ///\brief \ref named-templ-param "Named parameter"
1.995 + ///function for setting PredMap
1.996 + ///
1.997 + /// \ref named-templ-param "Named parameter"
1.998 + ///function for setting PredMap
1.999 + ///
1.1000 + template<class T>
1.1001 + BfsWizard<DefPredMapBase<T> > predMap(const T &t)
1.1002 + {
1.1003 + Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1.1004 + return BfsWizard<DefPredMapBase<T> >(*this);
1.1005 + }
1.1006 +
1.1007 +
1.1008 + template<class T>
1.1009 + struct DefReachedMapBase : public Base {
1.1010 + typedef T ReachedMap;
1.1011 + static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1.1012 + DefReachedMapBase(const TR &b) : TR(b) {}
1.1013 + };
1.1014 +
1.1015 + ///\brief \ref named-templ-param "Named parameter"
1.1016 + ///function for setting ReachedMap
1.1017 + ///
1.1018 + /// \ref named-templ-param "Named parameter"
1.1019 + ///function for setting ReachedMap
1.1020 + ///
1.1021 + template<class T>
1.1022 + BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1.1023 + {
1.1024 + Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1.1025 + return BfsWizard<DefReachedMapBase<T> >(*this);
1.1026 + }
1.1027 +
1.1028 +
1.1029 + template<class T>
1.1030 + struct DefProcessedMapBase : public Base {
1.1031 + typedef T ProcessedMap;
1.1032 + static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1.1033 + DefProcessedMapBase(const TR &b) : TR(b) {}
1.1034 + };
1.1035 +
1.1036 + ///\brief \ref named-templ-param "Named parameter"
1.1037 + ///function for setting ProcessedMap
1.1038 + ///
1.1039 + /// \ref named-templ-param "Named parameter"
1.1040 + ///function for setting ProcessedMap
1.1041 + ///
1.1042 + template<class T>
1.1043 + BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1.1044 + {
1.1045 + Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1.1046 + return BfsWizard<DefProcessedMapBase<T> >(*this);
1.1047 + }
1.1048 +
1.1049 +
1.1050 + template<class T>
1.1051 + struct DefDistMapBase : public Base {
1.1052 + typedef T DistMap;
1.1053 + static DistMap *createDistMap(const Digraph &) { return 0; };
1.1054 + DefDistMapBase(const TR &b) : TR(b) {}
1.1055 + };
1.1056 +
1.1057 + ///\brief \ref named-templ-param "Named parameter"
1.1058 + ///function for setting DistMap type
1.1059 + ///
1.1060 + /// \ref named-templ-param "Named parameter"
1.1061 + ///function for setting DistMap type
1.1062 + ///
1.1063 + template<class T>
1.1064 + BfsWizard<DefDistMapBase<T> > distMap(const T &t)
1.1065 + {
1.1066 + Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1.1067 + return BfsWizard<DefDistMapBase<T> >(*this);
1.1068 + }
1.1069 +
1.1070 + /// Sets the source node, from which the Bfs algorithm runs.
1.1071 +
1.1072 + /// Sets the source node, from which the Bfs algorithm runs.
1.1073 + /// \param s is the source node.
1.1074 + BfsWizard<TR> &source(Node s)
1.1075 + {
1.1076 + Base::_source=s;
1.1077 + return *this;
1.1078 + }
1.1079 +
1.1080 + };
1.1081 +
1.1082 + ///Function type interface for Bfs algorithm.
1.1083 +
1.1084 + /// \ingroup search
1.1085 + ///Function type interface for Bfs algorithm.
1.1086 + ///
1.1087 + ///This function also has several
1.1088 + ///\ref named-templ-func-param "named parameters",
1.1089 + ///they are declared as the members of class \ref BfsWizard.
1.1090 + ///The following
1.1091 + ///example shows how to use these parameters.
1.1092 + ///\code
1.1093 + /// bfs(g,source).predMap(preds).run();
1.1094 + ///\endcode
1.1095 + ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
1.1096 + ///to the end of the parameter list.
1.1097 + ///\sa BfsWizard
1.1098 + ///\sa Bfs
1.1099 + template<class GR>
1.1100 + BfsWizard<BfsWizardBase<GR> >
1.1101 + bfs(const GR &g,typename GR::Node s=INVALID)
1.1102 + {
1.1103 + return BfsWizard<BfsWizardBase<GR> >(g,s);
1.1104 + }
1.1105 +
1.1106 +#ifdef DOXYGEN
1.1107 + /// \brief Visitor class for bfs.
1.1108 + ///
1.1109 + /// This class defines the interface of the BfsVisit events, and
1.1110 + /// it could be the base of a real Visitor class.
1.1111 + template <typename _Digraph>
1.1112 + struct BfsVisitor {
1.1113 + typedef _Digraph Digraph;
1.1114 + typedef typename Digraph::Arc Arc;
1.1115 + typedef typename Digraph::Node Node;
1.1116 + /// \brief Called when the arc reach a node.
1.1117 + ///
1.1118 + /// It is called when the bfs find an arc which target is not
1.1119 + /// reached yet.
1.1120 + void discover(const Arc& arc) {}
1.1121 + /// \brief Called when the node reached first time.
1.1122 + ///
1.1123 + /// It is Called when the node reached first time.
1.1124 + void reach(const Node& node) {}
1.1125 + /// \brief Called when the arc examined but target of the arc
1.1126 + /// already discovered.
1.1127 + ///
1.1128 + /// It called when the arc examined but the target of the arc
1.1129 + /// already discovered.
1.1130 + void examine(const Arc& arc) {}
1.1131 + /// \brief Called for the source node of the bfs.
1.1132 + ///
1.1133 + /// It is called for the source node of the bfs.
1.1134 + void start(const Node& node) {}
1.1135 + /// \brief Called when the node processed.
1.1136 + ///
1.1137 + /// It is Called when the node processed.
1.1138 + void process(const Node& node) {}
1.1139 + };
1.1140 +#else
1.1141 + template <typename _Digraph>
1.1142 + struct BfsVisitor {
1.1143 + typedef _Digraph Digraph;
1.1144 + typedef typename Digraph::Arc Arc;
1.1145 + typedef typename Digraph::Node Node;
1.1146 + void discover(const Arc&) {}
1.1147 + void reach(const Node&) {}
1.1148 + void examine(const Arc&) {}
1.1149 + void start(const Node&) {}
1.1150 + void process(const Node&) {}
1.1151 +
1.1152 + template <typename _Visitor>
1.1153 + struct Constraints {
1.1154 + void constraints() {
1.1155 + Arc arc;
1.1156 + Node node;
1.1157 + visitor.discover(arc);
1.1158 + visitor.reach(node);
1.1159 + visitor.examine(arc);
1.1160 + visitor.start(node);
1.1161 + visitor.process(node);
1.1162 + }
1.1163 + _Visitor& visitor;
1.1164 + };
1.1165 + };
1.1166 +#endif
1.1167 +
1.1168 + /// \brief Default traits class of BfsVisit class.
1.1169 + ///
1.1170 + /// Default traits class of BfsVisit class.
1.1171 + /// \param _Digraph Digraph type.
1.1172 + template<class _Digraph>
1.1173 + struct BfsVisitDefaultTraits {
1.1174 +
1.1175 + /// \brief The digraph type the algorithm runs on.
1.1176 + typedef _Digraph Digraph;
1.1177 +
1.1178 + /// \brief The type of the map that indicates which nodes are reached.
1.1179 + ///
1.1180 + /// The type of the map that indicates which nodes are reached.
1.1181 + /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.1182 + /// \todo named parameter to set this type, function to read and write.
1.1183 + typedef typename Digraph::template NodeMap<bool> ReachedMap;
1.1184 +
1.1185 + /// \brief Instantiates a ReachedMap.
1.1186 + ///
1.1187 + /// This function instantiates a \ref ReachedMap.
1.1188 + /// \param digraph is the digraph, to which
1.1189 + /// we would like to define the \ref ReachedMap.
1.1190 + static ReachedMap *createReachedMap(const Digraph &digraph) {
1.1191 + return new ReachedMap(digraph);
1.1192 + }
1.1193 +
1.1194 + };
1.1195 +
1.1196 + /// \ingroup search
1.1197 + ///
1.1198 + /// \brief %BFS Visit algorithm class.
1.1199 + ///
1.1200 + /// This class provides an efficient implementation of the %BFS algorithm
1.1201 + /// with visitor interface.
1.1202 + ///
1.1203 + /// The %BfsVisit class provides an alternative interface to the Bfs
1.1204 + /// class. It works with callback mechanism, the BfsVisit object calls
1.1205 + /// on every bfs event the \c Visitor class member functions.
1.1206 + ///
1.1207 + /// \param _Digraph The digraph type the algorithm runs on. The default value is
1.1208 + /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it
1.1209 + /// is only passed to \ref BfsDefaultTraits.
1.1210 + /// \param _Visitor The Visitor object for the algorithm. The
1.1211 + /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitor which
1.1212 + /// does not observe the Bfs events. If you want to observe the bfs
1.1213 + /// events you should implement your own Visitor class.
1.1214 + /// \param _Traits Traits class to set various data types used by the
1.1215 + /// algorithm. The default traits class is
1.1216 + /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
1.1217 + /// See \ref BfsVisitDefaultTraits for the documentation of
1.1218 + /// a Bfs visit traits class.
1.1219 + ///
1.1220 + /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
1.1221 +#ifdef DOXYGEN
1.1222 + template <typename _Digraph, typename _Visitor, typename _Traits>
1.1223 +#else
1.1224 + template <typename _Digraph = ListDigraph,
1.1225 + typename _Visitor = BfsVisitor<_Digraph>,
1.1226 + typename _Traits = BfsDefaultTraits<_Digraph> >
1.1227 +#endif
1.1228 + class BfsVisit {
1.1229 + public:
1.1230 +
1.1231 + /// \brief \ref Exception for uninitialized parameters.
1.1232 + ///
1.1233 + /// This error represents problems in the initialization
1.1234 + /// of the parameters of the algorithms.
1.1235 + class UninitializedParameter : public lemon::UninitializedParameter {
1.1236 + public:
1.1237 + virtual const char* what() const throw()
1.1238 + {
1.1239 + return "lemon::BfsVisit::UninitializedParameter";
1.1240 + }
1.1241 + };
1.1242 +
1.1243 + typedef _Traits Traits;
1.1244 +
1.1245 + typedef typename Traits::Digraph Digraph;
1.1246 +
1.1247 + typedef _Visitor Visitor;
1.1248 +
1.1249 + ///The type of the map indicating which nodes are reached.
1.1250 + typedef typename Traits::ReachedMap ReachedMap;
1.1251 +
1.1252 + private:
1.1253 +
1.1254 + typedef typename Digraph::Node Node;
1.1255 + typedef typename Digraph::NodeIt NodeIt;
1.1256 + typedef typename Digraph::Arc Arc;
1.1257 + typedef typename Digraph::OutArcIt OutArcIt;
1.1258 +
1.1259 + /// Pointer to the underlying digraph.
1.1260 + const Digraph *_digraph;
1.1261 + /// Pointer to the visitor object.
1.1262 + Visitor *_visitor;
1.1263 + ///Pointer to the map of reached status of the nodes.
1.1264 + ReachedMap *_reached;
1.1265 + ///Indicates if \ref _reached is locally allocated (\c true) or not.
1.1266 + bool local_reached;
1.1267 +
1.1268 + std::vector<typename Digraph::Node> _list;
1.1269 + int _list_front, _list_back;
1.1270 +
1.1271 + /// \brief Creates the maps if necessary.
1.1272 + ///
1.1273 + /// Creates the maps if necessary.
1.1274 + void create_maps() {
1.1275 + if(!_reached) {
1.1276 + local_reached = true;
1.1277 + _reached = Traits::createReachedMap(*_digraph);
1.1278 + }
1.1279 + }
1.1280 +
1.1281 + protected:
1.1282 +
1.1283 + BfsVisit() {}
1.1284 +
1.1285 + public:
1.1286 +
1.1287 + typedef BfsVisit Create;
1.1288 +
1.1289 + /// \name Named template parameters
1.1290 +
1.1291 + ///@{
1.1292 + template <class T>
1.1293 + struct DefReachedMapTraits : public Traits {
1.1294 + typedef T ReachedMap;
1.1295 + static ReachedMap *createReachedMap(const Digraph &digraph) {
1.1296 + throw UninitializedParameter();
1.1297 + }
1.1298 + };
1.1299 + /// \brief \ref named-templ-param "Named parameter" for setting
1.1300 + /// ReachedMap type
1.1301 + ///
1.1302 + /// \ref named-templ-param "Named parameter" for setting ReachedMap type
1.1303 + template <class T>
1.1304 + struct DefReachedMap : public BfsVisit< Digraph, Visitor,
1.1305 + DefReachedMapTraits<T> > {
1.1306 + typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
1.1307 + };
1.1308 + ///@}
1.1309 +
1.1310 + public:
1.1311 +
1.1312 + /// \brief Constructor.
1.1313 + ///
1.1314 + /// Constructor.
1.1315 + ///
1.1316 + /// \param digraph the digraph the algorithm will run on.
1.1317 + /// \param visitor The visitor of the algorithm.
1.1318 + ///
1.1319 + BfsVisit(const Digraph& digraph, Visitor& visitor)
1.1320 + : _digraph(&digraph), _visitor(&visitor),
1.1321 + _reached(0), local_reached(false) {}
1.1322 +
1.1323 + /// \brief Destructor.
1.1324 + ///
1.1325 + /// Destructor.
1.1326 + ~BfsVisit() {
1.1327 + if(local_reached) delete _reached;
1.1328 + }
1.1329 +
1.1330 + /// \brief Sets the map indicating if a node is reached.
1.1331 + ///
1.1332 + /// Sets the map indicating if a node is reached.
1.1333 + /// If you don't use this function before calling \ref run(),
1.1334 + /// it will allocate one. The destuctor deallocates this
1.1335 + /// automatically allocated map, of course.
1.1336 + /// \return <tt> (*this) </tt>
1.1337 + BfsVisit &reachedMap(ReachedMap &m) {
1.1338 + if(local_reached) {
1.1339 + delete _reached;
1.1340 + local_reached = false;
1.1341 + }
1.1342 + _reached = &m;
1.1343 + return *this;
1.1344 + }
1.1345 +
1.1346 + public:
1.1347 + /// \name Execution control
1.1348 + /// The simplest way to execute the algorithm is to use
1.1349 + /// one of the member functions called \c run(...).
1.1350 + /// \n
1.1351 + /// If you need more control on the execution,
1.1352 + /// first you must call \ref init(), then you can adda source node
1.1353 + /// with \ref addSource().
1.1354 + /// Finally \ref start() will perform the actual path
1.1355 + /// computation.
1.1356 +
1.1357 + /// @{
1.1358 + /// \brief Initializes the internal data structures.
1.1359 + ///
1.1360 + /// Initializes the internal data structures.
1.1361 + ///
1.1362 + void init() {
1.1363 + create_maps();
1.1364 + _list.resize(countNodes(*_digraph));
1.1365 + _list_front = _list_back = -1;
1.1366 + for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
1.1367 + _reached->set(u, false);
1.1368 + }
1.1369 + }
1.1370 +
1.1371 + /// \brief Adds a new source node.
1.1372 + ///
1.1373 + /// Adds a new source node to the set of nodes to be processed.
1.1374 + void addSource(Node s) {
1.1375 + if(!(*_reached)[s]) {
1.1376 + _reached->set(s,true);
1.1377 + _visitor->start(s);
1.1378 + _visitor->reach(s);
1.1379 + _list[++_list_back] = s;
1.1380 + }
1.1381 + }
1.1382 +
1.1383 + /// \brief Processes the next node.
1.1384 + ///
1.1385 + /// Processes the next node.
1.1386 + ///
1.1387 + /// \return The processed node.
1.1388 + ///
1.1389 + /// \pre The queue must not be empty!
1.1390 + Node processNextNode() {
1.1391 + Node n = _list[++_list_front];
1.1392 + _visitor->process(n);
1.1393 + Arc e;
1.1394 + for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
1.1395 + Node m = _digraph->target(e);
1.1396 + if (!(*_reached)[m]) {
1.1397 + _visitor->discover(e);
1.1398 + _visitor->reach(m);
1.1399 + _reached->set(m, true);
1.1400 + _list[++_list_back] = m;
1.1401 + } else {
1.1402 + _visitor->examine(e);
1.1403 + }
1.1404 + }
1.1405 + return n;
1.1406 + }
1.1407 +
1.1408 + /// \brief Processes the next node.
1.1409 + ///
1.1410 + /// Processes the next node. And checks that the given target node
1.1411 + /// is reached. If the target node is reachable from the processed
1.1412 + /// node then the reached parameter will be set true. The reached
1.1413 + /// parameter should be initially false.
1.1414 + ///
1.1415 + /// \param target The target node.
1.1416 + /// \retval reach Indicates that the target node is reached.
1.1417 + /// \return The processed node.
1.1418 + ///
1.1419 + /// \warning The queue must not be empty!
1.1420 + Node processNextNode(Node target, bool& reach) {
1.1421 + Node n = _list[++_list_front];
1.1422 + _visitor->process(n);
1.1423 + Arc e;
1.1424 + for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
1.1425 + Node m = _digraph->target(e);
1.1426 + if (!(*_reached)[m]) {
1.1427 + _visitor->discover(e);
1.1428 + _visitor->reach(m);
1.1429 + _reached->set(m, true);
1.1430 + _list[++_list_back] = m;
1.1431 + reach = reach || (target == m);
1.1432 + } else {
1.1433 + _visitor->examine(e);
1.1434 + }
1.1435 + }
1.1436 + return n;
1.1437 + }
1.1438 +
1.1439 + /// \brief Processes the next node.
1.1440 + ///
1.1441 + /// Processes the next node. And checks that at least one of
1.1442 + /// reached node has true value in the \c nm node map. If one node
1.1443 + /// with true value is reachable from the processed node then the
1.1444 + /// rnode parameter will be set to the first of such nodes.
1.1445 + ///
1.1446 + /// \param nm The node map of possible targets.
1.1447 + /// \retval rnode The reached target node.
1.1448 + /// \return The processed node.
1.1449 + ///
1.1450 + /// \warning The queue must not be empty!
1.1451 + template <typename NM>
1.1452 + Node processNextNode(const NM& nm, Node& rnode) {
1.1453 + Node n = _list[++_list_front];
1.1454 + _visitor->process(n);
1.1455 + Arc e;
1.1456 + for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
1.1457 + Node m = _digraph->target(e);
1.1458 + if (!(*_reached)[m]) {
1.1459 + _visitor->discover(e);
1.1460 + _visitor->reach(m);
1.1461 + _reached->set(m, true);
1.1462 + _list[++_list_back] = m;
1.1463 + if (nm[m] && rnode == INVALID) rnode = m;
1.1464 + } else {
1.1465 + _visitor->examine(e);
1.1466 + }
1.1467 + }
1.1468 + return n;
1.1469 + }
1.1470 +
1.1471 + /// \brief Next node to be processed.
1.1472 + ///
1.1473 + /// Next node to be processed.
1.1474 + ///
1.1475 + /// \return The next node to be processed or INVALID if the stack is
1.1476 + /// empty.
1.1477 + Node nextNode() {
1.1478 + return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
1.1479 + }
1.1480 +
1.1481 + /// \brief Returns \c false if there are nodes
1.1482 + /// to be processed in the queue
1.1483 + ///
1.1484 + /// Returns \c false if there are nodes
1.1485 + /// to be processed in the queue
1.1486 + bool emptyQueue() { return _list_front == _list_back; }
1.1487 +
1.1488 + /// \brief Returns the number of the nodes to be processed.
1.1489 + ///
1.1490 + /// Returns the number of the nodes to be processed in the queue.
1.1491 + int queueSize() { return _list_back - _list_front; }
1.1492 +
1.1493 + /// \brief Executes the algorithm.
1.1494 + ///
1.1495 + /// Executes the algorithm.
1.1496 + ///
1.1497 + /// \pre init() must be called and at least one node should be added
1.1498 + /// with addSource() before using this function.
1.1499 + void start() {
1.1500 + while ( !emptyQueue() ) processNextNode();
1.1501 + }
1.1502 +
1.1503 + /// \brief Executes the algorithm until \c dest is reached.
1.1504 + ///
1.1505 + /// Executes the algorithm until \c dest is reached.
1.1506 + ///
1.1507 + /// \pre init() must be called and at least one node should be added
1.1508 + /// with addSource() before using this function.
1.1509 + void start(Node dest) {
1.1510 + bool reach = false;
1.1511 + while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
1.1512 + }
1.1513 +
1.1514 + /// \brief Executes the algorithm until a condition is met.
1.1515 + ///
1.1516 + /// Executes the algorithm until a condition is met.
1.1517 + ///
1.1518 + /// \pre init() must be called and at least one node should be added
1.1519 + /// with addSource() before using this function.
1.1520 + ///
1.1521 + ///\param nm must be a bool (or convertible) node map. The
1.1522 + ///algorithm will stop when it reaches a node \c v with
1.1523 + /// <tt>nm[v]</tt> true.
1.1524 + ///
1.1525 + ///\return The reached node \c v with <tt>nm[v]</tt> true or
1.1526 + ///\c INVALID if no such node was found.
1.1527 + template <typename NM>
1.1528 + Node start(const NM &nm) {
1.1529 + Node rnode = INVALID;
1.1530 + while ( !emptyQueue() && rnode == INVALID ) {
1.1531 + processNextNode(nm, rnode);
1.1532 + }
1.1533 + return rnode;
1.1534 + }
1.1535 +
1.1536 + /// \brief Runs %BFSVisit algorithm from node \c s.
1.1537 + ///
1.1538 + /// This method runs the %BFS algorithm from a root node \c s.
1.1539 + /// \note b.run(s) is just a shortcut of the following code.
1.1540 + ///\code
1.1541 + /// b.init();
1.1542 + /// b.addSource(s);
1.1543 + /// b.start();
1.1544 + ///\endcode
1.1545 + void run(Node s) {
1.1546 + init();
1.1547 + addSource(s);
1.1548 + start();
1.1549 + }
1.1550 +
1.1551 + /// \brief Runs %BFSVisit algorithm to visit all nodes in the digraph.
1.1552 + ///
1.1553 + /// This method runs the %BFS algorithm in order to
1.1554 + /// compute the %BFS path to each node. The algorithm computes
1.1555 + /// - The %BFS tree.
1.1556 + /// - The distance of each node from the root in the %BFS tree.
1.1557 + ///
1.1558 + ///\note b.run() is just a shortcut of the following code.
1.1559 + ///\code
1.1560 + /// b.init();
1.1561 + /// for (NodeIt it(digraph); it != INVALID; ++it) {
1.1562 + /// if (!b.reached(it)) {
1.1563 + /// b.addSource(it);
1.1564 + /// b.start();
1.1565 + /// }
1.1566 + /// }
1.1567 + ///\endcode
1.1568 + void run() {
1.1569 + init();
1.1570 + for (NodeIt it(*_digraph); it != INVALID; ++it) {
1.1571 + if (!reached(it)) {
1.1572 + addSource(it);
1.1573 + start();
1.1574 + }
1.1575 + }
1.1576 + }
1.1577 + ///@}
1.1578 +
1.1579 + /// \name Query Functions
1.1580 + /// The result of the %BFS algorithm can be obtained using these
1.1581 + /// functions.\n
1.1582 + /// Before the use of these functions,
1.1583 + /// either run() or start() must be called.
1.1584 + ///@{
1.1585 +
1.1586 + /// \brief Checks if a node is reachable from the root.
1.1587 + ///
1.1588 + /// Returns \c true if \c v is reachable from the root(s).
1.1589 + /// \warning The source nodes are inditated as unreachable.
1.1590 + /// \pre Either \ref run() or \ref start()
1.1591 + /// must be called before using this function.
1.1592 + ///
1.1593 + bool reached(Node v) { return (*_reached)[v]; }
1.1594 + ///@}
1.1595 + };
1.1596 +
1.1597 +} //END OF NAMESPACE LEMON
1.1598 +
1.1599 +#endif
1.1600 +