Changeset 144:a1323efc5753 in lemon0.x for src/work/bfs_iterator.hh
 Timestamp:
 03/02/04 15:51:13 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@199
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/bfs_iterator.hh
r133 r144 543 543 }; 544 544 545 template <typename Graph, typename OutEdgeIt, typename ReachedMap> 545 546 template <typename Graph, typename OutEdgeIt, 547 typename ReachedMap=typename Graph::NodeMap<bool> > 546 548 class BfsIterator4 { 547 549 typedef typename Graph::NodeIt NodeIt; 548 550 const Graph& G; 549 551 std::queue<NodeIt> bfs_queue; 550 ReachedMap reached; 551 bool b_node_newly_reached; 552 OutEdgeIt actual_edge; 552 ReachedMap& reached; 553 bool b_node_newly_reached; 554 OutEdgeIt actual_edge; 555 bool own_reached_map; 553 556 public: 554 BfsIterator4(const Graph& _G) : G(_G), reached(G, false) { } 557 BfsIterator4(const Graph& _G, ReachedMap& _reached) : 558 G(_G), reached(_reached), 559 own_reached_map(false) { } 560 BfsIterator4(const Graph& _G) : 561 G(_G), reached(*(new ReachedMap(G /*, false*/))), 562 own_reached_map(true) { } 563 ~BfsIterator4() { if (own_reached_map) delete &reached; } 555 564 void pushAndSetReached(NodeIt s) { 556 565 reached.set(s, true); … … 612 621 const ReachedMap& getReachedMap() const { return reached; } 613 622 const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; } 614 }; 615 616 617 template <typename Graph, typename OutEdgeIt, typename ReachedMap>618 structDfsIterator4 {623 }; 624 625 template <typename Graph, typename OutEdgeIt, 626 typename ReachedMap=typename Graph::NodeMap<bool> > 627 class DfsIterator4 { 619 628 typedef typename Graph::NodeIt NodeIt; 620 629 const Graph& G; 621 630 std::stack<OutEdgeIt> dfs_stack; 622 //ReachedMap& reached;623 631 bool b_node_newly_reached; 624 632 OutEdgeIt actual_edge; 625 633 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 } 634 ReachedMap& reached; 635 bool own_reached_map; 636 public: 637 DfsIterator4(const Graph& _G, ReachedMap& _reached) : 638 G(_G), reached(_reached), 639 own_reached_map(false) { } 640 DfsIterator4(const Graph& _G) : 641 G(_G), reached(*(new ReachedMap(G /*, false*/))), 642 own_reached_map(true) { } 643 ~DfsIterator4() { if (own_reached_map) delete &reached; } 646 644 void pushAndSetReached(NodeIt s) { 647 645 actual_node=s;
Note: See TracChangeset
for help on using the changeset viewer.