31 #include <lemon/maps.h> |
31 #include <lemon/maps.h> |
32 |
32 |
33 namespace lemon { |
33 namespace lemon { |
34 |
34 |
35 |
35 |
36 |
36 |
37 ///Default traits class of Bfs class. |
37 ///Default traits class of Bfs class. |
38 |
38 |
39 ///Default traits class of Bfs class. |
39 ///Default traits class of Bfs class. |
40 ///\tparam GR Digraph type. |
40 ///\tparam GR Digraph type. |
41 template<class GR> |
41 template<class GR> |
42 struct BfsDefaultTraits |
42 struct BfsDefaultTraits |
43 { |
43 { |
44 ///The digraph type the algorithm runs on. |
44 ///The digraph type the algorithm runs on. |
45 typedef GR Digraph; |
45 typedef GR Digraph; |
46 ///\brief The type of the map that stores the last |
46 ///\brief The type of the map that stores the last |
47 ///arcs of the shortest paths. |
47 ///arcs of the shortest paths. |
48 /// |
48 /// |
49 ///The type of the map that stores the last |
49 ///The type of the map that stores the last |
50 ///arcs of the shortest paths. |
50 ///arcs of the shortest paths. |
51 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
51 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
52 /// |
52 /// |
53 typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap; |
53 typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap; |
54 ///Instantiates a PredMap. |
54 ///Instantiates a PredMap. |
55 |
55 |
56 ///This function instantiates a \ref PredMap. |
56 ///This function instantiates a \ref PredMap. |
57 ///\param G is the digraph, to which we would like to define the PredMap. |
57 ///\param G is the digraph, to which we would like to define the PredMap. |
58 ///\todo The digraph alone may be insufficient to initialize |
58 ///\todo The digraph alone may be insufficient to initialize |
59 static PredMap *createPredMap(const GR &G) |
59 static PredMap *createPredMap(const GR &G) |
60 { |
60 { |
61 return new PredMap(G); |
61 return new PredMap(G); |
62 } |
62 } |
63 ///The type of the map that indicates which nodes are processed. |
63 ///The type of the map that indicates which nodes are processed. |
64 |
64 |
65 ///The type of the map that indicates which nodes are processed. |
65 ///The type of the map that indicates which nodes are processed. |
66 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
66 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
67 ///\todo named parameter to set this type, function to read and write. |
67 ///\todo named parameter to set this type, function to read and write. |
68 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
68 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
69 ///Instantiates a ProcessedMap. |
69 ///Instantiates a ProcessedMap. |
70 |
70 |
71 ///This function instantiates a \ref ProcessedMap. |
71 ///This function instantiates a \ref ProcessedMap. |
72 ///\param g is the digraph, to which |
72 ///\param g is the digraph, to which |
73 ///we would like to define the \ref ProcessedMap |
73 ///we would like to define the \ref ProcessedMap |
74 #ifdef DOXYGEN |
74 #ifdef DOXYGEN |
75 static ProcessedMap *createProcessedMap(const GR &g) |
75 static ProcessedMap *createProcessedMap(const GR &g) |
76 #else |
76 #else |
78 #endif |
78 #endif |
79 { |
79 { |
80 return new ProcessedMap(); |
80 return new ProcessedMap(); |
81 } |
81 } |
82 ///The type of the map that indicates which nodes are reached. |
82 ///The type of the map that indicates which nodes are reached. |
83 |
83 |
84 ///The type of the map that indicates which nodes are reached. |
84 ///The type of the map that indicates which nodes are reached. |
85 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
85 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
86 ///\todo named parameter to set this type, function to read and write. |
86 ///\todo named parameter to set this type, function to read and write. |
87 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
87 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
88 ///Instantiates a ReachedMap. |
88 ///Instantiates a ReachedMap. |
89 |
89 |
90 ///This function instantiates a \ref ReachedMap. |
90 ///This function instantiates a \ref ReachedMap. |
91 ///\param G is the digraph, to which |
91 ///\param G is the digraph, to which |
92 ///we would like to define the \ref ReachedMap. |
92 ///we would like to define the \ref ReachedMap. |
93 static ReachedMap *createReachedMap(const GR &G) |
93 static ReachedMap *createReachedMap(const GR &G) |
94 { |
94 { |
95 return new ReachedMap(G); |
95 return new ReachedMap(G); |
96 } |
96 } |
97 ///The type of the map that stores the dists of the nodes. |
97 ///The type of the map that stores the dists of the nodes. |
98 |
98 |
99 ///The type of the map that stores the dists of the nodes. |
99 ///The type of the map that stores the dists of the nodes. |
100 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
100 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
101 /// |
101 /// |
102 typedef typename Digraph::template NodeMap<int> DistMap; |
102 typedef typename Digraph::template NodeMap<int> DistMap; |
103 ///Instantiates a DistMap. |
103 ///Instantiates a DistMap. |
104 |
104 |
105 ///This function instantiates a \ref DistMap. |
105 ///This function instantiates a \ref DistMap. |
106 ///\param G is the digraph, to which we would like to define the \ref DistMap |
106 ///\param G is the digraph, to which we would like to define the \ref DistMap |
107 static DistMap *createDistMap(const GR &G) |
107 static DistMap *createDistMap(const GR &G) |
108 { |
108 { |
109 return new DistMap(G); |
109 return new DistMap(G); |
110 } |
110 } |
111 }; |
111 }; |
112 |
112 |
113 ///%BFS algorithm class. |
113 ///%BFS algorithm class. |
114 |
114 |
115 ///\ingroup search |
115 ///\ingroup search |
116 ///This class provides an efficient implementation of the %BFS algorithm. |
116 ///This class provides an efficient implementation of the %BFS algorithm. |
117 /// |
117 /// |
118 ///\tparam GR The digraph type the algorithm runs on. The default value is |
118 ///\tparam GR The digraph type the algorithm runs on. The default value is |
119 ///\ref ListDigraph. The value of GR is not used directly by Bfs, it |
119 ///\ref ListDigraph. The value of GR is not used directly by Bfs, it |
140 * of the parameters of the algorithms. |
140 * of the parameters of the algorithms. |
141 */ |
141 */ |
142 class UninitializedParameter : public lemon::UninitializedParameter { |
142 class UninitializedParameter : public lemon::UninitializedParameter { |
143 public: |
143 public: |
144 virtual const char* what() const throw() { |
144 virtual const char* what() const throw() { |
145 return "lemon::Bfs::UninitializedParameter"; |
145 return "lemon::Bfs::UninitializedParameter"; |
146 } |
146 } |
147 }; |
147 }; |
148 |
148 |
149 typedef TR Traits; |
149 typedef TR Traits; |
150 ///The type of the underlying digraph. |
150 ///The type of the underlying digraph. |
151 typedef typename TR::Digraph Digraph; |
151 typedef typename TR::Digraph Digraph; |
152 |
152 |
153 ///\brief The type of the map that stores the last |
153 ///\brief The type of the map that stores the last |
154 ///arcs of the shortest paths. |
154 ///arcs of the shortest paths. |
155 typedef typename TR::PredMap PredMap; |
155 typedef typename TR::PredMap PredMap; |
156 ///The type of the map indicating which nodes are reached. |
156 ///The type of the map indicating which nodes are reached. |
157 typedef typename TR::ReachedMap ReachedMap; |
157 typedef typename TR::ReachedMap ReachedMap; |
188 std::vector<typename Digraph::Node> _queue; |
188 std::vector<typename Digraph::Node> _queue; |
189 int _queue_head,_queue_tail,_queue_next_dist; |
189 int _queue_head,_queue_tail,_queue_next_dist; |
190 int _curr_dist; |
190 int _curr_dist; |
191 |
191 |
192 ///Creates the maps if necessary. |
192 ///Creates the maps if necessary. |
193 |
193 |
194 ///\todo Better memory allocation (instead of new). |
194 ///\todo Better memory allocation (instead of new). |
195 void create_maps() |
195 void create_maps() |
196 { |
196 { |
197 if(!_pred) { |
197 if(!_pred) { |
198 local_pred = true; |
198 local_pred = true; |
199 _pred = Traits::createPredMap(*G); |
199 _pred = Traits::createPredMap(*G); |
200 } |
200 } |
201 if(!_dist) { |
201 if(!_dist) { |
202 local_dist = true; |
202 local_dist = true; |
203 _dist = Traits::createDistMap(*G); |
203 _dist = Traits::createDistMap(*G); |
204 } |
204 } |
205 if(!_reached) { |
205 if(!_reached) { |
206 local_reached = true; |
206 local_reached = true; |
207 _reached = Traits::createReachedMap(*G); |
207 _reached = Traits::createReachedMap(*G); |
208 } |
208 } |
209 if(!_processed) { |
209 if(!_processed) { |
210 local_processed = true; |
210 local_processed = true; |
211 _processed = Traits::createProcessedMap(*G); |
211 _processed = Traits::createProcessedMap(*G); |
212 } |
212 } |
213 } |
213 } |
214 |
214 |
215 protected: |
215 protected: |
216 |
216 |
217 Bfs() {} |
217 Bfs() {} |
218 |
218 |
219 public: |
219 public: |
220 |
220 |
221 typedef Bfs Create; |
221 typedef Bfs Create; |
222 |
222 |
223 ///\name Named template parameters |
223 ///\name Named template parameters |
224 |
224 |
225 ///@{ |
225 ///@{ |
226 |
226 |
227 template <class T> |
227 template <class T> |
228 struct DefPredMapTraits : public Traits { |
228 struct DefPredMapTraits : public Traits { |
229 typedef T PredMap; |
229 typedef T PredMap; |
230 static PredMap *createPredMap(const Digraph &) |
230 static PredMap *createPredMap(const Digraph &) |
231 { |
231 { |
232 throw UninitializedParameter(); |
232 throw UninitializedParameter(); |
233 } |
233 } |
234 }; |
234 }; |
235 ///\brief \ref named-templ-param "Named parameter" for setting |
235 ///\brief \ref named-templ-param "Named parameter" for setting |
236 ///PredMap type |
236 ///PredMap type |
237 /// |
237 /// |
238 ///\ref named-templ-param "Named parameter" for setting PredMap type |
238 ///\ref named-templ-param "Named parameter" for setting PredMap type |
239 /// |
239 /// |
240 template <class T> |
240 template <class T> |
241 struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > { |
241 struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > { |
242 typedef Bfs< Digraph, DefPredMapTraits<T> > Create; |
242 typedef Bfs< Digraph, DefPredMapTraits<T> > Create; |
243 }; |
243 }; |
244 |
244 |
245 template <class T> |
245 template <class T> |
246 struct DefDistMapTraits : public Traits { |
246 struct DefDistMapTraits : public Traits { |
247 typedef T DistMap; |
247 typedef T DistMap; |
248 static DistMap *createDistMap(const Digraph &) |
248 static DistMap *createDistMap(const Digraph &) |
249 { |
249 { |
250 throw UninitializedParameter(); |
250 throw UninitializedParameter(); |
251 } |
251 } |
252 }; |
252 }; |
253 ///\brief \ref named-templ-param "Named parameter" for setting |
253 ///\brief \ref named-templ-param "Named parameter" for setting |
254 ///DistMap type |
254 ///DistMap type |
255 /// |
255 /// |
256 ///\ref named-templ-param "Named parameter" for setting DistMap type |
256 ///\ref named-templ-param "Named parameter" for setting DistMap type |
257 /// |
257 /// |
258 template <class T> |
258 template <class T> |
259 struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > { |
259 struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > { |
260 typedef Bfs< Digraph, DefDistMapTraits<T> > Create; |
260 typedef Bfs< Digraph, DefDistMapTraits<T> > Create; |
261 }; |
261 }; |
262 |
262 |
263 template <class T> |
263 template <class T> |
264 struct DefReachedMapTraits : public Traits { |
264 struct DefReachedMapTraits : public Traits { |
265 typedef T ReachedMap; |
265 typedef T ReachedMap; |
266 static ReachedMap *createReachedMap(const Digraph &) |
266 static ReachedMap *createReachedMap(const Digraph &) |
267 { |
267 { |
268 throw UninitializedParameter(); |
268 throw UninitializedParameter(); |
269 } |
269 } |
270 }; |
270 }; |
271 ///\brief \ref named-templ-param "Named parameter" for setting |
271 ///\brief \ref named-templ-param "Named parameter" for setting |
272 ///ReachedMap type |
272 ///ReachedMap type |
273 /// |
273 /// |
274 ///\ref named-templ-param "Named parameter" for setting ReachedMap type |
274 ///\ref named-templ-param "Named parameter" for setting ReachedMap type |
275 /// |
275 /// |
276 template <class T> |
276 template <class T> |
277 struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > { |
277 struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > { |
278 typedef Bfs< Digraph, DefReachedMapTraits<T> > Create; |
278 typedef Bfs< Digraph, DefReachedMapTraits<T> > Create; |
279 }; |
279 }; |
280 |
280 |
281 template <class T> |
281 template <class T> |
282 struct DefProcessedMapTraits : public Traits { |
282 struct DefProcessedMapTraits : public Traits { |
283 typedef T ProcessedMap; |
283 typedef T ProcessedMap; |
284 static ProcessedMap *createProcessedMap(const Digraph &) |
284 static ProcessedMap *createProcessedMap(const Digraph &) |
285 { |
285 { |
286 throw UninitializedParameter(); |
286 throw UninitializedParameter(); |
287 } |
287 } |
288 }; |
288 }; |
289 ///\brief \ref named-templ-param "Named parameter" for setting |
289 ///\brief \ref named-templ-param "Named parameter" for setting |
290 ///ProcessedMap type |
290 ///ProcessedMap type |
291 /// |
291 /// |
293 /// |
293 /// |
294 template <class T> |
294 template <class T> |
295 struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits<T> > { |
295 struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits<T> > { |
296 typedef Bfs< Digraph, DefProcessedMapTraits<T> > Create; |
296 typedef Bfs< Digraph, DefProcessedMapTraits<T> > Create; |
297 }; |
297 }; |
298 |
298 |
299 struct DefDigraphProcessedMapTraits : public Traits { |
299 struct DefDigraphProcessedMapTraits : public Traits { |
300 typedef typename Digraph::template NodeMap<bool> ProcessedMap; |
300 typedef typename Digraph::template NodeMap<bool> ProcessedMap; |
301 static ProcessedMap *createProcessedMap(const Digraph &G) |
301 static ProcessedMap *createProcessedMap(const Digraph &G) |
302 { |
302 { |
303 return new ProcessedMap(G); |
303 return new ProcessedMap(G); |
304 } |
304 } |
305 }; |
305 }; |
306 ///\brief \ref named-templ-param "Named parameter" |
306 ///\brief \ref named-templ-param "Named parameter" |
307 ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>. |
307 ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>. |
308 /// |
308 /// |
309 ///\ref named-templ-param "Named parameter" |
309 ///\ref named-templ-param "Named parameter" |
310 ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>. |
310 ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>. |
311 ///If you don't set it explicitly, it will be automatically allocated. |
311 ///If you don't set it explicitly, it will be automatically allocated. |
312 template <class T> |
312 template <class T> |
313 struct DefProcessedMapToBeDefaultMap : |
313 struct DefProcessedMapToBeDefaultMap : |
314 public Bfs< Digraph, DefDigraphProcessedMapTraits> { |
314 public Bfs< Digraph, DefDigraphProcessedMapTraits> { |
315 typedef Bfs< Digraph, DefDigraphProcessedMapTraits> Create; |
315 typedef Bfs< Digraph, DefDigraphProcessedMapTraits> Create; |
316 }; |
316 }; |
317 |
317 |
318 ///@} |
318 ///@} |
319 |
319 |
320 public: |
320 public: |
321 |
321 |
322 ///Constructor. |
322 ///Constructor. |
323 |
323 |
324 ///\param _G the digraph the algorithm will run on. |
324 ///\param _G the digraph the algorithm will run on. |
325 /// |
325 /// |
326 Bfs(const Digraph& _G) : |
326 Bfs(const Digraph& _G) : |
327 G(&_G), |
327 G(&_G), |
328 _pred(NULL), local_pred(false), |
328 _pred(NULL), local_pred(false), |
329 _dist(NULL), local_dist(false), |
329 _dist(NULL), local_dist(false), |
330 _reached(NULL), local_reached(false), |
330 _reached(NULL), local_reached(false), |
331 _processed(NULL), local_processed(false) |
331 _processed(NULL), local_processed(false) |
332 { } |
332 { } |
333 |
333 |
334 ///Destructor. |
334 ///Destructor. |
335 ~Bfs() |
335 ~Bfs() |
336 { |
336 { |
337 if(local_pred) delete _pred; |
337 if(local_pred) delete _pred; |
338 if(local_dist) delete _dist; |
338 if(local_dist) delete _dist; |
339 if(local_reached) delete _reached; |
339 if(local_reached) delete _reached; |
340 if(local_processed) delete _processed; |
340 if(local_processed) delete _processed; |
430 create_maps(); |
430 create_maps(); |
431 _queue.resize(countNodes(*G)); |
431 _queue.resize(countNodes(*G)); |
432 _queue_head=_queue_tail=0; |
432 _queue_head=_queue_tail=0; |
433 _curr_dist=1; |
433 _curr_dist=1; |
434 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { |
434 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) { |
435 _pred->set(u,INVALID); |
435 _pred->set(u,INVALID); |
436 _reached->set(u,false); |
436 _reached->set(u,false); |
437 _processed->set(u,false); |
437 _processed->set(u,false); |
438 } |
438 } |
439 } |
439 } |
440 |
440 |
441 ///Adds a new source node. |
441 ///Adds a new source node. |
442 |
442 |
443 ///Adds a new source node to the set of nodes to be processed. |
443 ///Adds a new source node to the set of nodes to be processed. |
444 /// |
444 /// |
445 void addSource(Node s) |
445 void addSource(Node s) |
446 { |
446 { |
447 if(!(*_reached)[s]) |
447 if(!(*_reached)[s]) |
448 { |
448 { |
449 _reached->set(s,true); |
449 _reached->set(s,true); |
450 _pred->set(s,INVALID); |
450 _pred->set(s,INVALID); |
451 _dist->set(s,0); |
451 _dist->set(s,0); |
452 _queue[_queue_head++]=s; |
452 _queue[_queue_head++]=s; |
453 _queue_next_dist=_queue_head; |
453 _queue_next_dist=_queue_head; |
454 } |
454 } |
455 } |
455 } |
456 |
456 |
457 ///Processes the next node. |
457 ///Processes the next node. |
458 |
458 |
459 ///Processes the next node. |
459 ///Processes the next node. |
460 /// |
460 /// |
461 ///\return The processed node. |
461 ///\return The processed node. |
462 /// |
462 /// |
463 ///\warning The queue must not be empty! |
463 ///\warning The queue must not be empty! |
464 Node processNextNode() |
464 Node processNextNode() |
465 { |
465 { |
466 if(_queue_tail==_queue_next_dist) { |
466 if(_queue_tail==_queue_next_dist) { |
467 _curr_dist++; |
467 _curr_dist++; |
468 _queue_next_dist=_queue_head; |
468 _queue_next_dist=_queue_head; |
469 } |
469 } |
470 Node n=_queue[_queue_tail++]; |
470 Node n=_queue[_queue_tail++]; |
471 _processed->set(n,true); |
471 _processed->set(n,true); |
472 Node m; |
472 Node m; |
473 for(OutArcIt e(*G,n);e!=INVALID;++e) |
473 for(OutArcIt e(*G,n);e!=INVALID;++e) |
474 if(!(*_reached)[m=G->target(e)]) { |
474 if(!(*_reached)[m=G->target(e)]) { |
475 _queue[_queue_head++]=m; |
475 _queue[_queue_head++]=m; |
476 _reached->set(m,true); |
476 _reached->set(m,true); |
477 _pred->set(m,e); |
477 _pred->set(m,e); |
478 _dist->set(m,_curr_dist); |
478 _dist->set(m,_curr_dist); |
479 } |
479 } |
480 return n; |
480 return n; |
481 } |
481 } |
482 |
482 |
483 ///Processes the next node. |
483 ///Processes the next node. |
484 |
484 |
493 /// |
493 /// |
494 ///\warning The queue must not be empty! |
494 ///\warning The queue must not be empty! |
495 Node processNextNode(Node target, bool& reach) |
495 Node processNextNode(Node target, bool& reach) |
496 { |
496 { |
497 if(_queue_tail==_queue_next_dist) { |
497 if(_queue_tail==_queue_next_dist) { |
498 _curr_dist++; |
498 _curr_dist++; |
499 _queue_next_dist=_queue_head; |
499 _queue_next_dist=_queue_head; |
500 } |
500 } |
501 Node n=_queue[_queue_tail++]; |
501 Node n=_queue[_queue_tail++]; |
502 _processed->set(n,true); |
502 _processed->set(n,true); |
503 Node m; |
503 Node m; |
504 for(OutArcIt e(*G,n);e!=INVALID;++e) |
504 for(OutArcIt e(*G,n);e!=INVALID;++e) |
505 if(!(*_reached)[m=G->target(e)]) { |
505 if(!(*_reached)[m=G->target(e)]) { |
506 _queue[_queue_head++]=m; |
506 _queue[_queue_head++]=m; |
507 _reached->set(m,true); |
507 _reached->set(m,true); |
508 _pred->set(m,e); |
508 _pred->set(m,e); |
509 _dist->set(m,_curr_dist); |
509 _dist->set(m,_curr_dist); |
510 reach = reach || (target == m); |
510 reach = reach || (target == m); |
511 } |
511 } |
512 return n; |
512 return n; |
513 } |
513 } |
514 |
514 |
515 ///Processes the next node. |
515 ///Processes the next node. |
516 |
516 |
526 ///\warning The queue must not be empty! |
526 ///\warning The queue must not be empty! |
527 template<class NM> |
527 template<class NM> |
528 Node processNextNode(const NM& nm, Node& rnode) |
528 Node processNextNode(const NM& nm, Node& rnode) |
529 { |
529 { |
530 if(_queue_tail==_queue_next_dist) { |
530 if(_queue_tail==_queue_next_dist) { |
531 _curr_dist++; |
531 _curr_dist++; |
532 _queue_next_dist=_queue_head; |
532 _queue_next_dist=_queue_head; |
533 } |
533 } |
534 Node n=_queue[_queue_tail++]; |
534 Node n=_queue[_queue_tail++]; |
535 _processed->set(n,true); |
535 _processed->set(n,true); |
536 Node m; |
536 Node m; |
537 for(OutArcIt e(*G,n);e!=INVALID;++e) |
537 for(OutArcIt e(*G,n);e!=INVALID;++e) |
538 if(!(*_reached)[m=G->target(e)]) { |
538 if(!(*_reached)[m=G->target(e)]) { |
539 _queue[_queue_head++]=m; |
539 _queue[_queue_head++]=m; |
540 _reached->set(m,true); |
540 _reached->set(m,true); |
541 _pred->set(m,e); |
541 _pred->set(m,e); |
542 _dist->set(m,_curr_dist); |
542 _dist->set(m,_curr_dist); |
543 if (nm[m] && rnode == INVALID) rnode = m; |
543 if (nm[m] && rnode == INVALID) rnode = m; |
544 } |
544 } |
545 return n; |
545 return n; |
546 } |
546 } |
547 |
547 |
548 ///Next node to be processed. |
548 ///Next node to be processed. |
549 |
549 |
550 ///Next node to be processed. |
550 ///Next node to be processed. |
551 /// |
551 /// |
552 ///\return The next node to be processed or INVALID if the queue is |
552 ///\return The next node to be processed or INVALID if the queue is |
553 /// empty. |
553 /// empty. |
554 Node nextNode() |
554 Node nextNode() |
555 { |
555 { |
556 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID; |
556 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID; |
557 } |
557 } |
558 |
558 |
559 ///\brief Returns \c false if there are nodes |
559 ///\brief Returns \c false if there are nodes |
560 ///to be processed in the queue |
560 ///to be processed in the queue |
561 /// |
561 /// |
562 ///Returns \c false if there are nodes |
562 ///Returns \c false if there are nodes |
563 ///to be processed in the queue |
563 ///to be processed in the queue |
564 bool emptyQueue() { return _queue_tail==_queue_head; } |
564 bool emptyQueue() { return _queue_tail==_queue_head; } |
565 ///Returns the number of the nodes to be processed. |
565 ///Returns the number of the nodes to be processed. |
566 |
566 |
567 ///Returns the number of the nodes to be processed in the queue. |
567 ///Returns the number of the nodes to be processed in the queue. |
568 int queueSize() { return _queue_head-_queue_tail; } |
568 int queueSize() { return _queue_head-_queue_tail; } |
569 |
569 |
570 ///Executes the algorithm. |
570 ///Executes the algorithm. |
571 |
571 |
572 ///Executes the algorithm. |
572 ///Executes the algorithm. |
573 /// |
573 /// |
574 ///\pre init() must be called and at least one node should be added |
574 ///\pre init() must be called and at least one node should be added |
664 init(); |
664 init(); |
665 addSource(s); |
665 addSource(s); |
666 start(t); |
666 start(t); |
667 return reached(t) ? _curr_dist : 0; |
667 return reached(t) ? _curr_dist : 0; |
668 } |
668 } |
669 |
669 |
670 ///@} |
670 ///@} |
671 |
671 |
672 ///\name Query Functions |
672 ///\name Query Functions |
673 ///The result of the %BFS algorithm can be obtained using these |
673 ///The result of the %BFS algorithm can be obtained using these |
674 ///functions.\n |
674 ///functions.\n |
675 ///Before the use of these functions, |
675 ///Before the use of these functions, |
676 ///either run() or start() must be calleb. |
676 ///either run() or start() must be calleb. |
677 |
677 |
678 ///@{ |
678 ///@{ |
679 |
679 |
680 typedef PredMapPath<Digraph, PredMap> Path; |
680 typedef PredMapPath<Digraph, PredMap> Path; |
681 |
681 |
682 ///Gives back the shortest path. |
682 ///Gives back the shortest path. |
683 |
683 |
684 ///Gives back the shortest path. |
684 ///Gives back the shortest path. |
685 ///\pre The \c t should be reachable from the source. |
685 ///\pre The \c t should be reachable from the source. |
686 Path path(Node t) |
686 Path path(Node t) |
687 { |
687 { |
688 return Path(*G, *_pred, t); |
688 return Path(*G, *_pred, t); |
689 } |
689 } |
690 |
690 |
691 ///The distance of a node from the root(s). |
691 ///The distance of a node from the root(s). |
720 ///The shortest path tree used here is equal to the shortest path |
720 ///The shortest path tree used here is equal to the shortest path |
721 ///tree used in \ref predArc(). |
721 ///tree used in \ref predArc(). |
722 ///\pre Either \ref run() or \ref start() must be called before |
722 ///\pre Either \ref run() or \ref start() must be called before |
723 ///using this function. |
723 ///using this function. |
724 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: |
724 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: |
725 G->source((*_pred)[v]); } |
725 G->source((*_pred)[v]); } |
726 |
726 |
727 ///Returns a reference to the NodeMap of distances. |
727 ///Returns a reference to the NodeMap of distances. |
728 |
728 |
729 ///Returns a reference to the NodeMap of distances. |
729 ///Returns a reference to the NodeMap of distances. |
730 ///\pre Either \ref run() or \ref init() must |
730 ///\pre Either \ref run() or \ref init() must |
731 ///be called before using this function. |
731 ///be called before using this function. |
732 const DistMap &distMap() const { return *_dist;} |
732 const DistMap &distMap() const { return *_dist;} |
733 |
733 |
734 ///Returns a reference to the shortest path tree map. |
734 ///Returns a reference to the shortest path tree map. |
735 |
735 |
736 ///Returns a reference to the NodeMap of the arcs of the |
736 ///Returns a reference to the NodeMap of the arcs of the |
737 ///shortest path tree. |
737 ///shortest path tree. |
738 ///\pre Either \ref run() or \ref init() |
738 ///\pre Either \ref run() or \ref init() |
739 ///must be called before using this function. |
739 ///must be called before using this function. |
740 const PredMap &predMap() const { return *_pred;} |
740 const PredMap &predMap() const { return *_pred;} |
741 |
741 |
742 ///Checks if a node is reachable from the root. |
742 ///Checks if a node is reachable from the root. |
743 |
743 |
744 ///Returns \c true if \c v is reachable from the root. |
744 ///Returns \c true if \c v is reachable from the root. |
745 ///\warning The source nodes are indicated as unreached. |
745 ///\warning The source nodes are indicated as unreached. |
746 ///\pre Either \ref run() or \ref start() |
746 ///\pre Either \ref run() or \ref start() |
747 ///must be called before using this function. |
747 ///must be called before using this function. |
748 /// |
748 /// |
749 bool reached(Node v) { return (*_reached)[v]; } |
749 bool reached(Node v) { return (*_reached)[v]; } |
750 |
750 |
751 ///@} |
751 ///@} |
752 }; |
752 }; |
753 |
753 |
754 ///Default traits class of Bfs function. |
754 ///Default traits class of Bfs function. |
755 |
755 |
756 ///Default traits class of Bfs function. |
756 ///Default traits class of Bfs function. |
757 ///\tparam GR Digraph type. |
757 ///\tparam GR Digraph type. |
758 template<class GR> |
758 template<class GR> |
759 struct BfsWizardDefaultTraits |
759 struct BfsWizardDefaultTraits |
760 { |
760 { |
761 ///The digraph type the algorithm runs on. |
761 ///The digraph type the algorithm runs on. |
762 typedef GR Digraph; |
762 typedef GR Digraph; |
763 ///\brief The type of the map that stores the last |
763 ///\brief The type of the map that stores the last |
764 ///arcs of the shortest paths. |
764 ///arcs of the shortest paths. |
765 /// |
765 /// |
766 ///The type of the map that stores the last |
766 ///The type of the map that stores the last |
767 ///arcs of the shortest paths. |
767 ///arcs of the shortest paths. |
768 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
768 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
769 /// |
769 /// |
770 typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap; |
770 typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap; |
771 ///Instantiates a PredMap. |
771 ///Instantiates a PredMap. |
772 |
772 |
773 ///This function instantiates a \ref PredMap. |
773 ///This function instantiates a \ref PredMap. |
774 ///\param g is the digraph, to which we would like to define the PredMap. |
774 ///\param g is the digraph, to which we would like to define the PredMap. |
775 ///\todo The digraph alone may be insufficient to initialize |
775 ///\todo The digraph alone may be insufficient to initialize |
776 #ifdef DOXYGEN |
776 #ifdef DOXYGEN |
777 static PredMap *createPredMap(const GR &g) |
777 static PredMap *createPredMap(const GR &g) |
778 #else |
778 #else |
779 static PredMap *createPredMap(const GR &) |
779 static PredMap *createPredMap(const GR &) |
780 #endif |
780 #endif |
781 { |
781 { |
782 return new PredMap(); |
782 return new PredMap(); |
783 } |
783 } |
784 |
784 |
785 ///The type of the map that indicates which nodes are processed. |
785 ///The type of the map that indicates which nodes are processed. |
786 |
786 |
787 ///The type of the map that indicates which nodes are processed. |
787 ///The type of the map that indicates which nodes are processed. |
788 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
788 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
789 ///\todo named parameter to set this type, function to read and write. |
789 ///\todo named parameter to set this type, function to read and write. |
790 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
790 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; |
791 ///Instantiates a ProcessedMap. |
791 ///Instantiates a ProcessedMap. |
792 |
792 |
793 ///This function instantiates a \ref ProcessedMap. |
793 ///This function instantiates a \ref ProcessedMap. |
794 ///\param g is the digraph, to which |
794 ///\param g is the digraph, to which |
795 ///we would like to define the \ref ProcessedMap |
795 ///we would like to define the \ref ProcessedMap |
796 #ifdef DOXYGEN |
796 #ifdef DOXYGEN |
797 static ProcessedMap *createProcessedMap(const GR &g) |
797 static ProcessedMap *createProcessedMap(const GR &g) |
798 #else |
798 #else |
800 #endif |
800 #endif |
801 { |
801 { |
802 return new ProcessedMap(); |
802 return new ProcessedMap(); |
803 } |
803 } |
804 ///The type of the map that indicates which nodes are reached. |
804 ///The type of the map that indicates which nodes are reached. |
805 |
805 |
806 ///The type of the map that indicates which nodes are reached. |
806 ///The type of the map that indicates which nodes are reached. |
807 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
807 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
808 ///\todo named parameter to set this type, function to read and write. |
808 ///\todo named parameter to set this type, function to read and write. |
809 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
809 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
810 ///Instantiates a ReachedMap. |
810 ///Instantiates a ReachedMap. |
811 |
811 |
812 ///This function instantiates a \ref ReachedMap. |
812 ///This function instantiates a \ref ReachedMap. |
813 ///\param G is the digraph, to which |
813 ///\param G is the digraph, to which |
814 ///we would like to define the \ref ReachedMap. |
814 ///we would like to define the \ref ReachedMap. |
815 static ReachedMap *createReachedMap(const GR &G) |
815 static ReachedMap *createReachedMap(const GR &G) |
816 { |
816 { |
817 return new ReachedMap(G); |
817 return new ReachedMap(G); |
818 } |
818 } |
819 ///The type of the map that stores the dists of the nodes. |
819 ///The type of the map that stores the dists of the nodes. |
820 |
820 |
821 ///The type of the map that stores the dists of the nodes. |
821 ///The type of the map that stores the dists of the nodes. |
822 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
822 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. |
823 /// |
823 /// |
824 typedef NullMap<typename Digraph::Node,int> DistMap; |
824 typedef NullMap<typename Digraph::Node,int> DistMap; |
825 ///Instantiates a DistMap. |
825 ///Instantiates a DistMap. |
826 |
826 |
827 ///This function instantiates a \ref DistMap. |
827 ///This function instantiates a \ref DistMap. |
828 ///\param g is the digraph, to which we would like to define the \ref DistMap |
828 ///\param g is the digraph, to which we would like to define the \ref DistMap |
829 #ifdef DOXYGEN |
829 #ifdef DOXYGEN |
830 static DistMap *createDistMap(const GR &g) |
830 static DistMap *createDistMap(const GR &g) |
831 #else |
831 #else |
832 static DistMap *createDistMap(const GR &) |
832 static DistMap *createDistMap(const GR &) |
833 #endif |
833 #endif |
834 { |
834 { |
835 return new DistMap(); |
835 return new DistMap(); |
836 } |
836 } |
837 }; |
837 }; |
838 |
838 |
839 /// Default traits used by \ref BfsWizard |
839 /// Default traits used by \ref BfsWizard |
840 |
840 |
841 /// To make it easier to use Bfs algorithm |
841 /// To make it easier to use Bfs algorithm |
842 ///we have created a wizard class. |
842 ///we have created a wizard class. |
843 /// This \ref BfsWizard class needs default traits, |
843 /// This \ref BfsWizard class needs default traits, |
863 void *_pred; |
863 void *_pred; |
864 ///Pointer to the map of distances. |
864 ///Pointer to the map of distances. |
865 void *_dist; |
865 void *_dist; |
866 ///Pointer to the source node. |
866 ///Pointer to the source node. |
867 Node _source; |
867 Node _source; |
868 |
868 |
869 public: |
869 public: |
870 /// Constructor. |
870 /// Constructor. |
871 |
871 |
872 /// This constructor does not require parameters, therefore it initiates |
872 /// This constructor does not require parameters, therefore it initiates |
873 /// all of the attributes to default values (0, INVALID). |
873 /// all of the attributes to default values (0, INVALID). |
874 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), |
874 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), |
875 _dist(0), _source(INVALID) {} |
875 _dist(0), _source(INVALID) {} |
876 |
876 |
877 /// Constructor. |
877 /// Constructor. |
878 |
878 |
879 /// This constructor requires some parameters, |
879 /// This constructor requires some parameters, |
880 /// listed in the parameters list. |
880 /// listed in the parameters list. |
881 /// Others are initiated to 0. |
881 /// Others are initiated to 0. |
882 /// \param g is the initial value of \ref _g |
882 /// \param g is the initial value of \ref _g |
883 /// \param s is the initial value of \ref _source |
883 /// \param s is the initial value of \ref _source |
884 BfsWizardBase(const GR &g, Node s=INVALID) : |
884 BfsWizardBase(const GR &g, Node s=INVALID) : |
885 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), |
885 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), |
886 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {} |
886 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {} |
887 |
887 |
888 }; |
888 }; |
889 |
889 |
890 /// A class to make the usage of Bfs algorithm easier |
890 /// A class to make the usage of Bfs algorithm easier |
891 |
891 |
892 /// This class is created to make it easier to use Bfs algorithm. |
892 /// This class is created to make it easier to use Bfs algorithm. |
893 /// It uses the functions and features of the plain \ref Bfs, |
893 /// It uses the functions and features of the plain \ref Bfs, |
894 /// but it is much simpler to use it. |
894 /// but it is much simpler to use it. |
949 BfsWizard(const TR &b) : TR(b) {} |
949 BfsWizard(const TR &b) : TR(b) {} |
950 |
950 |
951 ~BfsWizard() {} |
951 ~BfsWizard() {} |
952 |
952 |
953 ///Runs Bfs algorithm from a given node. |
953 ///Runs Bfs algorithm from a given node. |
954 |
954 |
955 ///Runs Bfs algorithm from a given node. |
955 ///Runs Bfs algorithm from a given node. |
956 ///The node can be given by the \ref source function. |
956 ///The node can be given by the \ref source function. |
957 void run() |
957 void run() |
958 { |
958 { |
959 if(Base::_source==INVALID) throw UninitializedParameter(); |
959 if(Base::_source==INVALID) throw UninitializedParameter(); |
960 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); |
960 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g)); |
961 if(Base::_reached) |
961 if(Base::_reached) |
962 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); |
962 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached)); |
963 if(Base::_processed) |
963 if(Base::_processed) |
964 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); |
964 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed)); |
965 if(Base::_pred) |
965 if(Base::_pred) |
966 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); |
966 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred)); |
967 if(Base::_dist) |
967 if(Base::_dist) |
968 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); |
968 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist)); |
969 alg.run(Base::_source); |
969 alg.run(Base::_source); |
970 } |
970 } |
971 |
971 |
972 ///Runs Bfs algorithm from the given node. |
972 ///Runs Bfs algorithm from the given node. |
983 struct DefPredMapBase : public Base { |
983 struct DefPredMapBase : public Base { |
984 typedef T PredMap; |
984 typedef T PredMap; |
985 static PredMap *createPredMap(const Digraph &) { return 0; }; |
985 static PredMap *createPredMap(const Digraph &) { return 0; }; |
986 DefPredMapBase(const TR &b) : TR(b) {} |
986 DefPredMapBase(const TR &b) : TR(b) {} |
987 }; |
987 }; |
988 |
988 |
989 ///\brief \ref named-templ-param "Named parameter" |
989 ///\brief \ref named-templ-param "Named parameter" |
990 ///function for setting PredMap |
990 ///function for setting PredMap |
991 /// |
991 /// |
992 /// \ref named-templ-param "Named parameter" |
992 /// \ref named-templ-param "Named parameter" |
993 ///function for setting PredMap |
993 ///function for setting PredMap |
994 /// |
994 /// |
995 template<class T> |
995 template<class T> |
996 BfsWizard<DefPredMapBase<T> > predMap(const T &t) |
996 BfsWizard<DefPredMapBase<T> > predMap(const T &t) |
997 { |
997 { |
998 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); |
998 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t)); |
999 return BfsWizard<DefPredMapBase<T> >(*this); |
999 return BfsWizard<DefPredMapBase<T> >(*this); |
1000 } |
1000 } |
1001 |
1001 |
1002 |
1002 |
1003 template<class T> |
1003 template<class T> |
1004 struct DefReachedMapBase : public Base { |
1004 struct DefReachedMapBase : public Base { |
1005 typedef T ReachedMap; |
1005 typedef T ReachedMap; |
1006 static ReachedMap *createReachedMap(const Digraph &) { return 0; }; |
1006 static ReachedMap *createReachedMap(const Digraph &) { return 0; }; |
1007 DefReachedMapBase(const TR &b) : TR(b) {} |
1007 DefReachedMapBase(const TR &b) : TR(b) {} |
1008 }; |
1008 }; |
1009 |
1009 |
1010 ///\brief \ref named-templ-param "Named parameter" |
1010 ///\brief \ref named-templ-param "Named parameter" |
1011 ///function for setting ReachedMap |
1011 ///function for setting ReachedMap |
1012 /// |
1012 /// |
1013 /// \ref named-templ-param "Named parameter" |
1013 /// \ref named-templ-param "Named parameter" |
1014 ///function for setting ReachedMap |
1014 ///function for setting ReachedMap |
1015 /// |
1015 /// |
1016 template<class T> |
1016 template<class T> |
1017 BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) |
1017 BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) |
1018 { |
1018 { |
1019 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1019 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1020 return BfsWizard<DefReachedMapBase<T> >(*this); |
1020 return BfsWizard<DefReachedMapBase<T> >(*this); |
1021 } |
1021 } |
1022 |
1022 |
1023 |
1023 |
1024 template<class T> |
1024 template<class T> |
1025 struct DefProcessedMapBase : public Base { |
1025 struct DefProcessedMapBase : public Base { |
1026 typedef T ProcessedMap; |
1026 typedef T ProcessedMap; |
1027 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; |
1027 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; |
1028 DefProcessedMapBase(const TR &b) : TR(b) {} |
1028 DefProcessedMapBase(const TR &b) : TR(b) {} |
1029 }; |
1029 }; |
1030 |
1030 |
1031 ///\brief \ref named-templ-param "Named parameter" |
1031 ///\brief \ref named-templ-param "Named parameter" |
1032 ///function for setting ProcessedMap |
1032 ///function for setting ProcessedMap |
1033 /// |
1033 /// |
1034 /// \ref named-templ-param "Named parameter" |
1034 /// \ref named-templ-param "Named parameter" |
1035 ///function for setting ProcessedMap |
1035 ///function for setting ProcessedMap |
1036 /// |
1036 /// |
1037 template<class T> |
1037 template<class T> |
1038 BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) |
1038 BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) |
1039 { |
1039 { |
1040 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1040 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1041 return BfsWizard<DefProcessedMapBase<T> >(*this); |
1041 return BfsWizard<DefProcessedMapBase<T> >(*this); |
1042 } |
1042 } |
1043 |
1043 |
1044 |
1044 |
1045 template<class T> |
1045 template<class T> |
1046 struct DefDistMapBase : public Base { |
1046 struct DefDistMapBase : public Base { |
1047 typedef T DistMap; |
1047 typedef T DistMap; |
1048 static DistMap *createDistMap(const Digraph &) { return 0; }; |
1048 static DistMap *createDistMap(const Digraph &) { return 0; }; |
1049 DefDistMapBase(const TR &b) : TR(b) {} |
1049 DefDistMapBase(const TR &b) : TR(b) {} |
1050 }; |
1050 }; |
1051 |
1051 |
1052 ///\brief \ref named-templ-param "Named parameter" |
1052 ///\brief \ref named-templ-param "Named parameter" |
1053 ///function for setting DistMap type |
1053 ///function for setting DistMap type |
1054 /// |
1054 /// |
1055 /// \ref named-templ-param "Named parameter" |
1055 /// \ref named-templ-param "Named parameter" |
1056 ///function for setting DistMap type |
1056 ///function for setting DistMap type |
1057 /// |
1057 /// |
1058 template<class T> |
1058 template<class T> |
1059 BfsWizard<DefDistMapBase<T> > distMap(const T &t) |
1059 BfsWizard<DefDistMapBase<T> > distMap(const T &t) |
1060 { |
1060 { |
1061 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1061 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t)); |
1062 return BfsWizard<DefDistMapBase<T> >(*this); |
1062 return BfsWizard<DefDistMapBase<T> >(*this); |
1063 } |
1063 } |
1064 |
1064 |
1065 /// Sets the source node, from which the Bfs algorithm runs. |
1065 /// Sets the source node, from which the Bfs algorithm runs. |
1066 |
1066 |
1067 /// Sets the source node, from which the Bfs algorithm runs. |
1067 /// Sets the source node, from which the Bfs algorithm runs. |
1068 /// \param s is the source node. |
1068 /// \param s is the source node. |
1069 BfsWizard<TR> &source(Node s) |
1069 BfsWizard<TR> &source(Node s) |
1070 { |
1070 { |
1071 Base::_source=s; |
1071 Base::_source=s; |
1072 return *this; |
1072 return *this; |
1073 } |
1073 } |
1074 |
1074 |
1075 }; |
1075 }; |
1076 |
1076 |
1077 ///Function type interface for Bfs algorithm. |
1077 ///Function type interface for Bfs algorithm. |
1078 |
1078 |
1079 /// \ingroup search |
1079 /// \ingroup search |
1080 ///Function type interface for Bfs algorithm. |
1080 ///Function type interface for Bfs algorithm. |
1081 /// |
1081 /// |
1098 return BfsWizard<BfsWizardBase<GR> >(g,s); |
1098 return BfsWizard<BfsWizardBase<GR> >(g,s); |
1099 } |
1099 } |
1100 |
1100 |
1101 #ifdef DOXYGEN |
1101 #ifdef DOXYGEN |
1102 /// \brief Visitor class for bfs. |
1102 /// \brief Visitor class for bfs. |
1103 /// |
1103 /// |
1104 /// This class defines the interface of the BfsVisit events, and |
1104 /// This class defines the interface of the BfsVisit events, and |
1105 /// it could be the base of a real Visitor class. |
1105 /// it could be the base of a real Visitor class. |
1106 template <typename _Digraph> |
1106 template <typename _Digraph> |
1107 struct BfsVisitor { |
1107 struct BfsVisitor { |
1108 typedef _Digraph Digraph; |
1108 typedef _Digraph Digraph; |
1109 typedef typename Digraph::Arc Arc; |
1109 typedef typename Digraph::Arc Arc; |
1110 typedef typename Digraph::Node Node; |
1110 typedef typename Digraph::Node Node; |
1111 /// \brief Called when the arc reach a node. |
1111 /// \brief Called when the arc reach a node. |
1112 /// |
1112 /// |
1113 /// It is called when the bfs find an arc which target is not |
1113 /// It is called when the bfs find an arc which target is not |
1114 /// reached yet. |
1114 /// reached yet. |
1115 void discover(const Arc& arc) {} |
1115 void discover(const Arc& arc) {} |
1116 /// \brief Called when the node reached first time. |
1116 /// \brief Called when the node reached first time. |
1117 /// |
1117 /// |
1118 /// It is Called when the node reached first time. |
1118 /// It is Called when the node reached first time. |
1119 void reach(const Node& node) {} |
1119 void reach(const Node& node) {} |
1120 /// \brief Called when the arc examined but target of the arc |
1120 /// \brief Called when the arc examined but target of the arc |
1121 /// already discovered. |
1121 /// already discovered. |
1122 /// |
1122 /// |
1123 /// It called when the arc examined but the target of the arc |
1123 /// It called when the arc examined but the target of the arc |
1124 /// already discovered. |
1124 /// already discovered. |
1125 void examine(const Arc& arc) {} |
1125 void examine(const Arc& arc) {} |
1126 /// \brief Called for the source node of the bfs. |
1126 /// \brief Called for the source node of the bfs. |
1127 /// |
1127 /// |
1128 /// It is called for the source node of the bfs. |
1128 /// It is called for the source node of the bfs. |
1129 void start(const Node& node) {} |
1129 void start(const Node& node) {} |
1130 /// \brief Called when the node processed. |
1130 /// \brief Called when the node processed. |
1131 /// |
1131 /// |
1132 /// It is Called when the node processed. |
1132 /// It is Called when the node processed. |
1133 void process(const Node& node) {} |
1133 void process(const Node& node) {} |
1134 }; |
1134 }; |
1135 #else |
1135 #else |
1136 template <typename _Digraph> |
1136 template <typename _Digraph> |
1165 /// Default traits class of BfsVisit class. |
1165 /// Default traits class of BfsVisit class. |
1166 /// \tparam _Digraph Digraph type. |
1166 /// \tparam _Digraph Digraph type. |
1167 template<class _Digraph> |
1167 template<class _Digraph> |
1168 struct BfsVisitDefaultTraits { |
1168 struct BfsVisitDefaultTraits { |
1169 |
1169 |
1170 /// \brief The digraph type the algorithm runs on. |
1170 /// \brief The digraph type the algorithm runs on. |
1171 typedef _Digraph Digraph; |
1171 typedef _Digraph Digraph; |
1172 |
1172 |
1173 /// \brief The type of the map that indicates which nodes are reached. |
1173 /// \brief The type of the map that indicates which nodes are reached. |
1174 /// |
1174 /// |
1175 /// The type of the map that indicates which nodes are reached. |
1175 /// The type of the map that indicates which nodes are reached. |
1176 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. |
1176 /// It must meet the \ref concepts::WriteMap "WriteMap" concept. |
1177 /// \todo named parameter to set this type, function to read and write. |
1177 /// \todo named parameter to set this type, function to read and write. |
1178 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
1178 typedef typename Digraph::template NodeMap<bool> ReachedMap; |
1179 |
1179 |
1180 /// \brief Instantiates a ReachedMap. |
1180 /// \brief Instantiates a ReachedMap. |
1181 /// |
1181 /// |
1182 /// This function instantiates a \ref ReachedMap. |
1182 /// This function instantiates a \ref ReachedMap. |
1183 /// \param digraph is the digraph, to which |
1183 /// \param digraph is the digraph, to which |
1184 /// we would like to define the \ref ReachedMap. |
1184 /// we would like to define the \ref ReachedMap. |
1185 static ReachedMap *createReachedMap(const Digraph &digraph) { |
1185 static ReachedMap *createReachedMap(const Digraph &digraph) { |
1186 return new ReachedMap(digraph); |
1186 return new ReachedMap(digraph); |
1187 } |
1187 } |
1188 |
1188 |
1189 }; |
1189 }; |
1190 |
1190 |
1191 /// \ingroup search |
1191 /// \ingroup search |
1192 /// |
1192 /// |
1193 /// \brief %BFS Visit algorithm class. |
1193 /// \brief %BFS Visit algorithm class. |
1194 /// |
1194 /// |
1195 /// This class provides an efficient implementation of the %BFS algorithm |
1195 /// This class provides an efficient implementation of the %BFS algorithm |
1196 /// with visitor interface. |
1196 /// with visitor interface. |
1197 /// |
1197 /// |
1198 /// The %BfsVisit class provides an alternative interface to the Bfs |
1198 /// The %BfsVisit class provides an alternative interface to the Bfs |
1199 /// class. It works with callback mechanism, the BfsVisit object calls |
1199 /// class. It works with callback mechanism, the BfsVisit object calls |
1200 /// on every bfs event the \c Visitor class member functions. |
1200 /// on every bfs event the \c Visitor class member functions. |
1201 /// |
1201 /// |
1202 /// \tparam _Digraph The digraph type the algorithm runs on. The default value is |
1202 /// \tparam _Digraph The digraph type the algorithm runs on. The default value is |
1203 /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it |
1203 /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it |
1204 /// is only passed to \ref BfsDefaultTraits. |
1204 /// is only passed to \ref BfsDefaultTraits. |
1205 /// \tparam _Visitor The Visitor object for the algorithm. The |
1205 /// \tparam _Visitor The Visitor object for the algorithm. The |
1206 /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitor which |
1206 /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitor which |
1207 /// does not observe the Bfs events. If you want to observe the bfs |
1207 /// does not observe the Bfs events. If you want to observe the bfs |
1208 /// events you should implement your own Visitor class. |
1208 /// events you should implement your own Visitor class. |
1209 /// \tparam _Traits Traits class to set various data types used by the |
1209 /// \tparam _Traits Traits class to set various data types used by the |
1210 /// algorithm. The default traits class is |
1210 /// algorithm. The default traits class is |
1211 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>". |
1211 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>". |
1212 /// See \ref BfsVisitDefaultTraits for the documentation of |
1212 /// See \ref BfsVisitDefaultTraits for the documentation of |
1213 /// a Bfs visit traits class. |
1213 /// a Bfs visit traits class. |
1214 #ifdef DOXYGEN |
1214 #ifdef DOXYGEN |
1215 template <typename _Digraph, typename _Visitor, typename _Traits> |
1215 template <typename _Digraph, typename _Visitor, typename _Traits> |
1216 #else |
1216 #else |
1217 template <typename _Digraph = ListDigraph, |
1217 template <typename _Digraph = ListDigraph, |
1218 typename _Visitor = BfsVisitor<_Digraph>, |
1218 typename _Visitor = BfsVisitor<_Digraph>, |
1219 typename _Traits = BfsDefaultTraits<_Digraph> > |
1219 typename _Traits = BfsDefaultTraits<_Digraph> > |
1220 #endif |
1220 #endif |
1221 class BfsVisit { |
1221 class BfsVisit { |
1222 public: |
1222 public: |
1223 |
1223 |
1224 /// \brief \ref Exception for uninitialized parameters. |
1224 /// \brief \ref Exception for uninitialized parameters. |
1225 /// |
1225 /// |
1226 /// This error represents problems in the initialization |
1226 /// This error represents problems in the initialization |
1227 /// of the parameters of the algorithms. |
1227 /// of the parameters of the algorithms. |
1228 class UninitializedParameter : public lemon::UninitializedParameter { |
1228 class UninitializedParameter : public lemon::UninitializedParameter { |
1229 public: |
1229 public: |
1230 virtual const char* what() const throw() |
1230 virtual const char* what() const throw() |
1231 { |
1231 { |
1232 return "lemon::BfsVisit::UninitializedParameter"; |
1232 return "lemon::BfsVisit::UninitializedParameter"; |
1233 } |
1233 } |
1234 }; |
1234 }; |
1235 |
1235 |
1236 typedef _Traits Traits; |
1236 typedef _Traits Traits; |
1237 |
1237 |
1284 ///@{ |
1284 ///@{ |
1285 template <class T> |
1285 template <class T> |
1286 struct DefReachedMapTraits : public Traits { |
1286 struct DefReachedMapTraits : public Traits { |
1287 typedef T ReachedMap; |
1287 typedef T ReachedMap; |
1288 static ReachedMap *createReachedMap(const Digraph &digraph) { |
1288 static ReachedMap *createReachedMap(const Digraph &digraph) { |
1289 throw UninitializedParameter(); |
1289 throw UninitializedParameter(); |
1290 } |
1290 } |
1291 }; |
1291 }; |
1292 /// \brief \ref named-templ-param "Named parameter" for setting |
1292 /// \brief \ref named-templ-param "Named parameter" for setting |
1293 /// ReachedMap type |
1293 /// ReachedMap type |
1294 /// |
1294 /// |
1295 /// \ref named-templ-param "Named parameter" for setting ReachedMap type |
1295 /// \ref named-templ-param "Named parameter" for setting ReachedMap type |
1296 template <class T> |
1296 template <class T> |
1297 struct DefReachedMap : public BfsVisit< Digraph, Visitor, |
1297 struct DefReachedMap : public BfsVisit< Digraph, Visitor, |
1298 DefReachedMapTraits<T> > { |
1298 DefReachedMapTraits<T> > { |
1299 typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create; |
1299 typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create; |
1300 }; |
1300 }; |
1301 ///@} |
1301 ///@} |
1302 |
1302 |
1303 public: |
1303 public: |
1304 |
1304 |
1305 /// \brief Constructor. |
1305 /// \brief Constructor. |
1306 /// |
1306 /// |
1307 /// Constructor. |
1307 /// Constructor. |
1308 /// |
1308 /// |
1309 /// \param digraph the digraph the algorithm will run on. |
1309 /// \param digraph the digraph the algorithm will run on. |
1310 /// \param visitor The visitor of the algorithm. |
1310 /// \param visitor The visitor of the algorithm. |
1311 /// |
1311 /// |
1312 BfsVisit(const Digraph& digraph, Visitor& visitor) |
1312 BfsVisit(const Digraph& digraph, Visitor& visitor) |
1313 : _digraph(&digraph), _visitor(&visitor), |
1313 : _digraph(&digraph), _visitor(&visitor), |
1314 _reached(0), local_reached(false) {} |
1314 _reached(0), local_reached(false) {} |
1315 |
1315 |
1316 /// \brief Destructor. |
1316 /// \brief Destructor. |
1317 /// |
1317 /// |
1318 /// Destructor. |
1318 /// Destructor. |
1319 ~BfsVisit() { |
1319 ~BfsVisit() { |
1320 if(local_reached) delete _reached; |
1320 if(local_reached) delete _reached; |
1355 void init() { |
1355 void init() { |
1356 create_maps(); |
1356 create_maps(); |
1357 _list.resize(countNodes(*_digraph)); |
1357 _list.resize(countNodes(*_digraph)); |
1358 _list_front = _list_back = -1; |
1358 _list_front = _list_back = -1; |
1359 for (NodeIt u(*_digraph) ; u != INVALID ; ++u) { |
1359 for (NodeIt u(*_digraph) ; u != INVALID ; ++u) { |
1360 _reached->set(u, false); |
1360 _reached->set(u, false); |
1361 } |
1361 } |
1362 } |
1362 } |
1363 |
1363 |
1364 /// \brief Adds a new source node. |
1364 /// \brief Adds a new source node. |
1365 /// |
1365 /// |
1366 /// Adds a new source node to the set of nodes to be processed. |
1366 /// Adds a new source node to the set of nodes to be processed. |
1367 void addSource(Node s) { |
1367 void addSource(Node s) { |
1368 if(!(*_reached)[s]) { |
1368 if(!(*_reached)[s]) { |
1369 _reached->set(s,true); |
1369 _reached->set(s,true); |
1370 _visitor->start(s); |
1370 _visitor->start(s); |
1371 _visitor->reach(s); |
1371 _visitor->reach(s); |
1372 _list[++_list_back] = s; |
1372 _list[++_list_back] = s; |
1373 } |
1373 } |
1374 } |
1374 } |
1375 |
1375 |
1376 /// \brief Processes the next node. |
1376 /// \brief Processes the next node. |
1377 /// |
1377 /// |
1378 /// Processes the next node. |
1378 /// Processes the next node. |
1379 /// |
1379 /// |
1380 /// \return The processed node. |
1380 /// \return The processed node. |
1381 /// |
1381 /// |
1382 /// \pre The queue must not be empty! |
1382 /// \pre The queue must not be empty! |
1383 Node processNextNode() { |
1383 Node processNextNode() { |
1384 Node n = _list[++_list_front]; |
1384 Node n = _list[++_list_front]; |
1385 _visitor->process(n); |
1385 _visitor->process(n); |
1386 Arc e; |
1386 Arc e; |
1387 for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) { |
1387 for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) { |
1388 Node m = _digraph->target(e); |
1388 Node m = _digraph->target(e); |
1480 |
1480 |
1481 /// \brief Returns the number of the nodes to be processed. |
1481 /// \brief Returns the number of the nodes to be processed. |
1482 /// |
1482 /// |
1483 /// Returns the number of the nodes to be processed in the queue. |
1483 /// Returns the number of the nodes to be processed in the queue. |
1484 int queueSize() { return _list_back - _list_front; } |
1484 int queueSize() { return _list_back - _list_front; } |
1485 |
1485 |
1486 /// \brief Executes the algorithm. |
1486 /// \brief Executes the algorithm. |
1487 /// |
1487 /// |
1488 /// Executes the algorithm. |
1488 /// Executes the algorithm. |
1489 /// |
1489 /// |
1490 /// \pre init() must be called and at least one node should be added |
1490 /// \pre init() must be called and at least one node should be added |
1491 /// with addSource() before using this function. |
1491 /// with addSource() before using this function. |
1492 void start() { |
1492 void start() { |
1493 while ( !emptyQueue() ) processNextNode(); |
1493 while ( !emptyQueue() ) processNextNode(); |
1494 } |
1494 } |
1495 |
1495 |
1496 /// \brief Executes the algorithm until \c dest is reached. |
1496 /// \brief Executes the algorithm until \c dest is reached. |
1497 /// |
1497 /// |
1498 /// Executes the algorithm until \c dest is reached. |
1498 /// Executes the algorithm until \c dest is reached. |
1499 /// |
1499 /// |
1500 /// \pre init() must be called and at least one node should be added |
1500 /// \pre init() must be called and at least one node should be added |
1501 /// with addSource() before using this function. |
1501 /// with addSource() before using this function. |
1502 void start(Node dest) { |
1502 void start(Node dest) { |
1503 bool reach = false; |
1503 bool reach = false; |
1504 while ( !emptyQueue() && !reach ) processNextNode(dest, reach); |
1504 while ( !emptyQueue() && !reach ) processNextNode(dest, reach); |
1505 } |
1505 } |
1506 |
1506 |
1507 /// \brief Executes the algorithm until a condition is met. |
1507 /// \brief Executes the algorithm until a condition is met. |
1508 /// |
1508 /// |
1509 /// Executes the algorithm until a condition is met. |
1509 /// Executes the algorithm until a condition is met. |
1510 /// |
1510 /// |
1511 /// \pre init() must be called and at least one node should be added |
1511 /// \pre init() must be called and at least one node should be added |