621 const ReachedMap& getReachedMap() const { return reached; } |
621 const ReachedMap& getReachedMap() const { return reached; } |
622 const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; } |
622 const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; } |
623 }; |
623 }; |
624 |
624 |
625 |
625 |
626 template <typename GraphWrapper, typename OutEdgeIt, |
626 template <typename GraphWrapper, /*typename OutEdgeIt,*/ |
627 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ > |
627 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ > |
628 class BfsIterator5 { |
628 class BfsIterator5 { |
629 typedef typename GraphWrapper::NodeIt NodeIt; |
629 typedef typename GraphWrapper::NodeIt NodeIt; |
|
630 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; |
630 GraphWrapper G; |
631 GraphWrapper G; |
631 std::queue<NodeIt> bfs_queue; |
632 std::queue<NodeIt> bfs_queue; |
632 ReachedMap& reached; |
633 ReachedMap& reached; |
633 bool b_node_newly_reached; |
634 bool b_node_newly_reached; |
634 OutEdgeIt actual_edge; |
635 OutEdgeIt actual_edge; |
638 G(_G), reached(_reached), |
639 G(_G), reached(_reached), |
639 own_reached_map(false) { } |
640 own_reached_map(false) { } |
640 BfsIterator5(const GraphWrapper& _G) : |
641 BfsIterator5(const GraphWrapper& _G) : |
641 G(_G), reached(*(new ReachedMap(G /*, false*/))), |
642 G(_G), reached(*(new ReachedMap(G /*, false*/))), |
642 own_reached_map(true) { } |
643 own_reached_map(true) { } |
|
644 // BfsIterator5(const typename GraphWrapper::BaseGraph& _G, |
|
645 // ReachedMap& _reached) : |
|
646 // G(_G), reached(_reached), |
|
647 // own_reached_map(false) { } |
|
648 // BfsIterator5(const typename GraphWrapper::BaseGraph& _G) : |
|
649 // G(_G), reached(*(new ReachedMap(G /*, false*/))), |
|
650 // own_reached_map(true) { } |
643 ~BfsIterator5() { if (own_reached_map) delete &reached; } |
651 ~BfsIterator5() { if (own_reached_map) delete &reached; } |
644 void pushAndSetReached(NodeIt s) { |
652 void pushAndSetReached(NodeIt s) { |
645 reached.set(s, true); |
653 reached.set(s, true); |
646 if (bfs_queue.empty()) { |
654 if (bfs_queue.empty()) { |
647 bfs_queue.push(s); |
655 bfs_queue.push(s); |
658 } |
666 } |
659 } else { |
667 } else { |
660 bfs_queue.push(s); |
668 bfs_queue.push(s); |
661 } |
669 } |
662 } |
670 } |
663 BfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>& |
671 BfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>& |
664 operator++() { |
672 operator++() { |
665 if (G.valid(actual_edge)/*.valid()*/) { |
673 if (G.valid(actual_edge)/*.valid()*/) { |
666 /*++*/G.next(actual_edge); |
674 /*++*/G.next(actual_edge); |
667 if (G.valid(actual_edge)/*.valid()*/) { |
675 if (G.valid(actual_edge)/*.valid()*/) { |
668 NodeIt w=G.bNode(actual_edge); |
676 NodeIt w=G.bNode(actual_edge); |
756 NodeIt bNode() const { return G.bNode(actual_edge); } |
764 NodeIt bNode() const { return G.bNode(actual_edge); } |
757 const ReachedMap& getReachedMap() const { return reached; } |
765 const ReachedMap& getReachedMap() const { return reached; } |
758 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } |
766 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } |
759 }; |
767 }; |
760 |
768 |
761 template <typename GraphWrapper, typename OutEdgeIt, |
769 template <typename GraphWrapper, /*typename OutEdgeIt,*/ |
762 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ > |
770 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ > |
763 class DfsIterator5 { |
771 class DfsIterator5 { |
764 typedef typename GraphWrapper::NodeIt NodeIt; |
772 typedef typename GraphWrapper::NodeIt NodeIt; |
|
773 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; |
765 GraphWrapper G; |
774 GraphWrapper G; |
766 std::stack<OutEdgeIt> dfs_stack; |
775 std::stack<OutEdgeIt> dfs_stack; |
767 bool b_node_newly_reached; |
776 bool b_node_newly_reached; |
768 OutEdgeIt actual_edge; |
777 OutEdgeIt actual_edge; |
769 NodeIt actual_node; |
778 NodeIt actual_node; |
780 void pushAndSetReached(NodeIt s) { |
789 void pushAndSetReached(NodeIt s) { |
781 actual_node=s; |
790 actual_node=s; |
782 reached.set(s, true); |
791 reached.set(s, true); |
783 dfs_stack.push(G.template first<OutEdgeIt>(s)); |
792 dfs_stack.push(G.template first<OutEdgeIt>(s)); |
784 } |
793 } |
785 DfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>& |
794 DfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>& |
786 operator++() { |
795 operator++() { |
787 actual_edge=dfs_stack.top(); |
796 actual_edge=dfs_stack.top(); |
788 //actual_node=G.aNode(actual_edge); |
797 //actual_node=G.aNode(actual_edge); |
789 if (G.valid(actual_edge)/*.valid()*/) { |
798 if (G.valid(actual_edge)/*.valid()*/) { |
790 NodeIt w=G.bNode(actual_edge); |
799 NodeIt w=G.bNode(actual_edge); |