15 #include <utility> |
15 #include <utility> |
16 |
16 |
17 #include <lemon/invalid.h> |
17 #include <lemon/invalid.h> |
18 |
18 |
19 namespace lemon { |
19 namespace lemon { |
|
20 namespace marci { |
20 |
21 |
21 /// Bfs searches for the nodes wich are not marked in |
22 /// Bfs searches for the nodes wich are not marked in |
22 /// \c reached_map |
23 /// \c reached_map |
23 /// Reached have to be a read-write bool node-map. |
24 /// RM have to be a read-write bool node-map. |
24 /// \ingroup galgs |
25 /// \ingroup galgs |
25 template <typename Graph, /*typename OutEdgeIt,*/ |
26 template <typename Graph, /*typename OutEdgeIt,*/ |
26 typename ReachedMap/*=typename Graph::NodeMap<bool>*/ > |
27 typename RM/*=typename Graph::NodeMap<bool>*/ > |
27 class BfsIterator { |
28 class BfsIterator { |
|
29 public: |
|
30 typedef RM ReachedMap; |
28 protected: |
31 protected: |
29 typedef typename Graph::Node Node; |
32 typedef typename Graph::Node Node; |
30 typedef typename Graph::Edge Edge; |
33 typedef typename Graph::Edge Edge; |
31 typedef typename Graph::OutEdgeIt OutEdgeIt; |
34 typedef typename Graph::OutEdgeIt OutEdgeIt; |
32 const Graph* graph; |
35 const Graph* graph; |
33 std::queue<Node> bfs_queue; |
36 std::queue<Node> bfs_queue; |
34 ReachedMap& reached; |
37 ReachedMap* reached_map; |
35 bool b_node_newly_reached; |
38 bool b_node_newly_reached; |
|
39 //OutEdgeIt actual_edge; |
36 Edge actual_edge; |
40 Edge actual_edge; |
37 bool own_reached_map; |
41 /// \e |
|
42 BfsIterator(const Graph& _graph) : graph(&_graph), reached_map(0) { } |
|
43 /// RM have to be set before any bfs operation. |
|
44 BfsIterator<Graph, RM>& setReached(RM& _reached_map) { |
|
45 reached_map=&_reached_map; |
|
46 } |
38 public: |
47 public: |
39 /// In that constructor \c _reached have to be a reference |
48 /// In that constructor \c _reached_map have to be a reference |
40 /// for a bool bode-map. The algorithm will search for the |
49 /// for a bool bode-map. The algorithm will search for the |
41 /// initially \c false nodes |
50 /// initially \c false nodes |
42 /// in a bfs order. |
51 /// in a bfs order. |
43 BfsIterator(const Graph& _graph, ReachedMap& _reached) : |
52 BfsIterator(const Graph& _graph, ReachedMap& _reached_map) : |
44 graph(&_graph), reached(_reached), |
53 graph(&_graph), reached_map(&_reached_map) { } |
45 own_reached_map(false) { } |
|
46 /// The same as above, but the map storing the reached nodes |
54 /// The same as above, but the map storing the reached nodes |
47 /// is constructed dynamically to everywhere false. |
55 /// is constructed dynamically to everywhere false. |
48 /// \deprecated |
56 /// \deprecated |
49 BfsIterator(const Graph& _graph) : |
57 // BfsIterator(const Graph& _graph) : |
50 graph(&_graph), reached(*(new ReachedMap(*graph /*, false*/))), |
58 // graph(&_graph), reached_map(new ReachedMap(*graph /*, false*/)), |
51 own_reached_map(true) { } |
59 // own_reached_map(true) { } |
52 /// The map storing the reached nodes have to be destroyed if |
60 // /// The map storing the reached nodes have to be destroyed if |
53 /// it was constructed dynamically |
61 // /// it was constructed dynamically |
54 ~BfsIterator() { if (own_reached_map) delete &reached; } |
62 // ~BfsIterator() { if (own_reached_map) delete reached_map; } |
55 /// This method markes \c s reached. |
63 /// This method markes \c s reached. |
56 /// If the queue is empty, then \c s is pushed in the bfs queue |
64 /// If the queue is empty, then \c s is pushed in the bfs queue |
57 /// and the first out-edge is processed. |
65 /// and the first out-edge is processed. |
58 /// If the queue is not empty, then \c s is simply pushed. |
66 /// If the queue is not empty, then \c s is simply pushed. |
59 BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) { |
67 BfsIterator<Graph, /*OutEdgeIt,*/ ReachedMap>& pushAndSetReached(Node s) { |
60 reached.set(s, true); |
68 reached_map->set(s, true); |
61 if (bfs_queue.empty()) { |
69 if (bfs_queue.empty()) { |
62 bfs_queue.push(s); |
70 bfs_queue.push(s); |
63 actual_edge=OutEdgeIt(*graph, s); |
71 actual_edge=OutEdgeIt(*graph, s); |
64 //graph->first(actual_edge, s); |
72 //graph->first(actual_edge, s); |
65 if (actual_edge!=INVALID) { |
73 if (actual_edge!=INVALID) { |
66 Node w=graph->head(actual_edge); |
74 Node w=graph->head(actual_edge); |
67 if (!reached[w]) { |
75 if (!(*reached_map)[w]) { |
68 bfs_queue.push(w); |
76 bfs_queue.push(w); |
69 reached.set(w, true); |
77 reached_map->set(w, true); |
70 b_node_newly_reached=true; |
78 b_node_newly_reached=true; |
71 } else { |
79 } else { |
72 b_node_newly_reached=false; |
80 b_node_newly_reached=false; |
73 } |
81 } |
74 } |
82 } |
127 Node tail() const { return bfs_queue.front(); } |
135 Node tail() const { return bfs_queue.front(); } |
128 /// \pre The actual edge have to be valid. |
136 /// \pre The actual edge have to be valid. |
129 Node head() const { return graph->head(actual_edge); } |
137 Node head() const { return graph->head(actual_edge); } |
130 /// Guess what? |
138 /// Guess what? |
131 /// \deprecated |
139 /// \deprecated |
132 const ReachedMap& getReachedMap() const { return reached; } |
140 const ReachedMap& reachedMap() const { return *reached_map; } |
|
141 /// Guess what? |
|
142 /// \deprecated |
|
143 typename ReachedMap::ValueType reached(const Node& n) const { |
|
144 return (*reached_map)[n]; |
|
145 } |
133 /// Guess what? |
146 /// Guess what? |
134 /// \deprecated |
147 /// \deprecated |
135 const std::queue<Node>& getBfsQueue() const { return bfs_queue; } |
148 const std::queue<Node>& getBfsQueue() const { return bfs_queue; } |
136 }; |
149 }; |
137 |
150 |
138 /// Bfs searches for the nodes wich are not marked in |
151 /// Bfs searches for the nodes wich are not marked in |
139 /// \c reached_map |
152 /// \c reached_map |
140 /// Reached have to work as a read-write bool Node-map, |
153 /// RM have to work as a read-write bool Node-map, |
141 /// Pred is a write edge node-map and |
154 /// PM is a write edge node-map and |
142 /// Dist is a read-write node-map of integral value, have to be. |
155 /// PNM is a write node node-map and |
|
156 /// DM is a read-write node-map of integral value, have to be. |
143 /// \ingroup galgs |
157 /// \ingroup galgs |
144 template <typename Graph, |
158 template <typename Graph, |
145 typename ReachedMap=typename Graph::template NodeMap<bool>, |
159 typename RM=typename Graph::template NodeMap<bool>, |
146 typename PredMap |
160 typename PM |
147 =typename Graph::template NodeMap<typename Graph::Edge>, |
161 =typename Graph::template NodeMap<typename Graph::Edge>, |
148 typename DistMap=typename Graph::template NodeMap<int> > |
162 typename PNM |
149 class Bfs : public BfsIterator<Graph, ReachedMap> { |
163 =typename Graph::template NodeMap<typename Graph::Node>, |
150 typedef BfsIterator<Graph, ReachedMap> Parent; |
164 typename DM=typename Graph::template NodeMap<int> > |
|
165 class Bfs : public BfsIterator<Graph, RM> { |
|
166 typedef BfsIterator<Graph, RM> Parent; |
|
167 public: |
|
168 typedef RM ReachedMap; |
|
169 typedef PM PredMap; |
|
170 typedef PNM PredNodeMap; |
|
171 typedef DM DistMap; |
151 protected: |
172 protected: |
152 typedef typename Parent::Node Node; |
173 typedef typename Parent::Node Node; |
153 PredMap& pred; |
174 PredMap* pred_map; |
154 DistMap& dist; |
175 PredNodeMap* pred_node_map; |
|
176 DistMap* dist_map; |
|
177 /// \e |
|
178 Bfs<Graph, RM, PM, PNM, DM> |
|
179 (const Graph& _graph) : BfsIterator<Graph, RM>(_graph) { } |
|
180 /// PM have to be set before any bfs operation. |
|
181 Bfs<Graph, RM, PM, PNM, DM>& |
|
182 setPredMap(PredMap& _pred_map) { |
|
183 pred_map=&_pred_map; |
|
184 } |
|
185 /// PredNodeMap have to be set before any bfs operation. |
|
186 Bfs<Graph, RM, PM, PNM, DM>& |
|
187 setPredNodeMap(PredNodeMap& _pred_node_map) { |
|
188 pred_node_map=&_pred_node_map; |
|
189 } |
|
190 /// DistMap have to be set before any bfs operation. |
|
191 Bfs<Graph, RM, PM, PNM, DM>& |
|
192 setDistMap(DistMap& _dist_map) { |
|
193 dist_map=&_dist_map; |
|
194 } |
155 public: |
195 public: |
156 /// The algorithm will search in a bfs order for |
196 /// The algorithm will search in a bfs order for |
157 /// the nodes which are \c false initially. |
197 /// the nodes which are \c false initially. |
158 /// The constructor makes no initial changes on the maps. |
198 /// The constructor makes no initial changes on the maps. |
159 Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : |
199 Bfs<Graph, RM, PM, PNM, DM> |
160 BfsIterator<Graph, ReachedMap>(_graph, _reached), |
200 (const Graph& _graph, ReachedMap& _reached_map, |
161 pred(_pred), dist(_dist) { } |
201 PredMap& _pred_map, PredNodeMap& _pred_node_map, |
|
202 DistMap& _dist_map) : BfsIterator<Graph, RM>(_graph, _reached_map), |
|
203 pred_map(&_pred_map), pred_node_map(&_pred_node_map), |
|
204 dist_map(&_dist_map) { } |
162 /// \c s is marked to be reached and pushed in the bfs queue. |
205 /// \c s is marked to be reached and pushed in the bfs queue. |
163 /// If the queue is empty, then the first out-edge is processed. |
206 /// If the queue is empty, then the first out-edge is processed. |
164 /// If \c s was not marked previously, then |
207 /// If \c s was not marked previously, then |
165 /// in addition its pred is set to be \c INVALID, and dist to \c 0. |
208 /// in addition its pred_map is set to be \c INVALID, |
|
209 /// and dist_map to \c 0. |
166 /// if \c s was marked previuosly, then it is simply pushed. |
210 /// if \c s was marked previuosly, then it is simply pushed. |
167 Bfs<Graph, ReachedMap, PredMap, DistMap>& push(Node s) { |
211 Bfs<Graph, RM, PM, PNM, DM>& push(Node s) { |
168 if (this->reached[s]) { |
212 if ((*(this->reached_map))[s]) { |
169 Parent::pushAndSetReached(s); |
213 Parent::pushAndSetReached(s); |
170 } else { |
214 } else { |
171 Parent::pushAndSetReached(s); |
215 Parent::pushAndSetReached(s); |
172 pred.set(s, INVALID); |
216 pred_map->set(s, INVALID); |
173 dist.set(s, 0); |
217 pred_node_map->set(s, INVALID); |
|
218 dist_map->set(s, 0); |
174 } |
219 } |
175 return *this; |
220 return *this; |
176 } |
221 } |
177 /// A bfs is processed from \c s. |
222 /// A bfs is processed from \c s. |
178 Bfs<Graph, ReachedMap, PredMap, DistMap>& run(Node s) { |
223 Bfs<Graph, RM, PM, PNM, DM>& run(Node s) { |
179 push(s); |
224 push(s); |
180 while (!this->finished()) this->operator++(); |
225 while (!this->finished()) this->operator++(); |
181 return *this; |
226 return *this; |
182 } |
227 } |
183 /// Beside the bfs iteration, \c pred and \dist are saved in a |
228 /// Beside the bfs iteration, \c pred_map and \dist_map are saved in a |
184 /// newly reached node. |
229 /// newly reached node. |
185 Bfs<Graph, ReachedMap, PredMap, DistMap>& operator++() { |
230 Bfs<Graph, RM, PM, PNM, DM>& operator++() { |
186 Parent::operator++(); |
231 Parent::operator++(); |
187 if (this->graph->valid(this->actual_edge) && this->b_node_newly_reached) |
232 if ((this->actual_edge)!=INVALID && this->b_node_newly_reached) |
188 { |
233 { |
189 pred.set(this->head(), this->actual_edge); |
234 pred_map->set(this->head(), this->actual_edge); |
190 dist.set(this->head(), dist[this->tail()]); |
235 pred_node_map->set(this->head(), this->tail()); |
191 } |
236 dist_map->set(this->head(), (*dist_map)[this->tail()]); |
192 return *this; |
237 } |
193 } |
238 return *this; |
194 /// Guess what? |
239 } |
195 /// \deprecated |
240 /// Guess what? |
196 const PredMap& getPredMap() const { return pred; } |
241 /// \deprecated |
|
242 const PredMap& predMap() const { return *pred_map; } |
|
243 /// Guess what? |
|
244 /// \deprecated |
|
245 typename PredMap::ValueType pred(const Node& n) const { |
|
246 return (*pred_map)[n]; |
|
247 } |
|
248 /// Guess what? |
|
249 /// \deprecated |
|
250 const PredNodeMap& predNodeMap() const { return *pred_node_map; } |
|
251 /// Guess what? |
|
252 /// \deprecated |
|
253 typename PredNodeMap::ValueType predNode(const Node& n) const { |
|
254 return (*pred_node_map)[n]; |
|
255 } |
197 /// Guess what? |
256 /// Guess what? |
198 /// \deprecated |
257 /// \deprecated |
199 const DistMap& getDistMap() const { return dist; } |
258 const DistMap& distMap() const { return *dist_map; } |
|
259 /// Guess what? |
|
260 /// \deprecated |
|
261 typename DistMap::ValueType dist(const Node& n) const { |
|
262 return (*dist_map)[n]; |
|
263 } |
200 }; |
264 }; |
|
265 |
|
266 // template <typename Graph, |
|
267 // typename RM=typename Graph::template NodeMap<bool>, |
|
268 // typename PM |
|
269 // =typename Graph::template NodeMap<typename Graph::Edge>, |
|
270 // typename PredNodeMap |
|
271 // =typename Graph::template NodeMap<typename Graph::Node>, |
|
272 // typename DistMap=typename Graph::template NodeMap<int> > |
|
273 // class BfsWizard : public Bfs<Graph> { |
|
274 // public: |
|
275 // typedef Bfs<Graph, PM, PredNodeMap, DistMap> Parent; |
|
276 // protected: |
|
277 // typedef typename Parent::Node Node; |
|
278 // bool own_reached_map; |
|
279 // bool own_pred_map; |
|
280 // bool own_pred_node_map; |
|
281 // bool own_dist_map; |
|
282 |
|
283 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& |
|
284 // makeRreached() { |
|
285 // own_reached_map=true; |
|
286 // reached=new ReachedMap(*graph, false); |
|
287 // } |
|
288 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& |
|
289 // deleteReachedMap() { |
|
290 // own_reached_map=false; |
|
291 // delete reached; |
|
292 // } |
|
293 |
|
294 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& |
|
295 // makePM() { |
|
296 // own_pred_map=true; |
|
297 // pred_map=new PM(*graph, INVALID); |
|
298 // } |
|
299 // BfsWizard<Graph, ReachedMap, PM, PredNodeMap, DistMap>& |
|
300 // deletePM() { |
|
301 // own_pred_map=false; |
|
302 // delete pred_map; |
|
303 // } |
|
304 |
|
305 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& |
|
306 // makePredNodeMap() { |
|
307 // own_pred_node_map=true; |
|
308 // pred_node_map=new PredNodeMap(*graph, INVALID); |
|
309 // } |
|
310 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& |
|
311 // deletePredNodeMap() { |
|
312 // own_pred_node_map=false; |
|
313 // delete pred_node_map; |
|
314 // } |
|
315 |
|
316 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& |
|
317 // makeDistMap() { |
|
318 // own_dist_map=true; |
|
319 // dist_map=new DistMap(*graph, 0); |
|
320 // } |
|
321 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& |
|
322 // deleteDistMap() { |
|
323 // own_dist_map=false; |
|
324 // delete dist_map; |
|
325 // } |
|
326 |
|
327 // public: |
|
328 // /// User friendly Bfs class. |
|
329 // /// The maps which are not explicitly given by the user are |
|
330 // /// constructed with false, INVALID, INVALID and 0 values. |
|
331 // /// For the user defined maps, the values are not modified, and |
|
332 // /// the bfs is processed without any preset on maps. Therefore, |
|
333 // /// the bfs will search only the nodes which are set false previously |
|
334 // /// in reached, and in the nodes wich are not newly reached by the |
|
335 // /// search, the map values are not modified. |
|
336 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap> |
|
337 // (const Graph& _graph) : |
|
338 // own_reached_map(false), |
|
339 // own_pred_map(false), |
|
340 // own_pred_node_map(false), |
|
341 // own_dist_map(false) { |
|
342 // } |
|
343 |
|
344 // /// \e |
|
345 // ~BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>() { |
|
346 // if (own_reached_map) deleteReachedMap(); |
|
347 // if (own_pred_map) deletePM(); |
|
348 // if (own_pred_node_map) deletePredNodeMap(); |
|
349 // if (own_dist_map) deleteDistMap(); |
|
350 // } |
|
351 |
|
352 // /// \e |
|
353 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& |
|
354 // setReachedMap(ReachedMap& _reached) { |
|
355 // if (own_reached_map) deleteReachedMap(); |
|
356 // Parent::setReachedMap(_reached); |
|
357 // } |
|
358 // /// \e |
|
359 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& |
|
360 // setPM(PM& _pred) { |
|
361 // if (own_pred_map) deletePM(); |
|
362 // Parent::setPM(_pred); |
|
363 // } |
|
364 // /// \e |
|
365 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& |
|
366 // setPredNodeMap(PredNodeMap& _pred_node) { |
|
367 // if (own_pred_node_map) deletePredNodeMap(); |
|
368 // Parent::setPredNodeMap(_pred_node); |
|
369 // } |
|
370 // /// \e |
|
371 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& |
|
372 // setDistMap(DistMap& _dist) { |
|
373 // if (own_dist_map) deleteDistMap(); |
|
374 // Parent::setDistMap(_dist); |
|
375 // } |
|
376 |
|
377 // /// \e |
|
378 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& |
|
379 // push(Node s) { |
|
380 // if (!reached) makeReachedMap(); |
|
381 // if (!pred_map) makePMMap(); |
|
382 // if (!pred_node_map) makePredNodeMap(); |
|
383 // if (!dist_map) makeDistMap(); |
|
384 // push(s); |
|
385 // return *this; |
|
386 // } |
|
387 |
|
388 // /// \e |
|
389 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& |
|
390 // operator++() { |
|
391 // if (!reached) makeRM(); |
|
392 // if (!pred_map) makePMMap(); |
|
393 // if (!pred_node_map) makePredNodeMap(); |
|
394 // if (!dist_map) makeDistMap(); |
|
395 // ++(*this); |
|
396 // return *this; |
|
397 // } |
|
398 |
|
399 // /// \e |
|
400 // BfsWizard<Graph, RM, PM, PredNodeMap, DistMap>& |
|
401 // run(Node s) { |
|
402 // if (!reached) makeRM(); |
|
403 // if (!pred_map) makePMMap(); |
|
404 // if (!pred_node_map) makePredNodeMap(); |
|
405 // if (!dist_map) makeDistMap(); |
|
406 // run(s); |
|
407 // return *this; |
|
408 // } |
|
409 |
|
410 // }; |
|
411 |
201 |
412 |
202 /// Dfs searches for the nodes wich are not marked in |
413 /// Dfs searches for the nodes wich are not marked in |
203 /// \c reached_map |
414 /// \c reached_map |
204 /// Reached have to be a read-write bool Node-map. |
415 /// Reached have to be a read-write bool Node-map. |
205 /// \ingroup galgs |
416 /// \ingroup galgs |