1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/work/jacint/reverse_bfs.h	Mon Feb 16 16:15:58 2004 +0000
     1.3 @@ -0,0 +1,89 @@
     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& G, NodeIt 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(NodeIt 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_H
    1.26 +#define REVERSE_BFS_H
    1.27 +
    1.28 +#include <queue>
    1.29 +#include <list_graph.hh>
    1.30 +
    1.31 +
    1.32 +namespace  marci {
    1.33 +
    1.34 +  template <typename Graph>
    1.35 +  class reverse_bfs {
    1.36 +    typedef typename Graph::NodeIt NodeIt;
    1.37 +    typedef typename Graph::EachNodeIt EachNodeIt;
    1.38 +    typedef typename Graph::InEdgeIt InEdgeIt;
    1.39 +
    1.40 +
    1.41 +    Graph& G;
    1.42 +    NodeIt t;
    1.43 +    typename Graph::NodeMap<int> distance;
    1.44 +    
    1.45 +
    1.46 +  public :
    1.47 +
    1.48 +    /*
    1.49 +      The distance of the Nodes is n, except t for which it is 0.
    1.50 +    */
    1.51 +    reverse_bfs(Graph& _G, NodeIt _t) : G(_G), t(_t), distance(G, G.nodeNum()) {
    1.52 +      distance.set(t,0);
    1.53 +    }
    1.54 +    
    1.55 +    void run() {
    1.56 +
    1.57 +      typename Graph::NodeMap<bool> reached(G, false); 
    1.58 +      reached.set(t, true);
    1.59 +
    1.60 +      std::queue<NodeIt> bfs_queue;
    1.61 +      bfs_queue.push(t);
    1.62 +
    1.63 +      while (!bfs_queue.empty()) {
    1.64 +
    1.65 +        NodeIt v=bfs_queue.front();	
    1.66 +	bfs_queue.pop();
    1.67 +
    1.68 +	for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
    1.69 +	  NodeIt w=G.tail(e);
    1.70 +	  if (!reached.get(w)) {
    1.71 +	    bfs_queue.push(w);
    1.72 +	    distance.set(w, distance.get(v)+1);
    1.73 +	    reached.set(w, true);
    1.74 +	  }
    1.75 +	}
    1.76 +      }
    1.77 +    }
    1.78 +
    1.79 +
    1.80 +
    1.81 +    int dist(NodeIt v) {
    1.82 +      return distance.get(v);
    1.83 +    }
    1.84 +
    1.85 +
    1.86 +  };
    1.87 +
    1.88 +} // namespace marci
    1.89 +
    1.90 +#endif //REVERSE_BFS_HH
    1.91 +
    1.92 +