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