COIN-OR::LEMON - Graph Library

Changeset 78:ecc1171307be in lemon-0.x for src/work/jacint/reverse_bfs.hh


Ignore:
Timestamp:
02/16/04 17:15:58 (17 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@101
Message:

modern valtozat

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/jacint/reverse_bfs.hh

    r50 r78  
    22reverse_bfs
    33by jacint
    4 Performs a bfs on the out edges. It does not count predecessors,
     4Performs a bfs on the out Edges. It does not count predecessors,
    55only the distances, but one can easily modify it to know the pred as well.
    66
    77Constructor:
    88
    9 reverse_bfs(graph_type& G, node_iterator t)
     9reverse_bfs(graph_type& G, NodeIt t)
    1010
    1111
     
    1717  The following function should be used after run() was already run.
    1818
    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.
     19int dist(NodeIt v) : returns the distance from v to t. It is the number of Nodes if t is not reachable from v.
    2020
    2121*/
     
    2626
    2727#include <marci_graph_traits.hh>
    28 #include <marci_property_vector.hh>
     28#include <marciMap.hh>
    2929
    3030
     
    3434  template <typename graph_type>
    3535  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;
    4040
    4141
    4242    graph_type& G;
    43     node_iterator t;
    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;
    4646   
    4747
     
    4949
    5050    /*
    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.
    5252    */
    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())) {
    5454      distance.put(t,0);
    5555    }
     
    5757    void run() {
    5858
    59       node_property_vector<graph_type, bool> reached(G, false);
     59      NodeMap<graph_type, bool> reached(G, false);
    6060      reached.put(t, true);
    6161
    62       std::queue<node_iterator> bfs_queue;
     62      std::queue<NodeIt> bfs_queue;
    6363      bfs_queue.push(t);
    6464
    6565      while (!bfs_queue.empty()) {
    6666
    67         node_iterator v=bfs_queue.front();     
     67        NodeIt v=bfs_queue.front();     
    6868        bfs_queue.pop();
    6969
    70         for(in_edge_iterator e=G.first_in_edge(v); e.valid(); ++e) {
    71           node_iterator w=G.tail(e);
     70        for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
     71          NodeIt w=G.tail(e);
    7272          if (!reached.get(w)) {
    7373            bfs_queue.push(w);
     
    8181
    8282
    83     int dist(node_iterator v) {
     83    int dist(NodeIt v) {
    8484      return distance.get(v);
    8585    }
Note: See TracChangeset for help on using the changeset viewer.