Changeset 303:1b377a730d02 in lemon0.x for src/work/marci/bfs_iterator.h
 Timestamp:
 04/05/04 18:52:46 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@421
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci/bfs_iterator.h
r301 r303 6 6 #include <stack> 7 7 #include <utility> 8 #include <graph_wrapper.h>9 8 10 9 namespace hugo { … … 631 630 632 631 633 template <typename Graph Wrapper, /*typename OutEdgeIt,*/634 typename ReachedMap/*=typename Graph Wrapper::NodeMap<bool>*/ >632 template <typename Graph, /*typename OutEdgeIt,*/ 633 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > 635 634 class BfsIterator5 { 636 typedef typename GraphWrapper::Node Node; 637 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; 638 GraphWrapper G; 635 protected: 636 typedef typename Graph::Node Node; 637 typedef typename Graph::OutEdgeIt OutEdgeIt; 638 const Graph* graph; 639 639 std::queue<Node> bfs_queue; 640 640 ReachedMap& reached; … … 643 643 bool own_reached_map; 644 644 public: 645 BfsIterator5(const Graph Wrapper& _G, ReachedMap& _reached) :646 G(_G), reached(_reached),645 BfsIterator5(const Graph& _graph, ReachedMap& _reached) : 646 graph(&_graph), reached(_reached), 647 647 own_reached_map(false) { } 648 BfsIterator5(const Graph Wrapper& _G) :649 G(_G), reached(*(new ReachedMap(G/*, false*/))),648 BfsIterator5(const Graph& _graph) : 649 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 650 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 651 ~BfsIterator5() { if (own_reached_map) delete &reached; } 659 652 void pushAndSetReached(Node s) { … … 661 654 if (bfs_queue.empty()) { 662 655 bfs_queue.push(s); 663 G./*getF*/first(actual_edge, s);664 if ( G.valid(actual_edge)/*.valid()*/) {665 Node w= G.bNode(actual_edge);666 if (!reached .get(w)) {656 graph>first(actual_edge, s); 657 if (graph>valid(actual_edge)) { 658 Node w=graph>bNode(actual_edge); 659 if (!reached[w]) { 667 660 bfs_queue.push(w); 668 661 reached.set(w, true); … … 676 669 } 677 670 } 678 BfsIterator5<Graph Wrapper, /*OutEdgeIt,*/ ReachedMap>&671 BfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>& 679 672 operator++() { 680 if ( G.valid(actual_edge)/*.valid()*/) {681 /*++*/G.next(actual_edge);682 if ( G.valid(actual_edge)/*.valid()*/) {683 Node w= G.bNode(actual_edge);684 if (!reached .get(w)) {673 if (graph>valid(actual_edge)) { 674 graph>next(actual_edge); 675 if (graph>valid(actual_edge)) { 676 Node w=graph>bNode(actual_edge); 677 if (!reached[w]) { 685 678 bfs_queue.push(w); 686 679 reached.set(w, true); … … 693 686 bfs_queue.pop(); 694 687 if (!bfs_queue.empty()) { 695 G./*getF*/first(actual_edge, bfs_queue.front());696 if ( G.valid(actual_edge)/*.valid()*/) {697 Node w= G.bNode(actual_edge);698 if (!reached .get(w)) {688 graph>first(actual_edge, bfs_queue.front()); 689 if (graph>valid(actual_edge)) { 690 Node w=graph>bNode(actual_edge); 691 if (!reached[w]) { 699 692 bfs_queue.push(w); 700 693 reached.set(w, true); … … 711 704 operator OutEdgeIt () const { return actual_edge; } 712 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 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 709 const ReachedMap& getReachedMap() const { return reached; } 717 710 const std::queue<Node>& getBfsQueue() const { return bfs_queue; } … … 774 767 // }; 775 768 776 template <typename Graph Wrapper, /*typename OutEdgeIt,*/777 typename ReachedMap/*=typename Graph Wrapper::NodeMap<bool>*/ >769 template <typename Graph, /*typename OutEdgeIt,*/ 770 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > 778 771 class DfsIterator5 { 779 typedef typename GraphWrapper::Node Node; 780 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; 781 GraphWrapper G; 772 protected: 773 typedef typename Graph::Node Node; 774 typedef typename Graph::OutEdgeIt OutEdgeIt; 775 const Graph* graph; 782 776 std::stack<OutEdgeIt> dfs_stack; 783 777 bool b_node_newly_reached; … … 787 781 bool own_reached_map; 788 782 public: 789 DfsIterator5(const Graph Wrapper& _G, ReachedMap& _reached) :790 G(_G), reached(_reached),783 DfsIterator5(const Graph& _graph, ReachedMap& _reached) : 784 graph(&_graph), reached(_reached), 791 785 own_reached_map(false) { } 792 DfsIterator5(const Graph Wrapper& _G) :793 G(_G), reached(*(new ReachedMap(G/*, false*/))),786 DfsIterator5(const Graph& _graph) : 787 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 794 788 own_reached_map(true) { } 795 789 ~DfsIterator5() { if (own_reached_map) delete &reached; } … … 798 792 reached.set(s, true); 799 793 OutEdgeIt e; 800 G.first(e, s);794 graph>first(e, s); 801 795 dfs_stack.push(e); 802 796 } 803 DfsIterator5<Graph Wrapper, /*OutEdgeIt,*/ ReachedMap>&797 DfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>& 804 798 operator++() { 805 799 actual_edge=dfs_stack.top(); 806 800 //actual_node=G.aNode(actual_edge); 807 if ( G.valid(actual_edge)/*.valid()*/) {808 Node w= G.bNode(actual_edge);801 if (graph>valid(actual_edge)/*.valid()*/) { 802 Node w=graph>bNode(actual_edge); 809 803 actual_node=w; 810 if (!reached .get(w)) {804 if (!reached[w]) { 811 805 OutEdgeIt e; 812 G.first(e, w);806 graph>first(e, w); 813 807 dfs_stack.push(e); 814 808 reached.set(w, true); 815 809 b_node_newly_reached=true; 816 810 } else { 817 actual_node= G.aNode(actual_edge);818 /*++*/G.next(dfs_stack.top());811 actual_node=graph>aNode(actual_edge); 812 graph>next(dfs_stack.top()); 819 813 b_node_newly_reached=false; 820 814 } … … 828 822 operator OutEdgeIt () const { return actual_edge; } 829 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 825 Node aNode() const { return actual_node; /*FIXME*/} 832 826 Node bNode() const { return G.bNode(actual_edge); }
Note: See TracChangeset
for help on using the changeset viewer.