1.1 --- a/src/work/marci/experiment/bfs_iterator.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,841 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#ifndef LEMON_BFS_ITERATOR_H
1.6 -#define LEMON_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 lemon {
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 lemon
1.843 -
1.844 -#endif //LEMON_BFS_ITERATOR_H