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