Aprosagok...
1 #ifndef BFS_ITERATOR_HH
2 #define BFS_ITERATOR_HH
7 #include <graph_wrapper.h>
11 template <typename Graph>
13 typedef typename Graph::NodeIt NodeIt;
14 typedef typename Graph::EdgeIt EdgeIt;
15 typedef typename Graph::EachNodeIt EachNodeIt;
16 typedef typename Graph::OutEdgeIt OutEdgeIt;
19 typename Graph::NodeMap<bool> reached;
20 typename Graph::NodeMap<EdgeIt> pred;
21 typename Graph::NodeMap<int> dist;
22 std::queue<NodeIt> bfs_queue;
23 bfs(Graph& _G, NodeIt _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {
25 for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i)
26 reached.set(i, false);
32 while (!bfs_queue.empty()) {
33 NodeIt v=bfs_queue.front();
34 OutEdgeIt e=G.template first<OutEdgeIt>(v);
36 for( ; e.valid(); ++e) {
38 std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
39 if (!reached.get(w)) {
40 std::cout << G.id(w) << " is newly reached :-)" << std::endl;
42 dist.set(w, dist.get(v)+1);
46 std::cout << G.id(w) << " is already reached" << std::endl;
53 template <typename Graph>
55 typedef typename Graph::NodeIt NodeIt;
56 typedef typename Graph::EdgeIt EdgeIt;
57 typedef typename Graph::OutEdgeIt OutEdgeIt;
59 bfs_visitor(Graph& _G) : G(_G) { }
60 void at_previously_reached(OutEdgeIt& e) {
61 //NodeIt v=G.aNode(e);
63 std::cout << G.id(w) << " is already reached" << std::endl;
65 void at_newly_reached(OutEdgeIt& e) {
66 //NodeIt v=G.aNode(e);
68 std::cout << G.id(w) << " is newly reached :-)" << std::endl;
72 template <typename Graph, typename ReachedMap, typename visitor_type>
74 typedef typename Graph::NodeIt NodeIt;
75 typedef typename Graph::EdgeIt EdgeIt;
76 typedef typename Graph::OutEdgeIt OutEdgeIt;
78 std::queue<OutEdgeIt>& bfs_queue;
80 visitor_type& visitor;
82 while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
83 if (bfs_queue.empty()) return;
84 OutEdgeIt e=bfs_queue.front();
85 //NodeIt v=G.aNode(e);
87 if (!reached.get(w)) {
88 visitor.at_newly_reached(e);
89 bfs_queue.push(G.template first<OutEdgeIt>(w));
92 visitor.at_previously_reached(e);
95 bfs_iterator(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) {
96 //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
99 bfs_iterator<Graph, ReachedMap, visitor_type>& operator++() {
100 //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
101 //if (bfs_queue.empty()) return *this;
102 if (!valid()) return *this;
103 ++(bfs_queue.front());
104 //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
109 // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
110 // if (bfs_queue.empty()) return;
111 // ++(bfs_queue.front());
112 // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
115 while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
116 if (bfs_queue.empty()) return false; else return true;
119 // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
120 // if (bfs_queue.empty()) return true; else return false;
122 operator EdgeIt () { return bfs_queue.front(); }
126 template <typename Graph, typename ReachedMap>
127 struct bfs_iterator1 {
128 typedef typename Graph::NodeIt NodeIt;
129 typedef typename Graph::EdgeIt EdgeIt;
130 typedef typename Graph::OutEdgeIt OutEdgeIt;
132 std::queue<OutEdgeIt>& bfs_queue;
135 bfs_iterator1(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) {
137 if (!bfs_queue.empty() && bfs_queue.front().valid()) {
138 OutEdgeIt e=bfs_queue.front();
140 if (!reached.get(w)) {
141 bfs_queue.push(G.template first<OutEdgeIt>(w));
142 reached.set(w, true);
145 _newly_reached=false;
149 bfs_iterator1<Graph, ReachedMap>& operator++() {
150 if (!valid()) return *this;
151 ++(bfs_queue.front());
153 if (!bfs_queue.empty() && bfs_queue.front().valid()) {
154 OutEdgeIt e=bfs_queue.front();
156 if (!reached.get(w)) {
157 bfs_queue.push(G.template first<OutEdgeIt>(w));
158 reached.set(w, true);
161 _newly_reached=false;
167 while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
168 if (bfs_queue.empty()) return false; else return true;
170 operator OutEdgeIt() { return bfs_queue.front(); }
172 bool newly_reached() { return _newly_reached; }
176 template <typename Graph, typename OutEdgeIt, typename ReachedMap>
178 typedef typename Graph::NodeIt NodeIt;
180 std::queue<OutEdgeIt>& bfs_queue;
182 bool b_node_newly_reached;
183 OutEdgeIt actual_edge;
184 BfsIterator(Graph& _G,
185 std::queue<OutEdgeIt>& _bfs_queue,
186 ReachedMap& _reached) :
187 G(_G), bfs_queue(_bfs_queue), reached(_reached) {
188 actual_edge=bfs_queue.front();
189 if (actual_edge.valid()) {
190 NodeIt w=G.bNode(actual_edge);
191 if (!reached.get(w)) {
192 bfs_queue.push(G.firstOutEdge(w));
193 reached.set(w, true);
194 b_node_newly_reached=true;
196 b_node_newly_reached=false;
200 BfsIterator<Graph, OutEdgeIt, ReachedMap>&
202 if (bfs_queue.front().valid()) {
203 ++(bfs_queue.front());
204 actual_edge=bfs_queue.front();
205 if (actual_edge.valid()) {
206 NodeIt w=G.bNode(actual_edge);
207 if (!reached.get(w)) {
208 bfs_queue.push(G.firstOutEdge(w));
209 reached.set(w, true);
210 b_node_newly_reached=true;
212 b_node_newly_reached=false;
217 actual_edge=bfs_queue.front();
218 if (actual_edge.valid()) {
219 NodeIt w=G.bNode(actual_edge);
220 if (!reached.get(w)) {
221 bfs_queue.push(G.firstOutEdge(w));
222 reached.set(w, true);
223 b_node_newly_reached=true;
225 b_node_newly_reached=false;
231 bool finished() { return bfs_queue.empty(); }
232 operator OutEdgeIt () { return actual_edge; }
233 bool bNodeIsNewlyReached() { return b_node_newly_reached; }
234 bool aNodeIsExamined() { return !(actual_edge.valid()); }
238 template <typename Graph, typename OutEdgeIt, typename ReachedMap>
240 typedef typename Graph::NodeIt NodeIt;
242 std::stack<OutEdgeIt>& bfs_queue;
244 bool b_node_newly_reached;
245 OutEdgeIt actual_edge;
246 DfsIterator(Graph& _G,
247 std::stack<OutEdgeIt>& _bfs_queue,
248 ReachedMap& _reached) :
249 G(_G), bfs_queue(_bfs_queue), reached(_reached) {
250 actual_edge=bfs_queue.top();
251 if (actual_edge.valid()) {
252 NodeIt w=G.bNode(actual_edge);
253 if (!reached.get(w)) {
254 bfs_queue.push(G.firstOutEdge(w));
255 reached.set(w, true);
256 b_node_newly_reached=true;
259 b_node_newly_reached=false;
265 DfsIterator<Graph, OutEdgeIt, ReachedMap>&
267 actual_edge=bfs_queue.top();
268 if (actual_edge.valid()) {
269 NodeIt w=G.bNode(actual_edge);
270 if (!reached.get(w)) {
271 bfs_queue.push(G.firstOutEdge(w));
272 reached.set(w, true);
273 b_node_newly_reached=true;
276 b_node_newly_reached=false;
283 bool finished() { return bfs_queue.empty(); }
284 operator OutEdgeIt () { return actual_edge; }
285 bool bNodeIsNewlyReached() { return b_node_newly_reached; }
286 bool aNodeIsExamined() { return !(actual_edge.valid()); }
289 template <typename Graph, typename OutEdgeIt, typename ReachedMap>
290 struct BfsIterator1 {
291 typedef typename Graph::NodeIt NodeIt;
293 std::queue<OutEdgeIt>& bfs_queue;
295 bool b_node_newly_reached;
296 OutEdgeIt actual_edge;
297 BfsIterator1(Graph& _G,
298 std::queue<OutEdgeIt>& _bfs_queue,
299 ReachedMap& _reached) :
300 G(_G), bfs_queue(_bfs_queue), reached(_reached) {
301 actual_edge=bfs_queue.front();
302 if (actual_edge.valid()) {
303 NodeIt w=G.bNode(actual_edge);
304 if (!reached.get(w)) {
305 bfs_queue.push(OutEdgeIt(G, w));
306 reached.set(w, true);
307 b_node_newly_reached=true;
309 b_node_newly_reached=false;
314 if (bfs_queue.front().valid()) {
315 ++(bfs_queue.front());
316 actual_edge=bfs_queue.front();
317 if (actual_edge.valid()) {
318 NodeIt w=G.bNode(actual_edge);
319 if (!reached.get(w)) {
320 bfs_queue.push(OutEdgeIt(G, w));
321 reached.set(w, true);
322 b_node_newly_reached=true;
324 b_node_newly_reached=false;
329 actual_edge=bfs_queue.front();
330 if (actual_edge.valid()) {
331 NodeIt w=G.bNode(actual_edge);
332 if (!reached.get(w)) {
333 bfs_queue.push(OutEdgeIt(G, w));
334 reached.set(w, true);
335 b_node_newly_reached=true;
337 b_node_newly_reached=false;
343 bool finished() { return bfs_queue.empty(); }
344 operator OutEdgeIt () { return actual_edge; }
345 bool bNodeIsNewlyReached() { return b_node_newly_reached; }
346 bool aNodeIsExamined() { return !(actual_edge.valid()); }
350 template <typename Graph, typename OutEdgeIt, typename ReachedMap>
351 struct DfsIterator1 {
352 typedef typename Graph::NodeIt NodeIt;
354 std::stack<OutEdgeIt>& bfs_queue;
356 bool b_node_newly_reached;
357 OutEdgeIt actual_edge;
358 DfsIterator1(Graph& _G,
359 std::stack<OutEdgeIt>& _bfs_queue,
360 ReachedMap& _reached) :
361 G(_G), bfs_queue(_bfs_queue), reached(_reached) {
362 //actual_edge=bfs_queue.top();
363 //if (actual_edge.valid()) {
364 // NodeIt w=G.bNode(actual_edge);
365 //if (!reached.get(w)) {
366 // bfs_queue.push(OutEdgeIt(G, w));
367 // reached.set(w, true);
368 // b_node_newly_reached=true;
370 // ++(bfs_queue.top());
371 // b_node_newly_reached=false;
378 actual_edge=bfs_queue.top();
379 if (actual_edge.valid()) {
380 NodeIt w=G.bNode(actual_edge);
381 if (!reached.get(w)) {
382 bfs_queue.push(OutEdgeIt(G, w));
383 reached.set(w, true);
384 b_node_newly_reached=true;
387 b_node_newly_reached=false;
394 bool finished() { return bfs_queue.empty(); }
395 operator OutEdgeIt () { return actual_edge; }
396 bool bNodeIsNewlyReached() { return b_node_newly_reached; }
397 bool aNodeIsLeaved() { return !(actual_edge.valid()); }
400 template <typename Graph, typename OutEdgeIt, typename ReachedMap>
402 typedef typename Graph::NodeIt NodeIt;
404 std::queue<OutEdgeIt> bfs_queue;
406 bool b_node_newly_reached;
407 OutEdgeIt actual_edge;
409 BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { }
410 void pushAndSetReached(NodeIt s) {
411 reached.set(s, true);
412 if (bfs_queue.empty()) {
413 bfs_queue.push(G.template first<OutEdgeIt>(s));
414 actual_edge=bfs_queue.front();
415 if (actual_edge.valid()) {
416 NodeIt w=G.bNode(actual_edge);
417 if (!reached.get(w)) {
418 bfs_queue.push(G.template first<OutEdgeIt>(w));
419 reached.set(w, true);
420 b_node_newly_reached=true;
422 b_node_newly_reached=false;
427 bfs_queue.push(G.template first<OutEdgeIt>(s));
430 BfsIterator2<Graph, OutEdgeIt, ReachedMap>&
432 if (bfs_queue.front().valid()) {
433 ++(bfs_queue.front());
434 actual_edge=bfs_queue.front();
435 if (actual_edge.valid()) {
436 NodeIt w=G.bNode(actual_edge);
437 if (!reached.get(w)) {
438 bfs_queue.push(G.template first<OutEdgeIt>(w));
439 reached.set(w, true);
440 b_node_newly_reached=true;
442 b_node_newly_reached=false;
447 if (!bfs_queue.empty()) {
448 actual_edge=bfs_queue.front();
449 if (actual_edge.valid()) {
450 NodeIt w=G.bNode(actual_edge);
451 if (!reached.get(w)) {
452 bfs_queue.push(G.template first<OutEdgeIt>(w));
453 reached.set(w, true);
454 b_node_newly_reached=true;
456 b_node_newly_reached=false;
463 bool finished() const { return bfs_queue.empty(); }
464 operator OutEdgeIt () const { return actual_edge; }
465 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
466 bool isANodeExamined() const { return !(actual_edge.valid()); }
467 const ReachedMap& getReachedMap() const { return reached; }
468 const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; }
472 template <typename Graph, typename OutEdgeIt, typename ReachedMap>
474 typedef typename Graph::NodeIt NodeIt;
476 std::queue< std::pair<NodeIt, OutEdgeIt> > bfs_queue;
478 bool b_node_newly_reached;
479 OutEdgeIt actual_edge;
481 BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { }
482 void pushAndSetReached(NodeIt s) {
483 reached.set(s, true);
484 if (bfs_queue.empty()) {
485 bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
486 actual_edge=bfs_queue.front().second;
487 if (actual_edge.valid()) {
488 NodeIt w=G.bNode(actual_edge);
489 if (!reached.get(w)) {
490 bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
491 reached.set(w, true);
492 b_node_newly_reached=true;
494 b_node_newly_reached=false;
499 bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(s, G.template first<OutEdgeIt>(s)));
502 BfsIterator3<Graph, OutEdgeIt, ReachedMap>&
504 if (bfs_queue.front().second.valid()) {
505 ++(bfs_queue.front().second);
506 actual_edge=bfs_queue.front().second;
507 if (actual_edge.valid()) {
508 NodeIt w=G.bNode(actual_edge);
509 if (!reached.get(w)) {
510 bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
511 reached.set(w, true);
512 b_node_newly_reached=true;
514 b_node_newly_reached=false;
519 if (!bfs_queue.empty()) {
520 actual_edge=bfs_queue.front().second;
521 if (actual_edge.valid()) {
522 NodeIt w=G.bNode(actual_edge);
523 if (!reached.get(w)) {
524 bfs_queue.push(std::pair<NodeIt, OutEdgeIt>(w, G.template first<OutEdgeIt>(w)));
525 reached.set(w, true);
526 b_node_newly_reached=true;
528 b_node_newly_reached=false;
535 bool finished() const { return bfs_queue.empty(); }
536 operator OutEdgeIt () const { return actual_edge; }
537 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
538 bool isANodeExamined() const { return !(actual_edge.valid()); }
539 NodeIt aNode() const { return bfs_queue.front().first; }
540 NodeIt bNode() const { return G.bNode(actual_edge); }
541 const ReachedMap& getReachedMap() const { return reached; }
542 //const std::queue< std::pair<NodeIt, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; }
546 template <typename Graph, typename OutEdgeIt,
547 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
549 typedef typename Graph::NodeIt NodeIt;
551 std::queue<NodeIt> bfs_queue;
553 bool b_node_newly_reached;
554 OutEdgeIt actual_edge;
555 bool own_reached_map;
557 BfsIterator4(const Graph& _G, ReachedMap& _reached) :
558 G(_G), reached(_reached),
559 own_reached_map(false) { }
560 BfsIterator4(const Graph& _G) :
561 G(_G), reached(*(new ReachedMap(G /*, false*/))),
562 own_reached_map(true) { }
563 ~BfsIterator4() { if (own_reached_map) delete &reached; }
564 void pushAndSetReached(NodeIt s) {
565 //std::cout << "mimi" << &reached << std::endl;
566 reached.set(s, true);
567 //std::cout << "mumus" << std::endl;
568 if (bfs_queue.empty()) {
569 //std::cout << "bibi1" << std::endl;
571 //std::cout << "zizi" << std::endl;
572 G.getFirst(actual_edge, s);
573 //std::cout << "kiki" << std::endl;
574 if (G.valid(actual_edge)/*.valid()*/) {
575 NodeIt w=G.bNode(actual_edge);
576 if (!reached.get(w)) {
578 reached.set(w, true);
579 b_node_newly_reached=true;
581 b_node_newly_reached=false;
585 //std::cout << "bibi2" << std::endl;
589 BfsIterator4<Graph, OutEdgeIt, ReachedMap>&
591 if (G.valid(actual_edge)/*.valid()*/) {
592 /*++*/G.next(actual_edge);
593 if (G.valid(actual_edge)/*.valid()*/) {
594 NodeIt w=G.bNode(actual_edge);
595 if (!reached.get(w)) {
597 reached.set(w, true);
598 b_node_newly_reached=true;
600 b_node_newly_reached=false;
605 if (!bfs_queue.empty()) {
606 G.getFirst(actual_edge, bfs_queue.front());
607 if (G.valid(actual_edge)/*.valid()*/) {
608 NodeIt w=G.bNode(actual_edge);
609 if (!reached.get(w)) {
611 reached.set(w, true);
612 b_node_newly_reached=true;
614 b_node_newly_reached=false;
621 bool finished() const { return bfs_queue.empty(); }
622 operator OutEdgeIt () const { return actual_edge; }
623 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
624 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
625 NodeIt aNode() const { return bfs_queue.front(); }
626 NodeIt bNode() const { return G.bNode(actual_edge); }
627 const ReachedMap& getReachedMap() const { return reached; }
628 const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
632 template <typename GraphWrapper, /*typename OutEdgeIt,*/
633 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
635 typedef typename GraphWrapper::NodeIt NodeIt;
636 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
638 std::queue<NodeIt> bfs_queue;
640 bool b_node_newly_reached;
641 OutEdgeIt actual_edge;
642 bool own_reached_map;
644 BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
645 G(_G), reached(_reached),
646 own_reached_map(false) { }
647 BfsIterator5(const GraphWrapper& _G) :
648 G(_G), reached(*(new ReachedMap(G /*, false*/))),
649 own_reached_map(true) { }
650 // BfsIterator5(const typename GraphWrapper::BaseGraph& _G,
651 // ReachedMap& _reached) :
652 // G(_G), reached(_reached),
653 // own_reached_map(false) { }
654 // BfsIterator5(const typename GraphWrapper::BaseGraph& _G) :
655 // G(_G), reached(*(new ReachedMap(G /*, false*/))),
656 // own_reached_map(true) { }
657 ~BfsIterator5() { if (own_reached_map) delete &reached; }
658 void pushAndSetReached(NodeIt s) {
659 reached.set(s, true);
660 if (bfs_queue.empty()) {
662 G.getFirst(actual_edge, s);
663 if (G.valid(actual_edge)/*.valid()*/) {
664 NodeIt w=G.bNode(actual_edge);
665 if (!reached.get(w)) {
667 reached.set(w, true);
668 b_node_newly_reached=true;
670 b_node_newly_reached=false;
677 BfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
679 if (G.valid(actual_edge)/*.valid()*/) {
680 /*++*/G.next(actual_edge);
681 if (G.valid(actual_edge)/*.valid()*/) {
682 NodeIt w=G.bNode(actual_edge);
683 if (!reached.get(w)) {
685 reached.set(w, true);
686 b_node_newly_reached=true;
688 b_node_newly_reached=false;
693 if (!bfs_queue.empty()) {
694 G.getFirst(actual_edge, bfs_queue.front());
695 if (G.valid(actual_edge)/*.valid()*/) {
696 NodeIt w=G.bNode(actual_edge);
697 if (!reached.get(w)) {
699 reached.set(w, true);
700 b_node_newly_reached=true;
702 b_node_newly_reached=false;
709 bool finished() const { return bfs_queue.empty(); }
710 operator OutEdgeIt () const { return actual_edge; }
711 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
712 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
713 NodeIt aNode() const { return bfs_queue.front(); }
714 NodeIt bNode() const { return G.bNode(actual_edge); }
715 const ReachedMap& getReachedMap() const { return reached; }
716 const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; }
719 template <typename Graph, typename OutEdgeIt,
720 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ >
722 typedef typename Graph::NodeIt NodeIt;
724 std::stack<OutEdgeIt> dfs_stack;
725 bool b_node_newly_reached;
726 OutEdgeIt actual_edge;
729 bool own_reached_map;
731 DfsIterator4(const Graph& _G, ReachedMap& _reached) :
732 G(_G), reached(_reached),
733 own_reached_map(false) { }
734 DfsIterator4(const Graph& _G) :
735 G(_G), reached(*(new ReachedMap(G /*, false*/))),
736 own_reached_map(true) { }
737 ~DfsIterator4() { if (own_reached_map) delete &reached; }
738 void pushAndSetReached(NodeIt s) {
740 reached.set(s, true);
741 dfs_stack.push(G.template first<OutEdgeIt>(s));
743 DfsIterator4<Graph, OutEdgeIt, ReachedMap>&
745 actual_edge=dfs_stack.top();
746 //actual_node=G.aNode(actual_edge);
747 if (G.valid(actual_edge)/*.valid()*/) {
748 NodeIt w=G.bNode(actual_edge);
750 if (!reached.get(w)) {
751 dfs_stack.push(G.template first<OutEdgeIt>(w));
752 reached.set(w, true);
753 b_node_newly_reached=true;
755 actual_node=G.aNode(actual_edge);
756 /*++*/G.next(dfs_stack.top());
757 b_node_newly_reached=false;
760 //actual_node=G.aNode(dfs_stack.top());
765 bool finished() const { return dfs_stack.empty(); }
766 operator OutEdgeIt () const { return actual_edge; }
767 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
768 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
769 NodeIt aNode() const { return actual_node; /*FIXME*/}
770 NodeIt bNode() const { return G.bNode(actual_edge); }
771 const ReachedMap& getReachedMap() const { return reached; }
772 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
775 template <typename GraphWrapper, /*typename OutEdgeIt,*/
776 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ >
778 typedef typename GraphWrapper::NodeIt NodeIt;
779 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
781 std::stack<OutEdgeIt> dfs_stack;
782 bool b_node_newly_reached;
783 OutEdgeIt actual_edge;
786 bool own_reached_map;
788 DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) :
789 G(_G), reached(_reached),
790 own_reached_map(false) { }
791 DfsIterator5(const GraphWrapper& _G) :
792 G(_G), reached(*(new ReachedMap(G /*, false*/))),
793 own_reached_map(true) { }
794 ~DfsIterator5() { if (own_reached_map) delete &reached; }
795 void pushAndSetReached(NodeIt s) {
797 reached.set(s, true);
798 dfs_stack.push(G.template first<OutEdgeIt>(s));
800 DfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>&
802 actual_edge=dfs_stack.top();
803 //actual_node=G.aNode(actual_edge);
804 if (G.valid(actual_edge)/*.valid()*/) {
805 NodeIt w=G.bNode(actual_edge);
807 if (!reached.get(w)) {
808 dfs_stack.push(G.template first<OutEdgeIt>(w));
809 reached.set(w, true);
810 b_node_newly_reached=true;
812 actual_node=G.aNode(actual_edge);
813 /*++*/G.next(dfs_stack.top());
814 b_node_newly_reached=false;
817 //actual_node=G.aNode(dfs_stack.top());
822 bool finished() const { return dfs_stack.empty(); }
823 operator OutEdgeIt () const { return actual_edge; }
824 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
825 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); }
826 NodeIt aNode() const { return actual_node; /*FIXME*/}
827 NodeIt bNode() const { return G.bNode(actual_edge); }
828 const ReachedMap& getReachedMap() const { return reached; }
829 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; }
836 #endif //BFS_ITERATOR_HH