|
1 // -*- c++ -*- |
|
2 #ifndef BFS_ITERATOR_H |
|
3 #define BFS_ITERATOR_H |
|
4 |
|
5 #include <queue> |
|
6 #include <stack> |
|
7 #include <utility> |
|
8 #include <graph_wrapper.h> |
|
9 |
|
10 namespace hugo { |
|
11 |
|
12 template <typename Graph> |
|
13 struct bfs { |
|
14 typedef typename Graph::Node Node; |
|
15 typedef typename Graph::Edge Edge; |
|
16 typedef typename Graph::NodeIt NodeIt; |
|
17 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
18 Graph& G; |
|
19 Node s; |
|
20 typename Graph::NodeMap<bool> reached; |
|
21 typename Graph::NodeMap<Edge> pred; |
|
22 typename Graph::NodeMap<int> dist; |
|
23 std::queue<Node> bfs_queue; |
|
24 bfs(Graph& _G, Node _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) { |
|
25 bfs_queue.push(s); |
|
26 for(NodeIt i=G.template first<NodeIt>(); i.valid(); ++i) |
|
27 reached.set(i, false); |
|
28 reached.set(s, true); |
|
29 dist.set(s, 0); |
|
30 } |
|
31 |
|
32 void run() { |
|
33 while (!bfs_queue.empty()) { |
|
34 Node v=bfs_queue.front(); |
|
35 OutEdgeIt e=G.template first<OutEdgeIt>(v); |
|
36 bfs_queue.pop(); |
|
37 for( ; e.valid(); ++e) { |
|
38 Node w=G.bNode(e); |
|
39 std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl; |
|
40 if (!reached.get(w)) { |
|
41 std::cout << G.id(w) << " is newly reached :-)" << std::endl; |
|
42 bfs_queue.push(w); |
|
43 dist.set(w, dist.get(v)+1); |
|
44 pred.set(w, e); |
|
45 reached.set(w, true); |
|
46 } else { |
|
47 std::cout << G.id(w) << " is already reached" << std::endl; |
|
48 } |
|
49 } |
|
50 } |
|
51 } |
|
52 }; |
|
53 |
|
54 // template <typename Graph> |
|
55 // struct bfs_visitor { |
|
56 // typedef typename Graph::Node Node; |
|
57 // typedef typename Graph::Edge Edge; |
|
58 // typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
59 // Graph& G; |
|
60 // bfs_visitor(Graph& _G) : G(_G) { } |
|
61 // void at_previously_reached(OutEdgeIt& e) { |
|
62 // //Node v=G.aNode(e); |
|
63 // Node w=G.bNode(e); |
|
64 // std::cout << G.id(w) << " is already reached" << std::endl; |
|
65 // } |
|
66 // void at_newly_reached(OutEdgeIt& e) { |
|
67 // //Node v=G.aNode(e); |
|
68 // Node w=G.bNode(e); |
|
69 // std::cout << G.id(w) << " is newly reached :-)" << std::endl; |
|
70 // } |
|
71 // }; |
|
72 |
|
73 // template <typename Graph, typename ReachedMap, typename visitor_type> |
|
74 // struct bfs_iterator { |
|
75 // typedef typename Graph::Node Node; |
|
76 // typedef typename Graph::Edge Edge; |
|
77 // typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
78 // Graph& G; |
|
79 // std::queue<OutEdgeIt>& bfs_queue; |
|
80 // ReachedMap& reached; |
|
81 // visitor_type& visitor; |
|
82 // void process() { |
|
83 // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } |
|
84 // if (bfs_queue.empty()) return; |
|
85 // OutEdgeIt e=bfs_queue.front(); |
|
86 // //Node v=G.aNode(e); |
|
87 // Node w=G.bNode(e); |
|
88 // if (!reached.get(w)) { |
|
89 // visitor.at_newly_reached(e); |
|
90 // bfs_queue.push(G.template first<OutEdgeIt>(w)); |
|
91 // reached.set(w, true); |
|
92 // } else { |
|
93 // visitor.at_previously_reached(e); |
|
94 // } |
|
95 // } |
|
96 // bfs_iterator(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) { |
|
97 // //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } |
|
98 // valid(); |
|
99 // } |
|
100 // bfs_iterator<Graph, ReachedMap, visitor_type>& operator++() { |
|
101 // //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } |
|
102 // //if (bfs_queue.empty()) return *this; |
|
103 // if (!valid()) return *this; |
|
104 // ++(bfs_queue.front()); |
|
105 // //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } |
|
106 // valid(); |
|
107 // return *this; |
|
108 // } |
|
109 // //void next() { |
|
110 // // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } |
|
111 // // if (bfs_queue.empty()) return; |
|
112 // // ++(bfs_queue.front()); |
|
113 // // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } |
|
114 // //} |
|
115 // bool valid() { |
|
116 // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } |
|
117 // if (bfs_queue.empty()) return false; else return true; |
|
118 // } |
|
119 // //bool finished() { |
|
120 // // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } |
|
121 // // if (bfs_queue.empty()) return true; else return false; |
|
122 // //} |
|
123 // operator Edge () { return bfs_queue.front(); } |
|
124 |
|
125 // }; |
|
126 |
|
127 // template <typename Graph, typename ReachedMap> |
|
128 // struct bfs_iterator1 { |
|
129 // typedef typename Graph::Node Node; |
|
130 // typedef typename Graph::Edge Edge; |
|
131 // typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
132 // Graph& G; |
|
133 // std::queue<OutEdgeIt>& bfs_queue; |
|
134 // ReachedMap& reached; |
|
135 // bool _newly_reached; |
|
136 // bfs_iterator1(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) { |
|
137 // valid(); |
|
138 // if (!bfs_queue.empty() && bfs_queue.front().valid()) { |
|
139 // OutEdgeIt e=bfs_queue.front(); |
|
140 // Node w=G.bNode(e); |
|
141 // if (!reached.get(w)) { |
|
142 // bfs_queue.push(G.template first<OutEdgeIt>(w)); |
|
143 // reached.set(w, true); |
|
144 // _newly_reached=true; |
|
145 // } else { |
|
146 // _newly_reached=false; |
|
147 // } |
|
148 // } |
|
149 // } |
|
150 // bfs_iterator1<Graph, ReachedMap>& operator++() { |
|
151 // if (!valid()) return *this; |
|
152 // ++(bfs_queue.front()); |
|
153 // valid(); |
|
154 // if (!bfs_queue.empty() && bfs_queue.front().valid()) { |
|
155 // OutEdgeIt e=bfs_queue.front(); |
|
156 // Node w=G.bNode(e); |
|
157 // if (!reached.get(w)) { |
|
158 // bfs_queue.push(G.template first<OutEdgeIt>(w)); |
|
159 // reached.set(w, true); |
|
160 // _newly_reached=true; |
|
161 // } else { |
|
162 // _newly_reached=false; |
|
163 // } |
|
164 // } |
|
165 // return *this; |
|
166 // } |
|
167 // bool valid() { |
|
168 // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } |
|
169 // if (bfs_queue.empty()) return false; else return true; |
|
170 // } |
|
171 // operator OutEdgeIt() { return bfs_queue.front(); } |
|
172 // //ize |
|
173 // bool newly_reached() { return _newly_reached; } |
|
174 |
|
175 // }; |
|
176 |
|
177 // template <typename Graph, typename OutEdgeIt, typename ReachedMap> |
|
178 // struct BfsIterator { |
|
179 // typedef typename Graph::Node Node; |
|
180 // Graph& G; |
|
181 // std::queue<OutEdgeIt>& bfs_queue; |
|
182 // ReachedMap& reached; |
|
183 // bool b_node_newly_reached; |
|
184 // OutEdgeIt actual_edge; |
|
185 // BfsIterator(Graph& _G, |
|
186 // std::queue<OutEdgeIt>& _bfs_queue, |
|
187 // ReachedMap& _reached) : |
|
188 // G(_G), bfs_queue(_bfs_queue), reached(_reached) { |
|
189 // actual_edge=bfs_queue.front(); |
|
190 // if (actual_edge.valid()) { |
|
191 // Node w=G.bNode(actual_edge); |
|
192 // if (!reached.get(w)) { |
|
193 // bfs_queue.push(G.firstOutEdge(w)); |
|
194 // reached.set(w, true); |
|
195 // b_node_newly_reached=true; |
|
196 // } else { |
|
197 // b_node_newly_reached=false; |
|
198 // } |
|
199 // } |
|
200 // } |
|
201 // BfsIterator<Graph, OutEdgeIt, ReachedMap>& |
|
202 // operator++() { |
|
203 // if (bfs_queue.front().valid()) { |
|
204 // ++(bfs_queue.front()); |
|
205 // actual_edge=bfs_queue.front(); |
|
206 // if (actual_edge.valid()) { |
|
207 // Node w=G.bNode(actual_edge); |
|
208 // if (!reached.get(w)) { |
|
209 // bfs_queue.push(G.firstOutEdge(w)); |
|
210 // reached.set(w, true); |
|
211 // b_node_newly_reached=true; |
|
212 // } else { |
|
213 // b_node_newly_reached=false; |
|
214 // } |
|
215 // } |
|
216 // } else { |
|
217 // bfs_queue.pop(); |
|
218 // actual_edge=bfs_queue.front(); |
|
219 // if (actual_edge.valid()) { |
|
220 // Node w=G.bNode(actual_edge); |
|
221 // if (!reached.get(w)) { |
|
222 // bfs_queue.push(G.firstOutEdge(w)); |
|
223 // reached.set(w, true); |
|
224 // b_node_newly_reached=true; |
|
225 // } else { |
|
226 // b_node_newly_reached=false; |
|
227 // } |
|
228 // } |
|
229 // } |
|
230 // return *this; |
|
231 // } |
|
232 // bool finished() { return bfs_queue.empty(); } |
|
233 // operator OutEdgeIt () { return actual_edge; } |
|
234 // bool bNodeIsNewlyReached() { return b_node_newly_reached; } |
|
235 // bool aNodeIsExamined() { return !(actual_edge.valid()); } |
|
236 // }; |
|
237 |
|
238 |
|
239 // template <typename Graph, typename OutEdgeIt, typename ReachedMap> |
|
240 // struct DfsIterator { |
|
241 // typedef typename Graph::Node Node; |
|
242 // Graph& G; |
|
243 // std::stack<OutEdgeIt>& bfs_queue; |
|
244 // ReachedMap& reached; |
|
245 // bool b_node_newly_reached; |
|
246 // OutEdgeIt actual_edge; |
|
247 // DfsIterator(Graph& _G, |
|
248 // std::stack<OutEdgeIt>& _bfs_queue, |
|
249 // ReachedMap& _reached) : |
|
250 // G(_G), bfs_queue(_bfs_queue), reached(_reached) { |
|
251 // actual_edge=bfs_queue.top(); |
|
252 // if (actual_edge.valid()) { |
|
253 // Node w=G.bNode(actual_edge); |
|
254 // if (!reached.get(w)) { |
|
255 // bfs_queue.push(G.firstOutEdge(w)); |
|
256 // reached.set(w, true); |
|
257 // b_node_newly_reached=true; |
|
258 // } else { |
|
259 // ++(bfs_queue.top()); |
|
260 // b_node_newly_reached=false; |
|
261 // } |
|
262 // } else { |
|
263 // bfs_queue.pop(); |
|
264 // } |
|
265 // } |
|
266 // DfsIterator<Graph, OutEdgeIt, ReachedMap>& |
|
267 // operator++() { |
|
268 // actual_edge=bfs_queue.top(); |
|
269 // if (actual_edge.valid()) { |
|
270 // Node w=G.bNode(actual_edge); |
|
271 // if (!reached.get(w)) { |
|
272 // bfs_queue.push(G.firstOutEdge(w)); |
|
273 // reached.set(w, true); |
|
274 // b_node_newly_reached=true; |
|
275 // } else { |
|
276 // ++(bfs_queue.top()); |
|
277 // b_node_newly_reached=false; |
|
278 // } |
|
279 // } else { |
|
280 // bfs_queue.pop(); |
|
281 // } |
|
282 // return *this; |
|
283 // } |
|
284 // bool finished() { return bfs_queue.empty(); } |
|
285 // operator OutEdgeIt () { return actual_edge; } |
|
286 // bool bNodeIsNewlyReached() { return b_node_newly_reached; } |
|
287 // bool aNodeIsExamined() { return !(actual_edge.valid()); } |
|
288 // }; |
|
289 |
|
290 // template <typename Graph, typename OutEdgeIt, typename ReachedMap> |
|
291 // struct BfsIterator1 { |
|
292 // typedef typename Graph::Node Node; |
|
293 // Graph& G; |
|
294 // std::queue<OutEdgeIt>& bfs_queue; |
|
295 // ReachedMap& reached; |
|
296 // bool b_node_newly_reached; |
|
297 // OutEdgeIt actual_edge; |
|
298 // BfsIterator1(Graph& _G, |
|
299 // std::queue<OutEdgeIt>& _bfs_queue, |
|
300 // ReachedMap& _reached) : |
|
301 // G(_G), bfs_queue(_bfs_queue), reached(_reached) { |
|
302 // actual_edge=bfs_queue.front(); |
|
303 // if (actual_edge.valid()) { |
|
304 // Node w=G.bNode(actual_edge); |
|
305 // if (!reached.get(w)) { |
|
306 // bfs_queue.push(OutEdgeIt(G, w)); |
|
307 // reached.set(w, true); |
|
308 // b_node_newly_reached=true; |
|
309 // } else { |
|
310 // b_node_newly_reached=false; |
|
311 // } |
|
312 // } |
|
313 // } |
|
314 // void next() { |
|
315 // if (bfs_queue.front().valid()) { |
|
316 // ++(bfs_queue.front()); |
|
317 // actual_edge=bfs_queue.front(); |
|
318 // if (actual_edge.valid()) { |
|
319 // Node w=G.bNode(actual_edge); |
|
320 // if (!reached.get(w)) { |
|
321 // bfs_queue.push(OutEdgeIt(G, w)); |
|
322 // reached.set(w, true); |
|
323 // b_node_newly_reached=true; |
|
324 // } else { |
|
325 // b_node_newly_reached=false; |
|
326 // } |
|
327 // } |
|
328 // } else { |
|
329 // bfs_queue.pop(); |
|
330 // actual_edge=bfs_queue.front(); |
|
331 // if (actual_edge.valid()) { |
|
332 // Node w=G.bNode(actual_edge); |
|
333 // if (!reached.get(w)) { |
|
334 // bfs_queue.push(OutEdgeIt(G, w)); |
|
335 // reached.set(w, true); |
|
336 // b_node_newly_reached=true; |
|
337 // } else { |
|
338 // b_node_newly_reached=false; |
|
339 // } |
|
340 // } |
|
341 // } |
|
342 // //return *this; |
|
343 // } |
|
344 // bool finished() { return bfs_queue.empty(); } |
|
345 // operator OutEdgeIt () { return actual_edge; } |
|
346 // bool bNodeIsNewlyReached() { return b_node_newly_reached; } |
|
347 // bool aNodeIsExamined() { return !(actual_edge.valid()); } |
|
348 // }; |
|
349 |
|
350 |
|
351 // template <typename Graph, typename OutEdgeIt, typename ReachedMap> |
|
352 // struct DfsIterator1 { |
|
353 // typedef typename Graph::Node Node; |
|
354 // Graph& G; |
|
355 // std::stack<OutEdgeIt>& bfs_queue; |
|
356 // ReachedMap& reached; |
|
357 // bool b_node_newly_reached; |
|
358 // OutEdgeIt actual_edge; |
|
359 // DfsIterator1(Graph& _G, |
|
360 // std::stack<OutEdgeIt>& _bfs_queue, |
|
361 // ReachedMap& _reached) : |
|
362 // G(_G), bfs_queue(_bfs_queue), reached(_reached) { |
|
363 // //actual_edge=bfs_queue.top(); |
|
364 // //if (actual_edge.valid()) { |
|
365 // // Node w=G.bNode(actual_edge); |
|
366 // //if (!reached.get(w)) { |
|
367 // // bfs_queue.push(OutEdgeIt(G, w)); |
|
368 // // reached.set(w, true); |
|
369 // // b_node_newly_reached=true; |
|
370 // //} else { |
|
371 // // ++(bfs_queue.top()); |
|
372 // // b_node_newly_reached=false; |
|
373 // //} |
|
374 // //} else { |
|
375 // // bfs_queue.pop(); |
|
376 // //} |
|
377 // } |
|
378 // void next() { |
|
379 // actual_edge=bfs_queue.top(); |
|
380 // if (actual_edge.valid()) { |
|
381 // Node w=G.bNode(actual_edge); |
|
382 // if (!reached.get(w)) { |
|
383 // bfs_queue.push(OutEdgeIt(G, w)); |
|
384 // reached.set(w, true); |
|
385 // b_node_newly_reached=true; |
|
386 // } else { |
|
387 // ++(bfs_queue.top()); |
|
388 // b_node_newly_reached=false; |
|
389 // } |
|
390 // } else { |
|
391 // bfs_queue.pop(); |
|
392 // } |
|
393 // //return *this; |
|
394 // } |
|
395 // bool finished() { return bfs_queue.empty(); } |
|
396 // operator OutEdgeIt () { return actual_edge; } |
|
397 // bool bNodeIsNewlyReached() { return b_node_newly_reached; } |
|
398 // bool aNodeIsLeaved() { return !(actual_edge.valid()); } |
|
399 // }; |
|
400 |
|
401 // template <typename Graph, typename OutEdgeIt, typename ReachedMap> |
|
402 // class BfsIterator2 { |
|
403 // typedef typename Graph::Node Node; |
|
404 // const Graph& G; |
|
405 // std::queue<OutEdgeIt> bfs_queue; |
|
406 // ReachedMap reached; |
|
407 // bool b_node_newly_reached; |
|
408 // OutEdgeIt actual_edge; |
|
409 // public: |
|
410 // BfsIterator2(const Graph& _G) : G(_G), reached(G, false) { } |
|
411 // void pushAndSetReached(Node s) { |
|
412 // reached.set(s, true); |
|
413 // if (bfs_queue.empty()) { |
|
414 // bfs_queue.push(G.template first<OutEdgeIt>(s)); |
|
415 // actual_edge=bfs_queue.front(); |
|
416 // if (actual_edge.valid()) { |
|
417 // Node w=G.bNode(actual_edge); |
|
418 // if (!reached.get(w)) { |
|
419 // bfs_queue.push(G.template first<OutEdgeIt>(w)); |
|
420 // reached.set(w, true); |
|
421 // b_node_newly_reached=true; |
|
422 // } else { |
|
423 // b_node_newly_reached=false; |
|
424 // } |
|
425 // } //else { |
|
426 // //} |
|
427 // } else { |
|
428 // bfs_queue.push(G.template first<OutEdgeIt>(s)); |
|
429 // } |
|
430 // } |
|
431 // BfsIterator2<Graph, OutEdgeIt, ReachedMap>& |
|
432 // operator++() { |
|
433 // if (bfs_queue.front().valid()) { |
|
434 // ++(bfs_queue.front()); |
|
435 // actual_edge=bfs_queue.front(); |
|
436 // if (actual_edge.valid()) { |
|
437 // Node w=G.bNode(actual_edge); |
|
438 // if (!reached.get(w)) { |
|
439 // bfs_queue.push(G.template first<OutEdgeIt>(w)); |
|
440 // reached.set(w, true); |
|
441 // b_node_newly_reached=true; |
|
442 // } else { |
|
443 // b_node_newly_reached=false; |
|
444 // } |
|
445 // } |
|
446 // } else { |
|
447 // bfs_queue.pop(); |
|
448 // if (!bfs_queue.empty()) { |
|
449 // actual_edge=bfs_queue.front(); |
|
450 // if (actual_edge.valid()) { |
|
451 // Node w=G.bNode(actual_edge); |
|
452 // if (!reached.get(w)) { |
|
453 // bfs_queue.push(G.template first<OutEdgeIt>(w)); |
|
454 // reached.set(w, true); |
|
455 // b_node_newly_reached=true; |
|
456 // } else { |
|
457 // b_node_newly_reached=false; |
|
458 // } |
|
459 // } |
|
460 // } |
|
461 // } |
|
462 // return *this; |
|
463 // } |
|
464 // bool finished() const { return bfs_queue.empty(); } |
|
465 // operator OutEdgeIt () const { return actual_edge; } |
|
466 // bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
|
467 // bool isANodeExamined() const { return !(actual_edge.valid()); } |
|
468 // const ReachedMap& getReachedMap() const { return reached; } |
|
469 // const std::queue<OutEdgeIt>& getBfsQueue() const { return bfs_queue; } |
|
470 // }; |
|
471 |
|
472 |
|
473 // template <typename Graph, typename OutEdgeIt, typename ReachedMap> |
|
474 // class BfsIterator3 { |
|
475 // typedef typename Graph::Node Node; |
|
476 // const Graph& G; |
|
477 // std::queue< std::pair<Node, OutEdgeIt> > bfs_queue; |
|
478 // ReachedMap reached; |
|
479 // bool b_node_newly_reached; |
|
480 // OutEdgeIt actual_edge; |
|
481 // public: |
|
482 // BfsIterator3(const Graph& _G) : G(_G), reached(G, false) { } |
|
483 // void pushAndSetReached(Node s) { |
|
484 // reached.set(s, true); |
|
485 // if (bfs_queue.empty()) { |
|
486 // bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s))); |
|
487 // actual_edge=bfs_queue.front().second; |
|
488 // if (actual_edge.valid()) { |
|
489 // Node w=G.bNode(actual_edge); |
|
490 // if (!reached.get(w)) { |
|
491 // bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w))); |
|
492 // reached.set(w, true); |
|
493 // b_node_newly_reached=true; |
|
494 // } else { |
|
495 // b_node_newly_reached=false; |
|
496 // } |
|
497 // } //else { |
|
498 // //} |
|
499 // } else { |
|
500 // bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s))); |
|
501 // } |
|
502 // } |
|
503 // BfsIterator3<Graph, OutEdgeIt, ReachedMap>& |
|
504 // operator++() { |
|
505 // if (bfs_queue.front().second.valid()) { |
|
506 // ++(bfs_queue.front().second); |
|
507 // actual_edge=bfs_queue.front().second; |
|
508 // if (actual_edge.valid()) { |
|
509 // Node w=G.bNode(actual_edge); |
|
510 // if (!reached.get(w)) { |
|
511 // bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w))); |
|
512 // reached.set(w, true); |
|
513 // b_node_newly_reached=true; |
|
514 // } else { |
|
515 // b_node_newly_reached=false; |
|
516 // } |
|
517 // } |
|
518 // } else { |
|
519 // bfs_queue.pop(); |
|
520 // if (!bfs_queue.empty()) { |
|
521 // actual_edge=bfs_queue.front().second; |
|
522 // if (actual_edge.valid()) { |
|
523 // Node w=G.bNode(actual_edge); |
|
524 // if (!reached.get(w)) { |
|
525 // bfs_queue.push(std::pair<Node, OutEdgeIt>(w, G.template first<OutEdgeIt>(w))); |
|
526 // reached.set(w, true); |
|
527 // b_node_newly_reached=true; |
|
528 // } else { |
|
529 // b_node_newly_reached=false; |
|
530 // } |
|
531 // } |
|
532 // } |
|
533 // } |
|
534 // return *this; |
|
535 // } |
|
536 // bool finished() const { return bfs_queue.empty(); } |
|
537 // operator OutEdgeIt () const { return actual_edge; } |
|
538 // bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
|
539 // bool isANodeExamined() const { return !(actual_edge.valid()); } |
|
540 // Node aNode() const { return bfs_queue.front().first; } |
|
541 // Node bNode() const { return G.bNode(actual_edge); } |
|
542 // const ReachedMap& getReachedMap() const { return reached; } |
|
543 // //const std::queue< std::pair<Node, OutEdgeIt> >& getBfsQueue() const { return bfs_queue; } |
|
544 // }; |
|
545 |
|
546 |
|
547 template <typename Graph, typename OutEdgeIt, |
|
548 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
|
549 class BfsIterator4 { |
|
550 typedef typename Graph::Node Node; |
|
551 const Graph& G; |
|
552 std::queue<Node> bfs_queue; |
|
553 ReachedMap& reached; |
|
554 bool b_node_newly_reached; |
|
555 OutEdgeIt actual_edge; |
|
556 bool own_reached_map; |
|
557 public: |
|
558 BfsIterator4(const Graph& _G, ReachedMap& _reached) : |
|
559 G(_G), reached(_reached), |
|
560 own_reached_map(false) { } |
|
561 BfsIterator4(const Graph& _G) : |
|
562 G(_G), reached(*(new ReachedMap(G /*, false*/))), |
|
563 own_reached_map(true) { } |
|
564 ~BfsIterator4() { if (own_reached_map) delete &reached; } |
|
565 void pushAndSetReached(Node s) { |
|
566 //std::cout << "mimi" << &reached << std::endl; |
|
567 reached.set(s, true); |
|
568 //std::cout << "mumus" << std::endl; |
|
569 if (bfs_queue.empty()) { |
|
570 //std::cout << "bibi1" << std::endl; |
|
571 bfs_queue.push(s); |
|
572 //std::cout << "zizi" << std::endl; |
|
573 G./*getF*/first(actual_edge, s); |
|
574 //std::cout << "kiki" << std::endl; |
|
575 if (G.valid(actual_edge)/*.valid()*/) { |
|
576 Node w=G.bNode(actual_edge); |
|
577 if (!reached.get(w)) { |
|
578 bfs_queue.push(w); |
|
579 reached.set(w, true); |
|
580 b_node_newly_reached=true; |
|
581 } else { |
|
582 b_node_newly_reached=false; |
|
583 } |
|
584 } |
|
585 } else { |
|
586 //std::cout << "bibi2" << std::endl; |
|
587 bfs_queue.push(s); |
|
588 } |
|
589 } |
|
590 BfsIterator4<Graph, OutEdgeIt, ReachedMap>& |
|
591 operator++() { |
|
592 if (G.valid(actual_edge)/*.valid()*/) { |
|
593 /*++*/G.next(actual_edge); |
|
594 if (G.valid(actual_edge)/*.valid()*/) { |
|
595 Node w=G.bNode(actual_edge); |
|
596 if (!reached.get(w)) { |
|
597 bfs_queue.push(w); |
|
598 reached.set(w, true); |
|
599 b_node_newly_reached=true; |
|
600 } else { |
|
601 b_node_newly_reached=false; |
|
602 } |
|
603 } |
|
604 } else { |
|
605 bfs_queue.pop(); |
|
606 if (!bfs_queue.empty()) { |
|
607 G./*getF*/first(actual_edge, bfs_queue.front()); |
|
608 if (G.valid(actual_edge)/*.valid()*/) { |
|
609 Node w=G.bNode(actual_edge); |
|
610 if (!reached.get(w)) { |
|
611 bfs_queue.push(w); |
|
612 reached.set(w, true); |
|
613 b_node_newly_reached=true; |
|
614 } else { |
|
615 b_node_newly_reached=false; |
|
616 } |
|
617 } |
|
618 } |
|
619 } |
|
620 return *this; |
|
621 } |
|
622 bool finished() const { return bfs_queue.empty(); } |
|
623 operator OutEdgeIt () const { return actual_edge; } |
|
624 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
|
625 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } |
|
626 Node aNode() const { return bfs_queue.front(); } |
|
627 Node bNode() const { return G.bNode(actual_edge); } |
|
628 const ReachedMap& getReachedMap() const { return reached; } |
|
629 const std::queue<Node>& getBfsQueue() const { return bfs_queue; } |
|
630 }; |
|
631 |
|
632 |
|
633 template <typename GraphWrapper, /*typename OutEdgeIt,*/ |
|
634 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ > |
|
635 class BfsIterator5 { |
|
636 typedef typename GraphWrapper::Node Node; |
|
637 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; |
|
638 GraphWrapper G; |
|
639 std::queue<Node> bfs_queue; |
|
640 ReachedMap& reached; |
|
641 bool b_node_newly_reached; |
|
642 OutEdgeIt actual_edge; |
|
643 bool own_reached_map; |
|
644 public: |
|
645 BfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) : |
|
646 G(_G), reached(_reached), |
|
647 own_reached_map(false) { } |
|
648 BfsIterator5(const GraphWrapper& _G) : |
|
649 G(_G), reached(*(new ReachedMap(G /*, false*/))), |
|
650 own_reached_map(true) { } |
|
651 // BfsIterator5(const typename GraphWrapper::BaseGraph& _G, |
|
652 // ReachedMap& _reached) : |
|
653 // G(_G), reached(_reached), |
|
654 // own_reached_map(false) { } |
|
655 // BfsIterator5(const typename GraphWrapper::BaseGraph& _G) : |
|
656 // G(_G), reached(*(new ReachedMap(G /*, false*/))), |
|
657 // own_reached_map(true) { } |
|
658 ~BfsIterator5() { if (own_reached_map) delete &reached; } |
|
659 void pushAndSetReached(Node s) { |
|
660 reached.set(s, true); |
|
661 if (bfs_queue.empty()) { |
|
662 bfs_queue.push(s); |
|
663 G./*getF*/first(actual_edge, s); |
|
664 if (G.valid(actual_edge)/*.valid()*/) { |
|
665 Node w=G.bNode(actual_edge); |
|
666 if (!reached.get(w)) { |
|
667 bfs_queue.push(w); |
|
668 reached.set(w, true); |
|
669 b_node_newly_reached=true; |
|
670 } else { |
|
671 b_node_newly_reached=false; |
|
672 } |
|
673 } |
|
674 } else { |
|
675 bfs_queue.push(s); |
|
676 } |
|
677 } |
|
678 BfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>& |
|
679 operator++() { |
|
680 if (G.valid(actual_edge)/*.valid()*/) { |
|
681 /*++*/G.next(actual_edge); |
|
682 if (G.valid(actual_edge)/*.valid()*/) { |
|
683 Node w=G.bNode(actual_edge); |
|
684 if (!reached.get(w)) { |
|
685 bfs_queue.push(w); |
|
686 reached.set(w, true); |
|
687 b_node_newly_reached=true; |
|
688 } else { |
|
689 b_node_newly_reached=false; |
|
690 } |
|
691 } |
|
692 } else { |
|
693 bfs_queue.pop(); |
|
694 if (!bfs_queue.empty()) { |
|
695 G./*getF*/first(actual_edge, bfs_queue.front()); |
|
696 if (G.valid(actual_edge)/*.valid()*/) { |
|
697 Node w=G.bNode(actual_edge); |
|
698 if (!reached.get(w)) { |
|
699 bfs_queue.push(w); |
|
700 reached.set(w, true); |
|
701 b_node_newly_reached=true; |
|
702 } else { |
|
703 b_node_newly_reached=false; |
|
704 } |
|
705 } |
|
706 } |
|
707 } |
|
708 return *this; |
|
709 } |
|
710 bool finished() const { return bfs_queue.empty(); } |
|
711 operator OutEdgeIt () const { return actual_edge; } |
|
712 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
|
713 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } |
|
714 Node aNode() const { return bfs_queue.front(); } |
|
715 Node bNode() const { return G.bNode(actual_edge); } |
|
716 const ReachedMap& getReachedMap() const { return reached; } |
|
717 const std::queue<Node>& getBfsQueue() const { return bfs_queue; } |
|
718 }; |
|
719 |
|
720 template <typename Graph, typename OutEdgeIt, |
|
721 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
|
722 class DfsIterator4 { |
|
723 typedef typename Graph::Node Node; |
|
724 const Graph& G; |
|
725 std::stack<OutEdgeIt> dfs_stack; |
|
726 bool b_node_newly_reached; |
|
727 OutEdgeIt actual_edge; |
|
728 Node actual_node; |
|
729 ReachedMap& reached; |
|
730 bool own_reached_map; |
|
731 public: |
|
732 DfsIterator4(const Graph& _G, ReachedMap& _reached) : |
|
733 G(_G), reached(_reached), |
|
734 own_reached_map(false) { } |
|
735 DfsIterator4(const Graph& _G) : |
|
736 G(_G), reached(*(new ReachedMap(G /*, false*/))), |
|
737 own_reached_map(true) { } |
|
738 ~DfsIterator4() { if (own_reached_map) delete &reached; } |
|
739 void pushAndSetReached(Node s) { |
|
740 actual_node=s; |
|
741 reached.set(s, true); |
|
742 dfs_stack.push(G.template first<OutEdgeIt>(s)); |
|
743 } |
|
744 DfsIterator4<Graph, OutEdgeIt, ReachedMap>& |
|
745 operator++() { |
|
746 actual_edge=dfs_stack.top(); |
|
747 //actual_node=G.aNode(actual_edge); |
|
748 if (G.valid(actual_edge)/*.valid()*/) { |
|
749 Node w=G.bNode(actual_edge); |
|
750 actual_node=w; |
|
751 if (!reached.get(w)) { |
|
752 dfs_stack.push(G.template first<OutEdgeIt>(w)); |
|
753 reached.set(w, true); |
|
754 b_node_newly_reached=true; |
|
755 } else { |
|
756 actual_node=G.aNode(actual_edge); |
|
757 /*++*/G.next(dfs_stack.top()); |
|
758 b_node_newly_reached=false; |
|
759 } |
|
760 } else { |
|
761 //actual_node=G.aNode(dfs_stack.top()); |
|
762 dfs_stack.pop(); |
|
763 } |
|
764 return *this; |
|
765 } |
|
766 bool finished() const { return dfs_stack.empty(); } |
|
767 operator OutEdgeIt () const { return actual_edge; } |
|
768 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
|
769 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } |
|
770 Node aNode() const { return actual_node; /*FIXME*/} |
|
771 Node bNode() const { return G.bNode(actual_edge); } |
|
772 const ReachedMap& getReachedMap() const { return reached; } |
|
773 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } |
|
774 }; |
|
775 |
|
776 template <typename GraphWrapper, /*typename OutEdgeIt,*/ |
|
777 typename ReachedMap/*=typename GraphWrapper::NodeMap<bool>*/ > |
|
778 class DfsIterator5 { |
|
779 typedef typename GraphWrapper::Node Node; |
|
780 typedef typename GraphWrapper::OutEdgeIt OutEdgeIt; |
|
781 GraphWrapper G; |
|
782 std::stack<OutEdgeIt> dfs_stack; |
|
783 bool b_node_newly_reached; |
|
784 OutEdgeIt actual_edge; |
|
785 Node actual_node; |
|
786 ReachedMap& reached; |
|
787 bool own_reached_map; |
|
788 public: |
|
789 DfsIterator5(const GraphWrapper& _G, ReachedMap& _reached) : |
|
790 G(_G), reached(_reached), |
|
791 own_reached_map(false) { } |
|
792 DfsIterator5(const GraphWrapper& _G) : |
|
793 G(_G), reached(*(new ReachedMap(G /*, false*/))), |
|
794 own_reached_map(true) { } |
|
795 ~DfsIterator5() { if (own_reached_map) delete &reached; } |
|
796 void pushAndSetReached(Node s) { |
|
797 actual_node=s; |
|
798 reached.set(s, true); |
|
799 dfs_stack.push(G.template first<OutEdgeIt>(s)); |
|
800 } |
|
801 DfsIterator5<GraphWrapper, /*OutEdgeIt,*/ ReachedMap>& |
|
802 operator++() { |
|
803 actual_edge=dfs_stack.top(); |
|
804 //actual_node=G.aNode(actual_edge); |
|
805 if (G.valid(actual_edge)/*.valid()*/) { |
|
806 Node w=G.bNode(actual_edge); |
|
807 actual_node=w; |
|
808 if (!reached.get(w)) { |
|
809 dfs_stack.push(G.template first<OutEdgeIt>(w)); |
|
810 reached.set(w, true); |
|
811 b_node_newly_reached=true; |
|
812 } else { |
|
813 actual_node=G.aNode(actual_edge); |
|
814 /*++*/G.next(dfs_stack.top()); |
|
815 b_node_newly_reached=false; |
|
816 } |
|
817 } else { |
|
818 //actual_node=G.aNode(dfs_stack.top()); |
|
819 dfs_stack.pop(); |
|
820 } |
|
821 return *this; |
|
822 } |
|
823 bool finished() const { return dfs_stack.empty(); } |
|
824 operator OutEdgeIt () const { return actual_edge; } |
|
825 bool isBNodeNewlyReached() const { return b_node_newly_reached; } |
|
826 bool isANodeExamined() const { return !(G.valid(actual_edge)/*.valid()*/); } |
|
827 Node aNode() const { return actual_node; /*FIXME*/} |
|
828 Node bNode() const { return G.bNode(actual_edge); } |
|
829 const ReachedMap& getReachedMap() const { return reached; } |
|
830 const std::stack<OutEdgeIt>& getDfsStack() const { return dfs_stack; } |
|
831 }; |
|
832 |
|
833 |
|
834 |
|
835 } // namespace hugo |
|
836 |
|
837 #endif //BFS_ITERATOR_H |