1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/work/reverse_bfs.hh	Tue Jan 20 21:27:28 2004 +0000
     1.3 @@ -0,0 +1,94 @@
     1.4 +/*
     1.5 +reverse_bfs
     1.6 +by jacint
     1.7 +Performs a bfs on the out edges. It does not count predecessors, 
     1.8 +only the distances, but one can easily modify it to know the pred as well.
     1.9 +
    1.10 +Constructor: 
    1.11 +
    1.12 +reverse_bfs(graph_type& G, node_iterator t)
    1.13 +
    1.14 +
    1.15 +
    1.16 +Member functions:
    1.17 +
    1.18 +void run(): runs a reverse bfs from t
    1.19 +
    1.20 +  The following function should be used after run() was already run.
    1.21 +
    1.22 +int dist(node_iterator v) : returns the distance from v to t. It is the number of nodes if t is not reachable from v.
    1.23 +
    1.24 +*/
    1.25 +#ifndef REVERSE_BFS_HH
    1.26 +#define REVERSE_BFS_HH
    1.27 +
    1.28 +#include <queue>
    1.29 +
    1.30 +#include <marci_graph_traits.hh>
    1.31 +#include <marci_property_vector.hh>
    1.32 +
    1.33 +
    1.34 +
    1.35 +namespace  marci {
    1.36 +
    1.37 +  template <typename graph_type>
    1.38 +  class reverse_bfs {
    1.39 +    typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    1.40 +    //typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
    1.41 +    typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
    1.42 +    typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
    1.43 +
    1.44 +
    1.45 +    graph_type& G;
    1.46 +    node_iterator t;
    1.47 +//    node_property_vector<graph_type, edge_iterator> pred;
    1.48 +    node_property_vector<graph_type, int> distance;
    1.49 +    
    1.50 +
    1.51 +  public :
    1.52 +
    1.53 +    /*
    1.54 +      The distance of the nodes is n, except t for which it is 0.
    1.55 +    */
    1.56 +    reverse_bfs(graph_type& _G, node_iterator _t) : G(_G), t(_t), distance(G, number_of(G.first_node())) {
    1.57 +      distance.put(t,0);
    1.58 +    }
    1.59 +    
    1.60 +    void run() {
    1.61 +
    1.62 +      node_property_vector<graph_type, bool> reached(G, false); 
    1.63 +      reached.put(t, true);
    1.64 +
    1.65 +      std::queue<node_iterator> bfs_queue;
    1.66 +      bfs_queue.push(t);
    1.67 +
    1.68 +      while (!bfs_queue.empty()) {
    1.69 +
    1.70 +        node_iterator v=bfs_queue.front();	
    1.71 +	bfs_queue.pop();
    1.72 +
    1.73 +	for(in_edge_iterator e=G.first_in_edge(v); e.is_valid(); ++e) {
    1.74 +	  node_iterator w=G.tail(e);
    1.75 +	  if (!reached.get(w)) {
    1.76 +	    bfs_queue.push(w);
    1.77 +	    distance.put(w, distance.get(v)+1);
    1.78 +	    reached.put(w, true);
    1.79 +	  }
    1.80 +	}
    1.81 +      }
    1.82 +    }
    1.83 +
    1.84 +
    1.85 +
    1.86 +    int dist(node_iterator v) {
    1.87 +      return distance.get(v);
    1.88 +    }
    1.89 +
    1.90 +
    1.91 +  };
    1.92 +
    1.93 +} // namespace marci
    1.94 +
    1.95 +#endif //REVERSE_BFS_HH
    1.96 +
    1.97 +