35 /// The same as above, but the map storing the reached nodes |
43 /// The same as above, but the map storing the reached nodes |
36 /// is constructed dynamically to everywhere false. |
44 /// is constructed dynamically to everywhere false. |
37 BfsIterator(const Graph& _graph) : |
45 BfsIterator(const Graph& _graph) : |
38 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), |
46 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), |
39 own_reached_map(true) { } |
47 own_reached_map(true) { } |
40 /// The storing the reached nodes have to be destroyed if |
48 /// The map storing the reached nodes have to be destroyed if |
41 /// it was constructed dynamically |
49 /// it was constructed dynamically |
42 ~BfsIterator() { if (own_reached_map) delete &reached; } |
50 ~BfsIterator() { if (own_reached_map) delete &reached; } |
43 /// This method markes \c s reached. |
51 /// This method markes \c s reached. |
44 /// If the queue is empty, then \c s is pushed in the bfs queue |
52 /// If the queue is empty, then \c s is pushed in the bfs queue |
45 /// and the first out-edge is processed. |
53 /// and the first out-edge is processed. |
159 push(s); |
167 push(s); |
160 while (!this->finished()) this->operator++(); |
168 while (!this->finished()) this->operator++(); |
161 } |
169 } |
162 /// Beside the bfs iteration, \c pred and \dist are saved in a |
170 /// Beside the bfs iteration, \c pred and \dist are saved in a |
163 /// newly reached node. |
171 /// newly reached node. |
164 Bfs<Graph, ReachedMap, PredMap, DistMap> operator++() { |
172 Bfs<Graph, ReachedMap, PredMap, DistMap>& operator++() { |
165 Parent::operator++(); |
173 Parent::operator++(); |
166 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) |
174 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) |
167 { |
175 { |
168 pred.set(this->bNode(), this->actual_edge); |
176 pred.set(this->bNode(), this->actual_edge); |
169 dist.set(this->bNode(), dist[this->aNode()]); |
177 dist.set(this->bNode(), dist[this->aNode()]); |
294 push(s); |
302 push(s); |
295 while (!this->finished()) this->operator++(); |
303 while (!this->finished()) this->operator++(); |
296 } |
304 } |
297 /// Beside the dfs iteration, \c pred is saved in a |
305 /// Beside the dfs iteration, \c pred is saved in a |
298 /// newly reached node. |
306 /// newly reached node. |
299 Dfs<Graph, ReachedMap, PredMap> operator++() { |
307 Dfs<Graph, ReachedMap, PredMap>& operator++() { |
300 Parent::operator++(); |
308 Parent::operator++(); |
301 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) |
309 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) |
302 { |
310 { |
303 pred.set(this->bNode(), this->actual_edge); |
311 pred.set(this->bNode(), this->actual_edge); |
304 } |
312 } |