628 // const ReachedMap& getReachedMap() const { return reached; } |
627 // const ReachedMap& getReachedMap() const { return reached; } |
629 // const std::queue<Node>& getBfsQueue() const { return bfs_queue; } |
628 // const std::queue<Node>& getBfsQueue() const { return bfs_queue; } |
630 // }; |
629 // }; |
631 |
630 |
632 |
631 |
633 template <typename GraphWrapper, /*typename OutEdgeIt,*/ |
632 template <typename Graph, /*typename OutEdgeIt,*/ |
634 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ > |
633 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
635 class BfsIterator5 { |
634 class BfsIterator5 { |
636 typedef typename GraphWrapper::Node Node; |
635 protected: |
637 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; |
636 typedef typename Graph::Node Node; |
638 GraphWrapper G; |
637 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
638 const Graph* graph; |
639 std::queue<Node> bfs_queue; |
639 std::queue<Node> bfs_queue; |
640 ReachedMap& reached; |
640 ReachedMap& reached; |
641 bool b_node_newly_reached; |
641 bool b_node_newly_reached; |
642 OutEdgeIt actual_edge; |
642 OutEdgeIt actual_edge; |
643 bool own_reached_map; |
643 bool own_reached_map; |
644 public: |
644 public: |
645 BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) : |
645 BfsIterator5(const Graph& _graph, ReachedMap& _reached) : |
646 G(_G), reached(_reached), |
646 graph(&_graph), reached(_reached), |
647 own_reached_map(false) { } |
647 own_reached_map(false) { } |
648 BfsIterator5(const GraphWrapper& _G) : |
648 BfsIterator5(const Graph& _graph) : |
649 G(_G), reached(*(new ReachedMap(G /*, false*/))), |
649 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), |
650 own_reached_map(true) { } |
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; } |
651 ~BfsIterator5() { if (own_reached_map) delete &reached; } |
659 void pushAndSetReached(Node s) { |
652 void pushAndSetReached(Node s) { |
660 reached.set(s, true); |
653 reached.set(s, true); |
661 if (bfs_queue.empty()) { |
654 if (bfs_queue.empty()) { |
662 bfs_queue.push(s); |
655 bfs_queue.push(s); |
663 G./*getF*/first(actual_edge, s); |
656 graph->first(actual_edge, s); |
664 if (G.valid(actual_edge)/*.valid()*/) { |
657 if (graph->valid(actual_edge)) { |
665 Node w=G.bNode(actual_edge); |
658 Node w=graph->bNode(actual_edge); |
666 if (!reached.get(w)) { |
659 if (!reached[w]) { |
667 bfs_queue.push(w); |
660 bfs_queue.push(w); |
668 reached.set(w, true); |
661 reached.set(w, true); |
669 b_node_newly_reached=true; |
662 b_node_newly_reached=true; |
670 } else { |
663 } else { |
671 b_node_newly_reached=false; |
664 b_node_newly_reached=false; |
673 } |
666 } |
674 } else { |
667 } else { |
675 bfs_queue.push(s); |
668 bfs_queue.push(s); |
676 } |
669 } |
677 } |
670 } |
678 BfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>& |
671 BfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>& |
679 operator++() { |
672 operator++() { |
680 if (G.valid(actual_edge)/*.valid()*/) { |
673 if (graph->valid(actual_edge)) { |
681 /*++*/G.next(actual_edge); |
674 graph->next(actual_edge); |
682 if (G.valid(actual_edge)/*.valid()*/) { |
675 if (graph->valid(actual_edge)) { |
683 Node w=G.bNode(actual_edge); |
676 Node w=graph->bNode(actual_edge); |
684 if (!reached.get(w)) { |
677 if (!reached[w]) { |
685 bfs_queue.push(w); |
678 bfs_queue.push(w); |
686 reached.set(w, true); |
679 reached.set(w, true); |
687 b_node_newly_reached=true; |
680 b_node_newly_reached=true; |
688 } else { |
681 } else { |
689 b_node_newly_reached=false; |
682 b_node_newly_reached=false; |
690 } |
683 } |
691 } |
684 } |
692 } else { |
685 } else { |
693 bfs_queue.pop(); |
686 bfs_queue.pop(); |
694 if (!bfs_queue.empty()) { |
687 if (!bfs_queue.empty()) { |
695 G./*getF*/first(actual_edge, bfs_queue.front()); |
688 graph->first(actual_edge, bfs_queue.front()); |
696 if (G.valid(actual_edge)/*.valid()*/) { |
689 if (graph->valid(actual_edge)) { |
697 Node w=G.bNode(actual_edge); |
690 Node w=graph->bNode(actual_edge); |
698 if (!reached.get(w)) { |
691 if (!reached[w]) { |
699 bfs_queue.push(w); |
692 bfs_queue.push(w); |
700 reached.set(w, true); |
693 reached.set(w, true); |
701 b_node_newly_reached=true; |
694 b_node_newly_reached=true; |
702 } else { |
695 } else { |
703 b_node_newly_reached=false; |
696 b_node_newly_reached=false; |
708 return *this; |
701 return *this; |
709 } |
702 } |
710 bool finished() const { return bfs_queue.empty(); } |
703 bool finished() const { return bfs_queue.empty(); } |
711 operator OutEdgeIt () const { return actual_edge; } |
704 operator OutEdgeIt () const { return actual_edge; } |
712 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
705 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
713 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } |
706 bool isANodeExamined() const { return !(graph->valid(actual_edge)); } |
714 Node aNode() const { return bfs_queue.front(); } |
707 Node aNode() const { return bfs_queue.front(); } |
715 Node bNode() const { return G.bNode(actual_edge); } |
708 Node bNode() const { return graph->bNode(actual_edge); } |
716 const ReachedMap& getReachedMap() const { return reached; } |
709 const ReachedMap& getReachedMap() const { return reached; } |
717 const std::queue<Node>& getBfsQueue() const { return bfs_queue; } |
710 const std::queue<Node>& getBfsQueue() const { return bfs_queue; } |
718 }; |
711 }; |
719 |
712 |
720 // template <typename Graph, typename OutEdgeIt, |
713 // template <typename Graph, typename OutEdgeIt, |
771 // Node bNode() const { return G.bNode(actual_edge); } |
764 // Node bNode() const { return G.bNode(actual_edge); } |
772 // const ReachedMap& getReachedMap() const { return reached; } |
765 // const ReachedMap& getReachedMap() const { return reached; } |
773 // const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } |
766 // const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } |
774 // }; |
767 // }; |
775 |
768 |
776 template <typename GraphWrapper, /*typename OutEdgeIt,*/ |
769 template <typename Graph, /*typename OutEdgeIt,*/ |
777 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ > |
770 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
778 class DfsIterator5 { |
771 class DfsIterator5 { |
779 typedef typename GraphWrapper::Node Node; |
772 protected: |
780 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; |
773 typedef typename Graph::Node Node; |
781 GraphWrapper G; |
774 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
775 const Graph* graph; |
782 std::stack<OutEdgeIt> dfs_stack; |
776 std::stack<OutEdgeIt> dfs_stack; |
783 bool b_node_newly_reached; |
777 bool b_node_newly_reached; |
784 OutEdgeIt actual_edge; |
778 OutEdgeIt actual_edge; |
785 Node actual_node; |
779 Node actual_node; |
786 ReachedMap& reached; |
780 ReachedMap& reached; |
787 bool own_reached_map; |
781 bool own_reached_map; |
788 public: |
782 public: |
789 DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) : |
783 DfsIterator5(const Graph& _graph, ReachedMap& _reached) : |
790 G(_G), reached(_reached), |
784 graph(&_graph), reached(_reached), |
791 own_reached_map(false) { } |
785 own_reached_map(false) { } |
792 DfsIterator5(const GraphWrapper& _G) : |
786 DfsIterator5(const Graph& _graph) : |
793 G(_G), reached(*(new ReachedMap(G /*, false*/))), |
787 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), |
794 own_reached_map(true) { } |
788 own_reached_map(true) { } |
795 ~DfsIterator5() { if (own_reached_map) delete &reached; } |
789 ~DfsIterator5() { if (own_reached_map) delete &reached; } |
796 void pushAndSetReached(Node s) { |
790 void pushAndSetReached(Node s) { |
797 actual_node=s; |
791 actual_node=s; |
798 reached.set(s, true); |
792 reached.set(s, true); |
799 OutEdgeIt e; |
793 OutEdgeIt e; |
800 G.first(e, s); |
794 graph->first(e, s); |
801 dfs_stack.push(e); |
795 dfs_stack.push(e); |
802 } |
796 } |
803 DfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>& |
797 DfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>& |
804 operator++() { |
798 operator++() { |
805 actual_edge=dfs_stack.top(); |
799 actual_edge=dfs_stack.top(); |
806 //actual_node=G.aNode(actual_edge); |
800 //actual_node=G.aNode(actual_edge); |
807 if (G.valid(actual_edge)/*.valid()*/) { |
801 if (graph->valid(actual_edge)/*.valid()*/) { |
808 Node w=G.bNode(actual_edge); |
802 Node w=graph->bNode(actual_edge); |
809 actual_node=w; |
803 actual_node=w; |
810 if (!reached.get(w)) { |
804 if (!reached[w]) { |
811 OutEdgeIt e; |
805 OutEdgeIt e; |
812 G.first(e, w); |
806 graph->first(e, w); |
813 dfs_stack.push(e); |
807 dfs_stack.push(e); |
814 reached.set(w, true); |
808 reached.set(w, true); |
815 b_node_newly_reached=true; |
809 b_node_newly_reached=true; |
816 } else { |
810 } else { |
817 actual_node=G.aNode(actual_edge); |
811 actual_node=graph->aNode(actual_edge); |
818 /*++*/G.next(dfs_stack.top()); |
812 graph->next(dfs_stack.top()); |
819 b_node_newly_reached=false; |
813 b_node_newly_reached=false; |
820 } |
814 } |
821 } else { |
815 } else { |
822 //actual_node=G.aNode(dfs_stack.top()); |
816 //actual_node=G.aNode(dfs_stack.top()); |
823 dfs_stack.pop(); |
817 dfs_stack.pop(); |
825 return *this; |
819 return *this; |
826 } |
820 } |
827 bool finished() const { return dfs_stack.empty(); } |
821 bool finished() const { return dfs_stack.empty(); } |
828 operator OutEdgeIt () const { return actual_edge; } |
822 operator OutEdgeIt () const { return actual_edge; } |
829 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
823 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
830 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } |
824 bool isANodeExamined() const { return !(graph->valid(actual_edge)); } |
831 Node aNode() const { return actual_node; /*FIXME*/} |
825 Node aNode() const { return actual_node; /*FIXME*/} |
832 Node bNode() const { return G.bNode(actual_edge); } |
826 Node bNode() const { return G.bNode(actual_edge); } |
833 const ReachedMap& getReachedMap() const { return reached; } |
827 const ReachedMap& getReachedMap() const { return reached; } |
834 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } |
828 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } |
835 }; |
829 }; |