COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/reverse_bfs.hh @ 137:6364b07f8cd4

Last change on this file since 137:6364b07f8cd4 was 120:576f55fec89e, checked in by athos, 17 years ago

Itt van.

File size: 2.1 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_list_graph.hh>
28//#include <marci_property_vector.hh>
29
30
31
32namespace  hugo {
33
34  template <typename graph_type>
35  class reverse_bfs {
36
37    typedef typename graph_type::NodeIt NodeIt;
38    typedef typename graph_type::EdgeIt EdgeIt;
39    typedef typename graph_type::EachNodeIt EachNodeIt;
40    typedef typename graph_type::EachEdgeIt EachEdgeIt;
41    typedef typename graph_type::OutEdgeIt OutEdgeIt;
42    typedef typename graph_type::InEdgeIt InEdgeIt;
43    typedef typename graph_type::SymEdgeIt SymEdgeIt;
44
45
46
47    graph_type& G;
48    NodeIt t;
49//    node_property_vector<graph_type, edge_iterator> pred;
50    //node_property_vector<graph_type, int>
51    typename graph_type::NodeMap<int> distance;
52   
53
54  public :
55
56    /*
57      The distance of the nodes is n, except t for which it is 0.
58    */
59    reverse_bfs(graph_type& _G, NodeIt _t) :
60      G(_G), t(_t),
61      distance(G, G.nodeNum()) {
62      distance.set(t,0);
63    }
64   
65    void run() {
66
67      //node_property_vector<graph_type, bool>
68      typename graph_type::NodeMap<bool> reached(G, false);
69      reached.set(t, true);
70
71      std::queue<NodeIt> bfs_queue;
72      bfs_queue.push(t);
73
74      while (!bfs_queue.empty()) {
75
76        NodeIt v=bfs_queue.front();     
77        bfs_queue.pop();
78
79        for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
80          NodeIt w=G.tail(e);
81          if (!reached.get(w)) {
82            bfs_queue.push(w);
83            distance.set(w, distance.get(v)+1);
84            reached.set(w, true);
85          }
86        }
87      }
88    }
89
90
91
92    int dist(NodeIt v) {
93      return distance.get(v);
94    }
95
96
97  };
98
99} // namespace hugo
100
101#endif //REVERSE_BFS_HH
102
103
Note: See TracBrowser for help on using the repository browser.