marci@58: #ifndef BFS_ITERATOR_HH marci@58: #define BFS_ITERATOR_HH marci@42: marci@42: #include marci@42: #include marci@75: #include marci@75: #include marci@42: marci@42: namespace marci { marci@42: marci@42: template marci@42: struct bfs { marci@42: typedef typename Graph::NodeIt NodeIt; marci@42: typedef typename Graph::EdgeIt EdgeIt; marci@42: typedef typename Graph::EachNodeIt EachNodeIt; marci@42: typedef typename Graph::OutEdgeIt OutEdgeIt; marci@42: Graph& G; marci@42: NodeIt s; marci@42: typename Graph::NodeMap reached; marci@42: typename Graph::NodeMap pred; marci@42: typename Graph::NodeMap dist; marci@42: std::queue bfs_queue; marci@42: bfs(Graph& _G, NodeIt _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) { marci@42: bfs_queue.push(s); marci@42: for(EachNodeIt i=G.template first(); i.valid(); ++i) marci@42: reached.set(i, false); marci@42: reached.set(s, true); marci@42: dist.set(s, 0); marci@42: } marci@42: marci@42: void run() { marci@42: while (!bfs_queue.empty()) { marci@42: NodeIt v=bfs_queue.front(); marci@42: OutEdgeIt e=G.template first(v); marci@42: bfs_queue.pop(); marci@42: for( ; e.valid(); ++e) { marci@42: NodeIt w=G.bNode(e); marci@42: std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl; marci@42: if (!reached.get(w)) { marci@42: std::cout << G.id(w) << " is newly reached :-)" << std::endl; marci@42: bfs_queue.push(w); marci@42: dist.set(w, dist.get(v)+1); marci@42: pred.set(w, e); marci@42: reached.set(w, true); marci@42: } else { marci@42: std::cout << G.id(w) << " is already reached" << std::endl; marci@42: } marci@42: } marci@42: } marci@42: } marci@42: }; marci@42: marci@42: template marci@42: struct bfs_visitor { marci@42: typedef typename Graph::NodeIt NodeIt; marci@42: typedef typename Graph::EdgeIt EdgeIt; marci@42: typedef typename Graph::OutEdgeIt OutEdgeIt; marci@42: Graph& G; marci@42: bfs_visitor(Graph& _G) : G(_G) { } marci@42: void at_previously_reached(OutEdgeIt& e) { marci@42: //NodeIt v=G.aNode(e); marci@42: NodeIt w=G.bNode(e); marci@42: std::cout << G.id(w) << " is already reached" << std::endl; marci@42: } marci@42: void at_newly_reached(OutEdgeIt& e) { marci@42: //NodeIt v=G.aNode(e); marci@42: NodeIt w=G.bNode(e); marci@42: std::cout << G.id(w) << " is newly reached :-)" << std::endl; marci@42: } marci@42: }; marci@42: marci@42: template marci@42: struct bfs_iterator { marci@42: typedef typename Graph::NodeIt NodeIt; marci@42: typedef typename Graph::EdgeIt EdgeIt; marci@42: typedef typename Graph::OutEdgeIt OutEdgeIt; marci@42: Graph& G; marci@42: std::queue& bfs_queue; marci@42: ReachedMap& reached; marci@42: visitor_type& visitor; marci@42: void process() { marci@42: while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } marci@42: if (bfs_queue.empty()) return; marci@42: OutEdgeIt e=bfs_queue.front(); marci@42: //NodeIt v=G.aNode(e); marci@42: NodeIt w=G.bNode(e); marci@42: if (!reached.get(w)) { marci@42: visitor.at_newly_reached(e); marci@42: bfs_queue.push(G.template first(w)); marci@42: reached.set(w, true); marci@42: } else { marci@42: visitor.at_previously_reached(e); marci@42: } marci@42: } marci@42: bfs_iterator(Graph& _G, std::queue& _bfs_queue, ReachedMap& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) { marci@42: //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } marci@42: valid(); marci@42: } marci@42: bfs_iterator& operator++() { marci@42: //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } marci@42: //if (bfs_queue.empty()) return *this; marci@42: if (!valid()) return *this; marci@42: ++(bfs_queue.front()); marci@42: //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } marci@42: valid(); marci@42: return *this; marci@42: } marci@42: //void next() { marci@42: // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } marci@42: // if (bfs_queue.empty()) return; marci@42: // ++(bfs_queue.front()); marci@42: // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } marci@42: //} marci@42: bool valid() { marci@42: while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } marci@42: if (bfs_queue.empty()) return false; else return true; marci@42: } marci@42: //bool finished() { marci@42: // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } marci@42: // if (bfs_queue.empty()) return true; else return false; marci@42: //} marci@42: operator EdgeIt () { return bfs_queue.front(); } marci@42: marci@42: }; marci@42: marci@42: template marci@42: struct bfs_iterator1 { marci@42: typedef typename Graph::NodeIt NodeIt; marci@42: typedef typename Graph::EdgeIt EdgeIt; marci@42: typedef typename Graph::OutEdgeIt OutEdgeIt; marci@42: Graph& G; marci@42: std::queue& bfs_queue; marci@42: ReachedMap& reached; marci@42: bool _newly_reached; marci@42: bfs_iterator1(Graph& _G, std::queue& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) { marci@42: valid(); marci@42: if (!bfs_queue.empty() && bfs_queue.front().valid()) { marci@42: OutEdgeIt e=bfs_queue.front(); marci@42: NodeIt w=G.bNode(e); marci@42: if (!reached.get(w)) { marci@42: bfs_queue.push(G.template first(w)); marci@42: reached.set(w, true); marci@42: _newly_reached=true; marci@42: } else { marci@42: _newly_reached=false; marci@42: } marci@42: } marci@42: } marci@42: bfs_iterator1& operator++() { marci@42: if (!valid()) return *this; marci@42: ++(bfs_queue.front()); marci@42: valid(); marci@42: if (!bfs_queue.empty() && bfs_queue.front().valid()) { marci@42: OutEdgeIt e=bfs_queue.front(); marci@42: NodeIt w=G.bNode(e); marci@42: if (!reached.get(w)) { marci@42: bfs_queue.push(G.template first(w)); marci@42: reached.set(w, true); marci@42: _newly_reached=true; marci@42: } else { marci@42: _newly_reached=false; marci@42: } marci@42: } marci@42: return *this; marci@42: } marci@42: bool valid() { marci@42: while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } marci@42: if (bfs_queue.empty()) return false; else return true; marci@42: } marci@42: operator OutEdgeIt() { return bfs_queue.front(); } marci@42: //ize marci@42: bool newly_reached() { return _newly_reached; } marci@42: marci@42: }; marci@42: marci@42: template marci@42: struct BfsIterator { marci@42: typedef typename Graph::NodeIt NodeIt; marci@42: Graph& G; marci@42: std::queue& bfs_queue; marci@42: ReachedMap& reached; marci@42: bool b_node_newly_reached; marci@42: OutEdgeIt actual_edge; marci@42: BfsIterator(Graph& _G, marci@42: std::queue& _bfs_queue, marci@42: ReachedMap& _reached) : marci@42: G(_G), bfs_queue(_bfs_queue), reached(_reached) { marci@42: actual_edge=bfs_queue.front(); marci@42: if (actual_edge.valid()) { marci@42: NodeIt w=G.bNode(actual_edge); marci@42: if (!reached.get(w)) { marci@42: bfs_queue.push(G.firstOutEdge(w)); marci@42: reached.set(w, true); marci@42: b_node_newly_reached=true; marci@42: } else { marci@42: b_node_newly_reached=false; marci@42: } marci@42: } marci@42: } marci@42: BfsIterator& marci@42: operator++() { marci@42: if (bfs_queue.front().valid()) { marci@42: ++(bfs_queue.front()); marci@42: actual_edge=bfs_queue.front(); marci@42: if (actual_edge.valid()) { marci@42: NodeIt w=G.bNode(actual_edge); marci@42: if (!reached.get(w)) { marci@42: bfs_queue.push(G.firstOutEdge(w)); marci@42: reached.set(w, true); marci@42: b_node_newly_reached=true; marci@42: } else { marci@42: b_node_newly_reached=false; marci@42: } marci@42: } marci@42: } else { marci@42: bfs_queue.pop(); marci@42: actual_edge=bfs_queue.front(); marci@42: if (actual_edge.valid()) { marci@42: NodeIt w=G.bNode(actual_edge); marci@42: if (!reached.get(w)) { marci@42: bfs_queue.push(G.firstOutEdge(w)); marci@42: reached.set(w, true); marci@42: b_node_newly_reached=true; marci@42: } else { marci@42: b_node_newly_reached=false; marci@42: } marci@42: } marci@42: } marci@42: return *this; marci@42: } marci@42: bool finished() { return bfs_queue.empty(); } marci@42: operator OutEdgeIt () { return actual_edge; } marci@42: bool bNodeIsNewlyReached() { return b_node_newly_reached; } marci@42: bool aNodeIsExamined() { return !(actual_edge.valid()); } marci@42: }; marci@42: marci@42: marci@42: template marci@42: struct DfsIterator { marci@42: typedef typename Graph::NodeIt NodeIt; marci@42: Graph& G; marci@42: std::stack& bfs_queue; marci@42: ReachedMap& reached; marci@42: bool b_node_newly_reached; marci@42: OutEdgeIt actual_edge; marci@42: DfsIterator(Graph& _G, marci@42: std::stack& _bfs_queue, marci@42: ReachedMap& _reached) : marci@42: G(_G), bfs_queue(_bfs_queue), reached(_reached) { marci@42: actual_edge=bfs_queue.top(); marci@42: if (actual_edge.valid()) { marci@42: NodeIt w=G.bNode(actual_edge); marci@42: if (!reached.get(w)) { marci@42: bfs_queue.push(G.firstOutEdge(w)); marci@42: reached.set(w, true); marci@42: b_node_newly_reached=true; marci@42: } else { marci@42: ++(bfs_queue.top()); marci@42: b_node_newly_reached=false; marci@42: } marci@42: } else { marci@42: bfs_queue.pop(); marci@42: } marci@42: } marci@42: DfsIterator& marci@42: operator++() { marci@42: actual_edge=bfs_queue.top(); marci@42: if (actual_edge.valid()) { marci@42: NodeIt w=G.bNode(actual_edge); marci@42: if (!reached.get(w)) { marci@42: bfs_queue.push(G.firstOutEdge(w)); marci@42: reached.set(w, true); marci@42: b_node_newly_reached=true; marci@42: } else { marci@42: ++(bfs_queue.top()); marci@42: b_node_newly_reached=false; marci@42: } marci@42: } else { marci@42: bfs_queue.pop(); marci@42: } marci@42: return *this; marci@42: } marci@42: bool finished() { return bfs_queue.empty(); } marci@42: operator OutEdgeIt () { return actual_edge; } marci@42: bool bNodeIsNewlyReached() { return b_node_newly_reached; } marci@42: bool aNodeIsLeaved() { return !(actual_edge.valid()); } marci@42: }; marci@42: marci@42: template marci@42: struct BfsIterator1 { marci@42: typedef typename Graph::NodeIt NodeIt; marci@42: Graph& G; marci@42: std::queue& bfs_queue; marci@42: ReachedMap& reached; marci@42: bool b_node_newly_reached; marci@42: OutEdgeIt actual_edge; marci@42: BfsIterator1(Graph& _G, marci@42: std::queue& _bfs_queue, marci@42: ReachedMap& _reached) : marci@42: G(_G), bfs_queue(_bfs_queue), reached(_reached) { marci@42: actual_edge=bfs_queue.front(); marci@42: if (actual_edge.valid()) { marci@42: NodeIt w=G.bNode(actual_edge); marci@42: if (!reached.get(w)) { marci@42: bfs_queue.push(OutEdgeIt(G, w)); marci@42: reached.set(w, true); marci@42: b_node_newly_reached=true; marci@42: } else { marci@42: b_node_newly_reached=false; marci@42: } marci@42: } marci@42: } marci@42: void next() { marci@42: if (bfs_queue.front().valid()) { marci@42: ++(bfs_queue.front()); marci@42: actual_edge=bfs_queue.front(); marci@42: if (actual_edge.valid()) { marci@42: NodeIt w=G.bNode(actual_edge); marci@42: if (!reached.get(w)) { marci@42: bfs_queue.push(OutEdgeIt(G, w)); marci@42: reached.set(w, true); marci@42: b_node_newly_reached=true; marci@42: } else { marci@42: b_node_newly_reached=false; marci@42: } marci@42: } marci@42: } else { marci@42: bfs_queue.pop(); marci@42: actual_edge=bfs_queue.front(); marci@42: if (actual_edge.valid()) { marci@42: NodeIt w=G.bNode(actual_edge); marci@42: if (!reached.get(w)) { marci@42: bfs_queue.push(OutEdgeIt(G, w)); marci@42: reached.set(w, true); marci@42: b_node_newly_reached=true; marci@42: } else { marci@42: b_node_newly_reached=false; marci@42: } marci@42: } marci@42: } marci@42: //return *this; marci@42: } marci@42: bool finished() { return bfs_queue.empty(); } marci@42: operator OutEdgeIt () { return actual_edge; } marci@42: bool bNodeIsNewlyReached() { return b_node_newly_reached; } marci@42: bool aNodeIsExamined() { return !(actual_edge.valid()); } marci@42: }; marci@42: marci@42: marci@42: template marci@42: struct DfsIterator1 { marci@42: typedef typename Graph::NodeIt NodeIt; marci@42: Graph& G; marci@42: std::stack& bfs_queue; marci@42: ReachedMap& reached; marci@42: bool b_node_newly_reached; marci@42: OutEdgeIt actual_edge; marci@42: DfsIterator1(Graph& _G, marci@42: std::stack& _bfs_queue, marci@42: ReachedMap& _reached) : marci@42: G(_G), bfs_queue(_bfs_queue), reached(_reached) { marci@42: //actual_edge=bfs_queue.top(); marci@42: //if (actual_edge.valid()) { marci@42: // NodeIt w=G.bNode(actual_edge); marci@42: //if (!reached.get(w)) { marci@42: // bfs_queue.push(OutEdgeIt(G, w)); marci@42: // reached.set(w, true); marci@42: // b_node_newly_reached=true; marci@42: //} else { marci@42: // ++(bfs_queue.top()); marci@42: // b_node_newly_reached=false; marci@42: //} marci@42: //} else { marci@42: // bfs_queue.pop(); marci@42: //} marci@42: } marci@42: void next() { marci@42: actual_edge=bfs_queue.top(); marci@42: if (actual_edge.valid()) { marci@42: NodeIt w=G.bNode(actual_edge); marci@42: if (!reached.get(w)) { marci@42: bfs_queue.push(OutEdgeIt(G, w)); marci@42: reached.set(w, true); marci@42: b_node_newly_reached=true; marci@42: } else { marci@42: ++(bfs_queue.top()); marci@42: b_node_newly_reached=false; marci@42: } marci@42: } else { marci@42: bfs_queue.pop(); marci@42: } marci@42: //return *this; marci@42: } marci@42: bool finished() { return bfs_queue.empty(); } marci@42: operator OutEdgeIt () { return actual_edge; } marci@42: bool bNodeIsNewlyReached() { return b_node_newly_reached; } marci@42: bool aNodeIsLeaved() { return !(actual_edge.valid()); } marci@42: }; marci@42: marci@58: template marci@58: class BfsIterator2 { marci@58: typedef typename Graph::NodeIt NodeIt; marci@58: const Graph& G; marci@58: std::queue bfs_queue; marci@58: ReachedMap reached; marci@58: bool b_node_newly_reached; marci@58: OutEdgeIt actual_edge; marci@58: public: marci@58: BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { } marci@64: void pushAndSetReached(NodeIt s) { marci@58: reached.set(s, true); marci@58: if (bfs_queue.empty()) { marci@58: bfs_queue.push(G.template first(s)); marci@58: actual_edge=bfs_queue.front(); marci@58: if (actual_edge.valid()) { marci@58: NodeIt w=G.bNode(actual_edge); marci@58: if (!reached.get(w)) { marci@58: bfs_queue.push(G.template first(w)); marci@58: reached.set(w, true); marci@58: b_node_newly_reached=true; marci@58: } else { marci@58: b_node_newly_reached=false; marci@58: } marci@58: } //else { marci@58: //} marci@58: } else { marci@58: bfs_queue.push(G.template first(s)); marci@58: } marci@58: } marci@58: BfsIterator2& marci@58: operator++() { marci@58: if (bfs_queue.front().valid()) { marci@58: ++(bfs_queue.front()); marci@58: actual_edge=bfs_queue.front(); marci@58: if (actual_edge.valid()) { marci@58: NodeIt w=G.bNode(actual_edge); marci@58: if (!reached.get(w)) { marci@58: bfs_queue.push(G.template first(w)); marci@58: reached.set(w, true); marci@58: b_node_newly_reached=true; marci@58: } else { marci@58: b_node_newly_reached=false; marci@58: } marci@58: } marci@58: } else { marci@58: bfs_queue.pop(); marci@58: if (!bfs_queue.empty()) { marci@58: actual_edge=bfs_queue.front(); marci@64: if (actual_edge.valid()) { marci@64: NodeIt w=G.bNode(actual_edge); marci@64: if (!reached.get(w)) { marci@64: bfs_queue.push(G.template first(w)); marci@64: reached.set(w, true); marci@64: b_node_newly_reached=true; marci@64: } else { marci@64: b_node_newly_reached=false; marci@64: } marci@58: } marci@58: } marci@58: } marci@58: return *this; marci@58: } marci@58: bool finished() const { return bfs_queue.empty(); } marci@58: operator OutEdgeIt () const { return actual_edge; } marci@58: bool isBNodeNewlyReached() const { return b_node_newly_reached; } marci@58: bool isANodeExamined() const { return !(actual_edge.valid()); } marci@58: const ReachedMap& getReachedMap() const { return reached; } marci@58: const std::queue& getBfsQueue() const { return bfs_queue; } marci@58: }; marci@58: marci@75: marci@75: template marci@75: class BfsIterator3 { marci@75: typedef typename Graph::NodeIt NodeIt; marci@75: const Graph& G; marci@75: std::queue< std::pair > bfs_queue; marci@75: ReachedMap reached; marci@75: bool b_node_newly_reached; marci@75: OutEdgeIt actual_edge; marci@75: public: marci@75: BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { } marci@75: void pushAndSetReached(NodeIt s) { marci@75: reached.set(s, true); marci@75: if (bfs_queue.empty()) { marci@75: bfs_queue.push(std::pair(s, G.template first(s))); marci@75: actual_edge=bfs_queue.front().second; marci@75: if (actual_edge.valid()) { marci@75: NodeIt w=G.bNode(actual_edge); marci@75: if (!reached.get(w)) { marci@75: bfs_queue.push(std::pair(w, G.template first(w))); marci@75: reached.set(w, true); marci@75: b_node_newly_reached=true; marci@75: } else { marci@75: b_node_newly_reached=false; marci@75: } marci@75: } //else { marci@75: //} marci@75: } else { marci@75: bfs_queue.push(std::pair(s, G.template first(s))); marci@75: } marci@75: } marci@75: BfsIterator3& marci@75: operator++() { marci@75: if (bfs_queue.front().second.valid()) { marci@75: ++(bfs_queue.front().second); marci@75: actual_edge=bfs_queue.front().second; marci@75: if (actual_edge.valid()) { marci@75: NodeIt w=G.bNode(actual_edge); marci@75: if (!reached.get(w)) { marci@75: bfs_queue.push(std::pair(w, G.template first(w))); marci@75: reached.set(w, true); marci@75: b_node_newly_reached=true; marci@75: } else { marci@75: b_node_newly_reached=false; marci@75: } marci@75: } marci@75: } else { marci@75: bfs_queue.pop(); marci@75: if (!bfs_queue.empty()) { marci@75: actual_edge=bfs_queue.front().second; marci@75: if (actual_edge.valid()) { marci@75: NodeIt w=G.bNode(actual_edge); marci@75: if (!reached.get(w)) { marci@75: bfs_queue.push(std::pair(w, G.template first(w))); marci@75: reached.set(w, true); marci@75: b_node_newly_reached=true; marci@75: } else { marci@75: b_node_newly_reached=false; marci@75: } marci@75: } marci@75: } marci@75: } marci@75: return *this; marci@75: } marci@75: bool finished() const { return bfs_queue.empty(); } marci@75: operator OutEdgeIt () const { return actual_edge; } marci@75: bool isBNodeNewlyReached() const { return b_node_newly_reached; } marci@75: bool isANodeExamined() const { return !(actual_edge.valid()); } marci@75: NodeIt aNode() const { return bfs_queue.front().first; } marci@75: NodeIt bNode() const { return G.bNode(actual_edge); } marci@75: const ReachedMap& getReachedMap() const { return reached; } marci@75: //const std::queue< std::pair >& getBfsQueue() const { return bfs_queue; } marci@75: }; marci@75: marci@75: template marci@75: class BfsIterator4 { marci@75: typedef typename Graph::NodeIt NodeIt; marci@75: const Graph& G; marci@75: std::queue bfs_queue; marci@75: ReachedMap reached; marci@75: bool b_node_newly_reached; marci@75: OutEdgeIt actual_edge; marci@75: public: marci@75: BfsIterator4(const Graph& _G) : G(_G), reached(G, false) { } marci@75: void pushAndSetReached(NodeIt s) { marci@75: reached.set(s, true); marci@75: if (bfs_queue.empty()) { marci@75: bfs_queue.push(s); marci@75: G.getFirst(actual_edge, s); marci@75: if (actual_edge.valid()) { marci@75: NodeIt w=G.bNode(actual_edge); marci@75: if (!reached.get(w)) { marci@75: bfs_queue.push(w); marci@75: reached.set(w, true); marci@75: b_node_newly_reached=true; marci@75: } else { marci@75: b_node_newly_reached=false; marci@75: } marci@75: } marci@75: } else { marci@75: bfs_queue.push(s); marci@75: } marci@75: } marci@75: BfsIterator4& marci@75: operator++() { marci@75: if (actual_edge.valid()) { marci@75: ++actual_edge; marci@75: if (actual_edge.valid()) { marci@75: NodeIt w=G.bNode(actual_edge); marci@75: if (!reached.get(w)) { marci@75: bfs_queue.push(w); marci@75: reached.set(w, true); marci@75: b_node_newly_reached=true; marci@75: } else { marci@75: b_node_newly_reached=false; marci@75: } marci@75: } marci@75: } else { marci@75: bfs_queue.pop(); marci@75: if (!bfs_queue.empty()) { marci@75: G.getFirst(actual_edge, bfs_queue.front()); marci@75: if (actual_edge.valid()) { marci@75: NodeIt w=G.bNode(actual_edge); marci@75: if (!reached.get(w)) { marci@75: bfs_queue.push(w); marci@75: reached.set(w, true); marci@75: b_node_newly_reached=true; marci@75: } else { marci@75: b_node_newly_reached=false; marci@75: } marci@75: } marci@75: } marci@75: } marci@75: return *this; marci@75: } marci@75: bool finished() const { return bfs_queue.empty(); } marci@75: operator OutEdgeIt () const { return actual_edge; } marci@75: bool isBNodeNewlyReached() const { return b_node_newly_reached; } marci@75: bool isANodeExamined() const { return !(actual_edge.valid()); } marci@75: NodeIt aNode() const { return bfs_queue.front(); } marci@75: NodeIt bNode() const { return G.bNode(actual_edge); } marci@75: const ReachedMap& getReachedMap() const { return reached; } marci@75: const std::queue& getBfsQueue() const { return bfs_queue; } marci@75: }; marci@75: marci@75: marci@75: template marci@75: class BfsIterator5 { marci@75: typedef typename GraphWrapper::NodeIt NodeIt; marci@75: typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; marci@75: GraphWrapper gw; marci@75: std::queue bfs_queue; marci@75: ReachedMap reached; marci@75: bool b_node_newly_reached; marci@75: OutEdgeIt actual_edge; marci@75: public: marci@75: BfsIterator5(GraphWrapper _gw) : marci@75: gw(_gw), reached(_gw.getGraph()) { } marci@75: void pushAndSetReached(NodeIt s) { marci@75: reached.set(s, true); marci@75: if (bfs_queue.empty()) { marci@75: bfs_queue.push(s); marci@75: gw.getFirst(actual_edge, s); marci@75: if (actual_edge.valid()) { marci@75: NodeIt w=gw.bNode(actual_edge); marci@75: if (!reached.get(w)) { marci@75: bfs_queue.push(w); marci@75: reached.set(w, true); marci@75: b_node_newly_reached=true; marci@75: } else { marci@75: b_node_newly_reached=false; marci@75: } marci@75: } marci@75: } else { marci@75: bfs_queue.push(s); marci@75: } marci@75: } marci@75: BfsIterator5& marci@75: operator++() { marci@75: if (actual_edge.valid()) { marci@75: ++actual_edge; marci@75: if (actual_edge.valid()) { marci@75: NodeIt w=gw.bNode(actual_edge); marci@75: if (!reached.get(w)) { marci@75: bfs_queue.push(w); marci@75: reached.set(w, true); marci@75: b_node_newly_reached=true; marci@75: } else { marci@75: b_node_newly_reached=false; marci@75: } marci@75: } marci@75: } else { marci@75: bfs_queue.pop(); marci@75: if (!bfs_queue.empty()) { marci@75: gw.getFirst(actual_edge, bfs_queue.front()); marci@75: if (actual_edge.valid()) { marci@75: NodeIt w=gw.bNode(actual_edge); marci@75: if (!reached.get(w)) { marci@75: bfs_queue.push(w); marci@75: reached.set(w, true); marci@75: b_node_newly_reached=true; marci@75: } else { marci@75: b_node_newly_reached=false; marci@75: } marci@75: } marci@75: } marci@75: } marci@75: return *this; marci@75: } marci@75: bool finished() const { return bfs_queue.empty(); } marci@75: operator OutEdgeIt () const { return actual_edge; } marci@75: bool isBNodeNewlyReached() const { return b_node_newly_reached; } marci@75: bool isANodeExamined() const { return !(actual_edge.valid()); } marci@75: NodeIt aNode() const { return bfs_queue.front(); } marci@75: NodeIt bNode() const { return gw.bNode(actual_edge); } marci@75: const ReachedMap& getReachedMap() const { return reached; } marci@75: const std::queue& getBfsQueue() const { return bfs_queue; } marci@75: }; marci@75: marci@75: marci@75: marci@42: } // namespace marci marci@42: marci@58: #endif //BFS_ITERATOR_HH