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 |
---|