281 return *this; |
281 return *this; |
282 } |
282 } |
283 bool finished() { return bfs_queue.empty(); } |
283 bool finished() { return bfs_queue.empty(); } |
284 operator OutEdgeIt () { return actual_edge; } |
284 operator OutEdgeIt () { return actual_edge; } |
285 bool bNodeIsNewlyReached() { return b_node_newly_reached; } |
285 bool bNodeIsNewlyReached() { return b_node_newly_reached; } |
286 bool aNodeIsLeaved() { return !(actual_edge.valid()); } |
286 bool aNodeIsExamined() { return !(actual_edge.valid()); } |
287 }; |
287 }; |
288 |
288 |
289 template <typename Graph, typename OutEdgeIt, typename ReachedMap> |
289 template <typename Graph, typename OutEdgeIt, typename ReachedMap> |
290 struct BfsIterator1 { |
290 struct BfsIterator1 { |
291 typedef typename Graph::NodeIt NodeIt; |
291 typedef typename Graph::NodeIt NodeIt; |
612 const ReachedMap& getReachedMap() const { return reached; } |
612 const ReachedMap& getReachedMap() const { return reached; } |
613 const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; } |
613 const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; } |
614 }; |
614 }; |
615 |
615 |
616 |
616 |
|
617 template <typename Graph, typename OutEdgeIt, typename ReachedMap> |
|
618 struct DfsIterator4 { |
|
619 typedef typename Graph::NodeIt NodeIt; |
|
620 const Graph& G; |
|
621 std::stack<OutEdgeIt> dfs_stack; |
|
622 //ReachedMap& reached; |
|
623 bool b_node_newly_reached; |
|
624 OutEdgeIt actual_edge; |
|
625 NodeIt actual_node; |
|
626 ReachedMap reached; |
|
627 DfsIterator4(const Graph& _G |
|
628 /*, std::stack<OutEdgeIt>& _bfs_queue, |
|
629 ReachedMap& _reached*/) : |
|
630 G(_G), reached(G, false) /*, bfs_queue(_bfs_queue), reached(_reached)*/ { |
|
631 //actual_edge=bfs_queue.top(); |
|
632 //if (actual_edge.valid()) { |
|
633 // NodeIt w=G.bNode(actual_edge); |
|
634 //if (!reached.get(w)) { |
|
635 // bfs_queue.push(OutEdgeIt(G, w)); |
|
636 // reached.set(w, true); |
|
637 // b_node_newly_reached=true; |
|
638 //} else { |
|
639 // ++(bfs_queue.top()); |
|
640 // b_node_newly_reached=false; |
|
641 //} |
|
642 //} else { |
|
643 // bfs_queue.pop(); |
|
644 //} |
|
645 } |
|
646 void pushAndSetReached(NodeIt s) { |
|
647 reached.set(s, true); |
|
648 dfs_stack.push(G.template first<OutEdgeIt>(s)); |
|
649 } |
|
650 DfsIterator4<Graph, OutEdgeIt, ReachedMap>& |
|
651 operator++() { |
|
652 actual_edge=dfs_stack.top(); |
|
653 //actual_node=G.aNode(actual_edge); |
|
654 if (actual_edge.valid()) { |
|
655 NodeIt w=G.bNode(actual_edge); |
|
656 actual_node=w; |
|
657 if (!reached.get(w)) { |
|
658 dfs_stack.push(G.template first<OutEdgeIt>(w)); |
|
659 reached.set(w, true); |
|
660 b_node_newly_reached=true; |
|
661 } else { |
|
662 ++(dfs_stack.top()); |
|
663 b_node_newly_reached=false; |
|
664 } |
|
665 } else { |
|
666 //actual_node=G.aNode(dfs_stack.top()); |
|
667 dfs_stack.pop(); |
|
668 } |
|
669 return *this; |
|
670 } |
|
671 bool finished() const { return dfs_stack.empty(); } |
|
672 operator OutEdgeIt () const { return actual_edge; } |
|
673 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
|
674 bool isANodeExamined() const { return !(actual_edge.valid()); } |
|
675 NodeIt aNode() const { return actual_node; } |
|
676 NodeIt bNode() const { return G.bNode(actual_edge); } |
|
677 const ReachedMap& getReachedMap() const { return reached; } |
|
678 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } |
|
679 }; |
|
680 |
|
681 |
|
682 |
617 template <typename GraphWrapper, typename ReachedMap> |
683 template <typename GraphWrapper, typename ReachedMap> |
618 class BfsIterator5 { |
684 class BfsIterator5 { |
619 typedef typename GraphWrapper::NodeIt NodeIt; |
685 typedef typename GraphWrapper::NodeIt NodeIt; |
620 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; |
686 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; |
621 GraphWrapper gw; |
687 GraphWrapper gw; |