Changeset 11:33a84426c221 in lemon0.x for src/work
 Timestamp:
 01/12/04 12:48:49 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@24
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/marci_bfs.hh
r9 r11 128 128 }; 129 129 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 }; 130 180 131 181 } // namespace marci
Note: See TracChangeset
for help on using the changeset viewer.