6 #include <stack> |
6 #include <stack> |
7 #include <utility> |
7 #include <utility> |
8 |
8 |
9 namespace hugo { |
9 namespace hugo { |
10 |
10 |
11 // template <typename Graph> |
|
12 // struct bfs { |
|
13 // typedef typename Graph::Node Node; |
|
14 // typedef typename Graph::Edge Edge; |
|
15 // typedef typename Graph::NodeIt NodeIt; |
|
16 // typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
17 // Graph& G; |
|
18 // Node s; |
|
19 // typename Graph::NodeMap<bool> reached; |
|
20 // typename Graph::NodeMap<Edge> pred; |
|
21 // typename Graph::NodeMap<int> dist; |
|
22 // std::queue<Node> bfs_queue; |
|
23 // bfs(Graph& _G, Node _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) { |
|
24 // bfs_queue.push(s); |
|
25 // for(NodeIt i=G.template first<NodeIt>(); 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 // Node v=bfs_queue.front(); |
|
34 // OutEdgeIt e=G.template first<OutEdgeIt>(v); |
|
35 // bfs_queue.pop(); |
|
36 // for( ; e.valid(); ++e) { |
|
37 // Node 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::Node Node; |
|
56 // typedef typename Graph::Edge Edge; |
|
57 // typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
58 // Graph& G; |
|
59 // bfs_visitor(Graph& _G) : G(_G) { } |
|
60 // void at_previously_reached(OutEdgeIt& e) { |
|
61 // //Node v=G.aNode(e); |
|
62 // Node w=G.bNode(e); |
|
63 // std::cout << G.id(w) << " is already reached" << std::endl; |
|
64 // } |
|
65 // void at_newly_reached(OutEdgeIt& e) { |
|
66 // //Node v=G.aNode(e); |
|
67 // Node 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::Node Node; |
|
75 // typedef typename Graph::Edge Edge; |
|
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 // //Node v=G.aNode(e); |
|
86 // Node 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 Edge () { return bfs_queue.front(); } |
|
123 |
|
124 // }; |
|
125 |
|
126 // template <typename Graph, typename ReachedMap> |
|
127 // struct bfs_iterator1 { |
|
128 // typedef typename Graph::Node Node; |
|
129 // typedef typename Graph::Edge Edge; |
|
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 // Node 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 // Node 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::Node Node; |
|
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 // Node 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 // Node 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 // Node 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::Node Node; |
|
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 // Node 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 // Node 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::Node Node; |
|
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 // Node 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 // Node 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 // Node 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::Node Node; |
|
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 // // Node 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 // Node 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::Node Node; |
|
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(Node 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 // Node 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 // Node 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 // Node 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::Node Node; |
|
475 // const Graph& G; |
|
476 // std::queue< std::pair<Node, 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(Node s) { |
|
483 // reached.set(s, true); |
|
484 // if (bfs_queue.empty()) { |
|
485 // bfs_queue.push(std::pair<Node, OutEdgeIt>(s, G.template first<OutEdgeIt>(s))); |
|
486 // actual_edge=bfs_queue.front().second; |
|
487 // if (actual_edge.valid()) { |
|
488 // Node w=G.bNode(actual_edge); |
|
489 // if (!reached.get(w)) { |
|
490 // bfs_queue.push(std::pair<Node, 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<Node, 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 // Node w=G.bNode(actual_edge); |
|
509 // if (!reached.get(w)) { |
|
510 // bfs_queue.push(std::pair<Node, 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 // Node w=G.bNode(actual_edge); |
|
523 // if (!reached.get(w)) { |
|
524 // bfs_queue.push(std::pair<Node, 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 // Node aNode() const { return bfs_queue.front().first; } |
|
540 // Node bNode() const { return G.bNode(actual_edge); } |
|
541 // const ReachedMap& getReachedMap() const { return reached; } |
|
542 // //const std::queue< std::pair<Node, 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::Node Node; |
|
550 // const Graph& G; |
|
551 // std::queue<Node> 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(Node 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./*getF*/first(actual_edge, s); |
|
573 // //std::cout << "kiki" << std::endl; |
|
574 // if (G.valid(actual_edge)/*.valid()*/) { |
|
575 // Node 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 // Node 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./*getF*/first(actual_edge, bfs_queue.front()); |
|
607 // if (G.valid(actual_edge)/*.valid()*/) { |
|
608 // Node 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 // Node aNode() const { return bfs_queue.front(); } |
|
626 // Node bNode() const { return G.bNode(actual_edge); } |
|
627 // const ReachedMap& getReachedMap() const { return reached; } |
|
628 // const std::queue<Node>& getBfsQueue() const { return bfs_queue; } |
|
629 // }; |
|
630 |
|
631 |
|
632 template <typename Graph, /*typename OutEdgeIt,*/ |
11 template <typename Graph, /*typename OutEdgeIt,*/ |
633 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
12 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
634 class BfsIterator5 { |
13 class BfsIterator { |
635 protected: |
14 protected: |
636 typedef typename Graph::Node Node; |
15 typedef typename Graph::Node Node; |
637 typedef typename Graph::OutEdgeIt OutEdgeIt; |
16 typedef typename Graph::OutEdgeIt OutEdgeIt; |
638 const Graph* graph; |
17 const Graph* graph; |
639 std::queue<Node> bfs_queue; |
18 std::queue<Node> bfs_queue; |
640 ReachedMap& reached; |
19 ReachedMap& reached; |
641 bool b_node_newly_reached; |
20 bool b_node_newly_reached; |
642 OutEdgeIt actual_edge; |
21 OutEdgeIt actual_edge; |
643 bool own_reached_map; |
22 bool own_reached_map; |
644 public: |
23 public: |
645 BfsIterator5(const Graph& _graph, ReachedMap& _reached) : |
24 BfsIterator(const Graph& _graph, ReachedMap& _reached) : |
646 graph(&_graph), reached(_reached), |
25 graph(&_graph), reached(_reached), |
647 own_reached_map(false) { } |
26 own_reached_map(false) { } |
648 BfsIterator5(const Graph& _graph) : |
27 BfsIterator(const Graph& _graph) : |
649 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), |
28 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), |
650 own_reached_map(true) { } |
29 own_reached_map(true) { } |
651 ~BfsIterator5() { if (own_reached_map) delete &reached; } |
30 ~BfsIterator() { if (own_reached_map) delete &reached; } |
652 void pushAndSetReached(Node s) { |
31 void pushAndSetReached(Node s) { |
653 reached.set(s, true); |
32 reached.set(s, true); |
654 if (bfs_queue.empty()) { |
33 if (bfs_queue.empty()) { |
655 bfs_queue.push(s); |
34 bfs_queue.push(s); |
656 graph->first(actual_edge, s); |
35 graph->first(actual_edge, s); |