1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci/experiment/bfs_iterator.h Sat Apr 03 17:26:46 2004 +0000
1.3 @@ -0,0 +1,841 @@
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 +#include <graph_wrapper.h>
1.12 +
1.13 +namespace hugo {
1.14 +
1.15 +// template <typename Graph>
1.16 +// struct bfs {
1.17 +// typedef typename Graph::Node Node;
1.18 +// typedef typename Graph::Edge Edge;
1.19 +// typedef typename Graph::NodeIt NodeIt;
1.20 +// typedef typename Graph::OutEdgeIt OutEdgeIt;
1.21 +// Graph& G;
1.22 +// Node s;
1.23 +// typename Graph::NodeMap<bool> reached;
1.24 +// typename Graph::NodeMap<Edge> pred;
1.25 +// typename Graph::NodeMap<int> dist;
1.26 +// std::queue<Node> bfs_queue;
1.27 +// bfs(Graph& _G, Node _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {
1.28 +// bfs_queue.push(s);
1.29 +// for(NodeIt i=G.template first<NodeIt>(); i.valid(); ++i)
1.30 +// reached.set(i, false);
1.31 +// reached.set(s, true);
1.32 +// dist.set(s, 0);
1.33 +// }
1.34 +
1.35 +// void run() {
1.36 +// while (!bfs_queue.empty()) {
1.37 +// Node v=bfs_queue.front();
1.38 +// OutEdgeIt e=G.template first<OutEdgeIt>(v);
1.39 +// bfs_queue.pop();
1.40 +// for( ; e.valid(); ++e) {
1.41 +// Node w=G.bNode(e);
1.42 +// std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
1.43 +// if (!reached.get(w)) {
1.44 +// std::cout << G.id(w) << " is newly reached :-)" << std::endl;
1.45 +// bfs_queue.push(w);
1.46 +// dist.set(w, dist.get(v)+1);
1.47 +// pred.set(w, e);
1.48 +// reached.set(w, true);
1.49 +// } else {
1.50 +// std::cout << G.id(w) << " is already reached" << std::endl;
1.51 +// }
1.52 +// }
1.53 +// }
1.54 +// }
1.55 +// };
1.56 +
1.57 +// template <typename Graph>
1.58 +// struct bfs_visitor {
1.59 +// typedef typename Graph::Node Node;
1.60 +// typedef typename Graph::Edge Edge;
1.61 +// typedef typename Graph::OutEdgeIt OutEdgeIt;
1.62 +// Graph& G;
1.63 +// bfs_visitor(Graph& _G) : G(_G) { }
1.64 +// void at_previously_reached(OutEdgeIt& e) {
1.65 +// //Node v=G.aNode(e);
1.66 +// Node w=G.bNode(e);
1.67 +// std::cout << G.id(w) << " is already reached" << std::endl;
1.68 +// }
1.69 +// void at_newly_reached(OutEdgeIt& e) {
1.70 +// //Node v=G.aNode(e);
1.71 +// Node w=G.bNode(e);
1.72 +// std::cout << G.id(w) << " is newly reached :-)" << std::endl;
1.73 +// }
1.74 +// };
1.75 +
1.76 +// template <typename Graph, typename ReachedMap, typename visitor_type>
1.77 +// struct bfs_iterator {
1.78 +// typedef typename Graph::Node Node;
1.79 +// typedef typename Graph::Edge Edge;
1.80 +// typedef typename Graph::OutEdgeIt OutEdgeIt;
1.81 +// Graph& G;
1.82 +// std::queue<OutEdgeIt>& bfs_queue;
1.83 +// ReachedMap& reached;
1.84 +// visitor_type& visitor;
1.85 +// void process() {
1.86 +// while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.87 +// if (bfs_queue.empty()) return;
1.88 +// OutEdgeIt e=bfs_queue.front();
1.89 +// //Node v=G.aNode(e);
1.90 +// Node w=G.bNode(e);
1.91 +// if (!reached.get(w)) {
1.92 +// visitor.at_newly_reached(e);
1.93 +// bfs_queue.push(G.template first<OutEdgeIt>(w));
1.94 +// reached.set(w, true);
1.95 +// } else {
1.96 +// visitor.at_previously_reached(e);
1.97 +// }
1.98 +// }
1.99 +// bfs_iterator(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) {
1.100 +// //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.101 +// valid();
1.102 +// }
1.103 +// bfs_iterator<Graph, ReachedMap, visitor_type>& operator++() {
1.104 +// //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.105 +// //if (bfs_queue.empty()) return *this;
1.106 +// if (!valid()) return *this;
1.107 +// ++(bfs_queue.front());
1.108 +// //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.109 +// valid();
1.110 +// return *this;
1.111 +// }
1.112 +// //void next() {
1.113 +// // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.114 +// // if (bfs_queue.empty()) return;
1.115 +// // ++(bfs_queue.front());
1.116 +// // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.117 +// //}
1.118 +// bool valid() {
1.119 +// while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.120 +// if (bfs_queue.empty()) return false; else return true;
1.121 +// }
1.122 +// //bool finished() {
1.123 +// // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.124 +// // if (bfs_queue.empty()) return true; else return false;
1.125 +// //}
1.126 +// operator Edge () { return bfs_queue.front(); }
1.127 +
1.128 +// };
1.129 +
1.130 +// template <typename Graph, typename ReachedMap>
1.131 +// struct bfs_iterator1 {
1.132 +// typedef typename Graph::Node Node;
1.133 +// typedef typename Graph::Edge Edge;
1.134 +// typedef typename Graph::OutEdgeIt OutEdgeIt;
1.135 +// Graph& G;
1.136 +// std::queue<OutEdgeIt>& bfs_queue;
1.137 +// ReachedMap& reached;
1.138 +// bool _newly_reached;
1.139 +// bfs_iterator1(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) {
1.140 +// valid();
1.141 +// if (!bfs_queue.empty() && bfs_queue.front().valid()) {
1.142 +// OutEdgeIt e=bfs_queue.front();
1.143 +// Node w=G.bNode(e);
1.144 +// if (!reached.get(w)) {
1.145 +// bfs_queue.push(G.template first<OutEdgeIt>(w));
1.146 +// reached.set(w, true);
1.147 +// _newly_reached=true;
1.148 +// } else {
1.149 +// _newly_reached=false;
1.150 +// }
1.151 +// }
1.152 +// }
1.153 +// bfs_iterator1<Graph, ReachedMap>& operator++() {
1.154 +// if (!valid()) return *this;
1.155 +// ++(bfs_queue.front());
1.156 +// valid();
1.157 +// if (!bfs_queue.empty() && bfs_queue.front().valid()) {
1.158 +// OutEdgeIt e=bfs_queue.front();
1.159 +// Node w=G.bNode(e);
1.160 +// if (!reached.get(w)) {
1.161 +// bfs_queue.push(G.template first<OutEdgeIt>(w));
1.162 +// reached.set(w, true);
1.163 +// _newly_reached=true;
1.164 +// } else {
1.165 +// _newly_reached=false;
1.166 +// }
1.167 +// }
1.168 +// return *this;
1.169 +// }
1.170 +// bool valid() {
1.171 +// while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.172 +// if (bfs_queue.empty()) return false; else return true;
1.173 +// }
1.174 +// operator OutEdgeIt() { return bfs_queue.front(); }
1.175 +// //ize
1.176 +// bool newly_reached() { return _newly_reached; }
1.177 +
1.178 +// };
1.179 +
1.180 +// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
1.181 +// struct BfsIterator {
1.182 +// typedef typename Graph::Node Node;
1.183 +// Graph& G;
1.184 +// std::queue<OutEdgeIt>& bfs_queue;
1.185 +// ReachedMap& reached;
1.186 +// bool b_node_newly_reached;
1.187 +// OutEdgeIt actual_edge;
1.188 +// BfsIterator(Graph& _G,
1.189 +// std::queue<OutEdgeIt>& _bfs_queue,
1.190 +// ReachedMap& _reached) :
1.191 +// G(_G), bfs_queue(_bfs_queue), reached(_reached) {
1.192 +// actual_edge=bfs_queue.front();
1.193 +// if (actual_edge.valid()) {
1.194 +// Node w=G.bNode(actual_edge);
1.195 +// if (!reached.get(w)) {
1.196 +// bfs_queue.push(G.firstOutEdge(w));
1.197 +// reached.set(w, true);
1.198 +// b_node_newly_reached=true;
1.199 +// } else {
1.200 +// b_node_newly_reached=false;
1.201 +// }
1.202 +// }
1.203 +// }
1.204 +// BfsIterator<Graph, OutEdgeIt, ReachedMap>&
1.205 +// operator++() {
1.206 +// if (bfs_queue.front().valid()) {
1.207 +// ++(bfs_queue.front());
1.208 +// actual_edge=bfs_queue.front();
1.209 +// if (actual_edge.valid()) {
1.210 +// Node w=G.bNode(actual_edge);
1.211 +// if (!reached.get(w)) {
1.212 +// bfs_queue.push(G.firstOutEdge(w));
1.213 +// reached.set(w, true);
1.214 +// b_node_newly_reached=true;
1.215 +// } else {
1.216 +// b_node_newly_reached=false;
1.217 +// }
1.218 +// }
1.219 +// } else {
1.220 +// bfs_queue.pop();
1.221 +// actual_edge=bfs_queue.front();
1.222 +// if (actual_edge.valid()) {
1.223 +// Node w=G.bNode(actual_edge);
1.224 +// if (!reached.get(w)) {
1.225 +// bfs_queue.push(G.firstOutEdge(w));
1.226 +// reached.set(w, true);
1.227 +// b_node_newly_reached=true;
1.228 +// } else {
1.229 +// b_node_newly_reached=false;
1.230 +// }
1.231 +// }
1.232 +// }
1.233 +// return *this;
1.234 +// }
1.235 +// bool finished() { return bfs_queue.empty(); }
1.236 +// operator OutEdgeIt () { return actual_edge; }
1.237 +// bool bNodeIsNewlyReached() { return b_node_newly_reached; }
1.238 +// bool aNodeIsExamined() { return !(actual_edge.valid()); }
1.239 +// };
1.240 +
1.241 +
1.242 +// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
1.243 +// struct DfsIterator {
1.244 +// typedef typename Graph::Node Node;
1.245 +// Graph& G;
1.246 +// std::stack<OutEdgeIt>& bfs_queue;
1.247 +// ReachedMap& reached;
1.248 +// bool b_node_newly_reached;
1.249 +// OutEdgeIt actual_edge;
1.250 +// DfsIterator(Graph& _G,
1.251 +// std::stack<OutEdgeIt>& _bfs_queue,
1.252 +// ReachedMap& _reached) :
1.253 +// G(_G), bfs_queue(_bfs_queue), reached(_reached) {
1.254 +// actual_edge=bfs_queue.top();
1.255 +// if (actual_edge.valid()) {
1.256 +// Node w=G.bNode(actual_edge);
1.257 +// if (!reached.get(w)) {
1.258 +// bfs_queue.push(G.firstOutEdge(w));
1.259 +// reached.set(w, true);
1.260 +// b_node_newly_reached=true;
1.261 +// } else {
1.262 +// ++(bfs_queue.top());
1.263 +// b_node_newly_reached=false;
1.264 +// }
1.265 +// } else {
1.266 +// bfs_queue.pop();
1.267 +// }
1.268 +// }
1.269 +// DfsIterator<Graph, OutEdgeIt, ReachedMap>&
1.270 +// operator++() {
1.271 +// actual_edge=bfs_queue.top();
1.272 +// if (actual_edge.valid()) {
1.273 +// Node w=G.bNode(actual_edge);
1.274 +// if (!reached.get(w)) {
1.275 +// bfs_queue.push(G.firstOutEdge(w));
1.276 +// reached.set(w, true);
1.277 +// b_node_newly_reached=true;
1.278 +// } else {
1.279 +// ++(bfs_queue.top());
1.280 +// b_node_newly_reached=false;
1.281 +// }
1.282 +// } else {
1.283 +// bfs_queue.pop();
1.284 +// }
1.285 +// return *this;
1.286 +// }
1.287 +// bool finished() { return bfs_queue.empty(); }
1.288 +// operator OutEdgeIt () { return actual_edge; }
1.289 +// bool bNodeIsNewlyReached() { return b_node_newly_reached; }
1.290 +// bool aNodeIsExamined() { return !(actual_edge.valid()); }
1.291 +// };
1.292 +
1.293 +// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
1.294 +// struct BfsIterator1 {
1.295 +// typedef typename Graph::Node Node;
1.296 +// Graph& G;
1.297 +// std::queue<OutEdgeIt>& bfs_queue;
1.298 +// ReachedMap& reached;
1.299 +// bool b_node_newly_reached;
1.300 +// OutEdgeIt actual_edge;
1.301 +// BfsIterator1(Graph& _G,
1.302 +// std::queue<OutEdgeIt>& _bfs_queue,
1.303 +// ReachedMap& _reached) :
1.304 +// G(_G), bfs_queue(_bfs_queue), reached(_reached) {
1.305 +// actual_edge=bfs_queue.front();
1.306 +// if (actual_edge.valid()) {
1.307 +// Node w=G.bNode(actual_edge);
1.308 +// if (!reached.get(w)) {
1.309 +// bfs_queue.push(OutEdgeIt(G, w));
1.310 +// reached.set(w, true);
1.311 +// b_node_newly_reached=true;
1.312 +// } else {
1.313 +// b_node_newly_reached=false;
1.314 +// }
1.315 +// }
1.316 +// }
1.317 +// void next() {
1.318 +// if (bfs_queue.front().valid()) {
1.319 +// ++(bfs_queue.front());
1.320 +// actual_edge=bfs_queue.front();
1.321 +// if (actual_edge.valid()) {
1.322 +// Node w=G.bNode(actual_edge);
1.323 +// if (!reached.get(w)) {
1.324 +// bfs_queue.push(OutEdgeIt(G, w));
1.325 +// reached.set(w, true);
1.326 +// b_node_newly_reached=true;
1.327 +// } else {
1.328 +// b_node_newly_reached=false;
1.329 +// }
1.330 +// }
1.331 +// } else {
1.332 +// bfs_queue.pop();
1.333 +// actual_edge=bfs_queue.front();
1.334 +// if (actual_edge.valid()) {
1.335 +// Node w=G.bNode(actual_edge);
1.336 +// if (!reached.get(w)) {
1.337 +// bfs_queue.push(OutEdgeIt(G, w));
1.338 +// reached.set(w, true);
1.339 +// b_node_newly_reached=true;
1.340 +// } else {
1.341 +// b_node_newly_reached=false;
1.342 +// }
1.343 +// }
1.344 +// }
1.345 +// //return *this;
1.346 +// }
1.347 +// bool finished() { return bfs_queue.empty(); }
1.348 +// operator OutEdgeIt () { return actual_edge; }
1.349 +// bool bNodeIsNewlyReached() { return b_node_newly_reached; }
1.350 +// bool aNodeIsExamined() { return !(actual_edge.valid()); }
1.351 +// };
1.352 +
1.353 +
1.354 +// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
1.355 +// struct DfsIterator1 {
1.356 +// typedef typename Graph::Node Node;
1.357 +// Graph& G;
1.358 +// std::stack<OutEdgeIt>& bfs_queue;
1.359 +// ReachedMap& reached;
1.360 +// bool b_node_newly_reached;
1.361 +// OutEdgeIt actual_edge;
1.362 +// DfsIterator1(Graph& _G,
1.363 +// std::stack<OutEdgeIt>& _bfs_queue,
1.364 +// ReachedMap& _reached) :
1.365 +// G(_G), bfs_queue(_bfs_queue), reached(_reached) {
1.366 +// //actual_edge=bfs_queue.top();
1.367 +// //if (actual_edge.valid()) {
1.368 +// // Node w=G.bNode(actual_edge);
1.369 +// //if (!reached.get(w)) {
1.370 +// // bfs_queue.push(OutEdgeIt(G, w));
1.371 +// // reached.set(w, true);
1.372 +// // b_node_newly_reached=true;
1.373 +// //} else {
1.374 +// // ++(bfs_queue.top());
1.375 +// // b_node_newly_reached=false;
1.376 +// //}
1.377 +// //} else {
1.378 +// // bfs_queue.pop();
1.379 +// //}
1.380 +// }
1.381 +// void next() {
1.382 +// actual_edge=bfs_queue.top();
1.383 +// if (actual_edge.valid()) {
1.384 +// Node w=G.bNode(actual_edge);
1.385 +// if (!reached.get(w)) {
1.386 +// bfs_queue.push(OutEdgeIt(G, w));
1.387 +// reached.set(w, true);
1.388 +// b_node_newly_reached=true;
1.389 +// } else {
1.390 +// ++(bfs_queue.top());
1.391 +// b_node_newly_reached=false;
1.392 +// }
1.393 +// } else {
1.394 +// bfs_queue.pop();
1.395 +// }
1.396 +// //return *this;
1.397 +// }
1.398 +// bool finished() { return bfs_queue.empty(); }
1.399 +// operator OutEdgeIt () { return actual_edge; }
1.400 +// bool bNodeIsNewlyReached() { return b_node_newly_reached; }
1.401 +// bool aNodeIsLeaved() { return !(actual_edge.valid()); }
1.402 +// };
1.403 +
1.404 +// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
1.405 +// class BfsIterator2 {
1.406 +// typedef typename Graph::Node Node;
1.407 +// const Graph& G;
1.408 +// std::queue<OutEdgeIt> bfs_queue;
1.409 +// ReachedMap reached;
1.410 +// bool b_node_newly_reached;
1.411 +// OutEdgeIt actual_edge;
1.412 +// public:
1.413 +// BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }
1.414 +// void pushAndSetReached(Node s) {
1.415 +// reached.set(s, true);
1.416 +// if (bfs_queue.empty()) {
1.417 +// bfs_queue.push(G.template first<OutEdgeIt>(s));
1.418 +// actual_edge=bfs_queue.front();
1.419 +// if (actual_edge.valid()) {
1.420 +// Node w=G.bNode(actual_edge);
1.421 +// if (!reached.get(w)) {
1.422 +// bfs_queue.push(G.template first<OutEdgeIt>(w));
1.423 +// reached.set(w, true);
1.424 +// b_node_newly_reached=true;
1.425 +// } else {
1.426 +// b_node_newly_reached=false;
1.427 +// }
1.428 +// } //else {
1.429 +// //}
1.430 +// } else {
1.431 +// bfs_queue.push(G.template first<OutEdgeIt>(s));
1.432 +// }
1.433 +// }
1.434 +// BfsIterator2<Graph, OutEdgeIt, ReachedMap>&
1.435 +// operator++() {
1.436 +// if (bfs_queue.front().valid()) {
1.437 +// ++(bfs_queue.front());
1.438 +// actual_edge=bfs_queue.front();
1.439 +// if (actual_edge.valid()) {
1.440 +// Node w=G.bNode(actual_edge);
1.441 +// if (!reached.get(w)) {
1.442 +// bfs_queue.push(G.template first<OutEdgeIt>(w));
1.443 +// reached.set(w, true);
1.444 +// b_node_newly_reached=true;
1.445 +// } else {
1.446 +// b_node_newly_reached=false;
1.447 +// }
1.448 +// }
1.449 +// } else {
1.450 +// bfs_queue.pop();
1.451 +// if (!bfs_queue.empty()) {
1.452 +// actual_edge=bfs_queue.front();
1.453 +// if (actual_edge.valid()) {
1.454 +// Node w=G.bNode(actual_edge);
1.455 +// if (!reached.get(w)) {
1.456 +// bfs_queue.push(G.template first<OutEdgeIt>(w));
1.457 +// reached.set(w, true);
1.458 +// b_node_newly_reached=true;
1.459 +// } else {
1.460 +// b_node_newly_reached=false;
1.461 +// }
1.462 +// }
1.463 +// }
1.464 +// }
1.465 +// return *this;
1.466 +// }
1.467 +// bool finished() const { return bfs_queue.empty(); }
1.468 +// operator OutEdgeIt () const { return actual_edge; }
1.469 +// bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.470 +// bool isANodeExamined() const { return !(actual_edge.valid()); }
1.471 +// const ReachedMap& getReachedMap() const { return reached; }
1.472 +// const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; }
1.473 +// };
1.474 +
1.475 +
1.476 +// template <typename Graph, typename OutEdgeIt, typename ReachedMap>
1.477 +// class BfsIterator3 {
1.478 +// typedef typename Graph::Node Node;
1.479 +// const Graph& G;
1.480 +// std::queue< std::pair<Node, OutEdgeIt> > bfs_queue;
1.481 +// ReachedMap reached;
1.482 +// bool b_node_newly_reached;
1.483 +// OutEdgeIt actual_edge;
1.484 +// public:
1.485 +// BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { }
1.486 +// void pushAndSetReached(Node s) {
1.487 +// reached.set(s, true);
1.488 +// if (bfs_queue.empty()) {
1.489 +// bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
1.490 +// actual_edge=bfs_queue.front().second;
1.491 +// if (actual_edge.valid()) {
1.492 +// Node w=G.bNode(actual_edge);
1.493 +// if (!reached.get(w)) {
1.494 +// bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
1.495 +// reached.set(w, true);
1.496 +// b_node_newly_reached=true;
1.497 +// } else {
1.498 +// b_node_newly_reached=false;
1.499 +// }
1.500 +// } //else {
1.501 +// //}
1.502 +// } else {
1.503 +// bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
1.504 +// }
1.505 +// }
1.506 +// BfsIterator3<Graph, OutEdgeIt, ReachedMap>&
1.507 +// operator++() {
1.508 +// if (bfs_queue.front().second.valid()) {
1.509 +// ++(bfs_queue.front().second);
1.510 +// actual_edge=bfs_queue.front().second;
1.511 +// if (actual_edge.valid()) {
1.512 +// Node w=G.bNode(actual_edge);
1.513 +// if (!reached.get(w)) {
1.514 +// bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
1.515 +// reached.set(w, true);
1.516 +// b_node_newly_reached=true;
1.517 +// } else {
1.518 +// b_node_newly_reached=false;
1.519 +// }
1.520 +// }
1.521 +// } else {
1.522 +// bfs_queue.pop();
1.523 +// if (!bfs_queue.empty()) {
1.524 +// actual_edge=bfs_queue.front().second;
1.525 +// if (actual_edge.valid()) {
1.526 +// Node w=G.bNode(actual_edge);
1.527 +// if (!reached.get(w)) {
1.528 +// bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
1.529 +// reached.set(w, true);
1.530 +// b_node_newly_reached=true;
1.531 +// } else {
1.532 +// b_node_newly_reached=false;
1.533 +// }
1.534 +// }
1.535 +// }
1.536 +// }
1.537 +// return *this;
1.538 +// }
1.539 +// bool finished() const { return bfs_queue.empty(); }
1.540 +// operator OutEdgeIt () const { return actual_edge; }
1.541 +// bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.542 +// bool isANodeExamined() const { return !(actual_edge.valid()); }
1.543 +// Node aNode() const { return bfs_queue.front().first; }
1.544 +// Node bNode() const { return G.bNode(actual_edge); }
1.545 +// const ReachedMap& getReachedMap() const { return reached; }
1.546 +// //const std::queue< std::pair<Node, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; }
1.547 +// };
1.548 +
1.549 +
1.550 +// template <typename Graph, typename OutEdgeIt,
1.551 +// typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
1.552 +// class BfsIterator4 {
1.553 +// typedef typename Graph::Node Node;
1.554 +// const Graph& G;
1.555 +// std::queue<Node> bfs_queue;
1.556 +// ReachedMap& reached;
1.557 +// bool b_node_newly_reached;
1.558 +// OutEdgeIt actual_edge;
1.559 +// bool own_reached_map;
1.560 +// public:
1.561 +// BfsIterator4(const Graph& _G, ReachedMap& _reached) :
1.562 +// G(_G), reached(_reached),
1.563 +// own_reached_map(false) { }
1.564 +// BfsIterator4(const Graph& _G) :
1.565 +// G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.566 +// own_reached_map(true) { }
1.567 +// ~BfsIterator4() { if (own_reached_map) delete &reached; }
1.568 +// void pushAndSetReached(Node s) {
1.569 +// //std::cout << "mimi" << &reached << std::endl;
1.570 +// reached.set(s, true);
1.571 +// //std::cout << "mumus" << std::endl;
1.572 +// if (bfs_queue.empty()) {
1.573 +// //std::cout << "bibi1" << std::endl;
1.574 +// bfs_queue.push(s);
1.575 +// //std::cout << "zizi" << std::endl;
1.576 +// G./*getF*/first(actual_edge, s);
1.577 +// //std::cout << "kiki" << std::endl;
1.578 +// if (G.valid(actual_edge)/*.valid()*/) {
1.579 +// Node w=G.bNode(actual_edge);
1.580 +// if (!reached.get(w)) {
1.581 +// bfs_queue.push(w);
1.582 +// reached.set(w, true);
1.583 +// b_node_newly_reached=true;
1.584 +// } else {
1.585 +// b_node_newly_reached=false;
1.586 +// }
1.587 +// }
1.588 +// } else {
1.589 +// //std::cout << "bibi2" << std::endl;
1.590 +// bfs_queue.push(s);
1.591 +// }
1.592 +// }
1.593 +// BfsIterator4<Graph, OutEdgeIt, ReachedMap>&
1.594 +// operator++() {
1.595 +// if (G.valid(actual_edge)/*.valid()*/) {
1.596 +// /*++*/G.next(actual_edge);
1.597 +// if (G.valid(actual_edge)/*.valid()*/) {
1.598 +// Node w=G.bNode(actual_edge);
1.599 +// if (!reached.get(w)) {
1.600 +// bfs_queue.push(w);
1.601 +// reached.set(w, true);
1.602 +// b_node_newly_reached=true;
1.603 +// } else {
1.604 +// b_node_newly_reached=false;
1.605 +// }
1.606 +// }
1.607 +// } else {
1.608 +// bfs_queue.pop();
1.609 +// if (!bfs_queue.empty()) {
1.610 +// G./*getF*/first(actual_edge, bfs_queue.front());
1.611 +// if (G.valid(actual_edge)/*.valid()*/) {
1.612 +// Node w=G.bNode(actual_edge);
1.613 +// if (!reached.get(w)) {
1.614 +// bfs_queue.push(w);
1.615 +// reached.set(w, true);
1.616 +// b_node_newly_reached=true;
1.617 +// } else {
1.618 +// b_node_newly_reached=false;
1.619 +// }
1.620 +// }
1.621 +// }
1.622 +// }
1.623 +// return *this;
1.624 +// }
1.625 +// bool finished() const { return bfs_queue.empty(); }
1.626 +// operator OutEdgeIt () const { return actual_edge; }
1.627 +// bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.628 +// bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.629 +// Node aNode() const { return bfs_queue.front(); }
1.630 +// Node bNode() const { return G.bNode(actual_edge); }
1.631 +// const ReachedMap& getReachedMap() const { return reached; }
1.632 +// const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
1.633 +// };
1.634 +
1.635 +
1.636 + template <typename GraphWrapper, /*typename OutEdgeIt,*/
1.637 + typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
1.638 + class BfsIterator5 {
1.639 + typedef typename GraphWrapper::Node Node;
1.640 + typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
1.641 + GraphWrapper G;
1.642 + std::queue<Node> bfs_queue;
1.643 + ReachedMap& reached;
1.644 + bool b_node_newly_reached;
1.645 + OutEdgeIt actual_edge;
1.646 + bool own_reached_map;
1.647 + public:
1.648 + BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
1.649 + G(_G), reached(_reached),
1.650 + own_reached_map(false) { }
1.651 + BfsIterator5(const GraphWrapper& _G) :
1.652 + G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.653 + own_reached_map(true) { }
1.654 +// BfsIterator5(const typename GraphWrapper::BaseGraph& _G,
1.655 +// ReachedMap& _reached) :
1.656 +// G(_G), reached(_reached),
1.657 +// own_reached_map(false) { }
1.658 +// BfsIterator5(const typename GraphWrapper::BaseGraph& _G) :
1.659 +// G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.660 +// own_reached_map(true) { }
1.661 + ~BfsIterator5() { if (own_reached_map) delete &reached; }
1.662 + void pushAndSetReached(Node s) {
1.663 + reached.set(s, true);
1.664 + if (bfs_queue.empty()) {
1.665 + bfs_queue.push(s);
1.666 + G./*getF*/first(actual_edge, s);
1.667 + if (G.valid(actual_edge)/*.valid()*/) {
1.668 + Node w=G.bNode(actual_edge);
1.669 + if (!reached.get(w)) {
1.670 + bfs_queue.push(w);
1.671 + reached.set(w, true);
1.672 + b_node_newly_reached=true;
1.673 + } else {
1.674 + b_node_newly_reached=false;
1.675 + }
1.676 + }
1.677 + } else {
1.678 + bfs_queue.push(s);
1.679 + }
1.680 + }
1.681 + BfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
1.682 + operator++() {
1.683 + if (G.valid(actual_edge)/*.valid()*/) {
1.684 + /*++*/G.next(actual_edge);
1.685 + if (G.valid(actual_edge)/*.valid()*/) {
1.686 + Node w=G.bNode(actual_edge);
1.687 + if (!reached.get(w)) {
1.688 + bfs_queue.push(w);
1.689 + reached.set(w, true);
1.690 + b_node_newly_reached=true;
1.691 + } else {
1.692 + b_node_newly_reached=false;
1.693 + }
1.694 + }
1.695 + } else {
1.696 + bfs_queue.pop();
1.697 + if (!bfs_queue.empty()) {
1.698 + G./*getF*/first(actual_edge, bfs_queue.front());
1.699 + if (G.valid(actual_edge)/*.valid()*/) {
1.700 + Node w=G.bNode(actual_edge);
1.701 + if (!reached.get(w)) {
1.702 + bfs_queue.push(w);
1.703 + reached.set(w, true);
1.704 + b_node_newly_reached=true;
1.705 + } else {
1.706 + b_node_newly_reached=false;
1.707 + }
1.708 + }
1.709 + }
1.710 + }
1.711 + return *this;
1.712 + }
1.713 + bool finished() const { return bfs_queue.empty(); }
1.714 + operator OutEdgeIt () const { return actual_edge; }
1.715 + bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.716 + bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.717 + Node aNode() const { return bfs_queue.front(); }
1.718 + Node bNode() const { return G.bNode(actual_edge); }
1.719 + const ReachedMap& getReachedMap() const { return reached; }
1.720 + const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
1.721 + };
1.722 +
1.723 +// template <typename Graph, typename OutEdgeIt,
1.724 +// typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
1.725 +// class DfsIterator4 {
1.726 +// typedef typename Graph::Node Node;
1.727 +// const Graph& G;
1.728 +// std::stack<OutEdgeIt> dfs_stack;
1.729 +// bool b_node_newly_reached;
1.730 +// OutEdgeIt actual_edge;
1.731 +// Node actual_node;
1.732 +// ReachedMap& reached;
1.733 +// bool own_reached_map;
1.734 +// public:
1.735 +// DfsIterator4(const Graph& _G, ReachedMap& _reached) :
1.736 +// G(_G), reached(_reached),
1.737 +// own_reached_map(false) { }
1.738 +// DfsIterator4(const Graph& _G) :
1.739 +// G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.740 +// own_reached_map(true) { }
1.741 +// ~DfsIterator4() { if (own_reached_map) delete &reached; }
1.742 +// void pushAndSetReached(Node s) {
1.743 +// actual_node=s;
1.744 +// reached.set(s, true);
1.745 +// dfs_stack.push(G.template first<OutEdgeIt>(s));
1.746 +// }
1.747 +// DfsIterator4<Graph, OutEdgeIt, ReachedMap>&
1.748 +// operator++() {
1.749 +// actual_edge=dfs_stack.top();
1.750 +// //actual_node=G.aNode(actual_edge);
1.751 +// if (G.valid(actual_edge)/*.valid()*/) {
1.752 +// Node w=G.bNode(actual_edge);
1.753 +// actual_node=w;
1.754 +// if (!reached.get(w)) {
1.755 +// dfs_stack.push(G.template first<OutEdgeIt>(w));
1.756 +// reached.set(w, true);
1.757 +// b_node_newly_reached=true;
1.758 +// } else {
1.759 +// actual_node=G.aNode(actual_edge);
1.760 +// /*++*/G.next(dfs_stack.top());
1.761 +// b_node_newly_reached=false;
1.762 +// }
1.763 +// } else {
1.764 +// //actual_node=G.aNode(dfs_stack.top());
1.765 +// dfs_stack.pop();
1.766 +// }
1.767 +// return *this;
1.768 +// }
1.769 +// bool finished() const { return dfs_stack.empty(); }
1.770 +// operator OutEdgeIt () const { return actual_edge; }
1.771 +// bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.772 +// bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.773 +// Node aNode() const { return actual_node; /*FIXME*/}
1.774 +// Node bNode() const { return G.bNode(actual_edge); }
1.775 +// const ReachedMap& getReachedMap() const { return reached; }
1.776 +// const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
1.777 +// };
1.778 +
1.779 + template <typename GraphWrapper, /*typename OutEdgeIt,*/
1.780 + typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
1.781 + class DfsIterator5 {
1.782 + typedef typename GraphWrapper::Node Node;
1.783 + typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
1.784 + GraphWrapper G;
1.785 + std::stack<OutEdgeIt> dfs_stack;
1.786 + bool b_node_newly_reached;
1.787 + OutEdgeIt actual_edge;
1.788 + Node actual_node;
1.789 + ReachedMap& reached;
1.790 + bool own_reached_map;
1.791 + public:
1.792 + DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
1.793 + G(_G), reached(_reached),
1.794 + own_reached_map(false) { }
1.795 + DfsIterator5(const GraphWrapper& _G) :
1.796 + G(_G), reached(*(new ReachedMap(G /*, false*/))),
1.797 + own_reached_map(true) { }
1.798 + ~DfsIterator5() { if (own_reached_map) delete &reached; }
1.799 + void pushAndSetReached(Node s) {
1.800 + actual_node=s;
1.801 + reached.set(s, true);
1.802 + OutEdgeIt e;
1.803 + G.first(e, s);
1.804 + dfs_stack.push(e);
1.805 + }
1.806 + DfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
1.807 + operator++() {
1.808 + actual_edge=dfs_stack.top();
1.809 + //actual_node=G.aNode(actual_edge);
1.810 + if (G.valid(actual_edge)/*.valid()*/) {
1.811 + Node w=G.bNode(actual_edge);
1.812 + actual_node=w;
1.813 + if (!reached.get(w)) {
1.814 + OutEdgeIt e;
1.815 + G.first(e, w);
1.816 + dfs_stack.push(e);
1.817 + reached.set(w, true);
1.818 + b_node_newly_reached=true;
1.819 + } else {
1.820 + actual_node=G.aNode(actual_edge);
1.821 + /*++*/G.next(dfs_stack.top());
1.822 + b_node_newly_reached=false;
1.823 + }
1.824 + } else {
1.825 + //actual_node=G.aNode(dfs_stack.top());
1.826 + dfs_stack.pop();
1.827 + }
1.828 + return *this;
1.829 + }
1.830 + bool finished() const { return dfs_stack.empty(); }
1.831 + operator OutEdgeIt () const { return actual_edge; }
1.832 + bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.833 + bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
1.834 + Node aNode() const { return actual_node; /*FIXME*/}
1.835 + Node bNode() const { return G.bNode(actual_edge); }
1.836 + const ReachedMap& getReachedMap() const { return reached; }
1.837 + const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
1.838 + };
1.839 +
1.840 +
1.841 +
1.842 +} // namespace hugo
1.843 +
1.844 +#endif //HUGO_BFS_ITERATOR_H