125 //} |
125 //} |
126 operator edge_iterator () { return bfs_queue.front(); } |
126 operator edge_iterator () { return bfs_queue.front(); } |
127 |
127 |
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 } // namespace marci |
181 } // namespace marci |
132 |
182 |
133 #endif //MARCI_BFS_HH |
183 #endif //MARCI_BFS_HH |