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