COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/reverse_bfs.hh @ 50:e125f12784e2

Last change on this file since 50:e125f12784e2 was 50:e125f12784e2, checked in by jacint, 17 years ago

* empty log message *

File size: 2.0 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, node_iterator 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(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
32namespace  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.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
Note: See TracBrowser for help on using the repository browser.