1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci/bfs_mm.h Sat Oct 16 00:20:13 2004 +0000
1.3 @@ -0,0 +1,559 @@
1.4 +// -*- c++ -*-
1.5 +#ifndef LEMON_BFS_DFS_H
1.6 +#define LEMON_BFS_DFS_H
1.7 +
1.8 +/// \ingroup galgs
1.9 +/// \file
1.10 +/// \brief Bfs and dfs iterators.
1.11 +///
1.12 +/// This file contains bfs and dfs iterator classes.
1.13 +///
1.14 +// /// \author Marton Makai
1.15 +
1.16 +#include <queue>
1.17 +#include <stack>
1.18 +#include <utility>
1.19 +
1.20 +#include <lemon/invalid.h>
1.21 +
1.22 +namespace lemon {
1.23 + namespace marci {
1.24 +
1.25 + /// Bfs searches for the nodes wich are not marked in
1.26 + /// \c reached_map
1.27 + /// RM have to be a read-write bool node-map.
1.28 + /// \ingroup galgs
1.29 + template <typename Graph, /*typename OutEdgeIt,*/
1.30 + typename RM/*=typename Graph::NodeMap<bool>*/ >
1.31 + class BfsIterator {
1.32 + public:
1.33 + typedef RM ReachedMap;
1.34 + protected:
1.35 + typedef typename Graph::Node Node;
1.36 + typedef typename Graph::Edge Edge;
1.37 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.38 + const Graph* graph;
1.39 + std::queue<Node> bfs_queue;
1.40 + ReachedMap* reached_map;
1.41 + bool b_node_newly_reached;
1.42 + //OutEdgeIt actual_edge;
1.43 + Edge actual_edge;
1.44 + /// \e
1.45 + BfsIterator(const Graph& _graph) : graph(&_graph), reached_map(0) { }
1.46 + /// RM have to be set before any bfs operation.
1.47 + BfsIterator<Graph, RM>& setReached(RM& _reached_map) {
1.48 + reached_map=&_reached_map;
1.49 + }
1.50 + public:
1.51 + /// In that constructor \c _reached_map have to be a reference
1.52 + /// for a bool bode-map. The algorithm will search for the
1.53 + /// initially \c false nodes
1.54 + /// in a bfs order.
1.55 + BfsIterator(const Graph& _graph, ReachedMap& _reached_map) :
1.56 + graph(&_graph), reached_map(&_reached_map) { }
1.57 + /// The same as above, but the map storing the reached nodes
1.58 + /// is constructed dynamically to everywhere false.
1.59 + /// \deprecated
1.60 +// BfsIterator(const Graph& _graph) :
1.61 +// graph(&_graph), reached_map(new ReachedMap(*graph /*, false*/)),
1.62 +// own_reached_map(true) { }
1.63 +// /// The map storing the reached nodes have to be destroyed if
1.64 +// /// it was constructed dynamically
1.65 +// ~BfsIterator() { if (own_reached_map) delete reached_map; }
1.66 + /// This method markes \c s reached.
1.67 + /// If the queue is empty, then \c s is pushed in the bfs queue
1.68 + /// and the first out-edge is processed.
1.69 + /// If the queue is not empty, then \c s is simply pushed.
1.70 + BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) {
1.71 + reached_map->set(s, true);
1.72 + if (bfs_queue.empty()) {
1.73 + bfs_queue.push(s);
1.74 + actual_edge=OutEdgeIt(*graph, s);
1.75 + //graph->first(actual_edge, s);
1.76 + if (actual_edge!=INVALID) {
1.77 + Node w=graph->head(actual_edge);
1.78 + if (!(*reached_map)[w]) {
1.79 + bfs_queue.push(w);
1.80 + reached_map->set(w, true);
1.81 + b_node_newly_reached=true;
1.82 + } else {
1.83 + b_node_newly_reached=false;
1.84 + }
1.85 + }
1.86 + } else {
1.87 + bfs_queue.push(s);
1.88 + }
1.89 + return *this;
1.90 + }
1.91 + /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator,
1.92 + /// its \c operator++() iterates on the edges in a bfs order.
1.93 + BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
1.94 + operator++() {
1.95 + if (actual_edge!=INVALID) {
1.96 + actual_edge=++OutEdgeIt(*graph, actual_edge);
1.97 + //++actual_edge;
1.98 + if (actual_edge!=INVALID) {
1.99 + Node w=graph->head(actual_edge);
1.100 + if (!(*reached_map)[w]) {
1.101 + bfs_queue.push(w);
1.102 + reached_map->set(w, true);
1.103 + b_node_newly_reached=true;
1.104 + } else {
1.105 + b_node_newly_reached=false;
1.106 + }
1.107 + }
1.108 + } else {
1.109 + bfs_queue.pop();
1.110 + if (!bfs_queue.empty()) {
1.111 + actual_edge=OutEdgeIt(*graph, bfs_queue.front());
1.112 + //graph->first(actual_edge, bfs_queue.front());
1.113 + if (actual_edge!=INVALID) {
1.114 + Node w=graph->head(actual_edge);
1.115 + if (!(*reached_map)[w]) {
1.116 + bfs_queue.push(w);
1.117 + reached_map->set(w, true);
1.118 + b_node_newly_reached=true;
1.119 + } else {
1.120 + b_node_newly_reached=false;
1.121 + }
1.122 + }
1.123 + }
1.124 + }
1.125 + return *this;
1.126 + }
1.127 + /// Returns true iff the algorithm is finished.
1.128 + bool finished() const { return bfs_queue.empty(); }
1.129 + /// The conversion operator makes for converting the bfs-iterator
1.130 + /// to an \c out-edge-iterator.
1.131 + ///\bug Edge have to be in LEMON 0.2
1.132 + operator Edge() const { return actual_edge; }
1.133 + /// Returns if b-node has been reached just now.
1.134 + bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.135 + /// Returns if a-node is examined.
1.136 + bool isANodeExamined() const { return actual_edge==INVALID; }
1.137 + /// Returns a-node of the actual edge, so does if the edge is invalid.
1.138 + Node tail() const { return bfs_queue.front(); }
1.139 + /// \pre The actual edge have to be valid.
1.140 + Node head() const { return graph->head(actual_edge); }
1.141 + /// Guess what?
1.142 + /// \deprecated
1.143 + const ReachedMap& reachedMap() const { return *reached_map; }
1.144 + /// Guess what?
1.145 + /// \deprecated
1.146 + typename ReachedMap::ValueType reached(const Node& n) const {
1.147 + return (*reached_map)[n];
1.148 + }
1.149 + /// Guess what?
1.150 + /// \deprecated
1.151 + const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
1.152 + };
1.153 +
1.154 + /// Bfs searches for the nodes wich are not marked in
1.155 + /// \c reached_map
1.156 + /// RM have to work as a read-write bool Node-map,
1.157 + /// PM is a write edge node-map and
1.158 + /// PNM is a write node node-map and
1.159 + /// DM is a read-write node-map of integral value, have to be.
1.160 + /// \ingroup galgs
1.161 + template <typename Graph,
1.162 + typename RM=typename Graph::template NodeMap<bool>,
1.163 + typename PM
1.164 + =typename Graph::template NodeMap<typename Graph::Edge>,
1.165 + typename PNM
1.166 + =typename Graph::template NodeMap<typename Graph::Node>,
1.167 + typename DM=typename Graph::template NodeMap<int> >
1.168 + class Bfs : public BfsIterator<Graph, RM> {
1.169 + typedef BfsIterator<Graph, RM> Parent;
1.170 + public:
1.171 + typedef RM ReachedMap;
1.172 + typedef PM PredMap;
1.173 + typedef PNM PredNodeMap;
1.174 + typedef DM DistMap;
1.175 + protected:
1.176 + typedef typename Parent::Node Node;
1.177 + PredMap* pred_map;
1.178 + PredNodeMap* pred_node_map;
1.179 + DistMap* dist_map;
1.180 + /// \e
1.181 + Bfs<Graph, RM, PM, PNM, DM>
1.182 + (const Graph& _graph) : BfsIterator<Graph, RM>(_graph) { }
1.183 + /// PM have to be set before any bfs operation.
1.184 + Bfs<Graph, RM, PM, PNM, DM>&
1.185 + setPredMap(PredMap& _pred_map) {
1.186 + pred_map=&_pred_map;
1.187 + }
1.188 + /// PredNodeMap have to be set before any bfs operation.
1.189 + Bfs<Graph, RM, PM, PNM, DM>&
1.190 + setPredNodeMap(PredNodeMap& _pred_node_map) {
1.191 + pred_node_map=&_pred_node_map;
1.192 + }
1.193 + /// DistMap have to be set before any bfs operation.
1.194 + Bfs<Graph, RM, PM, PNM, DM>&
1.195 + setDistMap(DistMap& _dist_map) {
1.196 + dist_map=&_dist_map;
1.197 + }
1.198 + public:
1.199 + /// The algorithm will search in a bfs order for
1.200 + /// the nodes which are \c false initially.
1.201 + /// The constructor makes no initial changes on the maps.
1.202 + Bfs<Graph, RM, PM, PNM, DM>
1.203 + (const Graph& _graph, ReachedMap& _reached_map,
1.204 + PredMap& _pred_map, PredNodeMap& _pred_node_map,
1.205 + DistMap& _dist_map) : BfsIterator<Graph, RM>(_graph, _reached_map),
1.206 + pred_map(&_pred_map), pred_node_map(&_pred_node_map),
1.207 + dist_map(&_dist_map) { }
1.208 + /// \c s is marked to be reached and pushed in the bfs queue.
1.209 + /// If the queue is empty, then the first out-edge is processed.
1.210 + /// If \c s was not marked previously, then
1.211 + /// in addition its pred_map is set to be \c INVALID,
1.212 + /// and dist_map to \c 0.
1.213 + /// if \c s was marked previuosly, then it is simply pushed.
1.214 + Bfs<Graph, RM, PM, PNM, DM>& push(Node s) {
1.215 + if ((*(this->reached_map))[s]) {
1.216 + Parent::pushAndSetReached(s);
1.217 + } else {
1.218 + Parent::pushAndSetReached(s);
1.219 + pred_map->set(s, INVALID);
1.220 + pred_node_map->set(s, INVALID);
1.221 + dist_map->set(s, 0);
1.222 + }
1.223 + return *this;
1.224 + }
1.225 + /// A bfs is processed from \c s.
1.226 + Bfs<Graph, RM, PM, PNM, DM>& run(Node s) {
1.227 + push(s);
1.228 + while (!this->finished()) this->operator++();
1.229 + return *this;
1.230 + }
1.231 + /// Beside the bfs iteration, \c pred_map and \dist_map are saved in a
1.232 + /// newly reached node.
1.233 + Bfs<Graph, RM, PM, PNM, DM>& operator++() {
1.234 + Parent::operator++();
1.235 + if ((this->actual_edge)!=INVALID && this->b_node_newly_reached)
1.236 + {
1.237 + pred_map->set(this->head(), this->actual_edge);
1.238 + pred_node_map->set(this->head(), this->tail());
1.239 + dist_map->set(this->head(), (*dist_map)[this->tail()]);
1.240 + }
1.241 + return *this;
1.242 + }
1.243 + /// Guess what?
1.244 + /// \deprecated
1.245 + const PredMap& predMap() const { return *pred_map; }
1.246 + /// Guess what?
1.247 + /// \deprecated
1.248 + typename PredMap::ValueType pred(const Node& n) const {
1.249 + return (*pred_map)[n];
1.250 + }
1.251 + /// Guess what?
1.252 + /// \deprecated
1.253 + const PredNodeMap& predNodeMap() const { return *pred_node_map; }
1.254 + /// Guess what?
1.255 + /// \deprecated
1.256 + typename PredNodeMap::ValueType predNode(const Node& n) const {
1.257 + return (*pred_node_map)[n];
1.258 + }
1.259 + /// Guess what?
1.260 + /// \deprecated
1.261 + const DistMap& distMap() const { return *dist_map; }
1.262 + /// Guess what?
1.263 + /// \deprecated
1.264 + typename DistMap::ValueType dist(const Node& n) const {
1.265 + return (*dist_map)[n];
1.266 + }
1.267 + };
1.268 +
1.269 +// template <typename Graph,
1.270 +// typename RM=typename Graph::template NodeMap<bool>,
1.271 +// typename PM
1.272 +// =typename Graph::template NodeMap<typename Graph::Edge>,
1.273 +// typename PredNodeMap
1.274 +// =typename Graph::template NodeMap<typename Graph::Node>,
1.275 +// typename DistMap=typename Graph::template NodeMap<int> >
1.276 +// class BfsWizard : public Bfs<Graph> {
1.277 +// public:
1.278 +// typedef Bfs<Graph, PM, PredNodeMap, DistMap> Parent;
1.279 +// protected:
1.280 +// typedef typename Parent::Node Node;
1.281 +// bool own_reached_map;
1.282 +// bool own_pred_map;
1.283 +// bool own_pred_node_map;
1.284 +// bool own_dist_map;
1.285 +
1.286 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
1.287 +// makeRreached() {
1.288 +// own_reached_map=true;
1.289 +// reached=new ReachedMap(*graph, false);
1.290 +// }
1.291 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
1.292 +// deleteReachedMap() {
1.293 +// own_reached_map=false;
1.294 +// delete reached;
1.295 +// }
1.296 +
1.297 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
1.298 +// makePM() {
1.299 +// own_pred_map=true;
1.300 +// pred_map=new PM(*graph, INVALID);
1.301 +// }
1.302 +// BfsWizard<Graph, ReachedMap, PM, PredNodeMap, DistMap>&
1.303 +// deletePM() {
1.304 +// own_pred_map=false;
1.305 +// delete pred_map;
1.306 +// }
1.307 +
1.308 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
1.309 +// makePredNodeMap() {
1.310 +// own_pred_node_map=true;
1.311 +// pred_node_map=new PredNodeMap(*graph, INVALID);
1.312 +// }
1.313 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
1.314 +// deletePredNodeMap() {
1.315 +// own_pred_node_map=false;
1.316 +// delete pred_node_map;
1.317 +// }
1.318 +
1.319 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
1.320 +// makeDistMap() {
1.321 +// own_dist_map=true;
1.322 +// dist_map=new DistMap(*graph, 0);
1.323 +// }
1.324 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
1.325 +// deleteDistMap() {
1.326 +// own_dist_map=false;
1.327 +// delete dist_map;
1.328 +// }
1.329 +
1.330 +// public:
1.331 +// /// User friendly Bfs class.
1.332 +// /// The maps which are not explicitly given by the user are
1.333 +// /// constructed with false, INVALID, INVALID and 0 values.
1.334 +// /// For the user defined maps, the values are not modified, and
1.335 +// /// the bfs is processed without any preset on maps. Therefore,
1.336 +// /// the bfs will search only the nodes which are set false previously
1.337 +// /// in reached, and in the nodes wich are not newly reached by the
1.338 +// /// search, the map values are not modified.
1.339 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>
1.340 +// (const Graph& _graph) :
1.341 +// own_reached_map(false),
1.342 +// own_pred_map(false),
1.343 +// own_pred_node_map(false),
1.344 +// own_dist_map(false) {
1.345 +// }
1.346 +
1.347 +// /// \e
1.348 +// ~BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>() {
1.349 +// if (own_reached_map) deleteReachedMap();
1.350 +// if (own_pred_map) deletePM();
1.351 +// if (own_pred_node_map) deletePredNodeMap();
1.352 +// if (own_dist_map) deleteDistMap();
1.353 +// }
1.354 +
1.355 +// /// \e
1.356 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
1.357 +// setReachedMap(ReachedMap& _reached) {
1.358 +// if (own_reached_map) deleteReachedMap();
1.359 +// Parent::setReachedMap(_reached);
1.360 +// }
1.361 +// /// \e
1.362 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
1.363 +// setPM(PM& _pred) {
1.364 +// if (own_pred_map) deletePM();
1.365 +// Parent::setPM(_pred);
1.366 +// }
1.367 +// /// \e
1.368 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
1.369 +// setPredNodeMap(PredNodeMap& _pred_node) {
1.370 +// if (own_pred_node_map) deletePredNodeMap();
1.371 +// Parent::setPredNodeMap(_pred_node);
1.372 +// }
1.373 +// /// \e
1.374 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
1.375 +// setDistMap(DistMap& _dist) {
1.376 +// if (own_dist_map) deleteDistMap();
1.377 +// Parent::setDistMap(_dist);
1.378 +// }
1.379 +
1.380 +// /// \e
1.381 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
1.382 +// push(Node s) {
1.383 +// if (!reached) makeReachedMap();
1.384 +// if (!pred_map) makePMMap();
1.385 +// if (!pred_node_map) makePredNodeMap();
1.386 +// if (!dist_map) makeDistMap();
1.387 +// push(s);
1.388 +// return *this;
1.389 +// }
1.390 +
1.391 +// /// \e
1.392 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
1.393 +// operator++() {
1.394 +// if (!reached) makeRM();
1.395 +// if (!pred_map) makePMMap();
1.396 +// if (!pred_node_map) makePredNodeMap();
1.397 +// if (!dist_map) makeDistMap();
1.398 +// ++(*this);
1.399 +// return *this;
1.400 +// }
1.401 +
1.402 +// /// \e
1.403 +// BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>&
1.404 +// run(Node s) {
1.405 +// if (!reached) makeRM();
1.406 +// if (!pred_map) makePMMap();
1.407 +// if (!pred_node_map) makePredNodeMap();
1.408 +// if (!dist_map) makeDistMap();
1.409 +// run(s);
1.410 +// return *this;
1.411 +// }
1.412 +
1.413 +// };
1.414 +
1.415 +
1.416 + /// Dfs searches for the nodes wich are not marked in
1.417 + /// \c reached_map
1.418 + /// Reached have to be a read-write bool Node-map.
1.419 + /// \ingroup galgs
1.420 + template <typename Graph, /*typename OutEdgeIt,*/
1.421 + typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
1.422 + class DfsIterator {
1.423 + protected:
1.424 + typedef typename Graph::Node Node;
1.425 + typedef typename Graph::Edge Edge;
1.426 + typedef typename Graph::OutEdgeIt OutEdgeIt;
1.427 + const Graph* graph;
1.428 + std::stack<OutEdgeIt> dfs_stack;
1.429 + bool b_node_newly_reached;
1.430 + Edge actual_edge;
1.431 + Node actual_node;
1.432 + ReachedMap& reached;
1.433 + bool own_reached_map;
1.434 + public:
1.435 + /// In that constructor \c _reached have to be a reference
1.436 + /// for a bool node-map. The algorithm will search in a dfs order for
1.437 + /// the nodes which are \c false initially
1.438 + DfsIterator(const Graph& _graph, ReachedMap& _reached) :
1.439 + graph(&_graph), reached(_reached),
1.440 + own_reached_map(false) { }
1.441 + /// The same as above, but the map of reached nodes is
1.442 + /// constructed dynamically
1.443 + /// to everywhere false.
1.444 + DfsIterator(const Graph& _graph) :
1.445 + graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
1.446 + own_reached_map(true) { }
1.447 + ~DfsIterator() { if (own_reached_map) delete &reached; }
1.448 + /// This method markes s reached and first out-edge is processed.
1.449 + DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) {
1.450 + actual_node=s;
1.451 + reached.set(s, true);
1.452 + OutEdgeIt e(*graph, s);
1.453 + //graph->first(e, s);
1.454 + dfs_stack.push(e);
1.455 + return *this;
1.456 + }
1.457 + /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator,
1.458 + /// its \c operator++() iterates on the edges in a dfs order.
1.459 + DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
1.460 + operator++() {
1.461 + actual_edge=dfs_stack.top();
1.462 + if (actual_edge!=INVALID/*.valid()*/) {
1.463 + Node w=graph->head(actual_edge);
1.464 + actual_node=w;
1.465 + if (!reached[w]) {
1.466 + OutEdgeIt e(*graph, w);
1.467 + //graph->first(e, w);
1.468 + dfs_stack.push(e);
1.469 + reached.set(w, true);
1.470 + b_node_newly_reached=true;
1.471 + } else {
1.472 + actual_node=graph->tail(actual_edge);
1.473 + ++dfs_stack.top();
1.474 + b_node_newly_reached=false;
1.475 + }
1.476 + } else {
1.477 + //actual_node=G.aNode(dfs_stack.top());
1.478 + dfs_stack.pop();
1.479 + }
1.480 + return *this;
1.481 + }
1.482 + /// Returns true iff the algorithm is finished.
1.483 + bool finished() const { return dfs_stack.empty(); }
1.484 + /// The conversion operator makes for converting the bfs-iterator
1.485 + /// to an \c out-edge-iterator.
1.486 + ///\bug Edge have to be in LEMON 0.2
1.487 + operator Edge() const { return actual_edge; }
1.488 + /// Returns if b-node has been reached just now.
1.489 + bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.490 + /// Returns if a-node is examined.
1.491 + bool isANodeExamined() const { return actual_edge==INVALID; }
1.492 + /// Returns a-node of the actual edge, so does if the edge is invalid.
1.493 + Node tail() const { return actual_node; /*FIXME*/}
1.494 + /// Returns b-node of the actual edge.
1.495 + /// \pre The actual edge have to be valid.
1.496 + Node head() const { return graph->head(actual_edge); }
1.497 + /// Guess what?
1.498 + /// \deprecated
1.499 + const ReachedMap& getReachedMap() const { return reached; }
1.500 + /// Guess what?
1.501 + /// \deprecated
1.502 + const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
1.503 + };
1.504 +
1.505 + /// Dfs searches for the nodes wich are not marked in
1.506 + /// \c reached_map
1.507 + /// Reached is a read-write bool node-map,
1.508 + /// Pred is a write node-map, have to be.
1.509 + /// \ingroup galgs
1.510 + template <typename Graph,
1.511 + typename ReachedMap=typename Graph::template NodeMap<bool>,
1.512 + typename PredMap
1.513 + =typename Graph::template NodeMap<typename Graph::Edge> >
1.514 + class Dfs : public DfsIterator<Graph, ReachedMap> {
1.515 + typedef DfsIterator<Graph, ReachedMap> Parent;
1.516 + protected:
1.517 + typedef typename Parent::Node Node;
1.518 + PredMap& pred;
1.519 + public:
1.520 + /// The algorithm will search in a dfs order for
1.521 + /// the nodes which are \c false initially.
1.522 + /// The constructor makes no initial changes on the maps.
1.523 + Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(_pred) { }
1.524 + /// \c s is marked to be reached and pushed in the bfs queue.
1.525 + /// If the queue is empty, then the first out-edge is processed.
1.526 + /// If \c s was not marked previously, then
1.527 + /// in addition its pred is set to be \c INVALID.
1.528 + /// if \c s was marked previuosly, then it is simply pushed.
1.529 + Dfs<Graph, ReachedMap, PredMap>& push(Node s) {
1.530 + if (this->reached[s]) {
1.531 + Parent::pushAndSetReached(s);
1.532 + } else {
1.533 + Parent::pushAndSetReached(s);
1.534 + pred.set(s, INVALID);
1.535 + }
1.536 + return *this;
1.537 + }
1.538 + /// A bfs is processed from \c s.
1.539 + Dfs<Graph, ReachedMap, PredMap>& run(Node s) {
1.540 + push(s);
1.541 + while (!this->finished()) this->operator++();
1.542 + return *this;
1.543 + }
1.544 + /// Beside the dfs iteration, \c pred is saved in a
1.545 + /// newly reached node.
1.546 + Dfs<Graph, ReachedMap, PredMap>& operator++() {
1.547 + Parent::operator++();
1.548 + if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
1.549 + {
1.550 + pred.set(this->head(), this->actual_edge);
1.551 + }
1.552 + return *this;
1.553 + }
1.554 + /// Guess what?
1.555 + /// \deprecated
1.556 + const PredMap& getPredMap() const { return pred; }
1.557 + };
1.558 +
1.559 + } // namespace marci
1.560 +} // namespace lemon
1.561 +
1.562 +#endif //LEMON_BFS_DFS_H