COIN-OR::LEMON - Graph Library

Changeset 11:33a84426c221 in lemon-0.x for src/work/marci_bfs.hh


Ignore:
Timestamp:
01/12/04 12:48:49 (21 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@24
Message:

bfs_iterator1

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci_bfs.hh

    r9 r11  
    128128  };
    129129
     130  template <typename graph_type, typename reached_type>
     131  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
     137    graph_type& G;
     138    std::queue<out_edge_iterator>& bfs_queue;
     139    reached_type& reached;
     140    bool newly_reached;
     141    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()) {
     144        out_edge_iterator e=bfs_queue.front();
     145        node_iterator w=G.head(e);
     146        if (!reached.get(w)) {
     147          bfs_queue.push(G.first_out_edge(w));
     148          reached.put(w, true);
     149          newly_reached=true;
     150        } else {
     151          newly_reached=false;
     152        }
     153      }
     154    }
     155    bfs_iterator1<graph_type, reached_type>& operator++() {
     156      if (!is_valid()) return *this;
     157      ++(bfs_queue.front());
     158      is_valid();
     159      if (!bfs_queue.empty() && bfs_queue.front().is_valid()) {
     160        out_edge_iterator e=bfs_queue.front();
     161        node_iterator w=G.head(e);
     162        if (!reached.get(w)) {
     163          bfs_queue.push(G.first_out_edge(w));
     164          reached.put(w, true);
     165          newly_reached=true;
     166        } else {
     167          newly_reached=false;
     168        }
     169      }
     170      return *this;
     171    }
     172    bool is_valid() {
     173      while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
     174      if (bfs_queue.empty()) return false; else return true;
     175    }
     176    operator edge_iterator () { return bfs_queue.front(); }
     177    bool is_newly_reached() { return newly_reached; }
     178
     179  };
    130180
    131181} // namespace marci
Note: See TracChangeset for help on using the changeset viewer.