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