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_type& 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_HH |
|
23 #define REVERSE_BFS_HH |
|
24 |
|
25 #include <queue> |
|
26 |
|
27 #include <marci_graph_traits.hh> |
|
28 #include <marciMap.hh> |
|
29 |
|
30 |
|
31 |
|
32 namespace marci { |
|
33 |
|
34 template <typename graph_type> |
|
35 class reverse_bfs { |
|
36 typedef typename graph_traits<graph_type>::NodeIt NodeIt; |
|
37 //typedef typename graph_traits<graph_type>::EdgeIt EdgeIt; |
|
38 typedef typename graph_traits<graph_type>::EachNodeIt EachNodeIt; |
|
39 typedef typename graph_traits<graph_type>::InEdgeIt InEdgeIt; |
|
40 |
|
41 |
|
42 graph_type& G; |
|
43 NodeIt t; |
|
44 // NodeMap<graph_type, EdgeIt> pred; |
|
45 NodeMap<graph_type, int> distance; |
|
46 |
|
47 |
|
48 public : |
|
49 |
|
50 /* |
|
51 The distance of the Nodes is n, except t for which it is 0. |
|
52 */ |
|
53 reverse_bfs(graph_type& _G, NodeIt _t) : G(_G), t(_t), distance(G, number_of(G.first_Node())) { |
|
54 distance.put(t,0); |
|
55 } |
|
56 |
|
57 void run() { |
|
58 |
|
59 NodeMap<graph_type, bool> reached(G, false); |
|
60 reached.put(t, true); |
|
61 |
|
62 std::queue<NodeIt> bfs_queue; |
|
63 bfs_queue.push(t); |
|
64 |
|
65 while (!bfs_queue.empty()) { |
|
66 |
|
67 NodeIt v=bfs_queue.front(); |
|
68 bfs_queue.pop(); |
|
69 |
|
70 for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) { |
|
71 NodeIt w=G.tail(e); |
|
72 if (!reached.get(w)) { |
|
73 bfs_queue.push(w); |
|
74 distance.put(w, distance.get(v)+1); |
|
75 reached.put(w, true); |
|
76 } |
|
77 } |
|
78 } |
|
79 } |
|
80 |
|
81 |
|
82 |
|
83 int dist(NodeIt v) { |
|
84 return distance.get(v); |
|
85 } |
|
86 |
|
87 |
|
88 }; |
|
89 |
|
90 } // namespace hugo |
|
91 |
|
92 #endif //REVERSE_BFS_HH |
|
93 |
|
94 |
|