COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/jacint/reverse_bfs.hh @ 109:fc5982b39e10

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

marci -> hugo replacements
resize -> update replacements

File size: 1.8 KB
RevLine 
[50]1/*
2reverse_bfs
3by jacint
[78]4Performs a bfs on the out Edges. It does not count predecessors,
[50]5only the distances, but one can easily modify it to know the pred as well.
6
7Constructor:
8
[78]9reverse_bfs(graph_type& G, NodeIt t)
[50]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
[78]19int dist(NodeIt v) : returns the distance from v to t. It is the number of Nodes if t is not reachable from v.
[50]20
21*/
22#ifndef REVERSE_BFS_HH
23#define REVERSE_BFS_HH
24
25#include <queue>
26
27#include <marci_graph_traits.hh>
[78]28#include <marciMap.hh>
[50]29
30
31
32namespace  marci {
33
34  template <typename graph_type>
35  class reverse_bfs {
[78]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;
[50]40
41
42    graph_type& G;
[78]43    NodeIt t;
44//    NodeMap<graph_type, EdgeIt> pred;
45    NodeMap<graph_type, int> distance;
[50]46   
47
48  public :
49
50    /*
[78]51      The distance of the Nodes is n, except t for which it is 0.
[50]52    */
[78]53    reverse_bfs(graph_type& _G, NodeIt _t) : G(_G), t(_t), distance(G, number_of(G.first_Node())) {
[50]54      distance.put(t,0);
55    }
56   
57    void run() {
58
[78]59      NodeMap<graph_type, bool> reached(G, false);
[50]60      reached.put(t, true);
61
[78]62      std::queue<NodeIt> bfs_queue;
[50]63      bfs_queue.push(t);
64
65      while (!bfs_queue.empty()) {
66
[78]67        NodeIt v=bfs_queue.front();     
[50]68        bfs_queue.pop();
69
[78]70        for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
71          NodeIt w=G.tail(e);
[50]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
[78]83    int dist(NodeIt v) {
[50]84      return distance.get(v);
85    }
86
87
88  };
89
[105]90} // namespace hugo
[50]91
92#endif //REVERSE_BFS_HH
93
94
Note: See TracBrowser for help on using the repository browser.