marci@9: #ifndef MARCI_BFS_HH marci@9: #define MARCI_BFS_HH marci@9: marci@9: #include marci@9: marci@9: #include marci@9: marci@9: namespace marci { marci@9: marci@9: template marci@9: struct bfs { marci@19: typedef typename graph_type::node_iterator node_iterator; marci@19: typedef typename graph_type::edge_iterator edge_iterator; marci@19: typedef typename graph_type::each_node_iterator each_node_iterator; marci@19: typedef typename graph_type::out_edge_iterator out_edge_iterator; marci@9: graph_type& G; marci@9: node_iterator s; marci@9: node_property_vector reached; marci@9: node_property_vector pred; marci@9: node_property_vector dist; marci@9: std::queue bfs_queue; marci@9: bfs(graph_type& _G, node_iterator _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) { marci@9: bfs_queue.push(s); marci@19: for(each_node_iterator i=G.first_node(); i.valid(); ++i) marci@9: reached.put(i, false); marci@9: reached.put(s, true); marci@9: dist.put(s, 0); marci@9: } marci@9: marci@9: void run() { marci@9: while (!bfs_queue.empty()) { marci@9: node_iterator v=bfs_queue.front(); marci@9: out_edge_iterator e=G.first_out_edge(v); marci@9: bfs_queue.pop(); marci@19: for( ; e.valid(); ++e) { marci@9: node_iterator w=G.head(e); marci@9: std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl; marci@9: if (!reached.get(w)) { marci@9: std::cout << G.id(w) << " is newly reached :-)" << std::endl; marci@9: bfs_queue.push(w); marci@9: dist.put(w, dist.get(v)+1); marci@9: pred.put(w, e); marci@9: reached.put(w, true); marci@9: } else { marci@9: std::cout << G.id(w) << " is already reached" << std::endl; marci@9: } marci@9: } marci@9: } marci@9: } marci@9: }; marci@9: marci@9: template marci@9: struct bfs_visitor { marci@19: typedef typename graph_type::node_iterator node_iterator; marci@19: typedef typename graph_type::edge_iterator edge_iterator; marci@19: typedef typename graph_type::out_edge_iterator out_edge_iterator; marci@9: graph_type& G; marci@9: bfs_visitor(graph_type& _G) : G(_G) { } marci@9: void at_previously_reached(out_edge_iterator& e) { marci@9: //node_iterator v=G.tail(e); marci@9: node_iterator w=G.head(e); marci@9: std::cout << G.id(w) << " is already reached" << std::endl; marci@9: } marci@9: void at_newly_reached(out_edge_iterator& e) { marci@9: //node_iterator v=G.tail(e); marci@9: node_iterator w=G.head(e); marci@9: std::cout << G.id(w) << " is newly reached :-)" << std::endl; marci@9: } marci@9: }; marci@9: marci@9: template marci@9: struct bfs_iterator { marci@19: typedef typename graph_type::node_iterator node_iterator; marci@19: typedef typename graph_type::edge_iterator edge_iterator; marci@19: typedef typename graph_type::out_edge_iterator out_edge_iterator; marci@9: graph_type& G; marci@9: std::queue& bfs_queue; marci@9: reached_type& reached; marci@9: visitor_type& visitor; marci@9: void process() { marci@19: while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } marci@9: if (bfs_queue.empty()) return; marci@9: out_edge_iterator e=bfs_queue.front(); marci@9: //node_iterator v=G.tail(e); marci@9: node_iterator w=G.head(e); marci@9: if (!reached.get(w)) { marci@9: visitor.at_newly_reached(e); marci@9: bfs_queue.push(G.first_out_edge(w)); marci@9: reached.put(w, true); marci@9: } else { marci@9: visitor.at_previously_reached(e); marci@9: } marci@9: } marci@9: bfs_iterator(graph_type& _G, std::queue& _bfs_queue, reached_type& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) { marci@19: //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } marci@19: valid(); marci@9: } marci@9: bfs_iterator& operator++() { marci@19: //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } marci@9: //if (bfs_queue.empty()) return *this; marci@19: if (!valid()) return *this; marci@9: ++(bfs_queue.front()); marci@19: //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } marci@19: valid(); marci@9: return *this; marci@9: } marci@9: //void next() { marci@19: // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } marci@9: // if (bfs_queue.empty()) return; marci@9: // ++(bfs_queue.front()); marci@19: // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } marci@9: //} marci@19: bool valid() { marci@19: while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } marci@9: if (bfs_queue.empty()) return false; else return true; marci@9: } marci@9: //bool finished() { marci@19: // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } marci@9: // if (bfs_queue.empty()) return true; else return false; marci@9: //} marci@9: operator edge_iterator () { return bfs_queue.front(); } marci@9: marci@9: }; marci@9: marci@11: template marci@11: struct bfs_iterator1 { marci@19: typedef typename graph_type::node_iterator node_iterator; marci@19: typedef typename graph_type::edge_iterator edge_iterator; marci@19: typedef typename graph_type::out_edge_iterator out_edge_iterator; marci@11: graph_type& G; marci@11: std::queue& bfs_queue; marci@11: reached_type& reached; marci@19: bool _newly_reached; marci@11: bfs_iterator1(graph_type& _G, std::queue& _bfs_queue, reached_type& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) { marci@19: valid(); marci@19: if (!bfs_queue.empty() && bfs_queue.front().valid()) { marci@11: out_edge_iterator e=bfs_queue.front(); marci@11: node_iterator w=G.head(e); marci@11: if (!reached.get(w)) { marci@11: bfs_queue.push(G.first_out_edge(w)); marci@11: reached.put(w, true); marci@19: _newly_reached=true; marci@11: } else { marci@19: _newly_reached=false; marci@11: } marci@11: } marci@11: } marci@11: bfs_iterator1& operator++() { marci@19: if (!valid()) return *this; marci@11: ++(bfs_queue.front()); marci@19: valid(); marci@19: if (!bfs_queue.empty() && bfs_queue.front().valid()) { marci@11: out_edge_iterator e=bfs_queue.front(); marci@11: node_iterator w=G.head(e); marci@11: if (!reached.get(w)) { marci@11: bfs_queue.push(G.first_out_edge(w)); marci@11: reached.put(w, true); marci@19: _newly_reached=true; marci@11: } else { marci@19: _newly_reached=false; marci@11: } marci@11: } marci@11: return *this; marci@11: } marci@19: bool valid() { marci@19: while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } marci@11: if (bfs_queue.empty()) return false; else return true; marci@11: } marci@11: operator edge_iterator () { return bfs_queue.front(); } marci@19: bool newly_reached() { return _newly_reached; } marci@11: marci@11: }; marci@9: marci@9: } // namespace marci marci@9: marci@9: #endif //MARCI_BFS_HH