Line | |
---|

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& G, NodeIt 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(NodeIt 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_H |
---|

23 | #define REVERSE_BFS_H |
---|

24 | |
---|

25 | #include <queue> |
---|

26 | #include <list_graph.hh> |
---|

27 | |
---|

28 | |
---|

29 | namespace marci { |
---|

30 | |
---|

31 | template <typename Graph> |
---|

32 | class reverse_bfs { |
---|

33 | typedef typename Graph::NodeIt NodeIt; |
---|

34 | typedef typename Graph::EachNodeIt EachNodeIt; |
---|

35 | typedef typename Graph::InEdgeIt InEdgeIt; |
---|

36 | |
---|

37 | |
---|

38 | Graph& G; |
---|

39 | NodeIt t; |
---|

40 | typename Graph::NodeMap<int> distance; |
---|

41 | |
---|

42 | |
---|

43 | public : |
---|

44 | |
---|

45 | /* |
---|

46 | The distance of the Nodes is n, except t for which it is 0. |
---|

47 | */ |
---|

48 | reverse_bfs(Graph& _G, NodeIt _t) : G(_G), t(_t), distance(G, G.nodeNum()) { |
---|

49 | distance.set(t,0); |
---|

50 | } |
---|

51 | |
---|

52 | void run() { |
---|

53 | |
---|

54 | typename Graph::NodeMap<bool> reached(G, false); |
---|

55 | reached.set(t, true); |
---|

56 | |
---|

57 | std::queue<NodeIt> bfs_queue; |
---|

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

59 | |
---|

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

61 | |
---|

62 | NodeIt v=bfs_queue.front(); |
---|

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

64 | |
---|

65 | for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) { |
---|

66 | NodeIt w=G.tail(e); |
---|

67 | if (!reached.get(w)) { |
---|

68 | bfs_queue.push(w); |
---|

69 | distance.set(w, distance.get(v)+1); |
---|

70 | reached.set(w, true); |
---|

71 | } |
---|

72 | } |
---|

73 | } |
---|

74 | } |
---|

75 | |
---|

76 | |
---|

77 | |
---|

78 | int dist(NodeIt v) { |
---|

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

80 | } |
---|

81 | |
---|

82 | |
---|

83 | }; |
---|

84 | |
---|

85 | } // namespace marci |
---|

86 | |
---|

87 | #endif //REVERSE_BFS_HH |
---|

88 | |
---|

89 | |
---|

**Note:** See

TracBrowser
for help on using the repository browser.