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