1.1 --- a/src/work/reverse_bfs.hh	Fri Jan 30 14:55:10 2004 +0000
     1.2 +++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.3 @@ -1,94 +0,0 @@
     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.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 -