Changeset 148:004fdf703abb in lemon0.x for src/work/bfs_iterator.hh
 Timestamp:
 03/03/04 15:30:38 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@208
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/bfs_iterator.hh
r144 r148 545 545 546 546 template <typename Graph, typename OutEdgeIt, 547 typename ReachedMap =typename Graph::NodeMap<bool>>547 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > 548 548 class BfsIterator4 { 549 549 typedef typename Graph::NodeIt NodeIt; … … 567 567 bfs_queue.push(s); 568 568 G.getFirst(actual_edge, s); 569 if ( actual_edge.valid()) {569 if (G.valid(actual_edge)/*.valid()*/) { 570 570 NodeIt w=G.bNode(actual_edge); 571 571 if (!reached.get(w)) { … … 583 583 BfsIterator4<Graph, OutEdgeIt, ReachedMap>& 584 584 operator++() { 585 if ( actual_edge.valid()) {586 ++actual_edge;587 if ( actual_edge.valid()) {585 if (G.valid(actual_edge)/*.valid()*/) { 586 /*++*/G.next(actual_edge); 587 if (G.valid(actual_edge)/*.valid()*/) { 588 588 NodeIt w=G.bNode(actual_edge); 589 589 if (!reached.get(w)) { … … 599 599 if (!bfs_queue.empty()) { 600 600 G.getFirst(actual_edge, bfs_queue.front()); 601 if ( actual_edge.valid()) {601 if (G.valid(actual_edge)/*.valid()*/) { 602 602 NodeIt w=G.bNode(actual_edge); 603 603 if (!reached.get(w)) { … … 616 616 operator OutEdgeIt () const { return actual_edge; } 617 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 619 NodeIt aNode() const { return bfs_queue.front(); } 620 620 NodeIt bNode() const { return G.bNode(actual_edge); } … … 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 705 template <typename Graph, typename OutEdgeIt, 626 typename ReachedMap =typename Graph::NodeMap<bool>>706 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > 627 707 class DfsIterator4 { 628 708 typedef typename Graph::NodeIt NodeIt; … … 651 731 actual_edge=dfs_stack.top(); 652 732 //actual_node=G.aNode(actual_edge); 653 if ( actual_edge.valid()) {733 if (G.valid(actual_edge)/*.valid()*/) { 654 734 NodeIt w=G.bNode(actual_edge); 655 735 actual_node=w; … … 660 740 } else { 661 741 actual_node=G.aNode(actual_edge); 662 ++(dfs_stack.top());742 /*++*/G.next(dfs_stack.top()); 663 743 b_node_newly_reached=false; 664 744 } … … 672 752 operator OutEdgeIt () const { return actual_edge; } 673 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 755 NodeIt aNode() const { return actual_node; /*FIXME*/} 676 756 NodeIt bNode() const { return G.bNode(actual_edge); } … … 679 759 }; 680 760 681 682 683 template <typename GraphWrapper, typename ReachedMap> 684 class BfsIterator5 { 761 template <typename GraphWrapper, typename OutEdgeIt, 762 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ > 763 class DfsIterator5 { 685 764 typedef typename GraphWrapper::NodeIt NodeIt; 686 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; 687 GraphWrapper gw; 688 std::queue<NodeIt> bfs_queue; 689 ReachedMap reached; 690 bool b_node_newly_reached; 691 OutEdgeIt actual_edge; 765 GraphWrapper G; 766 std::stack<OutEdgeIt> dfs_stack; 767 bool b_node_newly_reached; 768 OutEdgeIt actual_edge; 769 NodeIt actual_node; 770 ReachedMap& reached; 771 bool own_reached_map; 692 772 public: 693 BfsIterator5(GraphWrapper _gw) : 694 gw(_gw), reached(_gw.getGraph()) { } 773 DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) : 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 780 void pushAndSetReached(NodeIt s) { 781 actual_node=s; 696 782 reached.set(s, true); 697 if (bfs_queue.empty()) { 698 bfs_queue.push(s); 699 gw.getFirst(actual_edge, s); 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>& 783 dfs_stack.push(G.template first<OutEdgeIt>(s)); 784 } 785 DfsIterator5<GraphWrapper, OutEdgeIt, ReachedMap>& 715 786 operator++() { 716 if (actual_edge.valid()) { 717 ++actual_edge; 718 if (actual_edge.valid()) { 719 NodeIt w=gw.bNode(actual_edge); 720 if (!reached.get(w)) { 721 bfs_queue.push(w); 722 reached.set(w, true); 723 b_node_newly_reached=true; 724 } else { 725 b_node_newly_reached=false; 726 } 727 } 728 } else { 729 bfs_queue.pop(); 730 if (!bfs_queue.empty()) { 731 gw.getFirst(actual_edge, bfs_queue.front()); 732 if (actual_edge.valid()) { 733 NodeIt w=gw.bNode(actual_edge); 734 if (!reached.get(w)) { 735 bfs_queue.push(w); 736 reached.set(w, true); 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(); } 787 actual_edge=dfs_stack.top(); 788 //actual_node=G.aNode(actual_edge); 789 if (G.valid(actual_edge)/*.valid()*/) { 790 NodeIt w=G.bNode(actual_edge); 791 actual_node=w; 792 if (!reached.get(w)) { 793 dfs_stack.push(G.template first<OutEdgeIt>(w)); 794 reached.set(w, true); 795 b_node_newly_reached=true; 796 } else { 797 actual_node=G.aNode(actual_edge); 798 /*++*/G.next(dfs_stack.top()); 799 b_node_newly_reached=false; 800 } 801 } else { 802 //actual_node=G.aNode(dfs_stack.top()); 803 dfs_stack.pop(); 804 } 805 return *this; 806 } 807 bool finished() const { return dfs_stack.empty(); } 747 808 operator OutEdgeIt () const { return actual_edge; } 748 809 bool isBNodeNewlyReached() const { return b_node_newly_reached; } 749 bool isANodeExamined() const { return !( actual_edge.valid()); }750 NodeIt aNode() const { return bfs_queue.front();}751 NodeIt bNode() const { return gw.bNode(actual_edge); }810 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } 811 NodeIt aNode() const { return actual_node; /*FIXME*/} 812 NodeIt bNode() const { return G.bNode(actual_edge); } 752 813 const ReachedMap& getReachedMap() const { return reached; } 753 const std:: queue<NodeIt>& getBfsQueue() const { return bfs_queue; }754 };814 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } 815 }; 755 816 756 817
Note: See TracChangeset
for help on using the changeset viewer.