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