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