1.1 --- a/src/work/marci/bfs_dfs.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,348 +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 -
1.24 - /// Bfs searches for the nodes wich are not marked in
1.25 - /// \c reached_map
1.26 - /// Reached have to be a read-write bool node-map.
1.27 - /// \ingroup galgs
1.28 - template <typename Graph, /*typename OutEdgeIt,*/
1.29 - typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
1.30 - class BfsIterator {
1.31 - protected:
1.32 - typedef typename Graph::Node Node;
1.33 - typedef typename Graph::Edge Edge;
1.34 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.35 - const Graph* graph;
1.36 - std::queue<Node> bfs_queue;
1.37 - ReachedMap& reached;
1.38 - bool b_node_newly_reached;
1.39 - Edge actual_edge;
1.40 - bool own_reached_map;
1.41 - public:
1.42 - /// In that constructor \c _reached have to be a reference
1.43 - /// for a bool bode-map. The algorithm will search for the
1.44 - /// initially \c false nodes
1.45 - /// in a bfs order.
1.46 - BfsIterator(const Graph& _graph, ReachedMap& _reached) :
1.47 - graph(&_graph), reached(_reached),
1.48 - own_reached_map(false) { }
1.49 - /// The same as above, but the map storing the reached nodes
1.50 - /// is constructed dynamically to everywhere false.
1.51 - /// \deprecated
1.52 - BfsIterator(const Graph& _graph) :
1.53 - graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
1.54 - own_reached_map(true) { }
1.55 - /// The map storing the reached nodes have to be destroyed if
1.56 - /// it was constructed dynamically
1.57 - ~BfsIterator() { if (own_reached_map) delete &reached; }
1.58 - /// This method markes \c s reached.
1.59 - /// If the queue is empty, then \c s is pushed in the bfs queue
1.60 - /// and the first out-edge is processed.
1.61 - /// If the queue is not empty, then \c s is simply pushed.
1.62 - BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) {
1.63 - reached.set(s, true);
1.64 - if (bfs_queue.empty()) {
1.65 - bfs_queue.push(s);
1.66 - actual_edge=OutEdgeIt(*graph, s);
1.67 - //graph->first(actual_edge, s);
1.68 - if (actual_edge!=INVALID) {
1.69 - Node w=graph->target(actual_edge);
1.70 - if (!reached[w]) {
1.71 - bfs_queue.push(w);
1.72 - reached.set(w, true);
1.73 - b_node_newly_reached=true;
1.74 - } else {
1.75 - b_node_newly_reached=false;
1.76 - }
1.77 - }
1.78 - } else {
1.79 - bfs_queue.push(s);
1.80 - }
1.81 - return *this;
1.82 - }
1.83 - /// As \c BfsIterator<Graph, ReachedMap> works as an edge-iterator,
1.84 - /// its \c operator++() iterates on the edges in a bfs order.
1.85 - BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
1.86 - operator++() {
1.87 - if (actual_edge!=INVALID) {
1.88 - actual_edge=++OutEdgeIt(*graph, actual_edge);
1.89 - //++actual_edge;
1.90 - if (actual_edge!=INVALID) {
1.91 - Node w=graph->target(actual_edge);
1.92 - if (!reached[w]) {
1.93 - bfs_queue.push(w);
1.94 - reached.set(w, true);
1.95 - b_node_newly_reached=true;
1.96 - } else {
1.97 - b_node_newly_reached=false;
1.98 - }
1.99 - }
1.100 - } else {
1.101 - bfs_queue.pop();
1.102 - if (!bfs_queue.empty()) {
1.103 - actual_edge=OutEdgeIt(*graph, bfs_queue.front());
1.104 - //graph->first(actual_edge, bfs_queue.front());
1.105 - if (actual_edge!=INVALID) {
1.106 - Node w=graph->target(actual_edge);
1.107 - if (!reached[w]) {
1.108 - bfs_queue.push(w);
1.109 - reached.set(w, true);
1.110 - b_node_newly_reached=true;
1.111 - } else {
1.112 - b_node_newly_reached=false;
1.113 - }
1.114 - }
1.115 - }
1.116 - }
1.117 - return *this;
1.118 - }
1.119 - /// Returns true iff the algorithm is finished.
1.120 - bool finished() const { return bfs_queue.empty(); }
1.121 - /// The conversion operator makes for converting the bfs-iterator
1.122 - /// to an \c out-edge-iterator.
1.123 - ///\bug Edge have to be in LEMON 0.2
1.124 - operator Edge() const { return actual_edge; }
1.125 - /// Returns if b-node has been reached just now.
1.126 - bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.127 - /// Returns if a-node is examined.
1.128 - bool isANodeExamined() const { return actual_edge==INVALID; }
1.129 - /// Returns a-node of the actual edge, so does if the edge is invalid.
1.130 - Node source() const { return bfs_queue.front(); }
1.131 - /// \pre The actual edge have to be valid.
1.132 - Node target() const { return graph->target(actual_edge); }
1.133 - /// Guess what?
1.134 - /// \deprecated
1.135 - const ReachedMap& getReachedMap() const { return reached; }
1.136 - /// Guess what?
1.137 - /// \deprecated
1.138 - const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
1.139 - };
1.140 -
1.141 - /// Bfs searches for the nodes wich are not marked in
1.142 - /// \c reached_map
1.143 - /// Reached have to work as a read-write bool Node-map,
1.144 - /// Pred is a write edge node-map and
1.145 - /// Dist is a read-write node-map of integral value, have to be.
1.146 - /// \ingroup galgs
1.147 - template <typename Graph,
1.148 - typename ReachedMap=typename Graph::template NodeMap<bool>,
1.149 - typename PredMap
1.150 - =typename Graph::template NodeMap<typename Graph::Edge>,
1.151 - typename DistMap=typename Graph::template NodeMap<int> >
1.152 - class Bfs : public BfsIterator<Graph, ReachedMap> {
1.153 - typedef BfsIterator<Graph, ReachedMap> Parent;
1.154 - protected:
1.155 - typedef typename Parent::Node Node;
1.156 - PredMap& pred;
1.157 - DistMap& dist;
1.158 - public:
1.159 - /// The algorithm will search in a bfs order for
1.160 - /// the nodes which are \c false initially.
1.161 - /// The constructor makes no initial changes on the maps.
1.162 - Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) :
1.163 - BfsIterator<Graph, ReachedMap>(_graph, _reached),
1.164 - pred(_pred), dist(_dist) { }
1.165 - /// \c s is marked to be reached and pushed in the bfs queue.
1.166 - /// If the queue is empty, then the first out-edge is processed.
1.167 - /// If \c s was not marked previously, then
1.168 - /// in addition its pred is set to be \c INVALID, and dist to \c 0.
1.169 - /// if \c s was marked previuosly, then it is simply pushed.
1.170 - Bfs<Graph, ReachedMap, PredMap, DistMap>& push(Node s) {
1.171 - if (this->reached[s]) {
1.172 - Parent::pushAndSetReached(s);
1.173 - } else {
1.174 - Parent::pushAndSetReached(s);
1.175 - pred.set(s, INVALID);
1.176 - dist.set(s, 0);
1.177 - }
1.178 - return *this;
1.179 - }
1.180 - /// A bfs is processed from \c s.
1.181 - Bfs<Graph, ReachedMap, PredMap, DistMap>& run(Node s) {
1.182 - push(s);
1.183 - while (!this->finished()) this->operator++();
1.184 - return *this;
1.185 - }
1.186 - /// Beside the bfs iteration, \c pred and \dist are saved in a
1.187 - /// newly reached node.
1.188 - Bfs<Graph, ReachedMap, PredMap, DistMap>& operator++() {
1.189 - Parent::operator++();
1.190 - if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
1.191 - {
1.192 - pred.set(this->target(), this->actual_edge);
1.193 - dist.set(this->target(), dist[this->source()]);
1.194 - }
1.195 - return *this;
1.196 - }
1.197 - /// Guess what?
1.198 - /// \deprecated
1.199 - const PredMap& getPredMap() const { return pred; }
1.200 - /// Guess what?
1.201 - /// \deprecated
1.202 - const DistMap& getDistMap() const { return dist; }
1.203 - };
1.204 -
1.205 - /// Dfs searches for the nodes wich are not marked in
1.206 - /// \c reached_map
1.207 - /// Reached have to be a read-write bool Node-map.
1.208 - /// \ingroup galgs
1.209 - template <typename Graph, /*typename OutEdgeIt,*/
1.210 - typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
1.211 - class DfsIterator {
1.212 - protected:
1.213 - typedef typename Graph::Node Node;
1.214 - typedef typename Graph::Edge Edge;
1.215 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.216 - const Graph* graph;
1.217 - std::stack<OutEdgeIt> dfs_stack;
1.218 - bool b_node_newly_reached;
1.219 - Edge actual_edge;
1.220 - Node actual_node;
1.221 - ReachedMap& reached;
1.222 - bool own_reached_map;
1.223 - public:
1.224 - /// In that constructor \c _reached have to be a reference
1.225 - /// for a bool node-map. The algorithm will search in a dfs order for
1.226 - /// the nodes which are \c false initially
1.227 - DfsIterator(const Graph& _graph, ReachedMap& _reached) :
1.228 - graph(&_graph), reached(_reached),
1.229 - own_reached_map(false) { }
1.230 - /// The same as above, but the map of reached nodes is
1.231 - /// constructed dynamically
1.232 - /// to everywhere false.
1.233 - DfsIterator(const Graph& _graph) :
1.234 - graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))),
1.235 - own_reached_map(true) { }
1.236 - ~DfsIterator() { if (own_reached_map) delete &reached; }
1.237 - /// This method markes s reached and first out-edge is processed.
1.238 - DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) {
1.239 - actual_node=s;
1.240 - reached.set(s, true);
1.241 - OutEdgeIt e(*graph, s);
1.242 - //graph->first(e, s);
1.243 - dfs_stack.push(e);
1.244 - return *this;
1.245 - }
1.246 - /// As \c DfsIterator<Graph, ReachedMap> works as an edge-iterator,
1.247 - /// its \c operator++() iterates on the edges in a dfs order.
1.248 - DfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>&
1.249 - operator++() {
1.250 - actual_edge=dfs_stack.top();
1.251 - if (actual_edge!=INVALID/*.valid()*/) {
1.252 - Node w=graph->target(actual_edge);
1.253 - actual_node=w;
1.254 - if (!reached[w]) {
1.255 - OutEdgeIt e(*graph, w);
1.256 - //graph->first(e, w);
1.257 - dfs_stack.push(e);
1.258 - reached.set(w, true);
1.259 - b_node_newly_reached=true;
1.260 - } else {
1.261 - actual_node=graph->source(actual_edge);
1.262 - ++dfs_stack.top();
1.263 - b_node_newly_reached=false;
1.264 - }
1.265 - } else {
1.266 - //actual_node=G.aNode(dfs_stack.top());
1.267 - dfs_stack.pop();
1.268 - }
1.269 - return *this;
1.270 - }
1.271 - /// Returns true iff the algorithm is finished.
1.272 - bool finished() const { return dfs_stack.empty(); }
1.273 - /// The conversion operator makes for converting the bfs-iterator
1.274 - /// to an \c out-edge-iterator.
1.275 - ///\bug Edge have to be in LEMON 0.2
1.276 - operator Edge() const { return actual_edge; }
1.277 - /// Returns if b-node has been reached just now.
1.278 - bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.279 - /// Returns if a-node is examined.
1.280 - bool isANodeExamined() const { return actual_edge==INVALID; }
1.281 - /// Returns a-node of the actual edge, so does if the edge is invalid.
1.282 - Node source() const { return actual_node; /*FIXME*/}
1.283 - /// Returns b-node of the actual edge.
1.284 - /// \pre The actual edge have to be valid.
1.285 - Node target() const { return graph->target(actual_edge); }
1.286 - /// Guess what?
1.287 - /// \deprecated
1.288 - const ReachedMap& getReachedMap() const { return reached; }
1.289 - /// Guess what?
1.290 - /// \deprecated
1.291 - const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
1.292 - };
1.293 -
1.294 - /// Dfs searches for the nodes wich are not marked in
1.295 - /// \c reached_map
1.296 - /// Reached is a read-write bool node-map,
1.297 - /// Pred is a write node-map, have to be.
1.298 - /// \ingroup galgs
1.299 - template <typename Graph,
1.300 - typename ReachedMap=typename Graph::template NodeMap<bool>,
1.301 - typename PredMap
1.302 - =typename Graph::template NodeMap<typename Graph::Edge> >
1.303 - class Dfs : public DfsIterator<Graph, ReachedMap> {
1.304 - typedef DfsIterator<Graph, ReachedMap> Parent;
1.305 - protected:
1.306 - typedef typename Parent::Node Node;
1.307 - PredMap& pred;
1.308 - public:
1.309 - /// The algorithm will search in a dfs order for
1.310 - /// the nodes which are \c false initially.
1.311 - /// The constructor makes no initial changes on the maps.
1.312 - Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(_pred) { }
1.313 - /// \c s is marked to be reached and pushed in the bfs queue.
1.314 - /// If the queue is empty, then the first out-edge is processed.
1.315 - /// If \c s was not marked previously, then
1.316 - /// in addition its pred is set to be \c INVALID.
1.317 - /// if \c s was marked previuosly, then it is simply pushed.
1.318 - Dfs<Graph, ReachedMap, PredMap>& push(Node s) {
1.319 - if (this->reached[s]) {
1.320 - Parent::pushAndSetReached(s);
1.321 - } else {
1.322 - Parent::pushAndSetReached(s);
1.323 - pred.set(s, INVALID);
1.324 - }
1.325 - return *this;
1.326 - }
1.327 - /// A bfs is processed from \c s.
1.328 - Dfs<Graph, ReachedMap, PredMap>& run(Node s) {
1.329 - push(s);
1.330 - while (!this->finished()) this->operator++();
1.331 - return *this;
1.332 - }
1.333 - /// Beside the dfs iteration, \c pred is saved in a
1.334 - /// newly reached node.
1.335 - Dfs<Graph, ReachedMap, PredMap>& operator++() {
1.336 - Parent::operator++();
1.337 - if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached)
1.338 - {
1.339 - pred.set(this->target(), this->actual_edge);
1.340 - }
1.341 - return *this;
1.342 - }
1.343 - /// Guess what?
1.344 - /// \deprecated
1.345 - const PredMap& getPredMap() const { return pred; }
1.346 - };
1.347 -
1.348 -
1.349 -} // namespace lemon
1.350 -
1.351 -#endif //LEMON_BFS_DFS_H