|
1 #ifndef MARCI_BFS_HH |
|
2 #define MARCI_BFS_HH |
|
3 |
|
4 #include <queue> |
|
5 #include <stack> |
|
6 |
|
7 namespace marci { |
|
8 |
|
9 template <typename Graph> |
|
10 struct bfs { |
|
11 typedef typename Graph::NodeIt NodeIt; |
|
12 typedef typename Graph::EdgeIt EdgeIt; |
|
13 typedef typename Graph::EachNodeIt EachNodeIt; |
|
14 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
15 Graph& G; |
|
16 NodeIt s; |
|
17 typename Graph::NodeMap<bool> reached; |
|
18 typename Graph::NodeMap<EdgeIt> pred; |
|
19 typename Graph::NodeMap<int> dist; |
|
20 std::queue<NodeIt> bfs_queue; |
|
21 bfs(Graph& _G, NodeIt _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) { |
|
22 bfs_queue.push(s); |
|
23 for(EachNodeIt i=G.template first<EachNodeIt>(); i.valid(); ++i) |
|
24 reached.set(i, false); |
|
25 reached.set(s, true); |
|
26 dist.set(s, 0); |
|
27 } |
|
28 |
|
29 void run() { |
|
30 while (!bfs_queue.empty()) { |
|
31 NodeIt v=bfs_queue.front(); |
|
32 OutEdgeIt e=G.template first<OutEdgeIt>(v); |
|
33 bfs_queue.pop(); |
|
34 for( ; e.valid(); ++e) { |
|
35 NodeIt w=G.bNode(e); |
|
36 std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl; |
|
37 if (!reached.get(w)) { |
|
38 std::cout << G.id(w) << " is newly reached :-)" << std::endl; |
|
39 bfs_queue.push(w); |
|
40 dist.set(w, dist.get(v)+1); |
|
41 pred.set(w, e); |
|
42 reached.set(w, true); |
|
43 } else { |
|
44 std::cout << G.id(w) << " is already reached" << std::endl; |
|
45 } |
|
46 } |
|
47 } |
|
48 } |
|
49 }; |
|
50 |
|
51 template <typename Graph> |
|
52 struct bfs_visitor { |
|
53 typedef typename Graph::NodeIt NodeIt; |
|
54 typedef typename Graph::EdgeIt EdgeIt; |
|
55 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
56 Graph& G; |
|
57 bfs_visitor(Graph& _G) : G(_G) { } |
|
58 void at_previously_reached(OutEdgeIt& e) { |
|
59 //NodeIt v=G.aNode(e); |
|
60 NodeIt w=G.bNode(e); |
|
61 std::cout << G.id(w) << " is already reached" << std::endl; |
|
62 } |
|
63 void at_newly_reached(OutEdgeIt& e) { |
|
64 //NodeIt v=G.aNode(e); |
|
65 NodeIt w=G.bNode(e); |
|
66 std::cout << G.id(w) << " is newly reached :-)" << std::endl; |
|
67 } |
|
68 }; |
|
69 |
|
70 template <typename Graph, typename ReachedMap, typename visitor_type> |
|
71 struct bfs_iterator { |
|
72 typedef typename Graph::NodeIt NodeIt; |
|
73 typedef typename Graph::EdgeIt EdgeIt; |
|
74 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
75 Graph& G; |
|
76 std::queue<OutEdgeIt>& bfs_queue; |
|
77 ReachedMap& reached; |
|
78 visitor_type& visitor; |
|
79 void process() { |
|
80 while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } |
|
81 if (bfs_queue.empty()) return; |
|
82 OutEdgeIt e=bfs_queue.front(); |
|
83 //NodeIt v=G.aNode(e); |
|
84 NodeIt w=G.bNode(e); |
|
85 if (!reached.get(w)) { |
|
86 visitor.at_newly_reached(e); |
|
87 bfs_queue.push(G.template first<OutEdgeIt>(w)); |
|
88 reached.set(w, true); |
|
89 } else { |
|
90 visitor.at_previously_reached(e); |
|
91 } |
|
92 } |
|
93 bfs_iterator(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) { |
|
94 //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } |
|
95 valid(); |
|
96 } |
|
97 bfs_iterator<Graph, ReachedMap, visitor_type>& operator++() { |
|
98 //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } |
|
99 //if (bfs_queue.empty()) return *this; |
|
100 if (!valid()) return *this; |
|
101 ++(bfs_queue.front()); |
|
102 //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } |
|
103 valid(); |
|
104 return *this; |
|
105 } |
|
106 //void next() { |
|
107 // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } |
|
108 // if (bfs_queue.empty()) return; |
|
109 // ++(bfs_queue.front()); |
|
110 // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } |
|
111 //} |
|
112 bool valid() { |
|
113 while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } |
|
114 if (bfs_queue.empty()) return false; else return true; |
|
115 } |
|
116 //bool finished() { |
|
117 // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } |
|
118 // if (bfs_queue.empty()) return true; else return false; |
|
119 //} |
|
120 operator EdgeIt () { return bfs_queue.front(); } |
|
121 |
|
122 }; |
|
123 |
|
124 template <typename Graph, typename ReachedMap> |
|
125 struct bfs_iterator1 { |
|
126 typedef typename Graph::NodeIt NodeIt; |
|
127 typedef typename Graph::EdgeIt EdgeIt; |
|
128 typedef typename Graph::OutEdgeIt OutEdgeIt; |
|
129 Graph& G; |
|
130 std::queue<OutEdgeIt>& bfs_queue; |
|
131 ReachedMap& reached; |
|
132 bool _newly_reached; |
|
133 bfs_iterator1(Graph& _G, std::queue<OutEdgeIt>& _bfs_queue, ReachedMap& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) { |
|
134 valid(); |
|
135 if (!bfs_queue.empty() && bfs_queue.front().valid()) { |
|
136 OutEdgeIt e=bfs_queue.front(); |
|
137 NodeIt w=G.bNode(e); |
|
138 if (!reached.get(w)) { |
|
139 bfs_queue.push(G.template first<OutEdgeIt>(w)); |
|
140 reached.set(w, true); |
|
141 _newly_reached=true; |
|
142 } else { |
|
143 _newly_reached=false; |
|
144 } |
|
145 } |
|
146 } |
|
147 bfs_iterator1<Graph, ReachedMap>& operator++() { |
|
148 if (!valid()) return *this; |
|
149 ++(bfs_queue.front()); |
|
150 valid(); |
|
151 if (!bfs_queue.empty() && bfs_queue.front().valid()) { |
|
152 OutEdgeIt e=bfs_queue.front(); |
|
153 NodeIt w=G.bNode(e); |
|
154 if (!reached.get(w)) { |
|
155 bfs_queue.push(G.template first<OutEdgeIt>(w)); |
|
156 reached.set(w, true); |
|
157 _newly_reached=true; |
|
158 } else { |
|
159 _newly_reached=false; |
|
160 } |
|
161 } |
|
162 return *this; |
|
163 } |
|
164 bool valid() { |
|
165 while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } |
|
166 if (bfs_queue.empty()) return false; else return true; |
|
167 } |
|
168 operator OutEdgeIt() { return bfs_queue.front(); } |
|
169 //ize |
|
170 bool newly_reached() { return _newly_reached; } |
|
171 |
|
172 }; |
|
173 |
|
174 template <typename Graph, typename OutEdgeIt, typename ReachedMap> |
|
175 struct BfsIterator { |
|
176 typedef typename Graph::NodeIt NodeIt; |
|
177 Graph& G; |
|
178 std::queue<OutEdgeIt>& bfs_queue; |
|
179 ReachedMap& reached; |
|
180 bool b_node_newly_reached; |
|
181 OutEdgeIt actual_edge; |
|
182 BfsIterator(Graph& _G, |
|
183 std::queue<OutEdgeIt>& _bfs_queue, |
|
184 ReachedMap& _reached) : |
|
185 G(_G), bfs_queue(_bfs_queue), reached(_reached) { |
|
186 actual_edge=bfs_queue.front(); |
|
187 if (actual_edge.valid()) { |
|
188 NodeIt w=G.bNode(actual_edge); |
|
189 if (!reached.get(w)) { |
|
190 bfs_queue.push(G.firstOutEdge(w)); |
|
191 reached.set(w, true); |
|
192 b_node_newly_reached=true; |
|
193 } else { |
|
194 b_node_newly_reached=false; |
|
195 } |
|
196 } |
|
197 } |
|
198 BfsIterator<Graph, OutEdgeIt, ReachedMap>& |
|
199 operator++() { |
|
200 if (bfs_queue.front().valid()) { |
|
201 ++(bfs_queue.front()); |
|
202 actual_edge=bfs_queue.front(); |
|
203 if (actual_edge.valid()) { |
|
204 NodeIt w=G.bNode(actual_edge); |
|
205 if (!reached.get(w)) { |
|
206 bfs_queue.push(G.firstOutEdge(w)); |
|
207 reached.set(w, true); |
|
208 b_node_newly_reached=true; |
|
209 } else { |
|
210 b_node_newly_reached=false; |
|
211 } |
|
212 } |
|
213 } else { |
|
214 bfs_queue.pop(); |
|
215 actual_edge=bfs_queue.front(); |
|
216 if (actual_edge.valid()) { |
|
217 NodeIt w=G.bNode(actual_edge); |
|
218 if (!reached.get(w)) { |
|
219 bfs_queue.push(G.firstOutEdge(w)); |
|
220 reached.set(w, true); |
|
221 b_node_newly_reached=true; |
|
222 } else { |
|
223 b_node_newly_reached=false; |
|
224 } |
|
225 } |
|
226 } |
|
227 return *this; |
|
228 } |
|
229 bool finished() { return bfs_queue.empty(); } |
|
230 operator OutEdgeIt () { return actual_edge; } |
|
231 bool bNodeIsNewlyReached() { return b_node_newly_reached; } |
|
232 bool aNodeIsExamined() { return !(actual_edge.valid()); } |
|
233 }; |
|
234 |
|
235 |
|
236 template <typename Graph, typename OutEdgeIt, typename ReachedMap> |
|
237 struct DfsIterator { |
|
238 typedef typename Graph::NodeIt NodeIt; |
|
239 Graph& G; |
|
240 std::stack<OutEdgeIt>& bfs_queue; |
|
241 ReachedMap& reached; |
|
242 bool b_node_newly_reached; |
|
243 OutEdgeIt actual_edge; |
|
244 DfsIterator(Graph& _G, |
|
245 std::stack<OutEdgeIt>& _bfs_queue, |
|
246 ReachedMap& _reached) : |
|
247 G(_G), bfs_queue(_bfs_queue), reached(_reached) { |
|
248 actual_edge=bfs_queue.top(); |
|
249 if (actual_edge.valid()) { |
|
250 NodeIt w=G.bNode(actual_edge); |
|
251 if (!reached.get(w)) { |
|
252 bfs_queue.push(G.firstOutEdge(w)); |
|
253 reached.set(w, true); |
|
254 b_node_newly_reached=true; |
|
255 } else { |
|
256 ++(bfs_queue.top()); |
|
257 b_node_newly_reached=false; |
|
258 } |
|
259 } else { |
|
260 bfs_queue.pop(); |
|
261 } |
|
262 } |
|
263 DfsIterator<Graph, OutEdgeIt, ReachedMap>& |
|
264 operator++() { |
|
265 actual_edge=bfs_queue.top(); |
|
266 if (actual_edge.valid()) { |
|
267 NodeIt w=G.bNode(actual_edge); |
|
268 if (!reached.get(w)) { |
|
269 bfs_queue.push(G.firstOutEdge(w)); |
|
270 reached.set(w, true); |
|
271 b_node_newly_reached=true; |
|
272 } else { |
|
273 ++(bfs_queue.top()); |
|
274 b_node_newly_reached=false; |
|
275 } |
|
276 } else { |
|
277 bfs_queue.pop(); |
|
278 } |
|
279 return *this; |
|
280 } |
|
281 bool finished() { return bfs_queue.empty(); } |
|
282 operator OutEdgeIt () { return actual_edge; } |
|
283 bool bNodeIsNewlyReached() { return b_node_newly_reached; } |
|
284 bool aNodeIsLeaved() { return !(actual_edge.valid()); } |
|
285 }; |
|
286 |
|
287 template <typename Graph, typename OutEdgeIt, typename ReachedMap> |
|
288 struct BfsIterator1 { |
|
289 typedef typename Graph::NodeIt NodeIt; |
|
290 Graph& G; |
|
291 std::queue<OutEdgeIt>& bfs_queue; |
|
292 ReachedMap& reached; |
|
293 bool b_node_newly_reached; |
|
294 OutEdgeIt actual_edge; |
|
295 BfsIterator1(Graph& _G, |
|
296 std::queue<OutEdgeIt>& _bfs_queue, |
|
297 ReachedMap& _reached) : |
|
298 G(_G), bfs_queue(_bfs_queue), reached(_reached) { |
|
299 actual_edge=bfs_queue.front(); |
|
300 if (actual_edge.valid()) { |
|
301 NodeIt w=G.bNode(actual_edge); |
|
302 if (!reached.get(w)) { |
|
303 bfs_queue.push(OutEdgeIt(G, w)); |
|
304 reached.set(w, true); |
|
305 b_node_newly_reached=true; |
|
306 } else { |
|
307 b_node_newly_reached=false; |
|
308 } |
|
309 } |
|
310 } |
|
311 void next() { |
|
312 if (bfs_queue.front().valid()) { |
|
313 ++(bfs_queue.front()); |
|
314 actual_edge=bfs_queue.front(); |
|
315 if (actual_edge.valid()) { |
|
316 NodeIt w=G.bNode(actual_edge); |
|
317 if (!reached.get(w)) { |
|
318 bfs_queue.push(OutEdgeIt(G, w)); |
|
319 reached.set(w, true); |
|
320 b_node_newly_reached=true; |
|
321 } else { |
|
322 b_node_newly_reached=false; |
|
323 } |
|
324 } |
|
325 } else { |
|
326 bfs_queue.pop(); |
|
327 actual_edge=bfs_queue.front(); |
|
328 if (actual_edge.valid()) { |
|
329 NodeIt w=G.bNode(actual_edge); |
|
330 if (!reached.get(w)) { |
|
331 bfs_queue.push(OutEdgeIt(G, w)); |
|
332 reached.set(w, true); |
|
333 b_node_newly_reached=true; |
|
334 } else { |
|
335 b_node_newly_reached=false; |
|
336 } |
|
337 } |
|
338 } |
|
339 //return *this; |
|
340 } |
|
341 bool finished() { return bfs_queue.empty(); } |
|
342 operator OutEdgeIt () { return actual_edge; } |
|
343 bool bNodeIsNewlyReached() { return b_node_newly_reached; } |
|
344 bool aNodeIsExamined() { return !(actual_edge.valid()); } |
|
345 }; |
|
346 |
|
347 |
|
348 template <typename Graph, typename OutEdgeIt, typename ReachedMap> |
|
349 struct DfsIterator1 { |
|
350 typedef typename Graph::NodeIt NodeIt; |
|
351 Graph& G; |
|
352 std::stack<OutEdgeIt>& bfs_queue; |
|
353 ReachedMap& reached; |
|
354 bool b_node_newly_reached; |
|
355 OutEdgeIt actual_edge; |
|
356 DfsIterator1(Graph& _G, |
|
357 std::stack<OutEdgeIt>& _bfs_queue, |
|
358 ReachedMap& _reached) : |
|
359 G(_G), bfs_queue(_bfs_queue), reached(_reached) { |
|
360 //actual_edge=bfs_queue.top(); |
|
361 //if (actual_edge.valid()) { |
|
362 // NodeIt w=G.bNode(actual_edge); |
|
363 //if (!reached.get(w)) { |
|
364 // bfs_queue.push(OutEdgeIt(G, w)); |
|
365 // reached.set(w, true); |
|
366 // b_node_newly_reached=true; |
|
367 //} else { |
|
368 // ++(bfs_queue.top()); |
|
369 // b_node_newly_reached=false; |
|
370 //} |
|
371 //} else { |
|
372 // bfs_queue.pop(); |
|
373 //} |
|
374 } |
|
375 void next() { |
|
376 actual_edge=bfs_queue.top(); |
|
377 if (actual_edge.valid()) { |
|
378 NodeIt w=G.bNode(actual_edge); |
|
379 if (!reached.get(w)) { |
|
380 bfs_queue.push(OutEdgeIt(G, w)); |
|
381 reached.set(w, true); |
|
382 b_node_newly_reached=true; |
|
383 } else { |
|
384 ++(bfs_queue.top()); |
|
385 b_node_newly_reached=false; |
|
386 } |
|
387 } else { |
|
388 bfs_queue.pop(); |
|
389 } |
|
390 //return *this; |
|
391 } |
|
392 bool finished() { return bfs_queue.empty(); } |
|
393 operator OutEdgeIt () { return actual_edge; } |
|
394 bool bNodeIsNewlyReached() { return b_node_newly_reached; } |
|
395 bool aNodeIsLeaved() { return !(actual_edge.valid()); } |
|
396 }; |
|
397 |
|
398 } // namespace marci |
|
399 |
|
400 #endif //MARCI_BFS_HH |