Changeset 78:ecc1171307be in lemon0.x for src/work/jacint/reverse_bfs.hh
 Timestamp:
 02/16/04 17:15:58 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@101
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/jacint/reverse_bfs.hh
r50 r78 2 2 reverse_bfs 3 3 by jacint 4 Performs a bfs on the out edges. It does not count predecessors,4 Performs a bfs on the out Edges. It does not count predecessors, 5 5 only the distances, but one can easily modify it to know the pred as well. 6 6 7 7 Constructor: 8 8 9 reverse_bfs(graph_type& G, node_iteratort)9 reverse_bfs(graph_type& G, NodeIt t) 10 10 11 11 … … 17 17 The following function should be used after run() was already run. 18 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.19 int dist(NodeIt v) : returns the distance from v to t. It is the number of Nodes if t is not reachable from v. 20 20 21 21 */ … … 26 26 27 27 #include <marci_graph_traits.hh> 28 #include <marci _property_vector.hh>28 #include <marciMap.hh> 29 29 30 30 … … 34 34 template <typename graph_type> 35 35 class reverse_bfs { 36 typedef typename graph_traits<graph_type>:: node_iterator node_iterator;37 //typedef typename graph_traits<graph_type>:: edge_iterator edge_iterator;38 typedef typename graph_traits<graph_type>:: each_node_iterator each_node_iterator;39 typedef typename graph_traits<graph_type>:: in_edge_iterator in_edge_iterator;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; 40 40 41 41 42 42 graph_type& G; 43 node_iteratort;44 // node_property_vector<graph_type, edge_iterator> pred;45 node_property_vector<graph_type, int> distance;43 NodeIt t; 44 // NodeMap<graph_type, EdgeIt> pred; 45 NodeMap<graph_type, int> distance; 46 46 47 47 … … 49 49 50 50 /* 51 The distance of the nodes is n, except t for which it is 0.51 The distance of the Nodes is n, except t for which it is 0. 52 52 */ 53 reverse_bfs(graph_type& _G, node_iterator _t) : G(_G), t(_t), distance(G, number_of(G.first_node())) {53 reverse_bfs(graph_type& _G, NodeIt _t) : G(_G), t(_t), distance(G, number_of(G.first_Node())) { 54 54 distance.put(t,0); 55 55 } … … 57 57 void run() { 58 58 59 node_property_vector<graph_type, bool> reached(G, false);59 NodeMap<graph_type, bool> reached(G, false); 60 60 reached.put(t, true); 61 61 62 std::queue< node_iterator> bfs_queue;62 std::queue<NodeIt> bfs_queue; 63 63 bfs_queue.push(t); 64 64 65 65 while (!bfs_queue.empty()) { 66 66 67 node_iteratorv=bfs_queue.front();67 NodeIt v=bfs_queue.front(); 68 68 bfs_queue.pop(); 69 69 70 for( in_edge_iterator e=G.first_in_edge(v); e.valid(); ++e) {71 node_iteratorw=G.tail(e);70 for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) { 71 NodeIt w=G.tail(e); 72 72 if (!reached.get(w)) { 73 73 bfs_queue.push(w); … … 81 81 82 82 83 int dist( node_iteratorv) {83 int dist(NodeIt v) { 84 84 return distance.get(v); 85 85 }
Note: See TracChangeset
for help on using the changeset viewer.