COIN-OR::LEMON - Graph Library

Changeset 19:3151a1026db9 in lemon-0.x for src/work/marci_bfs.hh


Ignore:
Timestamp:
01/20/04 18:39:13 (17 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@32
Message:

* empty log message *

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci_bfs.hh

    r11 r19  
    44#include <queue>
    55
    6 #include <marci_graph_traits.hh>
    76#include <marci_property_vector.hh>
    87
     
    1110  template <typename graph_type>
    1211  struct bfs {
    13     typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    14     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
    15     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
    16     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
    17 
     12    typedef typename graph_type::node_iterator node_iterator;
     13    typedef typename graph_type::edge_iterator edge_iterator;
     14    typedef typename graph_type::each_node_iterator each_node_iterator;
     15    typedef typename graph_type::out_edge_iterator out_edge_iterator;
    1816    graph_type& G;
    1917    node_iterator s;
     
    2422    bfs(graph_type& _G, node_iterator _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {
    2523      bfs_queue.push(s);
    26       for(each_node_iterator i=G.first_node(); i.is_valid(); ++i)
     24      for(each_node_iterator i=G.first_node(); i.valid(); ++i)
    2725        reached.put(i, false);
    2826      reached.put(s, true);
     
    3533        out_edge_iterator e=G.first_out_edge(v);
    3634        bfs_queue.pop();
    37         for( ; e.is_valid(); ++e) {
     35        for( ; e.valid(); ++e) {
    3836          node_iterator w=G.head(e);
    3937          std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
     
    5452  template <typename graph_type>
    5553  struct bfs_visitor {
    56     typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    57     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
    58     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
    59     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
     54    typedef typename graph_type::node_iterator node_iterator;
     55    typedef typename graph_type::edge_iterator edge_iterator;
     56    typedef typename graph_type::out_edge_iterator out_edge_iterator;
    6057    graph_type& G;
    6158    bfs_visitor(graph_type& _G) : G(_G) { }
     
    7471  template <typename graph_type, typename reached_type, typename visitor_type>
    7572  struct bfs_iterator {
    76     typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    77     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
    78     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
    79     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
    80 
     73    typedef typename graph_type::node_iterator node_iterator;
     74    typedef typename graph_type::edge_iterator edge_iterator;
     75    typedef typename graph_type::out_edge_iterator out_edge_iterator;
    8176    graph_type& G;
    8277    std::queue<out_edge_iterator>& bfs_queue;
     
    8479    visitor_type& visitor;
    8580    void process() {
    86       while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
     81      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
    8782      if (bfs_queue.empty()) return;
    8883      out_edge_iterator e=bfs_queue.front();
     
    9893    }
    9994    bfs_iterator(graph_type& _G, std::queue<out_edge_iterator>& _bfs_queue, reached_type& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) {
    100       //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
    101       is_valid();
     95      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
     96      valid();
    10297    }
    10398    bfs_iterator<graph_type, reached_type, visitor_type>& operator++() {
    104       //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
     99      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
    105100      //if (bfs_queue.empty()) return *this;
    106       if (!is_valid()) return *this;
     101      if (!valid()) return *this;
    107102      ++(bfs_queue.front());
    108       //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
    109       is_valid();
     103      //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
     104      valid();
    110105      return *this;
    111106    }
    112107    //void next() {
    113     //  while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
     108    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
    114109    //  if (bfs_queue.empty()) return;
    115110    //  ++(bfs_queue.front());
    116     //  while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
     111    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
    117112    //}
    118     bool is_valid() {
    119       while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
     113    bool valid() {
     114      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
    120115      if (bfs_queue.empty()) return false; else return true;
    121116    }
    122117    //bool finished() {
    123     //  while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
     118    //  while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
    124119    //  if (bfs_queue.empty()) return true; else return false;
    125120    //}
     
    130125  template <typename graph_type, typename reached_type>
    131126  struct bfs_iterator1 {
    132     typedef typename graph_traits<graph_type>::node_iterator node_iterator;
    133     typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
    134     typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
    135     typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
    136 
     127    typedef typename graph_type::node_iterator node_iterator;
     128    typedef typename graph_type::edge_iterator edge_iterator;
     129    typedef typename graph_type::out_edge_iterator out_edge_iterator;
    137130    graph_type& G;
    138131    std::queue<out_edge_iterator>& bfs_queue;
    139132    reached_type& reached;
    140     bool newly_reached;
     133    bool _newly_reached;
    141134    bfs_iterator1(graph_type& _G, std::queue<out_edge_iterator>& _bfs_queue, reached_type& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) {
    142       is_valid();
    143       if (!bfs_queue.empty() && bfs_queue.front().is_valid()) {
     135      valid();
     136      if (!bfs_queue.empty() && bfs_queue.front().valid()) {
    144137        out_edge_iterator e=bfs_queue.front();
    145138        node_iterator w=G.head(e);
     
    147140          bfs_queue.push(G.first_out_edge(w));
    148141          reached.put(w, true);
    149           newly_reached=true;
     142          _newly_reached=true;
    150143        } else {
    151           newly_reached=false;
     144          _newly_reached=false;
    152145        }
    153146      }
    154147    }
    155148    bfs_iterator1<graph_type, reached_type>& operator++() {
    156       if (!is_valid()) return *this;
     149      if (!valid()) return *this;
    157150      ++(bfs_queue.front());
    158       is_valid();
    159       if (!bfs_queue.empty() && bfs_queue.front().is_valid()) {
     151      valid();
     152      if (!bfs_queue.empty() && bfs_queue.front().valid()) {
    160153        out_edge_iterator e=bfs_queue.front();
    161154        node_iterator w=G.head(e);
     
    163156          bfs_queue.push(G.first_out_edge(w));
    164157          reached.put(w, true);
    165           newly_reached=true;
     158          _newly_reached=true;
    166159        } else {
    167           newly_reached=false;
     160          _newly_reached=false;
    168161        }
    169162      }
    170163      return *this;
    171164    }
    172     bool is_valid() {
    173       while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
     165    bool valid() {
     166      while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
    174167      if (bfs_queue.empty()) return false; else return true;
    175168    }
    176169    operator edge_iterator () { return bfs_queue.front(); }
    177     bool is_newly_reached() { return newly_reached; }
     170    bool newly_reached() { return _newly_reached; }
    178171
    179172  };
Note: See TracChangeset for help on using the changeset viewer.