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