1.1 --- a/lemon/bfs.h Tue Nov 21 17:28:08 2006 +0000
1.2 +++ b/lemon/bfs.h Tue Nov 21 18:22:08 2006 +0000
1.3 @@ -587,9 +587,9 @@
1.4 while ( !emptyQueue() ) processNextNode();
1.5 }
1.6
1.7 - ///Executes the algorithm until \c dest is reached.
1.8 + ///Executes the algorithm until \c dest is the next node to processed.
1.9
1.10 - ///Executes the algorithm until \c dest is reached.
1.11 + ///Executes the algorithm until \c dest is the next node to processed.
1.12 ///
1.13 ///\pre init() must be called and at least one node should be added
1.14 ///with addSource() before using this function.
1.15 @@ -614,8 +614,9 @@
1.16 ///\pre init() must be called and at least one node should be added
1.17 ///with addSource() before using this function.
1.18 ///
1.19 - ///\param nm must be a bool (or convertible) node map. The algorithm
1.20 - ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
1.21 + ///\param nm must be a bool (or convertible) node map. The
1.22 + ///algorithm will stop when for the next processable node \c v is
1.23 + ///<tt>nm[v]</tt> true.
1.24 ///\todo query the reached target
1.25 template<class NM>
1.26 void start(const NM &nm)
1.27 @@ -633,11 +634,11 @@
1.28 ///- The shortest path tree.
1.29 ///- The distance of each node from the root.
1.30 ///
1.31 - ///\note d.run(s) is just a shortcut of the following code.
1.32 + ///\note b.run(s) is just a shortcut of the following code.
1.33 ///\code
1.34 - /// d.init();
1.35 - /// d.addSource(s);
1.36 - /// d.start();
1.37 + /// b.init();
1.38 + /// b.addSource(s);
1.39 + /// b.start();
1.40 ///\endcode
1.41 void run(Node s) {
1.42 init();
1.43 @@ -651,12 +652,12 @@
1.44 ///
1.45 ///\return The length of the shortest s---t path if there exists one,
1.46 ///0 otherwise.
1.47 - ///\note Apart from the return value, d.run(s) is
1.48 + ///\note Apart from the return value, b.run(s) is
1.49 ///just a shortcut of the following code.
1.50 ///\code
1.51 - /// d.init();
1.52 - /// d.addSource(s);
1.53 - /// d.start(t);
1.54 + /// b.init();
1.55 + /// b.addSource(s);
1.56 + /// b.start(t);
1.57 ///\endcode
1.58 int run(Node s,Node t) {
1.59 init();
1.60 @@ -671,7 +672,7 @@
1.61 ///The result of the %BFS algorithm can be obtained using these
1.62 ///functions.\n
1.63 ///Before the use of these functions,
1.64 - ///either run() or start() must be called.
1.65 + ///either run() or start() must be calleb.
1.66
1.67 ///@{
1.68
1.69 @@ -943,7 +944,7 @@
1.70 ///The type of the map that stores the dists of the nodes.
1.71 typedef typename TR::DistMap DistMap;
1.72
1.73 -public:
1.74 + public:
1.75 /// Constructor.
1.76 BfsWizard() : TR() {}
1.77
1.78 @@ -1104,6 +1105,495 @@
1.79 return BfsWizard<BfsWizardBase<GR> >(g,s);
1.80 }
1.81
1.82 +#ifdef DOXYGEN
1.83 + /// \brief Visitor class for bfs.
1.84 + ///
1.85 + /// It gives a simple interface for a functional interface for bfs
1.86 + /// traversal. The traversal on a linear data structure.
1.87 + template <typename _Graph>
1.88 + struct BfsVisitor {
1.89 + typedef _Graph Graph;
1.90 + typedef typename Graph::Edge Edge;
1.91 + typedef typename Graph::Node Node;
1.92 + /// \brief Called when the edge reach a node.
1.93 + ///
1.94 + /// It is called when the bfs find an edge which target is not
1.95 + /// reached yet.
1.96 + void discover(const Edge& edge) {}
1.97 + /// \brief Called when the node reached first time.
1.98 + ///
1.99 + /// It is Called when the node reached first time.
1.100 + void reach(const Node& node) {}
1.101 + /// \brief Called when the edge examined but target of the edge
1.102 + /// already discovered.
1.103 + ///
1.104 + /// It called when the edge examined but the target of the edge
1.105 + /// already discovered.
1.106 + void examine(const Edge& edge) {}
1.107 + /// \brief Called for the source node of the bfs.
1.108 + ///
1.109 + /// It is called for the source node of the bfs.
1.110 + void start(const Node& node) {}
1.111 + /// \brief Called when the node processed.
1.112 + ///
1.113 + /// It is Called when the node processed.
1.114 + void process(const Node& node) {}
1.115 + };
1.116 +#else
1.117 + template <typename _Graph>
1.118 + struct BfsVisitor {
1.119 + typedef _Graph Graph;
1.120 + typedef typename Graph::Edge Edge;
1.121 + typedef typename Graph::Node Node;
1.122 + void discover(const Edge&) {}
1.123 + void reach(const Node&) {}
1.124 + void examine(const Edge&) {}
1.125 + void start(const Node&) {}
1.126 + void process(const Node&) {}
1.127 +
1.128 + template <typename _Visitor>
1.129 + struct Constraints {
1.130 + void constraints() {
1.131 + Edge edge;
1.132 + Node node;
1.133 + visitor.discover(edge);
1.134 + visitor.reach(node);
1.135 + visitor.examine(edge);
1.136 + visitor.start(node);
1.137 + visitor.process(node);
1.138 + }
1.139 + _Visitor& visitor;
1.140 + };
1.141 + };
1.142 +#endif
1.143 +
1.144 + /// \brief Default traits class of BfsVisit class.
1.145 + ///
1.146 + /// Default traits class of BfsVisit class.
1.147 + /// \param _Graph Graph type.
1.148 + template<class _Graph>
1.149 + struct BfsVisitDefaultTraits {
1.150 +
1.151 + /// \brief The graph type the algorithm runs on.
1.152 + typedef _Graph Graph;
1.153 +
1.154 + /// \brief The type of the map that indicates which nodes are reached.
1.155 + ///
1.156 + /// The type of the map that indicates which nodes are reached.
1.157 + /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
1.158 + /// \todo named parameter to set this type, function to read and write.
1.159 + typedef typename Graph::template NodeMap<bool> ReachedMap;
1.160 +
1.161 + /// \brief Instantiates a ReachedMap.
1.162 + ///
1.163 + /// This function instantiates a \ref ReachedMap.
1.164 + /// \param graph is the graph, to which
1.165 + /// we would like to define the \ref ReachedMap.
1.166 + static ReachedMap *createReachedMap(const Graph &graph) {
1.167 + return new ReachedMap(graph);
1.168 + }
1.169 +
1.170 + };
1.171 +
1.172 + /// %BFS Visit algorithm class.
1.173 +
1.174 + /// \ingroup flowalgs
1.175 + /// This class provides an efficient implementation of the %BFS algorithm
1.176 + /// with visitor interface.
1.177 + ///
1.178 + /// The %BfsVisit class provides an alternative interface to the Bfs
1.179 + /// class. It works with callback mechanism, the BfsVisit object calls
1.180 + /// on every bfs event the \c Visitor class member functions.
1.181 + ///
1.182 + /// \param _Graph The graph type the algorithm runs on. The default value is
1.183 + /// \ref ListGraph. The value of _Graph is not used directly by Bfs, it
1.184 + /// is only passed to \ref BfsDefaultTraits.
1.185 + /// \param _Visitor The Visitor object for the algorithm. The
1.186 + /// \ref BfsVisitor "BfsVisitor<_Graph>" is an empty Visitor which
1.187 + /// does not observe the Bfs events. If you want to observe the bfs
1.188 + /// events you should implement your own Visitor class.
1.189 + /// \param _Traits Traits class to set various data types used by the
1.190 + /// algorithm. The default traits class is
1.191 + /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Graph>".
1.192 + /// See \ref BfsVisitDefaultTraits for the documentation of
1.193 + /// a Bfs visit traits class.
1.194 + ///
1.195 + /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
1.196 +#ifdef DOXYGEN
1.197 + template <typename _Graph, typename _Visitor, typename _Traits>
1.198 +#else
1.199 + template <typename _Graph = ListGraph,
1.200 + typename _Visitor = BfsVisitor<_Graph>,
1.201 + typename _Traits = BfsDefaultTraits<_Graph> >
1.202 +#endif
1.203 + class BfsVisit {
1.204 + public:
1.205 +
1.206 + /// \brief \ref Exception for uninitialized parameters.
1.207 + ///
1.208 + /// This error represents problems in the initialization
1.209 + /// of the parameters of the algorithms.
1.210 + class UninitializedParameter : public lemon::UninitializedParameter {
1.211 + public:
1.212 + virtual const char* what() const throw()
1.213 + {
1.214 + return "lemon::BfsVisit::UninitializedParameter";
1.215 + }
1.216 + };
1.217 +
1.218 + typedef _Traits Traits;
1.219 +
1.220 + typedef typename Traits::Graph Graph;
1.221 +
1.222 + typedef _Visitor Visitor;
1.223 +
1.224 + ///The type of the map indicating which nodes are reached.
1.225 + typedef typename Traits::ReachedMap ReachedMap;
1.226 +
1.227 + private:
1.228 +
1.229 + typedef typename Graph::Node Node;
1.230 + typedef typename Graph::NodeIt NodeIt;
1.231 + typedef typename Graph::Edge Edge;
1.232 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.233 +
1.234 + /// Pointer to the underlying graph.
1.235 + const Graph *_graph;
1.236 + /// Pointer to the visitor object.
1.237 + Visitor *_visitor;
1.238 + ///Pointer to the map of reached status of the nodes.
1.239 + ReachedMap *_reached;
1.240 + ///Indicates if \ref _reached is locally allocated (\c true) or not.
1.241 + bool local_reached;
1.242 +
1.243 + std::vector<typename Graph::Node> _list;
1.244 + int _list_front, _list_back;
1.245 +
1.246 + /// \brief Creates the maps if necessary.
1.247 + ///
1.248 + /// Creates the maps if necessary.
1.249 + void create_maps() {
1.250 + if(!_reached) {
1.251 + local_reached = true;
1.252 + _reached = Traits::createReachedMap(*_graph);
1.253 + }
1.254 + }
1.255 +
1.256 + protected:
1.257 +
1.258 + BfsVisit() {}
1.259 +
1.260 + public:
1.261 +
1.262 + typedef BfsVisit Create;
1.263 +
1.264 + /// \name Named template parameters
1.265 +
1.266 + ///@{
1.267 + template <class T>
1.268 + struct DefReachedMapTraits : public Traits {
1.269 + typedef T ReachedMap;
1.270 + static ReachedMap *createReachedMap(const Graph &graph) {
1.271 + throw UninitializedParameter();
1.272 + }
1.273 + };
1.274 + /// \brief \ref named-templ-param "Named parameter" for setting
1.275 + /// ReachedMap type
1.276 + ///
1.277 + /// \ref named-templ-param "Named parameter" for setting ReachedMap type
1.278 + template <class T>
1.279 + struct DefReachedMap : public BfsVisit< Graph, Visitor,
1.280 + DefReachedMapTraits<T> > {
1.281 + typedef BfsVisit< Graph, Visitor, DefReachedMapTraits<T> > Create;
1.282 + };
1.283 + ///@}
1.284 +
1.285 + public:
1.286 +
1.287 + /// \brief Constructor.
1.288 + ///
1.289 + /// Constructor.
1.290 + ///
1.291 + /// \param graph the graph the algorithm will run on.
1.292 + /// \param visitor The visitor of the algorithm.
1.293 + ///
1.294 + BfsVisit(const Graph& graph, Visitor& visitor)
1.295 + : _graph(&graph), _visitor(&visitor),
1.296 + _reached(0), local_reached(false) {}
1.297 +
1.298 + /// \brief Destructor.
1.299 + ///
1.300 + /// Destructor.
1.301 + ~BfsVisit() {
1.302 + if(local_reached) delete _reached;
1.303 + }
1.304 +
1.305 + /// \brief Sets the map indicating if a node is reached.
1.306 + ///
1.307 + /// Sets the map indicating if a node is reached.
1.308 + /// If you don't use this function before calling \ref run(),
1.309 + /// it will allocate one. The destuctor deallocates this
1.310 + /// automatically allocated map, of course.
1.311 + /// \return <tt> (*this) </tt>
1.312 + BfsVisit &reachedMap(ReachedMap &m) {
1.313 + if(local_reached) {
1.314 + delete _reached;
1.315 + local_reached = false;
1.316 + }
1.317 + _reached = &m;
1.318 + return *this;
1.319 + }
1.320 +
1.321 + public:
1.322 + /// \name Execution control
1.323 + /// The simplest way to execute the algorithm is to use
1.324 + /// one of the member functions called \c run(...).
1.325 + /// \n
1.326 + /// If you need more control on the execution,
1.327 + /// first you must call \ref init(), then you can adda source node
1.328 + /// with \ref addSource().
1.329 + /// Finally \ref start() will perform the actual path
1.330 + /// computation.
1.331 +
1.332 + /// @{
1.333 + /// \brief Initializes the internal data structures.
1.334 + ///
1.335 + /// Initializes the internal data structures.
1.336 + ///
1.337 + void init() {
1.338 + create_maps();
1.339 + _list.resize(countNodes(*_graph));
1.340 + _list_front = _list_back = -1;
1.341 + for (NodeIt u(*_graph) ; u != INVALID ; ++u) {
1.342 + _reached->set(u, false);
1.343 + }
1.344 + }
1.345 +
1.346 + /// \brief Adds a new source node.
1.347 + ///
1.348 + /// Adds a new source node to the set of nodes to be processed.
1.349 + void addSource(Node s) {
1.350 + if(!(*_reached)[s]) {
1.351 + _reached->set(s,true);
1.352 + _visitor->start(s);
1.353 + _visitor->reach(s);
1.354 + _list[++_list_back] = s;
1.355 + }
1.356 + }
1.357 +
1.358 + /// \brief Processes the next node.
1.359 + ///
1.360 + /// Processes the next node.
1.361 + ///
1.362 + /// \return The processed node.
1.363 + ///
1.364 + /// \pre The queue must not be empty!
1.365 + Node processNextNode() {
1.366 + Node n = _list[++_list_front];
1.367 + _visitor->process(n);
1.368 + Edge e;
1.369 + for (_graph->firstOut(e, n); e != INVALID; _graph->nextOut(e)) {
1.370 + Node m = _graph->target(e);
1.371 + if (!(*_reached)[m]) {
1.372 + _visitor->discover(e);
1.373 + _visitor->reach(m);
1.374 + _reached->set(m, true);
1.375 + _list[++_list_back] = m;
1.376 + } else {
1.377 + _visitor->examine(e);
1.378 + }
1.379 + }
1.380 + return n;
1.381 + }
1.382 +
1.383 + /// \brief Processes the next node.
1.384 + ///
1.385 + /// Processes the next node. And checks that the given target node
1.386 + /// is reached. If the target node is reachable from the processed
1.387 + /// node then the reached parameter will be set true. The reached
1.388 + /// parameter should be initially false.
1.389 + ///
1.390 + /// \param target The target node.
1.391 + /// \retval reached Indicates that the target node is reached.
1.392 + /// \return The processed node.
1.393 + ///
1.394 + /// \warning The queue must not be empty!
1.395 + Node processNextNode(Node target, bool& reached) {
1.396 + Node n = _list[++_list_front];
1.397 + _visitor->process(n);
1.398 + Edge e;
1.399 + for (_graph->firstOut(e, n); e != INVALID; _graph->nextOut(e)) {
1.400 + Node m = _graph->target(e);
1.401 + if (!(*_reached)[m]) {
1.402 + _visitor->discover(e);
1.403 + _visitor->reach(m);
1.404 + _reached->set(m, true);
1.405 + _list[++_list_back] = m;
1.406 + reached = reached || (target == m);
1.407 + } else {
1.408 + _visitor->examine(e);
1.409 + }
1.410 + }
1.411 + return n;
1.412 + }
1.413 +
1.414 + /// \brief Processes the next node.
1.415 + ///
1.416 + /// Processes the next node. And checks that at least one of
1.417 + /// reached node has true value in the \c nm nodemap. If one node
1.418 + /// with true value is reachable from the processed node then the
1.419 + /// reached parameter will be set true. The reached parameter
1.420 + /// should be initially false.
1.421 + ///
1.422 + /// \param target The nodemaps of possible targets.
1.423 + /// \retval reached Indicates that one of the target nodes is reached.
1.424 + /// \return The processed node.
1.425 + ///
1.426 + /// \warning The queue must not be empty!
1.427 + template <typename NM>
1.428 + Node processNextNode(const NM& nm, bool& reached) {
1.429 + Node n = _list[++_list_front];
1.430 + _visitor->process(n);
1.431 + Edge e;
1.432 + for (_graph->firstOut(e, n); e != INVALID; _graph->nextOut(e)) {
1.433 + Node m = _graph->target(e);
1.434 + if (!(*_reached)[m]) {
1.435 + _visitor->discover(e);
1.436 + _visitor->reach(m);
1.437 + _reached->set(m, true);
1.438 + _list[++_list_back] = m;
1.439 + reached = reached || nm[m];
1.440 + } else {
1.441 + _visitor->examine(e);
1.442 + }
1.443 + }
1.444 + return n;
1.445 + }
1.446 +
1.447 + /// \brief Next node to be processed.
1.448 + ///
1.449 + /// Next node to be processed.
1.450 + ///
1.451 + /// \return The next node to be processed or INVALID if the stack is
1.452 + /// empty.
1.453 + Node nextNode() {
1.454 + return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
1.455 + }
1.456 +
1.457 + /// \brief Returns \c false if there are nodes
1.458 + /// to be processed in the queue
1.459 + ///
1.460 + /// Returns \c false if there are nodes
1.461 + /// to be processed in the queue
1.462 + bool emptyQueue() { return _list_front == _list_back; }
1.463 +
1.464 + /// \brief Returns the number of the nodes to be processed.
1.465 + ///
1.466 + /// Returns the number of the nodes to be processed in the queue.
1.467 + int queueSize() { return _list_back - _list_front; }
1.468 +
1.469 + /// \brief Executes the algorithm.
1.470 + ///
1.471 + /// Executes the algorithm.
1.472 + ///
1.473 + /// \pre init() must be called and at least one node should be added
1.474 + /// with addSource() before using this function.
1.475 + void start() {
1.476 + while ( !emptyQueue() ) processNextNode();
1.477 + }
1.478 +
1.479 + /// \brief Executes the algorithm until \c dest will be next processed.
1.480 + ///
1.481 + /// Executes the algorithm until \c dest will be next processed.
1.482 + ///
1.483 + /// \pre init() must be called and at least one node should be added
1.484 + /// with addSource() before using this function.
1.485 + void start(Node dest) {
1.486 + bool reached = false;
1.487 + while (!emptyQueue() && !reached) {
1.488 + processNextNode(dest, reached);
1.489 + }
1.490 + }
1.491 +
1.492 + /// \brief Executes the algorithm until a condition is met.
1.493 + ///
1.494 + /// Executes the algorithm until a condition is met.
1.495 + ///
1.496 + /// \pre init() must be called and at least one node should be added
1.497 + /// with addSource() before using this function.
1.498 + ///
1.499 + ///\param nm must be a bool (or convertible) node map. The
1.500 + ///algorithm will stop when it reaches a node \c v with
1.501 + ///<tt>nm[v]</tt> true.
1.502 + template <typename NM>
1.503 + void start(const NM &nm) {
1.504 + bool reached = false;
1.505 + while (!emptyQueue() && !reached) {
1.506 + processNextNode(nm, reached);
1.507 + }
1.508 + }
1.509 +
1.510 + /// \brief Runs %BFSVisit algorithm from node \c s.
1.511 + ///
1.512 + /// This method runs the %BFS algorithm from a root node \c s.
1.513 + /// \note b.run(s) is just a shortcut of the following code.
1.514 + ///\code
1.515 + /// b.init();
1.516 + /// b.addSource(s);
1.517 + /// b.start();
1.518 + ///\endcode
1.519 + void run(Node s) {
1.520 + init();
1.521 + addSource(s);
1.522 + start();
1.523 + }
1.524 +
1.525 + /// \brief Runs %BFSVisit algorithm to visit all nodes in the graph.
1.526 + ///
1.527 + /// This method runs the %BFS algorithm in order to
1.528 + /// compute the %BFS path to each node. The algorithm computes
1.529 + /// - The %BFS tree.
1.530 + /// - The distance of each node from the root in the %BFS tree.
1.531 + ///
1.532 + ///\note b.run() is just a shortcut of the following code.
1.533 + ///\code
1.534 + /// b.init();
1.535 + /// for (NodeIt it(graph); it != INVALID; ++it) {
1.536 + /// if (!b.reached(it)) {
1.537 + /// b.addSource(it);
1.538 + /// b.start();
1.539 + /// }
1.540 + /// }
1.541 + ///\endcode
1.542 + void run() {
1.543 + init();
1.544 + for (NodeIt it(*_graph); it != INVALID; ++it) {
1.545 + if (!reached(it)) {
1.546 + addSource(it);
1.547 + start();
1.548 + }
1.549 + }
1.550 + }
1.551 + ///@}
1.552 +
1.553 + /// \name Query Functions
1.554 + /// The result of the %BFS algorithm can be obtained using these
1.555 + /// functions.\n
1.556 + /// Before the use of these functions,
1.557 + /// either run() or start() must be called.
1.558 + ///@{
1.559 +
1.560 + /// \brief Checks if a node is reachable from the root.
1.561 + ///
1.562 + /// Returns \c true if \c v is reachable from the root(s).
1.563 + /// \warning The source nodes are inditated as unreachable.
1.564 + /// \pre Either \ref run() or \ref start()
1.565 + /// must be called before using this function.
1.566 + ///
1.567 + bool reached(Node v) { return (*_reached)[v]; }
1.568 + ///@}
1.569 + };
1.570 +
1.571 } //END OF NAMESPACE LEMON
1.572
1.573 #endif