540 NodeIt bNode() const { return G.bNode(actual_edge); } |
540 NodeIt bNode() const { return G.bNode(actual_edge); } |
541 const ReachedMap& getReachedMap() const { return reached; } |
541 const ReachedMap& getReachedMap() const { return reached; } |
542 //const std::queue< std::pair<NodeIt, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; } |
542 //const std::queue< std::pair<NodeIt, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; } |
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 class BfsIterator4 { |
548 class BfsIterator4 { |
547 typedef typename Graph::NodeIt NodeIt; |
549 typedef typename Graph::NodeIt NodeIt; |
548 const Graph& G; |
550 const Graph& G; |
549 std::queue<NodeIt> bfs_queue; |
551 std::queue<NodeIt> bfs_queue; |
550 ReachedMap reached; |
552 ReachedMap& reached; |
551 bool b_node_newly_reached; |
553 bool b_node_newly_reached; |
552 OutEdgeIt actual_edge; |
554 OutEdgeIt actual_edge; |
|
555 bool own_reached_map; |
553 public: |
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 void pushAndSetReached(NodeIt s) { |
564 void pushAndSetReached(NodeIt s) { |
556 reached.set(s, true); |
565 reached.set(s, true); |
557 if (bfs_queue.empty()) { |
566 if (bfs_queue.empty()) { |
558 bfs_queue.push(s); |
567 bfs_queue.push(s); |
559 G.getFirst(actual_edge, s); |
568 G.getFirst(actual_edge, s); |
609 bool isANodeExamined() const { return !(actual_edge.valid()); } |
618 bool isANodeExamined() const { return !(actual_edge.valid()); } |
610 NodeIt aNode() const { return bfs_queue.front(); } |
619 NodeIt aNode() const { return bfs_queue.front(); } |
611 NodeIt bNode() const { return G.bNode(actual_edge); } |
620 NodeIt bNode() const { return G.bNode(actual_edge); } |
612 const ReachedMap& getReachedMap() const { return reached; } |
621 const ReachedMap& getReachedMap() const { return reached; } |
613 const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; } |
622 const std::queue<NodeIt>& getBfsQueue() const { return bfs_queue; } |
614 }; |
623 }; |
615 |
624 |
616 |
625 template <typename Graph, typename OutEdgeIt, |
617 template <typename Graph, typename OutEdgeIt, typename ReachedMap> |
626 typename ReachedMap=typename Graph::NodeMap<bool> > |
618 struct DfsIterator4 { |
627 class DfsIterator4 { |
619 typedef typename Graph::NodeIt NodeIt; |
628 typedef typename Graph::NodeIt NodeIt; |
620 const Graph& G; |
629 const Graph& G; |
621 std::stack<OutEdgeIt> dfs_stack; |
630 std::stack<OutEdgeIt> dfs_stack; |
622 //ReachedMap& reached; |
|
623 bool b_node_newly_reached; |
631 bool b_node_newly_reached; |
624 OutEdgeIt actual_edge; |
632 OutEdgeIt actual_edge; |
625 NodeIt actual_node; |
633 NodeIt actual_node; |
626 ReachedMap reached; |
634 ReachedMap& reached; |
627 DfsIterator4(const Graph& _G |
635 bool own_reached_map; |
628 /*, std::stack<OutEdgeIt>& _bfs_queue, |
636 public: |
629 ReachedMap& _reached*/) : |
637 DfsIterator4(const Graph& _G, ReachedMap& _reached) : |
630 G(_G), reached(G, false) /*, bfs_queue(_bfs_queue), reached(_reached)*/ { |
638 G(_G), reached(_reached), |
631 //actual_edge=bfs_queue.top(); |
639 own_reached_map(false) { } |
632 //if (actual_edge.valid()) { |
640 DfsIterator4(const Graph& _G) : |
633 // NodeIt w=G.bNode(actual_edge); |
641 G(_G), reached(*(new ReachedMap(G /*, false*/))), |
634 //if (!reached.get(w)) { |
642 own_reached_map(true) { } |
635 // bfs_queue.push(OutEdgeIt(G, w)); |
643 ~DfsIterator4() { if (own_reached_map) delete &reached; } |
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) { |
644 void pushAndSetReached(NodeIt s) { |
647 actual_node=s; |
645 actual_node=s; |
648 reached.set(s, true); |
646 reached.set(s, true); |
649 dfs_stack.push(G.template first<OutEdgeIt>(s)); |
647 dfs_stack.push(G.template first<OutEdgeIt>(s)); |
650 } |
648 } |