613 return *this; |
613 return *this; |
614 } |
614 } |
615 bool finished() const { return bfs_queue.empty(); } |
615 bool finished() const { return bfs_queue.empty(); } |
616 operator OutEdgeIt () const { return actual_edge; } |
616 operator OutEdgeIt () const { return actual_edge; } |
617 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
617 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
618 bool isANodeExamined() const { return !(actual_edge.valid()); } |
618 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } |
619 NodeIt aNode() const { return bfs_queue.front(); } |
619 NodeIt aNode() const { return bfs_queue.front(); } |
620 NodeIt bNode() const { return G.bNode(actual_edge); } |
620 NodeIt bNode() const { return G.bNode(actual_edge); } |
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 |
|
626 template <typename GraphWrapper, typename OutEdgeIt, |
|
627 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ > |
|
628 class BfsIterator5 { |
|
629 typedef typename GraphWrapper::NodeIt NodeIt; |
|
630 GraphWrapper G; |
|
631 std::queue<NodeIt> bfs_queue; |
|
632 ReachedMap& reached; |
|
633 bool b_node_newly_reached; |
|
634 OutEdgeIt actual_edge; |
|
635 bool own_reached_map; |
|
636 public: |
|
637 BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) : |
|
638 G(_G), reached(_reached), |
|
639 own_reached_map(false) { } |
|
640 BfsIterator5(const GraphWrapper& _G) : |
|
641 G(_G), reached(*(new ReachedMap(G /*, false*/))), |
|
642 own_reached_map(true) { } |
|
643 ~BfsIterator5() { if (own_reached_map) delete &reached; } |
|
644 void pushAndSetReached(NodeIt s) { |
|
645 reached.set(s, true); |
|
646 if (bfs_queue.empty()) { |
|
647 bfs_queue.push(s); |
|
648 G.getFirst(actual_edge, s); |
|
649 if (G.valid(actual_edge)/*.valid()*/) { |
|
650 NodeIt w=G.bNode(actual_edge); |
|
651 if (!reached.get(w)) { |
|
652 bfs_queue.push(w); |
|
653 reached.set(w, true); |
|
654 b_node_newly_reached=true; |
|
655 } else { |
|
656 b_node_newly_reached=false; |
|
657 } |
|
658 } |
|
659 } else { |
|
660 bfs_queue.push(s); |
|
661 } |
|
662 } |
|
663 BfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>& |
|
664 operator++() { |
|
665 if (G.valid(actual_edge)/*.valid()*/) { |
|
666 /*++*/G.next(actual_edge); |
|
667 if (G.valid(actual_edge)/*.valid()*/) { |
|
668 NodeIt w=G.bNode(actual_edge); |
|
669 if (!reached.get(w)) { |
|
670 bfs_queue.push(w); |
|
671 reached.set(w, true); |
|
672 b_node_newly_reached=true; |
|
673 } else { |
|
674 b_node_newly_reached=false; |
|
675 } |
|
676 } |
|
677 } else { |
|
678 bfs_queue.pop(); |
|
679 if (!bfs_queue.empty()) { |
|
680 G.getFirst(actual_edge, bfs_queue.front()); |
|
681 if (G.valid(actual_edge)/*.valid()*/) { |
|
682 NodeIt w=G.bNode(actual_edge); |
|
683 if (!reached.get(w)) { |
|
684 bfs_queue.push(w); |
|
685 reached.set(w, true); |
|
686 b_node_newly_reached=true; |
|
687 } else { |
|
688 b_node_newly_reached=false; |
|
689 } |
|
690 } |
|
691 } |
|
692 } |
|
693 return *this; |
|
694 } |
|
695 bool finished() const { return bfs_queue.empty(); } |
|
696 operator OutEdgeIt () const { return actual_edge; } |
|
697 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
|
698 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } |
|
699 NodeIt aNode() const { return bfs_queue.front(); } |
|
700 NodeIt bNode() const { return G.bNode(actual_edge); } |
|
701 const ReachedMap& getReachedMap() const { return reached; } |
|
702 const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; } |
|
703 }; |
|
704 |
625 template <typename Graph, typename OutEdgeIt, |
705 template <typename Graph, typename OutEdgeIt, |
626 typename ReachedMap=typename Graph::NodeMap<bool> > |
706 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
627 class DfsIterator4 { |
707 class DfsIterator4 { |
628 typedef typename Graph::NodeIt NodeIt; |
708 typedef typename Graph::NodeIt NodeIt; |
629 const Graph& G; |
709 const Graph& G; |
630 std::stack<OutEdgeIt> dfs_stack; |
710 std::stack<OutEdgeIt> dfs_stack; |
631 bool b_node_newly_reached; |
711 bool b_node_newly_reached; |
648 } |
728 } |
649 DfsIterator4<Graph, OutEdgeIt, ReachedMap>& |
729 DfsIterator4<Graph, OutEdgeIt, ReachedMap>& |
650 operator++() { |
730 operator++() { |
651 actual_edge=dfs_stack.top(); |
731 actual_edge=dfs_stack.top(); |
652 //actual_node=G.aNode(actual_edge); |
732 //actual_node=G.aNode(actual_edge); |
653 if (actual_edge.valid()) { |
733 if (G.valid(actual_edge)/*.valid()*/) { |
654 NodeIt w=G.bNode(actual_edge); |
734 NodeIt w=G.bNode(actual_edge); |
655 actual_node=w; |
735 actual_node=w; |
656 if (!reached.get(w)) { |
736 if (!reached.get(w)) { |
657 dfs_stack.push(G.template first<OutEdgeIt>(w)); |
737 dfs_stack.push(G.template first<OutEdgeIt>(w)); |
658 reached.set(w, true); |
738 reached.set(w, true); |
659 b_node_newly_reached=true; |
739 b_node_newly_reached=true; |
660 } else { |
740 } else { |
661 actual_node=G.aNode(actual_edge); |
741 actual_node=G.aNode(actual_edge); |
662 ++(dfs_stack.top()); |
742 /*++*/G.next(dfs_stack.top()); |
663 b_node_newly_reached=false; |
743 b_node_newly_reached=false; |
664 } |
744 } |
665 } else { |
745 } else { |
666 //actual_node=G.aNode(dfs_stack.top()); |
746 //actual_node=G.aNode(dfs_stack.top()); |
667 dfs_stack.pop(); |
747 dfs_stack.pop(); |
669 return *this; |
749 return *this; |
670 } |
750 } |
671 bool finished() const { return dfs_stack.empty(); } |
751 bool finished() const { return dfs_stack.empty(); } |
672 operator OutEdgeIt () const { return actual_edge; } |
752 operator OutEdgeIt () const { return actual_edge; } |
673 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
753 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
674 bool isANodeExamined() const { return !(actual_edge.valid()); } |
754 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } |
675 NodeIt aNode() const { return actual_node; /*FIXME*/} |
755 NodeIt aNode() const { return actual_node; /*FIXME*/} |
676 NodeIt bNode() const { return G.bNode(actual_edge); } |
756 NodeIt bNode() const { return G.bNode(actual_edge); } |
677 const ReachedMap& getReachedMap() const { return reached; } |
757 const ReachedMap& getReachedMap() const { return reached; } |
678 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } |
758 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } |
679 }; |
759 }; |
680 |
760 |
681 |
761 template <typename GraphWrapper, typename OutEdgeIt, |
682 |
762 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ > |
683 template <typename GraphWrapper, typename ReachedMap> |
763 class DfsIterator5 { |
684 class BfsIterator5 { |
|
685 typedef typename GraphWrapper::NodeIt NodeIt; |
764 typedef typename GraphWrapper::NodeIt NodeIt; |
686 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; |
765 GraphWrapper G; |
687 GraphWrapper gw; |
766 std::stack<OutEdgeIt> dfs_stack; |
688 std::queue<NodeIt> bfs_queue; |
767 bool b_node_newly_reached; |
689 ReachedMap reached; |
768 OutEdgeIt actual_edge; |
690 bool b_node_newly_reached; |
769 NodeIt actual_node; |
691 OutEdgeIt actual_edge; |
770 ReachedMap& reached; |
|
771 bool own_reached_map; |
692 public: |
772 public: |
693 BfsIterator5(GraphWrapper _gw) : |
773 DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) : |
694 gw(_gw), reached(_gw.getGraph()) { } |
774 G(_G), reached(_reached), |
|
775 own_reached_map(false) { } |
|
776 DfsIterator5(const GraphWrapper& _G) : |
|
777 G(_G), reached(*(new ReachedMap(G /*, false*/))), |
|
778 own_reached_map(true) { } |
|
779 ~DfsIterator5() { if (own_reached_map) delete &reached; } |
695 void pushAndSetReached(NodeIt s) { |
780 void pushAndSetReached(NodeIt s) { |
|
781 actual_node=s; |
696 reached.set(s, true); |
782 reached.set(s, true); |
697 if (bfs_queue.empty()) { |
783 dfs_stack.push(G.template first<OutEdgeIt>(s)); |
698 bfs_queue.push(s); |
784 } |
699 gw.getFirst(actual_edge, s); |
785 DfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>& |
700 if (actual_edge.valid()) { |
|
701 NodeIt w=gw.bNode(actual_edge); |
|
702 if (!reached.get(w)) { |
|
703 bfs_queue.push(w); |
|
704 reached.set(w, true); |
|
705 b_node_newly_reached=true; |
|
706 } else { |
|
707 b_node_newly_reached=false; |
|
708 } |
|
709 } |
|
710 } else { |
|
711 bfs_queue.push(s); |
|
712 } |
|
713 } |
|
714 BfsIterator5<GraphWrapper, ReachedMap>& |
|
715 operator++() { |
786 operator++() { |
716 if (actual_edge.valid()) { |
787 actual_edge=dfs_stack.top(); |
717 ++actual_edge; |
788 //actual_node=G.aNode(actual_edge); |
718 if (actual_edge.valid()) { |
789 if (G.valid(actual_edge)/*.valid()*/) { |
719 NodeIt w=gw.bNode(actual_edge); |
790 NodeIt w=G.bNode(actual_edge); |
720 if (!reached.get(w)) { |
791 actual_node=w; |
721 bfs_queue.push(w); |
792 if (!reached.get(w)) { |
722 reached.set(w, true); |
793 dfs_stack.push(G.template first<OutEdgeIt>(w)); |
723 b_node_newly_reached=true; |
794 reached.set(w, true); |
724 } else { |
795 b_node_newly_reached=true; |
725 b_node_newly_reached=false; |
796 } else { |
726 } |
797 actual_node=G.aNode(actual_edge); |
727 } |
798 /*++*/G.next(dfs_stack.top()); |
728 } else { |
799 b_node_newly_reached=false; |
729 bfs_queue.pop(); |
800 } |
730 if (!bfs_queue.empty()) { |
801 } else { |
731 gw.getFirst(actual_edge, bfs_queue.front()); |
802 //actual_node=G.aNode(dfs_stack.top()); |
732 if (actual_edge.valid()) { |
803 dfs_stack.pop(); |
733 NodeIt w=gw.bNode(actual_edge); |
804 } |
734 if (!reached.get(w)) { |
805 return *this; |
735 bfs_queue.push(w); |
806 } |
736 reached.set(w, true); |
807 bool finished() const { return dfs_stack.empty(); } |
737 b_node_newly_reached=true; |
|
738 } else { |
|
739 b_node_newly_reached=false; |
|
740 } |
|
741 } |
|
742 } |
|
743 } |
|
744 return *this; |
|
745 } |
|
746 bool finished() const { return bfs_queue.empty(); } |
|
747 operator OutEdgeIt () const { return actual_edge; } |
808 operator OutEdgeIt () const { return actual_edge; } |
748 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
809 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
749 bool isANodeExamined() const { return !(actual_edge.valid()); } |
810 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } |
750 NodeIt aNode() const { return bfs_queue.front(); } |
811 NodeIt aNode() const { return actual_node; /*FIXME*/} |
751 NodeIt bNode() const { return gw.bNode(actual_edge); } |
812 NodeIt bNode() const { return G.bNode(actual_edge); } |
752 const ReachedMap& getReachedMap() const { return reached; } |
813 const ReachedMap& getReachedMap() const { return reached; } |
753 const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; } |
814 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } |
754 }; |
815 }; |
755 |
816 |
756 |
817 |
757 |
818 |
758 } // namespace hugo |
819 } // namespace hugo |
759 |
820 |