2 #ifndef HUGO_BFS_ITERATOR_H
3 #define HUGO_BFS_ITERATOR_H
8 #include <graph_wrapper.h>
12 // template <typename Graph>
14 // typedef typename Graph::Node Node;
15 // typedef typename Graph::Edge Edge;
16 // typedef typename Graph::NodeIt NodeIt;
17 // typedef typename Graph::OutEdgeIt OutEdgeIt;
20 // typename Graph::NodeMap<bool> reached;
21 // typename Graph::NodeMap<Edge> pred;
22 // typename Graph::NodeMap<int> dist;
23 // std::queue<Node> bfs_queue;
24 // bfs(Graph& _G, Node _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {
26 // for(NodeIt i=G.template first<NodeIt>(); i.valid(); ++i)
27 // reached.set(i, false);
28 // reached.set(s, true);
33 // while (!bfs_queue.empty()) {
34 // Node v=bfs_queue.front();
35 // OutEdgeIt e=G.template first<OutEdgeIt>(v);
37 // for( ; e.valid(); ++e) {
39 // std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
40 // if (!reached.get(w)) {
41 // std::cout << G.id(w) << " is newly reached :-)" << std::endl;
43 // dist.set(w, dist.get(v)+1);
45 // reached.set(w, true);
47 // std::cout << G.id(w) << " is already reached" << std::endl;
54 // template <typename Graph>
55 // struct bfs_visitor {
56 // typedef typename Graph::Node Node;
57 // typedef typename Graph::Edge Edge;
58 // typedef typename Graph::OutEdgeIt OutEdgeIt;
60 // bfs_visitor(Graph& _G) : G(_G) { }
61 // void at_previously_reached(OutEdgeIt& e) {
62 // //Node v=G.aNode(e);
64 // std::cout << G.id(w) << " is already reached" << std::endl;
66 // void at_newly_reached(OutEdgeIt& e) {
67 // //Node v=G.aNode(e);
69 // std::cout << G.id(w) << " is newly reached :-)" << std::endl;
73 // template <typename Graph, typename ReachedMap, typename visitor_type>
74 // struct bfs_iterator {
75 // typedef typename Graph::Node Node;
76 // typedef typename Graph::Edge Edge;
77 // typedef typename Graph::OutEdgeIt OutEdgeIt;
79 // std::queue<OutEdgeIt>& bfs_queue;
80 // ReachedMap& reached;
81 // visitor_type& visitor;
83 // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
84 // if (bfs_queue.empty()) return;
85 // OutEdgeIt e=bfs_queue.front();
86 // //Node v=G.aNode(e);
88 // if (!reached.get(w)) {
89 // visitor.at_newly_reached(e);
90 // bfs_queue.push(G.template first<OutEdgeIt>(w));
91 // reached.set(w, true);
93 // visitor.at_previously_reached(e);
96 // bfs_iterator(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) {
97 // //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
100 // bfs_iterator<Graph, ReachedMap, visitor_type>& operator++() {
101 // //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
102 // //if (bfs_queue.empty()) return *this;
103 // if (!valid()) return *this;
104 // ++(bfs_queue.front());
105 // //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
110 // // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
111 // // if (bfs_queue.empty()) return;
112 // // ++(bfs_queue.front());
113 // // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
116 // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
117 // if (bfs_queue.empty()) return false; else return true;
119 // //bool finished() {
120 // // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
121 // // if (bfs_queue.empty()) return true; else return false;
123 // operator Edge () { return bfs_queue.front(); }
127 // template <typename Graph, typename ReachedMap>
128 // struct bfs_iterator1 {
129 // typedef typename Graph::Node Node;
130 // typedef typename Graph::Edge Edge;
131 // typedef typename Graph::OutEdgeIt OutEdgeIt;
133 // std::queue<OutEdgeIt>& bfs_queue;
134 // ReachedMap& reached;
135 // bool _newly_reached;
136 // bfs_iterator1(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) {
138 // if (!bfs_queue.empty() && bfs_queue.front().valid()) {
139 // OutEdgeIt e=bfs_queue.front();
140 // Node w=G.bNode(e);
141 // if (!reached.get(w)) {
142 // bfs_queue.push(G.template first<OutEdgeIt>(w));
143 // reached.set(w, true);
144 // _newly_reached=true;
146 // _newly_reached=false;
150 // bfs_iterator1<Graph, ReachedMap>& operator++() {
151 // if (!valid()) return *this;
152 // ++(bfs_queue.front());
154 // if (!bfs_queue.empty() && bfs_queue.front().valid()) {
155 // OutEdgeIt e=bfs_queue.front();
156 // Node w=G.bNode(e);
157 // if (!reached.get(w)) {
158 // bfs_queue.push(G.template first<OutEdgeIt>(w));
159 // reached.set(w, true);
160 // _newly_reached=true;
162 // _newly_reached=false;
168 // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
169 // if (bfs_queue.empty()) return false; else return true;
171 // operator OutEdgeIt() { return bfs_queue.front(); }
173 // bool newly_reached() { return _newly_reached; }
177 // template <typename Graph, typename OutEdgeIt, typename ReachedMap>
178 // struct BfsIterator {
179 // typedef typename Graph::Node Node;
181 // std::queue<OutEdgeIt>& bfs_queue;
182 // ReachedMap& reached;
183 // bool b_node_newly_reached;
184 // OutEdgeIt actual_edge;
185 // BfsIterator(Graph& _G,
186 // std::queue<OutEdgeIt>& _bfs_queue,
187 // ReachedMap& _reached) :
188 // G(_G), bfs_queue(_bfs_queue), reached(_reached) {
189 // actual_edge=bfs_queue.front();
190 // if (actual_edge.valid()) {
191 // Node w=G.bNode(actual_edge);
192 // if (!reached.get(w)) {
193 // bfs_queue.push(G.firstOutEdge(w));
194 // reached.set(w, true);
195 // b_node_newly_reached=true;
197 // b_node_newly_reached=false;
201 // BfsIterator<Graph, OutEdgeIt, ReachedMap>&
203 // if (bfs_queue.front().valid()) {
204 // ++(bfs_queue.front());
205 // actual_edge=bfs_queue.front();
206 // if (actual_edge.valid()) {
207 // Node w=G.bNode(actual_edge);
208 // if (!reached.get(w)) {
209 // bfs_queue.push(G.firstOutEdge(w));
210 // reached.set(w, true);
211 // b_node_newly_reached=true;
213 // b_node_newly_reached=false;
218 // actual_edge=bfs_queue.front();
219 // if (actual_edge.valid()) {
220 // Node w=G.bNode(actual_edge);
221 // if (!reached.get(w)) {
222 // bfs_queue.push(G.firstOutEdge(w));
223 // reached.set(w, true);
224 // b_node_newly_reached=true;
226 // b_node_newly_reached=false;
232 // bool finished() { return bfs_queue.empty(); }
233 // operator OutEdgeIt () { return actual_edge; }
234 // bool bNodeIsNewlyReached() { return b_node_newly_reached; }
235 // bool aNodeIsExamined() { return !(actual_edge.valid()); }
239 // template <typename Graph, typename OutEdgeIt, typename ReachedMap>
240 // struct DfsIterator {
241 // typedef typename Graph::Node Node;
243 // std::stack<OutEdgeIt>& bfs_queue;
244 // ReachedMap& reached;
245 // bool b_node_newly_reached;
246 // OutEdgeIt actual_edge;
247 // DfsIterator(Graph& _G,
248 // std::stack<OutEdgeIt>& _bfs_queue,
249 // ReachedMap& _reached) :
250 // G(_G), bfs_queue(_bfs_queue), reached(_reached) {
251 // actual_edge=bfs_queue.top();
252 // if (actual_edge.valid()) {
253 // Node w=G.bNode(actual_edge);
254 // if (!reached.get(w)) {
255 // bfs_queue.push(G.firstOutEdge(w));
256 // reached.set(w, true);
257 // b_node_newly_reached=true;
259 // ++(bfs_queue.top());
260 // b_node_newly_reached=false;
266 // DfsIterator<Graph, OutEdgeIt, ReachedMap>&
268 // actual_edge=bfs_queue.top();
269 // if (actual_edge.valid()) {
270 // Node w=G.bNode(actual_edge);
271 // if (!reached.get(w)) {
272 // bfs_queue.push(G.firstOutEdge(w));
273 // reached.set(w, true);
274 // b_node_newly_reached=true;
276 // ++(bfs_queue.top());
277 // b_node_newly_reached=false;
284 // bool finished() { return bfs_queue.empty(); }
285 // operator OutEdgeIt () { return actual_edge; }
286 // bool bNodeIsNewlyReached() { return b_node_newly_reached; }
287 // bool aNodeIsExamined() { return !(actual_edge.valid()); }
290 // template <typename Graph, typename OutEdgeIt, typename ReachedMap>
291 // struct BfsIterator1 {
292 // typedef typename Graph::Node Node;
294 // std::queue<OutEdgeIt>& bfs_queue;
295 // ReachedMap& reached;
296 // bool b_node_newly_reached;
297 // OutEdgeIt actual_edge;
298 // BfsIterator1(Graph& _G,
299 // std::queue<OutEdgeIt>& _bfs_queue,
300 // ReachedMap& _reached) :
301 // G(_G), bfs_queue(_bfs_queue), reached(_reached) {
302 // actual_edge=bfs_queue.front();
303 // if (actual_edge.valid()) {
304 // Node w=G.bNode(actual_edge);
305 // if (!reached.get(w)) {
306 // bfs_queue.push(OutEdgeIt(G, w));
307 // reached.set(w, true);
308 // b_node_newly_reached=true;
310 // b_node_newly_reached=false;
315 // if (bfs_queue.front().valid()) {
316 // ++(bfs_queue.front());
317 // actual_edge=bfs_queue.front();
318 // if (actual_edge.valid()) {
319 // Node w=G.bNode(actual_edge);
320 // if (!reached.get(w)) {
321 // bfs_queue.push(OutEdgeIt(G, w));
322 // reached.set(w, true);
323 // b_node_newly_reached=true;
325 // b_node_newly_reached=false;
330 // actual_edge=bfs_queue.front();
331 // if (actual_edge.valid()) {
332 // Node w=G.bNode(actual_edge);
333 // if (!reached.get(w)) {
334 // bfs_queue.push(OutEdgeIt(G, w));
335 // reached.set(w, true);
336 // b_node_newly_reached=true;
338 // b_node_newly_reached=false;
344 // bool finished() { return bfs_queue.empty(); }
345 // operator OutEdgeIt () { return actual_edge; }
346 // bool bNodeIsNewlyReached() { return b_node_newly_reached; }
347 // bool aNodeIsExamined() { return !(actual_edge.valid()); }
351 // template <typename Graph, typename OutEdgeIt, typename ReachedMap>
352 // struct DfsIterator1 {
353 // typedef typename Graph::Node Node;
355 // std::stack<OutEdgeIt>& bfs_queue;
356 // ReachedMap& reached;
357 // bool b_node_newly_reached;
358 // OutEdgeIt actual_edge;
359 // DfsIterator1(Graph& _G,
360 // std::stack<OutEdgeIt>& _bfs_queue,
361 // ReachedMap& _reached) :
362 // G(_G), bfs_queue(_bfs_queue), reached(_reached) {
363 // //actual_edge=bfs_queue.top();
364 // //if (actual_edge.valid()) {
365 // // Node w=G.bNode(actual_edge);
366 // //if (!reached.get(w)) {
367 // // bfs_queue.push(OutEdgeIt(G, w));
368 // // reached.set(w, true);
369 // // b_node_newly_reached=true;
371 // // ++(bfs_queue.top());
372 // // b_node_newly_reached=false;
375 // // bfs_queue.pop();
379 // actual_edge=bfs_queue.top();
380 // if (actual_edge.valid()) {
381 // Node w=G.bNode(actual_edge);
382 // if (!reached.get(w)) {
383 // bfs_queue.push(OutEdgeIt(G, w));
384 // reached.set(w, true);
385 // b_node_newly_reached=true;
387 // ++(bfs_queue.top());
388 // b_node_newly_reached=false;
395 // bool finished() { return bfs_queue.empty(); }
396 // operator OutEdgeIt () { return actual_edge; }
397 // bool bNodeIsNewlyReached() { return b_node_newly_reached; }
398 // bool aNodeIsLeaved() { return !(actual_edge.valid()); }
401 // template <typename Graph, typename OutEdgeIt, typename ReachedMap>
402 // class BfsIterator2 {
403 // typedef typename Graph::Node Node;
405 // std::queue<OutEdgeIt> bfs_queue;
406 // ReachedMap reached;
407 // bool b_node_newly_reached;
408 // OutEdgeIt actual_edge;
410 // BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }
411 // void pushAndSetReached(Node s) {
412 // reached.set(s, true);
413 // if (bfs_queue.empty()) {
414 // bfs_queue.push(G.template first<OutEdgeIt>(s));
415 // actual_edge=bfs_queue.front();
416 // if (actual_edge.valid()) {
417 // Node w=G.bNode(actual_edge);
418 // if (!reached.get(w)) {
419 // bfs_queue.push(G.template first<OutEdgeIt>(w));
420 // reached.set(w, true);
421 // b_node_newly_reached=true;
423 // b_node_newly_reached=false;
428 // bfs_queue.push(G.template first<OutEdgeIt>(s));
431 // BfsIterator2<Graph, OutEdgeIt, ReachedMap>&
433 // if (bfs_queue.front().valid()) {
434 // ++(bfs_queue.front());
435 // actual_edge=bfs_queue.front();
436 // if (actual_edge.valid()) {
437 // Node w=G.bNode(actual_edge);
438 // if (!reached.get(w)) {
439 // bfs_queue.push(G.template first<OutEdgeIt>(w));
440 // reached.set(w, true);
441 // b_node_newly_reached=true;
443 // b_node_newly_reached=false;
448 // if (!bfs_queue.empty()) {
449 // actual_edge=bfs_queue.front();
450 // if (actual_edge.valid()) {
451 // Node w=G.bNode(actual_edge);
452 // if (!reached.get(w)) {
453 // bfs_queue.push(G.template first<OutEdgeIt>(w));
454 // reached.set(w, true);
455 // b_node_newly_reached=true;
457 // b_node_newly_reached=false;
464 // bool finished() const { return bfs_queue.empty(); }
465 // operator OutEdgeIt () const { return actual_edge; }
466 // bool isBNodeNewlyReached() const { return b_node_newly_reached; }
467 // bool isANodeExamined() const { return !(actual_edge.valid()); }
468 // const ReachedMap& getReachedMap() const { return reached; }
469 // const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; }
473 // template <typename Graph, typename OutEdgeIt, typename ReachedMap>
474 // class BfsIterator3 {
475 // typedef typename Graph::Node Node;
477 // std::queue< std::pair<Node, OutEdgeIt> > bfs_queue;
478 // ReachedMap reached;
479 // bool b_node_newly_reached;
480 // OutEdgeIt actual_edge;
482 // BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { }
483 // void pushAndSetReached(Node s) {
484 // reached.set(s, true);
485 // if (bfs_queue.empty()) {
486 // bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
487 // actual_edge=bfs_queue.front().second;
488 // if (actual_edge.valid()) {
489 // Node w=G.bNode(actual_edge);
490 // if (!reached.get(w)) {
491 // bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
492 // reached.set(w, true);
493 // b_node_newly_reached=true;
495 // b_node_newly_reached=false;
500 // bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
503 // BfsIterator3<Graph, OutEdgeIt, ReachedMap>&
505 // if (bfs_queue.front().second.valid()) {
506 // ++(bfs_queue.front().second);
507 // actual_edge=bfs_queue.front().second;
508 // if (actual_edge.valid()) {
509 // Node w=G.bNode(actual_edge);
510 // if (!reached.get(w)) {
511 // bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
512 // reached.set(w, true);
513 // b_node_newly_reached=true;
515 // b_node_newly_reached=false;
520 // if (!bfs_queue.empty()) {
521 // actual_edge=bfs_queue.front().second;
522 // if (actual_edge.valid()) {
523 // Node w=G.bNode(actual_edge);
524 // if (!reached.get(w)) {
525 // bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
526 // reached.set(w, true);
527 // b_node_newly_reached=true;
529 // b_node_newly_reached=false;
536 // bool finished() const { return bfs_queue.empty(); }
537 // operator OutEdgeIt () const { return actual_edge; }
538 // bool isBNodeNewlyReached() const { return b_node_newly_reached; }
539 // bool isANodeExamined() const { return !(actual_edge.valid()); }
540 // Node aNode() const { return bfs_queue.front().first; }
541 // Node bNode() const { return G.bNode(actual_edge); }
542 // const ReachedMap& getReachedMap() const { return reached; }
543 // //const std::queue< std::pair<Node, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; }
547 // template <typename Graph, typename OutEdgeIt,
548 // typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
549 // class BfsIterator4 {
550 // typedef typename Graph::Node Node;
552 // std::queue<Node> bfs_queue;
553 // ReachedMap& reached;
554 // bool b_node_newly_reached;
555 // OutEdgeIt actual_edge;
556 // bool own_reached_map;
558 // BfsIterator4(const Graph& _G, ReachedMap& _reached) :
559 // G(_G), reached(_reached),
560 // own_reached_map(false) { }
561 // BfsIterator4(const Graph& _G) :
562 // G(_G), reached(*(new ReachedMap(G /*, false*/))),
563 // own_reached_map(true) { }
564 // ~BfsIterator4() { if (own_reached_map) delete &reached; }
565 // void pushAndSetReached(Node s) {
566 // //std::cout << "mimi" << &reached << std::endl;
567 // reached.set(s, true);
568 // //std::cout << "mumus" << std::endl;
569 // if (bfs_queue.empty()) {
570 // //std::cout << "bibi1" << std::endl;
571 // bfs_queue.push(s);
572 // //std::cout << "zizi" << std::endl;
573 // G./*getF*/first(actual_edge, s);
574 // //std::cout << "kiki" << std::endl;
575 // if (G.valid(actual_edge)/*.valid()*/) {
576 // Node w=G.bNode(actual_edge);
577 // if (!reached.get(w)) {
578 // bfs_queue.push(w);
579 // reached.set(w, true);
580 // b_node_newly_reached=true;
582 // b_node_newly_reached=false;
586 // //std::cout << "bibi2" << std::endl;
587 // bfs_queue.push(s);
590 // BfsIterator4<Graph, OutEdgeIt, ReachedMap>&
592 // if (G.valid(actual_edge)/*.valid()*/) {
593 // /*++*/G.next(actual_edge);
594 // if (G.valid(actual_edge)/*.valid()*/) {
595 // Node w=G.bNode(actual_edge);
596 // if (!reached.get(w)) {
597 // bfs_queue.push(w);
598 // reached.set(w, true);
599 // b_node_newly_reached=true;
601 // b_node_newly_reached=false;
606 // if (!bfs_queue.empty()) {
607 // G./*getF*/first(actual_edge, bfs_queue.front());
608 // if (G.valid(actual_edge)/*.valid()*/) {
609 // Node w=G.bNode(actual_edge);
610 // if (!reached.get(w)) {
611 // bfs_queue.push(w);
612 // reached.set(w, true);
613 // b_node_newly_reached=true;
615 // b_node_newly_reached=false;
622 // bool finished() const { return bfs_queue.empty(); }
623 // operator OutEdgeIt () const { return actual_edge; }
624 // bool isBNodeNewlyReached() const { return b_node_newly_reached; }
625 // bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
626 // Node aNode() const { return bfs_queue.front(); }
627 // Node bNode() const { return G.bNode(actual_edge); }
628 // const ReachedMap& getReachedMap() const { return reached; }
629 // const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
633 template <typename GraphWrapper, /*typename OutEdgeIt,*/
634 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
636 typedef typename GraphWrapper::Node Node;
637 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
639 std::queue<Node> bfs_queue;
641 bool b_node_newly_reached;
642 OutEdgeIt actual_edge;
643 bool own_reached_map;
645 BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
646 G(_G), reached(_reached),
647 own_reached_map(false) { }
648 BfsIterator5(const GraphWrapper& _G) :
649 G(_G), reached(*(new ReachedMap(G /*, false*/))),
650 own_reached_map(true) { }
651 // BfsIterator5(const typename GraphWrapper::BaseGraph& _G,
652 // ReachedMap& _reached) :
653 // G(_G), reached(_reached),
654 // own_reached_map(false) { }
655 // BfsIterator5(const typename GraphWrapper::BaseGraph& _G) :
656 // G(_G), reached(*(new ReachedMap(G /*, false*/))),
657 // own_reached_map(true) { }
658 ~BfsIterator5() { if (own_reached_map) delete &reached; }
659 void pushAndSetReached(Node s) {
660 reached.set(s, true);
661 if (bfs_queue.empty()) {
663 G./*getF*/first(actual_edge, s);
664 if (G.valid(actual_edge)/*.valid()*/) {
665 Node w=G.bNode(actual_edge);
666 if (!reached.get(w)) {
668 reached.set(w, true);
669 b_node_newly_reached=true;
671 b_node_newly_reached=false;
678 BfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
680 if (G.valid(actual_edge)/*.valid()*/) {
681 /*++*/G.next(actual_edge);
682 if (G.valid(actual_edge)/*.valid()*/) {
683 Node w=G.bNode(actual_edge);
684 if (!reached.get(w)) {
686 reached.set(w, true);
687 b_node_newly_reached=true;
689 b_node_newly_reached=false;
694 if (!bfs_queue.empty()) {
695 G./*getF*/first(actual_edge, bfs_queue.front());
696 if (G.valid(actual_edge)/*.valid()*/) {
697 Node w=G.bNode(actual_edge);
698 if (!reached.get(w)) {
700 reached.set(w, true);
701 b_node_newly_reached=true;
703 b_node_newly_reached=false;
710 bool finished() const { return bfs_queue.empty(); }
711 operator OutEdgeIt () const { return actual_edge; }
712 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
713 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
714 Node aNode() const { return bfs_queue.front(); }
715 Node bNode() const { return G.bNode(actual_edge); }
716 const ReachedMap& getReachedMap() const { return reached; }
717 const std::queue<Node>& getBfsQueue() const { return bfs_queue; }
720 // template <typename Graph, typename OutEdgeIt,
721 // typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
722 // class DfsIterator4 {
723 // typedef typename Graph::Node Node;
725 // std::stack<OutEdgeIt> dfs_stack;
726 // bool b_node_newly_reached;
727 // OutEdgeIt actual_edge;
729 // ReachedMap& reached;
730 // bool own_reached_map;
732 // DfsIterator4(const Graph& _G, ReachedMap& _reached) :
733 // G(_G), reached(_reached),
734 // own_reached_map(false) { }
735 // DfsIterator4(const Graph& _G) :
736 // G(_G), reached(*(new ReachedMap(G /*, false*/))),
737 // own_reached_map(true) { }
738 // ~DfsIterator4() { if (own_reached_map) delete &reached; }
739 // void pushAndSetReached(Node s) {
741 // reached.set(s, true);
742 // dfs_stack.push(G.template first<OutEdgeIt>(s));
744 // DfsIterator4<Graph, OutEdgeIt, ReachedMap>&
746 // actual_edge=dfs_stack.top();
747 // //actual_node=G.aNode(actual_edge);
748 // if (G.valid(actual_edge)/*.valid()*/) {
749 // Node w=G.bNode(actual_edge);
751 // if (!reached.get(w)) {
752 // dfs_stack.push(G.template first<OutEdgeIt>(w));
753 // reached.set(w, true);
754 // b_node_newly_reached=true;
756 // actual_node=G.aNode(actual_edge);
757 // /*++*/G.next(dfs_stack.top());
758 // b_node_newly_reached=false;
761 // //actual_node=G.aNode(dfs_stack.top());
766 // bool finished() const { return dfs_stack.empty(); }
767 // operator OutEdgeIt () const { return actual_edge; }
768 // bool isBNodeNewlyReached() const { return b_node_newly_reached; }
769 // bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
770 // Node aNode() const { return actual_node; /*FIXME*/}
771 // Node bNode() const { return G.bNode(actual_edge); }
772 // const ReachedMap& getReachedMap() const { return reached; }
773 // const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
776 template <typename GraphWrapper, /*typename OutEdgeIt,*/
777 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
779 typedef typename GraphWrapper::Node Node;
780 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
782 std::stack<OutEdgeIt> dfs_stack;
783 bool b_node_newly_reached;
784 OutEdgeIt actual_edge;
787 bool own_reached_map;
789 DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
790 G(_G), reached(_reached),
791 own_reached_map(false) { }
792 DfsIterator5(const GraphWrapper& _G) :
793 G(_G), reached(*(new ReachedMap(G /*, false*/))),
794 own_reached_map(true) { }
795 ~DfsIterator5() { if (own_reached_map) delete &reached; }
796 void pushAndSetReached(Node s) {
798 reached.set(s, true);
803 DfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
805 actual_edge=dfs_stack.top();
806 //actual_node=G.aNode(actual_edge);
807 if (G.valid(actual_edge)/*.valid()*/) {
808 Node w=G.bNode(actual_edge);
810 if (!reached.get(w)) {
814 reached.set(w, true);
815 b_node_newly_reached=true;
817 actual_node=G.aNode(actual_edge);
818 /*++*/G.next(dfs_stack.top());
819 b_node_newly_reached=false;
822 //actual_node=G.aNode(dfs_stack.top());
827 bool finished() const { return dfs_stack.empty(); }
828 operator OutEdgeIt () const { return actual_edge; }
829 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
830 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
831 Node aNode() const { return actual_node; /*FIXME*/}
832 Node bNode() const { return G.bNode(actual_edge); }
833 const ReachedMap& getReachedMap() const { return reached; }
834 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
841 #endif //HUGO_BFS_ITERATOR_H