Changeset 298:315d826faa8f in lemon-0.x for src/work/marci/experiment/bfs_iterator_1.h
- Timestamp:
- 04/05/04 16:19:02 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@416
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/marci/experiment/bfs_iterator_1.h
r281 r298 631 631 632 632 633 template <typename Graph Wrapper, /*typename OutEdgeIt,*/634 typename ReachedMap/*=typename Graph Wrapper::NodeMap<bool>*/ >633 template <typename Graph, /*typename OutEdgeIt,*/ 634 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > 635 635 class BfsIterator5 { 636 typedef typename GraphWrapper::Node Node; 637 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; 638 const GraphWrapper* g; 636 protected: 637 typedef typename Graph::Node Node; 638 typedef typename Graph::OutEdgeIt OutEdgeIt; 639 const Graph* graph; 639 640 std::queue<Node> bfs_queue; 640 641 ReachedMap& reached; … … 643 644 bool own_reached_map; 644 645 public: 645 BfsIterator5(const Graph Wrapper& _g, ReachedMap& _reached) :646 g (&_g), reached(_reached),646 BfsIterator5(const Graph& _graph, ReachedMap& _reached) : 647 graph(&_graph), reached(_reached), 647 648 own_reached_map(false) { } 648 BfsIterator5(const Graph Wrapper& _g) :649 g (&_g), reached(*(new ReachedMap(*g/*, false*/))),649 BfsIterator5(const Graph& _graph) : 650 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 650 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 652 ~BfsIterator5() { if (own_reached_map) delete &reached; } 659 653 void pushAndSetReached(Node s) { … … 661 655 if (bfs_queue.empty()) { 662 656 bfs_queue.push(s); 663 g ->first(actual_edge, s);664 if (g ->valid(actual_edge)) {665 Node w=g ->bNode(actual_edge);657 graph->first(actual_edge, s); 658 if (graph->valid(actual_edge)) { 659 Node w=graph->bNode(actual_edge); 666 660 if (!reached.get(w)) { 667 661 bfs_queue.push(w); … … 676 670 } 677 671 } 678 BfsIterator5<Graph Wrapper, /*OutEdgeIt,*/ ReachedMap>&672 BfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>& 679 673 operator++() { 680 if (g ->valid(actual_edge)) {681 g ->next(actual_edge);682 if (g ->valid(actual_edge)) {683 Node w=g ->bNode(actual_edge);674 if (graph->valid(actual_edge)) { 675 graph->next(actual_edge); 676 if (graph->valid(actual_edge)) { 677 Node w=graph->bNode(actual_edge); 684 678 if (!reached.get(w)) { 685 679 bfs_queue.push(w); … … 693 687 bfs_queue.pop(); 694 688 if (!bfs_queue.empty()) { 695 g ->first(actual_edge, bfs_queue.front());696 if (g ->valid(actual_edge)) {697 Node w=g ->bNode(actual_edge);689 graph->first(actual_edge, bfs_queue.front()); 690 if (graph->valid(actual_edge)) { 691 Node w=graph->bNode(actual_edge); 698 692 if (!reached.get(w)) { 699 693 bfs_queue.push(w); … … 711 705 operator OutEdgeIt () const { return actual_edge; } 712 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 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 710 const ReachedMap& getReachedMap() const { return reached; } 717 711 const std::queue<Node>& getBfsQueue() const { return bfs_queue; } … … 774 768 // }; 775 769 776 template <typename Graph Wrapper, /*typename OutEdgeIt,*/777 typename ReachedMap/*=typename Graph Wrapper::NodeMap<bool>*/ >770 template <typename Graph, /*typename OutEdgeIt,*/ 771 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > 778 772 class DfsIterator5 { 779 typedef typename GraphWrapper::Node Node; 780 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; 781 const GraphWrapper* g; 773 protected: 774 typedef typename Graph::Node Node; 775 typedef typename Graph::OutEdgeIt OutEdgeIt; 776 const Graph* graph; 782 777 std::stack<OutEdgeIt> dfs_stack; 783 778 bool b_node_newly_reached; … … 787 782 bool own_reached_map; 788 783 public: 789 DfsIterator5(const Graph Wrapper& _g, ReachedMap& _reached) :790 g (&_g), reached(_reached),784 DfsIterator5(const Graph& _graph, ReachedMap& _reached) : 785 graph(&_graph), reached(_reached), 791 786 own_reached_map(false) { } 792 DfsIterator5(const Graph Wrapper& _g) :793 g (&_g), reached(*(new ReachedMap(*g/*, false*/))),787 DfsIterator5(const Graph& _graph) : 788 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), 794 789 own_reached_map(true) { } 795 790 ~DfsIterator5() { if (own_reached_map) delete &reached; } … … 798 793 reached.set(s, true); 799 794 OutEdgeIt e; 800 g ->first(e, s);795 graph->first(e, s); 801 796 dfs_stack.push(e); 802 797 } 803 DfsIterator5<Graph Wrapper, /*OutEdgeIt,*/ ReachedMap>&798 DfsIterator5<Graph, /*OutEdgeIt,*/ ReachedMap>& 804 799 operator++() { 805 800 actual_edge=dfs_stack.top(); 806 801 //actual_node=G.aNode(actual_edge); 807 if (g ->valid(actual_edge)/*.valid()*/) {808 Node w=g ->bNode(actual_edge);802 if (graph->valid(actual_edge)/*.valid()*/) { 803 Node w=graph->bNode(actual_edge); 809 804 actual_node=w; 810 805 if (!reached.get(w)) { 811 806 OutEdgeIt e; 812 g ->first(e, w);807 graph->first(e, w); 813 808 dfs_stack.push(e); 814 809 reached.set(w, true); 815 810 b_node_newly_reached=true; 816 811 } else { 817 actual_node=g ->aNode(actual_edge);818 g ->next(dfs_stack.top());812 actual_node=graph->aNode(actual_edge); 813 graph->next(dfs_stack.top()); 819 814 b_node_newly_reached=false; 820 815 } … … 828 823 operator OutEdgeIt () const { return actual_edge; } 829 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 826 Node aNode() const { return actual_node; /*FIXME*/} 832 827 Node bNode() const { return G.bNode(actual_edge); }
Note: See TracChangeset
for help on using the changeset viewer.