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