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