Changeset 99:f26897fb91fd in lemon0.x for src/work/bfs_iterator.hh
 Timestamp:
 02/18/04 16:58:28 (17 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@128
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/bfs_iterator.hh
r75 r99 284 284 operator OutEdgeIt () { return actual_edge; } 285 285 bool bNodeIsNewlyReached() { return b_node_newly_reached; } 286 bool aNodeIs Leaved() { return !(actual_edge.valid()); }286 bool aNodeIsExamined() { return !(actual_edge.valid()); } 287 287 }; 288 288 … … 615 615 616 616 617 template <typename Graph, typename OutEdgeIt, typename ReachedMap> 618 struct DfsIterator4 { 619 typedef typename Graph::NodeIt NodeIt; 620 const Graph& G; 621 std::stack<OutEdgeIt> dfs_stack; 622 //ReachedMap& reached; 623 bool b_node_newly_reached; 624 OutEdgeIt actual_edge; 625 NodeIt actual_node; 626 ReachedMap reached; 627 DfsIterator4(const Graph& _G 628 /*, std::stack<OutEdgeIt>& _bfs_queue, 629 ReachedMap& _reached*/) : 630 G(_G), reached(G, false) /*, bfs_queue(_bfs_queue), reached(_reached)*/ { 631 //actual_edge=bfs_queue.top(); 632 //if (actual_edge.valid()) { 633 // NodeIt w=G.bNode(actual_edge); 634 //if (!reached.get(w)) { 635 // bfs_queue.push(OutEdgeIt(G, w)); 636 // reached.set(w, true); 637 // b_node_newly_reached=true; 638 //} else { 639 // ++(bfs_queue.top()); 640 // b_node_newly_reached=false; 641 //} 642 //} else { 643 // bfs_queue.pop(); 644 //} 645 } 646 void pushAndSetReached(NodeIt s) { 647 reached.set(s, true); 648 dfs_stack.push(G.template first<OutEdgeIt>(s)); 649 } 650 DfsIterator4<Graph, OutEdgeIt, ReachedMap>& 651 operator++() { 652 actual_edge=dfs_stack.top(); 653 //actual_node=G.aNode(actual_edge); 654 if (actual_edge.valid()) { 655 NodeIt w=G.bNode(actual_edge); 656 actual_node=w; 657 if (!reached.get(w)) { 658 dfs_stack.push(G.template first<OutEdgeIt>(w)); 659 reached.set(w, true); 660 b_node_newly_reached=true; 661 } else { 662 ++(dfs_stack.top()); 663 b_node_newly_reached=false; 664 } 665 } else { 666 //actual_node=G.aNode(dfs_stack.top()); 667 dfs_stack.pop(); 668 } 669 return *this; 670 } 671 bool finished() const { return dfs_stack.empty(); } 672 operator OutEdgeIt () const { return actual_edge; } 673 bool isBNodeNewlyReached() const { return b_node_newly_reached; } 674 bool isANodeExamined() const { return !(actual_edge.valid()); } 675 NodeIt aNode() const { return actual_node; } 676 NodeIt bNode() const { return G.bNode(actual_edge); } 677 const ReachedMap& getReachedMap() const { return reached; } 678 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } 679 }; 680 681 682 617 683 template <typename GraphWrapper, typename ReachedMap> 618 684 class BfsIterator5 {
Note: See TracChangeset
for help on using the changeset viewer.