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_graph_traits.hh> |
---|

28 | #include <marci_property_vector.hh> |
---|

29 | |
---|

30 | |
---|

31 | |
---|

32 | namespace marci { |
---|

33 | |
---|

34 | template <typename graph_type> |
---|

35 | class reverse_bfs { |
---|

36 | typedef typename graph_traits<graph_type>::node_iterator node_iterator; |
---|

37 | //typedef typename graph_traits<graph_type>::edge_iterator edge_iterator; |
---|

38 | typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator; |
---|

39 | typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator; |
---|

40 | |
---|

41 | |
---|

42 | graph_type& G; |
---|

43 | node_iterator t; |
---|

44 | // node_property_vector<graph_type, edge_iterator> pred; |
---|

45 | node_property_vector<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, node_iterator _t) : G(_G), t(_t), distance(G, number_of(G.first_node())) { |
---|

54 | distance.put(t,0); |
---|

55 | } |
---|

56 | |
---|

57 | void run() { |
---|

58 | |
---|

59 | node_property_vector<graph_type, bool> reached(G, false); |
---|

60 | reached.put(t, true); |
---|

61 | |
---|

62 | std::queue<node_iterator> bfs_queue; |
---|

63 | bfs_queue.push(t); |
---|

64 | |
---|

65 | while (!bfs_queue.empty()) { |
---|

66 | |
---|

67 | node_iterator v=bfs_queue.front(); |
---|

68 | bfs_queue.pop(); |
---|

69 | |
---|

70 | for(in_edge_iterator e=G.first_in_edge(v); e.is_valid(); ++e) { |
---|

71 | node_iterator 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(node_iterator v) { |
---|

84 | return distance.get(v); |
---|

85 | } |
---|

86 | |
---|

87 | |
---|

88 | }; |
---|

89 | |
---|

90 | } // namespace marci |
---|

91 | |
---|

92 | #endif //REVERSE_BFS_HH |
---|

93 | |
---|

94 | |
---|