src/work/athos/reverse_bfs.hh
author alpar
Wed, 24 Mar 2004 13:06:06 +0000
changeset 242 b255f25ad394
parent 105 a3c73e9b9b2e
permissions -rw-r--r--
DocFixes
     1 /*
     2 reverse_bfs
     3 by jacint
     4 Performs a bfs on the out edges. It does not count predecessors, 
     5 only the distances, but one can easily modify it to know the pred as well.
     6 
     7 Constructor: 
     8 
     9 reverse_bfs(graph_type& G, node_iterator t)
    10 
    11 
    12 
    13 Member functions:
    14 
    15 void run(): runs a reverse bfs from t
    16 
    17   The following function should be used after run() was already run.
    18 
    19 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.
    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 
    32 namespace  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