/* reverse_bfs by jacint Performs a bfs on the out Edges. It does not count predecessors, only the distances, but one can easily modify it to know the pred as well. Constructor: reverse_bfs(graph_type& G, NodeIt t) Member functions: void run(): runs a reverse bfs from t The following function should be used after run() was already run. int dist(NodeIt v) : returns the distance from v to t. It is the number of Nodes if t is not reachable from v. */ #ifndef REVERSE_BFS_HH #define REVERSE_BFS_HH #include #include #include namespace marci { template class reverse_bfs { typedef typename graph_traits::NodeIt NodeIt; //typedef typename graph_traits::EdgeIt EdgeIt; typedef typename graph_traits::EachNodeIt EachNodeIt; typedef typename graph_traits::InEdgeIt InEdgeIt; graph_type& G; NodeIt t; // NodeMap pred; NodeMap distance; public : /* The distance of the Nodes is n, except t for which it is 0. */ reverse_bfs(graph_type& _G, NodeIt _t) : G(_G), t(_t), distance(G, number_of(G.first_Node())) { distance.put(t,0); } void run() { NodeMap reached(G, false); reached.put(t, true); std::queue bfs_queue; bfs_queue.push(t); while (!bfs_queue.empty()) { NodeIt v=bfs_queue.front(); bfs_queue.pop(); for(InEdgeIt e=G.template first(v); e.valid(); ++e) { NodeIt w=G.tail(e); if (!reached.get(w)) { bfs_queue.push(w); distance.put(w, distance.get(v)+1); reached.put(w, true); } } } } int dist(NodeIt v) { return distance.get(v); } }; } // namespace marci #endif //REVERSE_BFS_HH