1.1 --- a/src/work/marci/bfs_mm.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,559 +0,0 @@
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->target(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->target(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->target(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 source() const { return bfs_queue.front(); }
1.139 - /// \pre The actual edge have to be valid.
1.140 - Node target() const { return graph->target(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::Value 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->target(), this->actual_edge);
1.238 - pred_node_map->set(this->target(), this->source());
1.239 - dist_map->set(this->target(), (*dist_map)[this->source()]);
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::Value 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::Value 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::Value 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->target(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->source(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 source() 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 target() const { return graph->target(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->target(), 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