# source:lemon-0.x/src/work/jacint/reverse_bfs.h@95:3322fbf254d2

Last change on this file since 95:3322fbf254d2 was 78:ecc1171307be, checked in by jacint, 21 years ago

modern valtozat

File size: 1.6 KB
Line
1/*
2reverse_bfs
3by jacint
4Performs a bfs on the out Edges. It does not count predecessors,
5only the distances, but one can easily modify it to know the pred as well.
6
7Constructor:
8
9reverse_bfs(Graph& G, NodeIt t)
10
11
12
13Member functions:
14
15void run(): runs a reverse bfs from t
16
17  The following function should be used after run() was already run.
18
19int 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
29namespace  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.