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