COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/reverse_bfs.hh @ 105:a3c73e9b9b2e

Last change on this file since 105:a3c73e9b9b2e was 105:a3c73e9b9b2e, checked in by Alpar Juttner, 16 years ago

marci -> hugo replacements
resize -> update replacements

File size: 1.8 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_type& 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_HH
23#define REVERSE_BFS_HH
24
25#include <queue>
26
27#include <marci_graph_traits.hh>
28#include <marciMap.hh>
29
30
31
32namespace  marci {
33
34  template <typename graph_type>
35  class reverse_bfs {
36    typedef typename graph_traits<graph_type>::NodeIt NodeIt;
37    //typedef typename graph_traits<graph_type>::EdgeIt EdgeIt;
38    typedef typename graph_traits<graph_type>::EachNodeIt EachNodeIt;
39    typedef typename graph_traits<graph_type>::InEdgeIt InEdgeIt;
40
41
42    graph_type& G;
43    NodeIt t;
44//    NodeMap<graph_type, EdgeIt> pred;
45    NodeMap<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, NodeIt _t) : G(_G), t(_t), distance(G, number_of(G.first_Node())) {
54      distance.put(t,0);
55    }
56   
57    void run() {
58
59      NodeMap<graph_type, bool> reached(G, false);
60      reached.put(t, true);
61
62      std::queue<NodeIt> bfs_queue;
63      bfs_queue.push(t);
64
65      while (!bfs_queue.empty()) {
66
67        NodeIt v=bfs_queue.front();     
68        bfs_queue.pop();
69
70        for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
71          NodeIt 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(NodeIt v) {
84      return distance.get(v);
85    }
86
87
88  };
89
90} // namespace hugo
91
92#endif //REVERSE_BFS_HH
93
94
Note: See TracBrowser for help on using the repository browser.