|
1 /* |
|
2 reverse_bfs |
|
3 by jacint |
|
4 Performs a bfs on the out Edges. It does not count predecessors, |
|
5 only the distances, but one can easily modify it to know the pred as well. |
|
6 |
|
7 Constructor: |
|
8 |
|
9 reverse_bfs(Graph& G, NodeIt t) |
|
10 |
|
11 |
|
12 |
|
13 Member functions: |
|
14 |
|
15 void run(): runs a reverse bfs from t |
|
16 |
|
17 The following function should be used after run() was already run. |
|
18 |
|
19 int dist(NodeIt v) : returns the distance from v to t. It is the number of nodes if t is not reachable from v. |
|
20 |
|
21 */ |
|
22 #ifndef REVERSE_BFS_H |
|
23 #define REVERSE_BFS_H |
|
24 |
|
25 #include <queue> |
|
26 #include <list_graph.hh> |
|
27 |
|
28 |
|
29 namespace marci { |
|
30 |
|
31 template <typename Graph> |
|
32 class reverse_bfs { |
|
33 typedef typename Graph::NodeIt NodeIt; |
|
34 typedef typename Graph::EachNodeIt EachNodeIt; |
|
35 typedef typename Graph::InEdgeIt InEdgeIt; |
|
36 |
|
37 |
|
38 Graph& G; |
|
39 NodeIt t; |
|
40 typename Graph::NodeMap<int> distance; |
|
41 |
|
42 |
|
43 public : |
|
44 |
|
45 /* |
|
46 The distance of the Nodes is n, except t for which it is 0. |
|
47 */ |
|
48 reverse_bfs(Graph& _G, NodeIt _t) : G(_G), t(_t), distance(G, G.nodeNum()) { |
|
49 distance.set(t,0); |
|
50 } |
|
51 |
|
52 void run() { |
|
53 |
|
54 typename Graph::NodeMap<bool> reached(G, false); |
|
55 reached.set(t, true); |
|
56 |
|
57 std::queue<NodeIt> bfs_queue; |
|
58 bfs_queue.push(t); |
|
59 |
|
60 while (!bfs_queue.empty()) { |
|
61 |
|
62 NodeIt v=bfs_queue.front(); |
|
63 bfs_queue.pop(); |
|
64 |
|
65 for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) { |
|
66 NodeIt w=G.tail(e); |
|
67 if (!reached.get(w)) { |
|
68 bfs_queue.push(w); |
|
69 distance.set(w, distance.get(v)+1); |
|
70 reached.set(w, true); |
|
71 } |
|
72 } |
|
73 } |
|
74 } |
|
75 |
|
76 |
|
77 |
|
78 int dist(NodeIt v) { |
|
79 return distance.get(v); |
|
80 } |
|
81 |
|
82 |
|
83 }; |
|
84 |
|
85 } // namespace marci |
|
86 |
|
87 #endif //REVERSE_BFS_HH |
|
88 |
|
89 |