Branch data Line data Source code
1 : : /* -*- mode: C++; indent-tabs-mode: nil; -*-
2 : : *
3 : : * This file is a part of LEMON, a generic C++ optimization library.
4 : : *
5 : : * Copyright (C) 2003-2010
6 : : * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 : : * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 : : *
9 : : * Permission to use, modify and distribute this software is granted
10 : : * provided that this copyright notice appears in all copies. For
11 : : * precise terms see the accompanying LICENSE file.
12 : : *
13 : : * This software is provided "AS IS" with no warranty of any kind,
14 : : * express or implied, and with no claim as to its suitability for any
15 : : * purpose.
16 : : *
17 : : */
18 : :
19 : : #ifndef LEMON_BFS_H
20 : : #define LEMON_BFS_H
21 : :
22 : : ///\ingroup search
23 : : ///\file
24 : : ///\brief BFS algorithm.
25 : :
26 : : #include <lemon/list_graph.h>
27 : : #include <lemon/bits/path_dump.h>
28 : : #include <lemon/core.h>
29 : : #include <lemon/error.h>
30 : : #include <lemon/maps.h>
31 : : #include <lemon/path.h>
32 : :
33 : : namespace lemon {
34 : :
35 : : ///Default traits class of Bfs class.
36 : :
37 : : ///Default traits class of Bfs class.
38 : : ///\tparam GR Digraph type.
39 : : template<class GR>
40 : : struct BfsDefaultTraits
41 : : {
42 : : ///The type of the digraph the algorithm runs on.
43 : : typedef GR Digraph;
44 : :
45 : : ///\brief The type of the map that stores the predecessor
46 : : ///arcs of the shortest paths.
47 : : ///
48 : : ///The type of the map that stores the predecessor
49 : : ///arcs of the shortest paths.
50 : : ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
51 : : typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
52 : : ///Instantiates a \c PredMap.
53 : :
54 : : ///This function instantiates a \ref PredMap.
55 : : ///\param g is the digraph, to which we would like to define the
56 : : ///\ref PredMap.
57 : 269 : static PredMap *createPredMap(const Digraph &g)
58 : : {
59 [ + - ][ + - ]: 269 : return new PredMap(g);
60 : : }
61 : :
62 : : ///The type of the map that indicates which nodes are processed.
63 : :
64 : : ///The type of the map that indicates which nodes are processed.
65 : : ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
66 : : ///By default, it is a NullMap.
67 : : typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
68 : : ///Instantiates a \c ProcessedMap.
69 : :
70 : : ///This function instantiates a \ref ProcessedMap.
71 : : ///\param g is the digraph, to which
72 : : ///we would like to define the \ref ProcessedMap
73 : : #ifdef DOXYGEN
74 : : static ProcessedMap *createProcessedMap(const Digraph &g)
75 : : #else
76 : 269 : static ProcessedMap *createProcessedMap(const Digraph &)
77 : : #endif
78 : : {
79 : 269 : return new ProcessedMap();
80 : : }
81 : :
82 : : ///The type of the map that indicates which nodes are reached.
83 : :
84 : : ///The type of the map that indicates which nodes are reached.
85 : : ///It must conform to
86 : : ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
87 : : typedef typename Digraph::template NodeMap<bool> ReachedMap;
88 : : ///Instantiates a \c ReachedMap.
89 : :
90 : : ///This function instantiates a \ref ReachedMap.
91 : : ///\param g is the digraph, to which
92 : : ///we would like to define the \ref ReachedMap.
93 : 269 : static ReachedMap *createReachedMap(const Digraph &g)
94 : : {
95 [ + - ][ + - ]: 269 : return new ReachedMap(g);
96 : : }
97 : :
98 : : ///The type of the map that stores the distances of the nodes.
99 : :
100 : : ///The type of the map that stores the distances of the nodes.
101 : : ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
102 : : typedef typename Digraph::template NodeMap<int> DistMap;
103 : : ///Instantiates a \c DistMap.
104 : :
105 : : ///This function instantiates a \ref DistMap.
106 : : ///\param g is the digraph, to which we would like to define the
107 : : ///\ref DistMap.
108 : 269 : static DistMap *createDistMap(const Digraph &g)
109 : : {
110 [ + - ][ + - ]: 269 : return new DistMap(g);
111 : : }
112 : : };
113 : :
114 : : ///%BFS algorithm class.
115 : :
116 : : ///\ingroup search
117 : : ///This class provides an efficient implementation of the %BFS algorithm.
118 : : ///
119 : : ///There is also a \ref bfs() "function-type interface" for the BFS
120 : : ///algorithm, which is convenient in the simplier cases and it can be
121 : : ///used easier.
122 : : ///
123 : : ///\tparam GR The type of the digraph the algorithm runs on.
124 : : ///The default type is \ref ListDigraph.
125 : : ///\tparam TR The traits class that defines various types used by the
126 : : ///algorithm. By default, it is \ref BfsDefaultTraits
127 : : ///"BfsDefaultTraits<GR>".
128 : : ///In most cases, this parameter should not be set directly,
129 : : ///consider to use the named template parameters instead.
130 : : #ifdef DOXYGEN
131 : : template <typename GR,
132 : : typename TR>
133 : : #else
134 : : template <typename GR=ListDigraph,
135 : : typename TR=BfsDefaultTraits<GR> >
136 : : #endif
137 : : class Bfs {
138 : : public:
139 : :
140 : : ///The type of the digraph the algorithm runs on.
141 : : typedef typename TR::Digraph Digraph;
142 : :
143 : : ///\brief The type of the map that stores the predecessor arcs of the
144 : : ///shortest paths.
145 : : typedef typename TR::PredMap PredMap;
146 : : ///The type of the map that stores the distances of the nodes.
147 : : typedef typename TR::DistMap DistMap;
148 : : ///The type of the map that indicates which nodes are reached.
149 : : typedef typename TR::ReachedMap ReachedMap;
150 : : ///The type of the map that indicates which nodes are processed.
151 : : typedef typename TR::ProcessedMap ProcessedMap;
152 : : ///The type of the paths.
153 : : typedef PredMapPath<Digraph, PredMap> Path;
154 : :
155 : : ///The \ref BfsDefaultTraits "traits class" of the algorithm.
156 : : typedef TR Traits;
157 : :
158 : : private:
159 : :
160 : : typedef typename Digraph::Node Node;
161 : : typedef typename Digraph::NodeIt NodeIt;
162 : : typedef typename Digraph::Arc Arc;
163 : : typedef typename Digraph::OutArcIt OutArcIt;
164 : :
165 : : //Pointer to the underlying digraph.
166 : : const Digraph *G;
167 : : //Pointer to the map of predecessor arcs.
168 : : PredMap *_pred;
169 : : //Indicates if _pred is locally allocated (true) or not.
170 : : bool local_pred;
171 : : //Pointer to the map of distances.
172 : : DistMap *_dist;
173 : : //Indicates if _dist is locally allocated (true) or not.
174 : : bool local_dist;
175 : : //Pointer to the map of reached status of the nodes.
176 : : ReachedMap *_reached;
177 : : //Indicates if _reached is locally allocated (true) or not.
178 : : bool local_reached;
179 : : //Pointer to the map of processed status of the nodes.
180 : : ProcessedMap *_processed;
181 : : //Indicates if _processed is locally allocated (true) or not.
182 : : bool local_processed;
183 : :
184 : : std::vector<typename Digraph::Node> _queue;
185 : : int _queue_head,_queue_tail,_queue_next_dist;
186 : : int _curr_dist;
187 : :
188 : : //Creates the maps if necessary.
189 : 269 : void create_maps()
190 : : {
191 [ + - ][ + - ]: 269 : if(!_pred) {
192 : 269 : local_pred = true;
193 : 269 : _pred = Traits::createPredMap(*G);
194 : : }
195 [ + - ][ + - ]: 269 : if(!_dist) {
196 : 269 : local_dist = true;
197 : 269 : _dist = Traits::createDistMap(*G);
198 : : }
199 [ + - ][ + - ]: 269 : if(!_reached) {
200 : 269 : local_reached = true;
201 : 269 : _reached = Traits::createReachedMap(*G);
202 : : }
203 [ + - ][ + - ]: 269 : if(!_processed) {
204 : 269 : local_processed = true;
205 : 269 : _processed = Traits::createProcessedMap(*G);
206 : : }
207 : 269 : }
208 : :
209 : : protected:
210 : :
211 : : Bfs() {}
212 : :
213 : : public:
214 : :
215 : : typedef Bfs Create;
216 : :
217 : : ///\name Named Template Parameters
218 : :
219 : : ///@{
220 : :
221 : : template <class T>
222 : : struct SetPredMapTraits : public Traits {
223 : : typedef T PredMap;
224 : : static PredMap *createPredMap(const Digraph &)
225 : : {
226 : : LEMON_ASSERT(false, "PredMap is not initialized");
227 : : return 0; // ignore warnings
228 : : }
229 : : };
230 : : ///\brief \ref named-templ-param "Named parameter" for setting
231 : : ///\c PredMap type.
232 : : ///
233 : : ///\ref named-templ-param "Named parameter" for setting
234 : : ///\c PredMap type.
235 : : ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
236 : : template <class T>
237 : : struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
238 : : typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
239 : : };
240 : :
241 : : template <class T>
242 : : struct SetDistMapTraits : public Traits {
243 : : typedef T DistMap;
244 : : static DistMap *createDistMap(const Digraph &)
245 : : {
246 : : LEMON_ASSERT(false, "DistMap is not initialized");
247 : : return 0; // ignore warnings
248 : : }
249 : : };
250 : : ///\brief \ref named-templ-param "Named parameter" for setting
251 : : ///\c DistMap type.
252 : : ///
253 : : ///\ref named-templ-param "Named parameter" for setting
254 : : ///\c DistMap type.
255 : : ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
256 : : template <class T>
257 : : struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
258 : : typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
259 : : };
260 : :
261 : : template <class T>
262 : : struct SetReachedMapTraits : public Traits {
263 : : typedef T ReachedMap;
264 : : static ReachedMap *createReachedMap(const Digraph &)
265 : : {
266 : : LEMON_ASSERT(false, "ReachedMap is not initialized");
267 : : return 0; // ignore warnings
268 : : }
269 : : };
270 : : ///\brief \ref named-templ-param "Named parameter" for setting
271 : : ///\c ReachedMap type.
272 : : ///
273 : : ///\ref named-templ-param "Named parameter" for setting
274 : : ///\c ReachedMap type.
275 : : ///It must conform to
276 : : ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
277 : : template <class T>
278 : : struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
279 : : typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
280 : : };
281 : :
282 : : template <class T>
283 : : struct SetProcessedMapTraits : public Traits {
284 : : typedef T ProcessedMap;
285 : : static ProcessedMap *createProcessedMap(const Digraph &)
286 : : {
287 : : LEMON_ASSERT(false, "ProcessedMap is not initialized");
288 : : return 0; // ignore warnings
289 : : }
290 : : };
291 : : ///\brief \ref named-templ-param "Named parameter" for setting
292 : : ///\c ProcessedMap type.
293 : : ///
294 : : ///\ref named-templ-param "Named parameter" for setting
295 : : ///\c ProcessedMap type.
296 : : ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
297 : : template <class T>
298 : : struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
299 : : typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
300 : : };
301 : :
302 : : struct SetStandardProcessedMapTraits : public Traits {
303 : : typedef typename Digraph::template NodeMap<bool> ProcessedMap;
304 : : static ProcessedMap *createProcessedMap(const Digraph &g)
305 : : {
306 : : return new ProcessedMap(g);
307 : : return 0; // ignore warnings
308 : : }
309 : : };
310 : : ///\brief \ref named-templ-param "Named parameter" for setting
311 : : ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
312 : : ///
313 : : ///\ref named-templ-param "Named parameter" for setting
314 : : ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
315 : : ///If you don't set it explicitly, it will be automatically allocated.
316 : : struct SetStandardProcessedMap :
317 : : public Bfs< Digraph, SetStandardProcessedMapTraits > {
318 : : typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;
319 : : };
320 : :
321 : : ///@}
322 : :
323 : : public:
324 : :
325 : : ///Constructor.
326 : :
327 : : ///Constructor.
328 : : ///\param g The digraph the algorithm runs on.
329 : 269 : Bfs(const Digraph &g) :
330 : : G(&g),
331 : : _pred(NULL), local_pred(false),
332 : : _dist(NULL), local_dist(false),
333 : : _reached(NULL), local_reached(false),
334 : 269 : _processed(NULL), local_processed(false)
335 : 269 : { }
336 : :
337 : : ///Destructor.
338 : 269 : ~Bfs()
339 : : {
340 [ + - ][ + - ]: 269 : if(local_pred) delete _pred;
[ + - ][ + - ]
341 [ + - ][ + - ]: 269 : if(local_dist) delete _dist;
[ + - ][ + - ]
342 [ + - ][ + - ]: 269 : if(local_reached) delete _reached;
[ + - ][ + - ]
343 [ + - ][ + - ]: 269 : if(local_processed) delete _processed;
344 : 269 : }
345 : :
346 : : ///Sets the map that stores the predecessor arcs.
347 : :
348 : : ///Sets the map that stores the predecessor arcs.
349 : : ///If you don't use this function before calling \ref run(Node) "run()"
350 : : ///or \ref init(), an instance will be allocated automatically.
351 : : ///The destructor deallocates this automatically allocated map,
352 : : ///of course.
353 : : ///\return <tt> (*this) </tt>
354 : : Bfs &predMap(PredMap &m)
355 : : {
356 : : if(local_pred) {
357 : : delete _pred;
358 : : local_pred=false;
359 : : }
360 : : _pred = &m;
361 : : return *this;
362 : : }
363 : :
364 : : ///Sets the map that indicates which nodes are reached.
365 : :
366 : : ///Sets the map that indicates which nodes are reached.
367 : : ///If you don't use this function before calling \ref run(Node) "run()"
368 : : ///or \ref init(), an instance will be allocated automatically.
369 : : ///The destructor deallocates this automatically allocated map,
370 : : ///of course.
371 : : ///\return <tt> (*this) </tt>
372 : : Bfs &reachedMap(ReachedMap &m)
373 : : {
374 : : if(local_reached) {
375 : : delete _reached;
376 : : local_reached=false;
377 : : }
378 : : _reached = &m;
379 : : return *this;
380 : : }
381 : :
382 : : ///Sets the map that indicates which nodes are processed.
383 : :
384 : : ///Sets the map that indicates which nodes are processed.
385 : : ///If you don't use this function before calling \ref run(Node) "run()"
386 : : ///or \ref init(), an instance will be allocated automatically.
387 : : ///The destructor deallocates this automatically allocated map,
388 : : ///of course.
389 : : ///\return <tt> (*this) </tt>
390 : : Bfs &processedMap(ProcessedMap &m)
391 : : {
392 : : if(local_processed) {
393 : : delete _processed;
394 : : local_processed=false;
395 : : }
396 : : _processed = &m;
397 : : return *this;
398 : : }
399 : :
400 : : ///Sets the map that stores the distances of the nodes.
401 : :
402 : : ///Sets the map that stores the distances of the nodes calculated by
403 : : ///the algorithm.
404 : : ///If you don't use this function before calling \ref run(Node) "run()"
405 : : ///or \ref init(), an instance will be allocated automatically.
406 : : ///The destructor deallocates this automatically allocated map,
407 : : ///of course.
408 : : ///\return <tt> (*this) </tt>
409 : : Bfs &distMap(DistMap &m)
410 : : {
411 : : if(local_dist) {
412 : : delete _dist;
413 : : local_dist=false;
414 : : }
415 : : _dist = &m;
416 : : return *this;
417 : : }
418 : :
419 : : public:
420 : :
421 : : ///\name Execution Control
422 : : ///The simplest way to execute the BFS algorithm is to use one of the
423 : : ///member functions called \ref run(Node) "run()".\n
424 : : ///If you need better control on the execution, you have to call
425 : : ///\ref init() first, then you can add several source nodes with
426 : : ///\ref addSource(). Finally the actual path computation can be
427 : : ///performed with one of the \ref start() functions.
428 : :
429 : : ///@{
430 : :
431 : : ///\brief Initializes the internal data structures.
432 : : ///
433 : : ///Initializes the internal data structures.
434 : 269 : void init()
435 : : {
436 : 269 : create_maps();
437 : 269 : _queue.resize(countNodes(*G));
438 : 269 : _queue_head=_queue_tail=0;
439 : 269 : _curr_dist=1;
440 [ + - ][ + - ]: 1770 : for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
[ + - ][ + - ]
[ + + + - ]
[ + - ][ + - ]
[ + - ][ + + ]
441 [ + - ][ + - ]: 1501 : _pred->set(u,INVALID);
[ + - ][ + - ]
442 [ + - ][ + - ]: 1501 : _reached->set(u,false);
443 [ + - ][ + - ]: 1501 : _processed->set(u,false);
444 : : }
445 : 269 : }
446 : :
447 : : ///Adds a new source node.
448 : :
449 : : ///Adds a new source node to the set of nodes to be processed.
450 : : ///
451 : 269 : void addSource(Node s)
452 : : {
453 [ + - ][ + - ]: 269 : if(!(*_reached)[s])
454 : : {
455 [ + - ][ + - ]: 269 : _reached->set(s,true);
456 [ + - ][ + - ]: 269 : _pred->set(s,INVALID);
457 [ + - ][ + - ]: 269 : _dist->set(s,0);
458 : 269 : _queue[_queue_head++]=s;
459 : 269 : _queue_next_dist=_queue_head;
460 : : }
461 : 269 : }
462 : :
463 : : ///Processes the next node.
464 : :
465 : : ///Processes the next node.
466 : : ///
467 : : ///\return The processed node.
468 : : ///
469 : : ///\pre The queue must not be empty.
470 : 1310 : Node processNextNode()
471 : : {
472 [ + + ][ + + ]: 1310 : if(_queue_tail==_queue_next_dist) {
473 : 734 : _curr_dist++;
474 : 734 : _queue_next_dist=_queue_head;
475 : : }
476 [ + - ][ + - ]: 1310 : Node n=_queue[_queue_tail++];
477 [ + - ][ + - ]: 1310 : _processed->set(n,true);
478 [ + - ][ + - ]: 1310 : Node m;
479 [ + - ][ + - ]: 2670 : for(OutArcIt e(*G,n);e!=INVALID;++e)
[ + - ][ + - ]
[ + + ][ + - ]
[ + - ][ + - ]
[ + - ][ + + ]
480 [ + - ][ + - ]: 1360 : if(!(*_reached)[m=G->target(e)]) {
[ + + ][ + - ]
[ + - ][ + + ]
481 [ + - ][ + - ]: 1062 : _queue[_queue_head++]=m;
482 [ + - ][ + - ]: 1062 : _reached->set(m,true);
483 [ + - ][ + - ]: 1062 : _pred->set(m,e);
484 [ + - ][ + - ]: 1062 : _dist->set(m,_curr_dist);
485 : : }
486 : 1310 : return n;
487 : : }
488 : :
489 : : ///Processes the next node.
490 : :
491 : : ///Processes the next node and checks if the given target node
492 : : ///is reached. If the target node is reachable from the processed
493 : : ///node, then the \c reach parameter will be set to \c true.
494 : : ///
495 : : ///\param target The target node.
496 : : ///\retval reach Indicates if the target node is reached.
497 : : ///It should be initially \c false.
498 : : ///
499 : : ///\return The processed node.
500 : : ///
501 : : ///\pre The queue must not be empty.
502 : : Node processNextNode(Node target, bool& reach)
503 : : {
504 : : if(_queue_tail==_queue_next_dist) {
505 : : _curr_dist++;
506 : : _queue_next_dist=_queue_head;
507 : : }
508 : : Node n=_queue[_queue_tail++];
509 : : _processed->set(n,true);
510 : : Node m;
511 : : for(OutArcIt e(*G,n);e!=INVALID;++e)
512 : : if(!(*_reached)[m=G->target(e)]) {
513 : : _queue[_queue_head++]=m;
514 : : _reached->set(m,true);
515 : : _pred->set(m,e);
516 : : _dist->set(m,_curr_dist);
517 : : reach = reach || (target == m);
518 : : }
519 : : return n;
520 : : }
521 : :
522 : : ///Processes the next node.
523 : :
524 : : ///Processes the next node and checks if at least one of reached
525 : : ///nodes has \c true value in the \c nm node map. If one node
526 : : ///with \c true value is reachable from the processed node, then the
527 : : ///\c rnode parameter will be set to the first of such nodes.
528 : : ///
529 : : ///\param nm A \c bool (or convertible) node map that indicates the
530 : : ///possible targets.
531 : : ///\retval rnode The reached target node.
532 : : ///It should be initially \c INVALID.
533 : : ///
534 : : ///\return The processed node.
535 : : ///
536 : : ///\pre The queue must not be empty.
537 : : template<class NM>
538 : : Node processNextNode(const NM& nm, Node& rnode)
539 : : {
540 : : if(_queue_tail==_queue_next_dist) {
541 : : _curr_dist++;
542 : : _queue_next_dist=_queue_head;
543 : : }
544 : : Node n=_queue[_queue_tail++];
545 : : _processed->set(n,true);
546 : : Node m;
547 : : for(OutArcIt e(*G,n);e!=INVALID;++e)
548 : : if(!(*_reached)[m=G->target(e)]) {
549 : : _queue[_queue_head++]=m;
550 : : _reached->set(m,true);
551 : : _pred->set(m,e);
552 : : _dist->set(m,_curr_dist);
553 : : if (nm[m] && rnode == INVALID) rnode = m;
554 : : }
555 : : return n;
556 : : }
557 : :
558 : : ///The next node to be processed.
559 : :
560 : : ///Returns the next node to be processed or \c INVALID if the queue
561 : : ///is empty.
562 : : Node nextNode() const
563 : : {
564 : : return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
565 : : }
566 : :
567 : : ///Returns \c false if there are nodes to be processed.
568 : :
569 : : ///Returns \c false if there are nodes to be processed
570 : : ///in the queue.
571 : 3158 : bool emptyQueue() const { return _queue_tail==_queue_head; }
572 : :
573 : : ///Returns the number of the nodes to be processed.
574 : :
575 : : ///Returns the number of the nodes to be processed
576 : : ///in the queue.
577 : : int queueSize() const { return _queue_head-_queue_tail; }
578 : :
579 : : ///Executes the algorithm.
580 : :
581 : : ///Executes the algorithm.
582 : : ///
583 : : ///This method runs the %BFS algorithm from the root node(s)
584 : : ///in order to compute the shortest path to each node.
585 : : ///
586 : : ///The algorithm computes
587 : : ///- the shortest path tree (forest),
588 : : ///- the distance of each node from the root(s).
589 : : ///
590 : : ///\pre init() must be called and at least one root node should be
591 : : ///added with addSource() before using this function.
592 : : ///
593 : : ///\note <tt>b.start()</tt> is just a shortcut of the following code.
594 : : ///\code
595 : : /// while ( !b.emptyQueue() ) {
596 : : /// b.processNextNode();
597 : : /// }
598 : : ///\endcode
599 : : void start()
600 : : {
601 : : while ( !emptyQueue() ) processNextNode();
602 : : }
603 : :
604 : : ///Executes the algorithm until the given target node is reached.
605 : :
606 : : ///Executes the algorithm until the given target node is reached.
607 : : ///
608 : : ///This method runs the %BFS algorithm from the root node(s)
609 : : ///in order to compute the shortest path to \c t.
610 : : ///
611 : : ///The algorithm computes
612 : : ///- the shortest path to \c t,
613 : : ///- the distance of \c t from the root(s).
614 : : ///
615 : : ///\pre init() must be called and at least one root node should be
616 : : ///added with addSource() before using this function.
617 : : ///
618 : : ///\note <tt>b.start(t)</tt> is just a shortcut of the following code.
619 : : ///\code
620 : : /// bool reach = false;
621 : : /// while ( !b.emptyQueue() && !reach ) {
622 : : /// b.processNextNode(t, reach);
623 : : /// }
624 : : ///\endcode
625 : : void start(Node t)
626 : : {
627 : : bool reach = false;
628 : : while ( !emptyQueue() && !reach ) processNextNode(t, reach);
629 : : }
630 : :
631 : : ///Executes the algorithm until a condition is met.
632 : :
633 : : ///Executes the algorithm until a condition is met.
634 : : ///
635 : : ///This method runs the %BFS algorithm from the root node(s) in
636 : : ///order to compute the shortest path to a node \c v with
637 : : /// <tt>nm[v]</tt> true, if such a node can be found.
638 : : ///
639 : : ///\param nm A \c bool (or convertible) node map. The algorithm
640 : : ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
641 : : ///
642 : : ///\return The reached node \c v with <tt>nm[v]</tt> true or
643 : : ///\c INVALID if no such node was found.
644 : : ///
645 : : ///\pre init() must be called and at least one root node should be
646 : : ///added with addSource() before using this function.
647 : : ///
648 : : ///\note <tt>b.start(nm)</tt> is just a shortcut of the following code.
649 : : ///\code
650 : : /// Node rnode = INVALID;
651 : : /// while ( !b.emptyQueue() && rnode == INVALID ) {
652 : : /// b.processNextNode(nm, rnode);
653 : : /// }
654 : : /// return rnode;
655 : : ///\endcode
656 : : template<class NodeBoolMap>
657 : : Node start(const NodeBoolMap &nm)
658 : : {
659 : : Node rnode = INVALID;
660 : : while ( !emptyQueue() && rnode == INVALID ) {
661 : : processNextNode(nm, rnode);
662 : : }
663 : : return rnode;
664 : : }
665 : :
666 : : ///Runs the algorithm from the given source node.
667 : :
668 : : ///This method runs the %BFS algorithm from node \c s
669 : : ///in order to compute the shortest path to each node.
670 : : ///
671 : : ///The algorithm computes
672 : : ///- the shortest path tree,
673 : : ///- the distance of each node from the root.
674 : : ///
675 : : ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
676 : : ///\code
677 : : /// b.init();
678 : : /// b.addSource(s);
679 : : /// b.start();
680 : : ///\endcode
681 : : void run(Node s) {
682 : : init();
683 : : addSource(s);
684 : : start();
685 : : }
686 : :
687 : : ///Finds the shortest path between \c s and \c t.
688 : :
689 : : ///This method runs the %BFS algorithm from node \c s
690 : : ///in order to compute the shortest path to node \c t
691 : : ///(it stops searching when \c t is processed).
692 : : ///
693 : : ///\return \c true if \c t is reachable form \c s.
694 : : ///
695 : : ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
696 : : ///shortcut of the following code.
697 : : ///\code
698 : : /// b.init();
699 : : /// b.addSource(s);
700 : : /// b.start(t);
701 : : ///\endcode
702 : : bool run(Node s,Node t) {
703 : : init();
704 : : addSource(s);
705 : : start(t);
706 : : return reached(t);
707 : : }
708 : :
709 : : ///Runs the algorithm to visit all nodes in the digraph.
710 : :
711 : : ///This method runs the %BFS algorithm in order to visit all nodes
712 : : ///in the digraph.
713 : : ///
714 : : ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
715 : : ///\code
716 : : /// b.init();
717 : : /// for (NodeIt n(gr); n != INVALID; ++n) {
718 : : /// if (!b.reached(n)) {
719 : : /// b.addSource(n);
720 : : /// b.start();
721 : : /// }
722 : : /// }
723 : : ///\endcode
724 : : void run() {
725 : : init();
726 : : for (NodeIt n(*G); n != INVALID; ++n) {
727 : : if (!reached(n)) {
728 : : addSource(n);
729 : : start();
730 : : }
731 : : }
732 : : }
733 : :
734 : : ///@}
735 : :
736 : : ///\name Query Functions
737 : : ///The results of the BFS algorithm can be obtained using these
738 : : ///functions.\n
739 : : ///Either \ref run(Node) "run()" or \ref start() should be called
740 : : ///before using them.
741 : :
742 : : ///@{
743 : :
744 : : ///The shortest path to the given node.
745 : :
746 : : ///Returns the shortest path to the given node from the root(s).
747 : : ///
748 : : ///\warning \c t should be reached from the root(s).
749 : : ///
750 : : ///\pre Either \ref run(Node) "run()" or \ref init()
751 : : ///must be called before using this function.
752 : : Path path(Node t) const { return Path(*G, *_pred, t); }
753 : :
754 : : ///The distance of the given node from the root(s).
755 : :
756 : : ///Returns the distance of the given node from the root(s).
757 : : ///
758 : : ///\warning If node \c v is not reached from the root(s), then
759 : : ///the return value of this function is undefined.
760 : : ///
761 : : ///\pre Either \ref run(Node) "run()" or \ref init()
762 : : ///must be called before using this function.
763 : 948 : int dist(Node v) const { return (*_dist)[v]; }
764 : :
765 : : ///\brief Returns the 'previous arc' of the shortest path tree for
766 : : ///the given node.
767 : : ///
768 : : ///This function returns the 'previous arc' of the shortest path
769 : : ///tree for the node \c v, i.e. it returns the last arc of a
770 : : ///shortest path from a root to \c v. It is \c INVALID if \c v
771 : : ///is not reached from the root(s) or if \c v is a root.
772 : : ///
773 : : ///The shortest path tree used here is equal to the shortest path
774 : : ///tree used in \ref predNode() and \ref predMap().
775 : : ///
776 : : ///\pre Either \ref run(Node) "run()" or \ref init()
777 : : ///must be called before using this function.
778 : : Arc predArc(Node v) const { return (*_pred)[v];}
779 : :
780 : : ///\brief Returns the 'previous node' of the shortest path tree for
781 : : ///the given node.
782 : : ///
783 : : ///This function returns the 'previous node' of the shortest path
784 : : ///tree for the node \c v, i.e. it returns the last but one node
785 : : ///of a shortest path from a root to \c v. It is \c INVALID
786 : : ///if \c v is not reached from the root(s) or if \c v is a root.
787 : : ///
788 : : ///The shortest path tree used here is equal to the shortest path
789 : : ///tree used in \ref predArc() and \ref predMap().
790 : : ///
791 : : ///\pre Either \ref run(Node) "run()" or \ref init()
792 : : ///must be called before using this function.
793 : : Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
794 : : G->source((*_pred)[v]); }
795 : :
796 : : ///\brief Returns a const reference to the node map that stores the
797 : : /// distances of the nodes.
798 : : ///
799 : : ///Returns a const reference to the node map that stores the distances
800 : : ///of the nodes calculated by the algorithm.
801 : : ///
802 : : ///\pre Either \ref run(Node) "run()" or \ref init()
803 : : ///must be called before using this function.
804 : : const DistMap &distMap() const { return *_dist;}
805 : :
806 : : ///\brief Returns a const reference to the node map that stores the
807 : : ///predecessor arcs.
808 : : ///
809 : : ///Returns a const reference to the node map that stores the predecessor
810 : : ///arcs, which form the shortest path tree (forest).
811 : : ///
812 : : ///\pre Either \ref run(Node) "run()" or \ref init()
813 : : ///must be called before using this function.
814 : : const PredMap &predMap() const { return *_pred;}
815 : :
816 : : ///Checks if the given node is reached from the root(s).
817 : :
818 : : ///Returns \c true if \c v is reached from the root(s).
819 : : ///
820 : : ///\pre Either \ref run(Node) "run()" or \ref init()
821 : : ///must be called before using this function.
822 : : bool reached(Node v) const { return (*_reached)[v]; }
823 : :
824 : : ///@}
825 : : };
826 : :
827 : : ///Default traits class of bfs() function.
828 : :
829 : : ///Default traits class of bfs() function.
830 : : ///\tparam GR Digraph type.
831 : : template<class GR>
832 : : struct BfsWizardDefaultTraits
833 : : {
834 : : ///The type of the digraph the algorithm runs on.
835 : : typedef GR Digraph;
836 : :
837 : : ///\brief The type of the map that stores the predecessor
838 : : ///arcs of the shortest paths.
839 : : ///
840 : : ///The type of the map that stores the predecessor
841 : : ///arcs of the shortest paths.
842 : : ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
843 : : typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
844 : : ///Instantiates a PredMap.
845 : :
846 : : ///This function instantiates a PredMap.
847 : : ///\param g is the digraph, to which we would like to define the
848 : : ///PredMap.
849 : : static PredMap *createPredMap(const Digraph &g)
850 : : {
851 : : return new PredMap(g);
852 : : }
853 : :
854 : : ///The type of the map that indicates which nodes are processed.
855 : :
856 : : ///The type of the map that indicates which nodes are processed.
857 : : ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
858 : : ///By default, it is a NullMap.
859 : : typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
860 : : ///Instantiates a ProcessedMap.
861 : :
862 : : ///This function instantiates a ProcessedMap.
863 : : ///\param g is the digraph, to which
864 : : ///we would like to define the ProcessedMap.
865 : : #ifdef DOXYGEN
866 : : static ProcessedMap *createProcessedMap(const Digraph &g)
867 : : #else
868 : : static ProcessedMap *createProcessedMap(const Digraph &)
869 : : #endif
870 : : {
871 : : return new ProcessedMap();
872 : : }
873 : :
874 : : ///The type of the map that indicates which nodes are reached.
875 : :
876 : : ///The type of the map that indicates which nodes are reached.
877 : : ///It must conform to
878 : : ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
879 : : typedef typename Digraph::template NodeMap<bool> ReachedMap;
880 : : ///Instantiates a ReachedMap.
881 : :
882 : : ///This function instantiates a ReachedMap.
883 : : ///\param g is the digraph, to which
884 : : ///we would like to define the ReachedMap.
885 : : static ReachedMap *createReachedMap(const Digraph &g)
886 : : {
887 : : return new ReachedMap(g);
888 : : }
889 : :
890 : : ///The type of the map that stores the distances of the nodes.
891 : :
892 : : ///The type of the map that stores the distances of the nodes.
893 : : ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
894 : : typedef typename Digraph::template NodeMap<int> DistMap;
895 : : ///Instantiates a DistMap.
896 : :
897 : : ///This function instantiates a DistMap.
898 : : ///\param g is the digraph, to which we would like to define
899 : : ///the DistMap
900 : : static DistMap *createDistMap(const Digraph &g)
901 : : {
902 : : return new DistMap(g);
903 : : }
904 : :
905 : : ///The type of the shortest paths.
906 : :
907 : : ///The type of the shortest paths.
908 : : ///It must conform to the \ref concepts::Path "Path" concept.
909 : : typedef lemon::Path<Digraph> Path;
910 : : };
911 : :
912 : : /// Default traits class used by BfsWizard
913 : :
914 : : /// Default traits class used by BfsWizard.
915 : : /// \tparam GR The type of the digraph.
916 : : template<class GR>
917 : : class BfsWizardBase : public BfsWizardDefaultTraits<GR>
918 : : {
919 : :
920 : : typedef BfsWizardDefaultTraits<GR> Base;
921 : : protected:
922 : : //The type of the nodes in the digraph.
923 : : typedef typename Base::Digraph::Node Node;
924 : :
925 : : //Pointer to the digraph the algorithm runs on.
926 : : void *_g;
927 : : //Pointer to the map of reached nodes.
928 : : void *_reached;
929 : : //Pointer to the map of processed nodes.
930 : : void *_processed;
931 : : //Pointer to the map of predecessors arcs.
932 : : void *_pred;
933 : : //Pointer to the map of distances.
934 : : void *_dist;
935 : : //Pointer to the shortest path to the target node.
936 : : void *_path;
937 : : //Pointer to the distance of the target node.
938 : : int *_di;
939 : :
940 : : public:
941 : : /// Constructor.
942 : :
943 : : /// This constructor does not require parameters, it initiates
944 : : /// all of the attributes to \c 0.
945 : : BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
946 : : _dist(0), _path(0), _di(0) {}
947 : :
948 : : /// Constructor.
949 : :
950 : : /// This constructor requires one parameter,
951 : : /// others are initiated to \c 0.
952 : : /// \param g The digraph the algorithm runs on.
953 : : BfsWizardBase(const GR &g) :
954 : : _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
955 : : _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
956 : :
957 : : };
958 : :
959 : : /// Auxiliary class for the function-type interface of BFS algorithm.
960 : :
961 : : /// This auxiliary class is created to implement the
962 : : /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
963 : : /// It does not have own \ref run(Node) "run()" method, it uses the
964 : : /// functions and features of the plain \ref Bfs.
965 : : ///
966 : : /// This class should only be used through the \ref bfs() function,
967 : : /// which makes it easier to use the algorithm.
968 : : ///
969 : : /// \tparam TR The traits class that defines various types used by the
970 : : /// algorithm.
971 : : template<class TR>
972 : : class BfsWizard : public TR
973 : : {
974 : : typedef TR Base;
975 : :
976 : : typedef typename TR::Digraph Digraph;
977 : :
978 : : typedef typename Digraph::Node Node;
979 : : typedef typename Digraph::NodeIt NodeIt;
980 : : typedef typename Digraph::Arc Arc;
981 : : typedef typename Digraph::OutArcIt OutArcIt;
982 : :
983 : : typedef typename TR::PredMap PredMap;
984 : : typedef typename TR::DistMap DistMap;
985 : : typedef typename TR::ReachedMap ReachedMap;
986 : : typedef typename TR::ProcessedMap ProcessedMap;
987 : : typedef typename TR::Path Path;
988 : :
989 : : public:
990 : :
991 : : /// Constructor.
992 : : BfsWizard() : TR() {}
993 : :
994 : : /// Constructor that requires parameters.
995 : :
996 : : /// Constructor that requires parameters.
997 : : /// These parameters will be the default values for the traits class.
998 : : /// \param g The digraph the algorithm runs on.
999 : : BfsWizard(const Digraph &g) :
1000 : : TR(g) {}
1001 : :
1002 : : ///Copy constructor
1003 : : BfsWizard(const TR &b) : TR(b) {}
1004 : :
1005 : : ~BfsWizard() {}
1006 : :
1007 : : ///Runs BFS algorithm from the given source node.
1008 : :
1009 : : ///This method runs BFS algorithm from node \c s
1010 : : ///in order to compute the shortest path to each node.
1011 : : void run(Node s)
1012 : : {
1013 : : Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
1014 : : if (Base::_pred)
1015 : : alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1016 : : if (Base::_dist)
1017 : : alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1018 : : if (Base::_reached)
1019 : : alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
1020 : : if (Base::_processed)
1021 : : alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1022 : : if (s!=INVALID)
1023 : : alg.run(s);
1024 : : else
1025 : : alg.run();
1026 : : }
1027 : :
1028 : : ///Finds the shortest path between \c s and \c t.
1029 : :
1030 : : ///This method runs BFS algorithm from node \c s
1031 : : ///in order to compute the shortest path to node \c t
1032 : : ///(it stops searching when \c t is processed).
1033 : : ///
1034 : : ///\return \c true if \c t is reachable form \c s.
1035 : : bool run(Node s, Node t)
1036 : : {
1037 : : Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
1038 : : if (Base::_pred)
1039 : : alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1040 : : if (Base::_dist)
1041 : : alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1042 : : if (Base::_reached)
1043 : : alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
1044 : : if (Base::_processed)
1045 : : alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1046 : : alg.run(s,t);
1047 : : if (Base::_path)
1048 : : *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
1049 : : if (Base::_di)
1050 : : *Base::_di = alg.dist(t);
1051 : : return alg.reached(t);
1052 : : }
1053 : :
1054 : : ///Runs BFS algorithm to visit all nodes in the digraph.
1055 : :
1056 : : ///This method runs BFS algorithm in order to visit all nodes
1057 : : ///in the digraph.
1058 : : void run()
1059 : : {
1060 : : run(INVALID);
1061 : : }
1062 : :
1063 : : template<class T>
1064 : : struct SetPredMapBase : public Base {
1065 : : typedef T PredMap;
1066 : : static PredMap *createPredMap(const Digraph &) { return 0; };
1067 : : SetPredMapBase(const TR &b) : TR(b) {}
1068 : : };
1069 : :
1070 : : ///\brief \ref named-templ-param "Named parameter" for setting
1071 : : ///the predecessor map.
1072 : : ///
1073 : : ///\ref named-templ-param "Named parameter" function for setting
1074 : : ///the map that stores the predecessor arcs of the nodes.
1075 : : template<class T>
1076 : : BfsWizard<SetPredMapBase<T> > predMap(const T &t)
1077 : : {
1078 : : Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1079 : : return BfsWizard<SetPredMapBase<T> >(*this);
1080 : : }
1081 : :
1082 : : template<class T>
1083 : : struct SetReachedMapBase : public Base {
1084 : : typedef T ReachedMap;
1085 : : static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1086 : : SetReachedMapBase(const TR &b) : TR(b) {}
1087 : : };
1088 : :
1089 : : ///\brief \ref named-templ-param "Named parameter" for setting
1090 : : ///the reached map.
1091 : : ///
1092 : : ///\ref named-templ-param "Named parameter" function for setting
1093 : : ///the map that indicates which nodes are reached.
1094 : : template<class T>
1095 : : BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
1096 : : {
1097 : : Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
1098 : : return BfsWizard<SetReachedMapBase<T> >(*this);
1099 : : }
1100 : :
1101 : : template<class T>
1102 : : struct SetDistMapBase : public Base {
1103 : : typedef T DistMap;
1104 : : static DistMap *createDistMap(const Digraph &) { return 0; };
1105 : : SetDistMapBase(const TR &b) : TR(b) {}
1106 : : };
1107 : :
1108 : : ///\brief \ref named-templ-param "Named parameter" for setting
1109 : : ///the distance map.
1110 : : ///
1111 : : ///\ref named-templ-param "Named parameter" function for setting
1112 : : ///the map that stores the distances of the nodes calculated
1113 : : ///by the algorithm.
1114 : : template<class T>
1115 : : BfsWizard<SetDistMapBase<T> > distMap(const T &t)
1116 : : {
1117 : : Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1118 : : return BfsWizard<SetDistMapBase<T> >(*this);
1119 : : }
1120 : :
1121 : : template<class T>
1122 : : struct SetProcessedMapBase : public Base {
1123 : : typedef T ProcessedMap;
1124 : : static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1125 : : SetProcessedMapBase(const TR &b) : TR(b) {}
1126 : : };
1127 : :
1128 : : ///\brief \ref named-func-param "Named parameter" for setting
1129 : : ///the processed map.
1130 : : ///
1131 : : ///\ref named-templ-param "Named parameter" function for setting
1132 : : ///the map that indicates which nodes are processed.
1133 : : template<class T>
1134 : : BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1135 : : {
1136 : : Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
1137 : : return BfsWizard<SetProcessedMapBase<T> >(*this);
1138 : : }
1139 : :
1140 : : template<class T>
1141 : : struct SetPathBase : public Base {
1142 : : typedef T Path;
1143 : : SetPathBase(const TR &b) : TR(b) {}
1144 : : };
1145 : : ///\brief \ref named-func-param "Named parameter"
1146 : : ///for getting the shortest path to the target node.
1147 : : ///
1148 : : ///\ref named-func-param "Named parameter"
1149 : : ///for getting the shortest path to the target node.
1150 : : template<class T>
1151 : : BfsWizard<SetPathBase<T> > path(const T &t)
1152 : : {
1153 : : Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
1154 : : return BfsWizard<SetPathBase<T> >(*this);
1155 : : }
1156 : :
1157 : : ///\brief \ref named-func-param "Named parameter"
1158 : : ///for getting the distance of the target node.
1159 : : ///
1160 : : ///\ref named-func-param "Named parameter"
1161 : : ///for getting the distance of the target node.
1162 : : BfsWizard dist(const int &d)
1163 : : {
1164 : : Base::_di=const_cast<int*>(&d);
1165 : : return *this;
1166 : : }
1167 : :
1168 : : };
1169 : :
1170 : : ///Function-type interface for BFS algorithm.
1171 : :
1172 : : /// \ingroup search
1173 : : ///Function-type interface for BFS algorithm.
1174 : : ///
1175 : : ///This function also has several \ref named-func-param "named parameters",
1176 : : ///they are declared as the members of class \ref BfsWizard.
1177 : : ///The following examples show how to use these parameters.
1178 : : ///\code
1179 : : /// // Compute shortest path from node s to each node
1180 : : /// bfs(g).predMap(preds).distMap(dists).run(s);
1181 : : ///
1182 : : /// // Compute shortest path from s to t
1183 : : /// bool reached = bfs(g).path(p).dist(d).run(s,t);
1184 : : ///\endcode
1185 : : ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
1186 : : ///to the end of the parameter list.
1187 : : ///\sa BfsWizard
1188 : : ///\sa Bfs
1189 : : template<class GR>
1190 : : BfsWizard<BfsWizardBase<GR> >
1191 : : bfs(const GR &digraph)
1192 : : {
1193 : : return BfsWizard<BfsWizardBase<GR> >(digraph);
1194 : : }
1195 : :
1196 : : #ifdef DOXYGEN
1197 : : /// \brief Visitor class for BFS.
1198 : : ///
1199 : : /// This class defines the interface of the BfsVisit events, and
1200 : : /// it could be the base of a real visitor class.
1201 : : template <typename GR>
1202 : : struct BfsVisitor {
1203 : : typedef GR Digraph;
1204 : : typedef typename Digraph::Arc Arc;
1205 : : typedef typename Digraph::Node Node;
1206 : : /// \brief Called for the source node(s) of the BFS.
1207 : : ///
1208 : : /// This function is called for the source node(s) of the BFS.
1209 : : void start(const Node& node) {}
1210 : : /// \brief Called when a node is reached first time.
1211 : : ///
1212 : : /// This function is called when a node is reached first time.
1213 : : void reach(const Node& node) {}
1214 : : /// \brief Called when a node is processed.
1215 : : ///
1216 : : /// This function is called when a node is processed.
1217 : : void process(const Node& node) {}
1218 : : /// \brief Called when an arc reaches a new node.
1219 : : ///
1220 : : /// This function is called when the BFS finds an arc whose target node
1221 : : /// is not reached yet.
1222 : : void discover(const Arc& arc) {}
1223 : : /// \brief Called when an arc is examined but its target node is
1224 : : /// already discovered.
1225 : : ///
1226 : : /// This function is called when an arc is examined but its target node is
1227 : : /// already discovered.
1228 : : void examine(const Arc& arc) {}
1229 : : };
1230 : : #else
1231 : : template <typename GR>
1232 : : struct BfsVisitor {
1233 : : typedef GR Digraph;
1234 : : typedef typename Digraph::Arc Arc;
1235 : : typedef typename Digraph::Node Node;
1236 : : void start(const Node&) {}
1237 : : void reach(const Node&) {}
1238 : : void process(const Node&) {}
1239 : : void discover(const Arc&) {}
1240 : : void examine(const Arc&) {}
1241 : :
1242 : : template <typename _Visitor>
1243 : : struct Constraints {
1244 : : void constraints() {
1245 : : Arc arc;
1246 : : Node node;
1247 : : visitor.start(node);
1248 : : visitor.reach(node);
1249 : : visitor.process(node);
1250 : : visitor.discover(arc);
1251 : : visitor.examine(arc);
1252 : : }
1253 : : _Visitor& visitor;
1254 : : };
1255 : : };
1256 : : #endif
1257 : :
1258 : : /// \brief Default traits class of BfsVisit class.
1259 : : ///
1260 : : /// Default traits class of BfsVisit class.
1261 : : /// \tparam GR The type of the digraph the algorithm runs on.
1262 : : template<class GR>
1263 : : struct BfsVisitDefaultTraits {
1264 : :
1265 : : /// \brief The type of the digraph the algorithm runs on.
1266 : : typedef GR Digraph;
1267 : :
1268 : : /// \brief The type of the map that indicates which nodes are reached.
1269 : : ///
1270 : : /// The type of the map that indicates which nodes are reached.
1271 : : /// It must conform to
1272 : : ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1273 : : typedef typename Digraph::template NodeMap<bool> ReachedMap;
1274 : :
1275 : : /// \brief Instantiates a ReachedMap.
1276 : : ///
1277 : : /// This function instantiates a ReachedMap.
1278 : : /// \param digraph is the digraph, to which
1279 : : /// we would like to define the ReachedMap.
1280 : : static ReachedMap *createReachedMap(const Digraph &digraph) {
1281 : : return new ReachedMap(digraph);
1282 : : }
1283 : :
1284 : : };
1285 : :
1286 : : /// \ingroup search
1287 : : ///
1288 : : /// \brief BFS algorithm class with visitor interface.
1289 : : ///
1290 : : /// This class provides an efficient implementation of the BFS algorithm
1291 : : /// with visitor interface.
1292 : : ///
1293 : : /// The BfsVisit class provides an alternative interface to the Bfs
1294 : : /// class. It works with callback mechanism, the BfsVisit object calls
1295 : : /// the member functions of the \c Visitor class on every BFS event.
1296 : : ///
1297 : : /// This interface of the BFS algorithm should be used in special cases
1298 : : /// when extra actions have to be performed in connection with certain
1299 : : /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()
1300 : : /// instead.
1301 : : ///
1302 : : /// \tparam GR The type of the digraph the algorithm runs on.
1303 : : /// The default type is \ref ListDigraph.
1304 : : /// The value of GR is not used directly by \ref BfsVisit,
1305 : : /// it is only passed to \ref BfsVisitDefaultTraits.
1306 : : /// \tparam VS The Visitor type that is used by the algorithm.
1307 : : /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
1308 : : /// does not observe the BFS events. If you want to observe the BFS
1309 : : /// events, you should implement your own visitor class.
1310 : : /// \tparam TR The traits class that defines various types used by the
1311 : : /// algorithm. By default, it is \ref BfsVisitDefaultTraits
1312 : : /// "BfsVisitDefaultTraits<GR>".
1313 : : /// In most cases, this parameter should not be set directly,
1314 : : /// consider to use the named template parameters instead.
1315 : : #ifdef DOXYGEN
1316 : : template <typename GR, typename VS, typename TR>
1317 : : #else
1318 : : template <typename GR = ListDigraph,
1319 : : typename VS = BfsVisitor<GR>,
1320 : : typename TR = BfsVisitDefaultTraits<GR> >
1321 : : #endif
1322 : : class BfsVisit {
1323 : : public:
1324 : :
1325 : : ///The traits class.
1326 : : typedef TR Traits;
1327 : :
1328 : : ///The type of the digraph the algorithm runs on.
1329 : : typedef typename Traits::Digraph Digraph;
1330 : :
1331 : : ///The visitor type used by the algorithm.
1332 : : typedef VS Visitor;
1333 : :
1334 : : ///The type of the map that indicates which nodes are reached.
1335 : : typedef typename Traits::ReachedMap ReachedMap;
1336 : :
1337 : : private:
1338 : :
1339 : : typedef typename Digraph::Node Node;
1340 : : typedef typename Digraph::NodeIt NodeIt;
1341 : : typedef typename Digraph::Arc Arc;
1342 : : typedef typename Digraph::OutArcIt OutArcIt;
1343 : :
1344 : : //Pointer to the underlying digraph.
1345 : : const Digraph *_digraph;
1346 : : //Pointer to the visitor object.
1347 : : Visitor *_visitor;
1348 : : //Pointer to the map of reached status of the nodes.
1349 : : ReachedMap *_reached;
1350 : : //Indicates if _reached is locally allocated (true) or not.
1351 : : bool local_reached;
1352 : :
1353 : : std::vector<typename Digraph::Node> _list;
1354 : : int _list_front, _list_back;
1355 : :
1356 : : //Creates the maps if necessary.
1357 : : void create_maps() {
1358 : : if(!_reached) {
1359 : : local_reached = true;
1360 : : _reached = Traits::createReachedMap(*_digraph);
1361 : : }
1362 : : }
1363 : :
1364 : : protected:
1365 : :
1366 : : BfsVisit() {}
1367 : :
1368 : : public:
1369 : :
1370 : : typedef BfsVisit Create;
1371 : :
1372 : : /// \name Named Template Parameters
1373 : :
1374 : : ///@{
1375 : : template <class T>
1376 : : struct SetReachedMapTraits : public Traits {
1377 : : typedef T ReachedMap;
1378 : : static ReachedMap *createReachedMap(const Digraph &digraph) {
1379 : : LEMON_ASSERT(false, "ReachedMap is not initialized");
1380 : : return 0; // ignore warnings
1381 : : }
1382 : : };
1383 : : /// \brief \ref named-templ-param "Named parameter" for setting
1384 : : /// ReachedMap type.
1385 : : ///
1386 : : /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
1387 : : template <class T>
1388 : : struct SetReachedMap : public BfsVisit< Digraph, Visitor,
1389 : : SetReachedMapTraits<T> > {
1390 : : typedef BfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
1391 : : };
1392 : : ///@}
1393 : :
1394 : : public:
1395 : :
1396 : : /// \brief Constructor.
1397 : : ///
1398 : : /// Constructor.
1399 : : ///
1400 : : /// \param digraph The digraph the algorithm runs on.
1401 : : /// \param visitor The visitor object of the algorithm.
1402 : : BfsVisit(const Digraph& digraph, Visitor& visitor)
1403 : : : _digraph(&digraph), _visitor(&visitor),
1404 : : _reached(0), local_reached(false) {}
1405 : :
1406 : : /// \brief Destructor.
1407 : : ~BfsVisit() {
1408 : : if(local_reached) delete _reached;
1409 : : }
1410 : :
1411 : : /// \brief Sets the map that indicates which nodes are reached.
1412 : : ///
1413 : : /// Sets the map that indicates which nodes are reached.
1414 : : /// If you don't use this function before calling \ref run(Node) "run()"
1415 : : /// or \ref init(), an instance will be allocated automatically.
1416 : : /// The destructor deallocates this automatically allocated map,
1417 : : /// of course.
1418 : : /// \return <tt> (*this) </tt>
1419 : : BfsVisit &reachedMap(ReachedMap &m) {
1420 : : if(local_reached) {
1421 : : delete _reached;
1422 : : local_reached = false;
1423 : : }
1424 : : _reached = &m;
1425 : : return *this;
1426 : : }
1427 : :
1428 : : public:
1429 : :
1430 : : /// \name Execution Control
1431 : : /// The simplest way to execute the BFS algorithm is to use one of the
1432 : : /// member functions called \ref run(Node) "run()".\n
1433 : : /// If you need better control on the execution, you have to call
1434 : : /// \ref init() first, then you can add several source nodes with
1435 : : /// \ref addSource(). Finally the actual path computation can be
1436 : : /// performed with one of the \ref start() functions.
1437 : :
1438 : : /// @{
1439 : :
1440 : : /// \brief Initializes the internal data structures.
1441 : : ///
1442 : : /// Initializes the internal data structures.
1443 : : void init() {
1444 : : create_maps();
1445 : : _list.resize(countNodes(*_digraph));
1446 : : _list_front = _list_back = -1;
1447 : : for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
1448 : : _reached->set(u, false);
1449 : : }
1450 : : }
1451 : :
1452 : : /// \brief Adds a new source node.
1453 : : ///
1454 : : /// Adds a new source node to the set of nodes to be processed.
1455 : : void addSource(Node s) {
1456 : : if(!(*_reached)[s]) {
1457 : : _reached->set(s,true);
1458 : : _visitor->start(s);
1459 : : _visitor->reach(s);
1460 : : _list[++_list_back] = s;
1461 : : }
1462 : : }
1463 : :
1464 : : /// \brief Processes the next node.
1465 : : ///
1466 : : /// Processes the next node.
1467 : : ///
1468 : : /// \return The processed node.
1469 : : ///
1470 : : /// \pre The queue must not be empty.
1471 : : Node processNextNode() {
1472 : : Node n = _list[++_list_front];
1473 : : _visitor->process(n);
1474 : : Arc e;
1475 : : for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
1476 : : Node m = _digraph->target(e);
1477 : : if (!(*_reached)[m]) {
1478 : : _visitor->discover(e);
1479 : : _visitor->reach(m);
1480 : : _reached->set(m, true);
1481 : : _list[++_list_back] = m;
1482 : : } else {
1483 : : _visitor->examine(e);
1484 : : }
1485 : : }
1486 : : return n;
1487 : : }
1488 : :
1489 : : /// \brief Processes the next node.
1490 : : ///
1491 : : /// Processes the next node and checks if the given target node
1492 : : /// is reached. If the target node is reachable from the processed
1493 : : /// node, then the \c reach parameter will be set to \c true.
1494 : : ///
1495 : : /// \param target The target node.
1496 : : /// \retval reach Indicates if the target node is reached.
1497 : : /// It should be initially \c false.
1498 : : ///
1499 : : /// \return The processed node.
1500 : : ///
1501 : : /// \pre The queue must not be empty.
1502 : : Node processNextNode(Node target, bool& reach) {
1503 : : Node n = _list[++_list_front];
1504 : : _visitor->process(n);
1505 : : Arc e;
1506 : : for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
1507 : : Node m = _digraph->target(e);
1508 : : if (!(*_reached)[m]) {
1509 : : _visitor->discover(e);
1510 : : _visitor->reach(m);
1511 : : _reached->set(m, true);
1512 : : _list[++_list_back] = m;
1513 : : reach = reach || (target == m);
1514 : : } else {
1515 : : _visitor->examine(e);
1516 : : }
1517 : : }
1518 : : return n;
1519 : : }
1520 : :
1521 : : /// \brief Processes the next node.
1522 : : ///
1523 : : /// Processes the next node and checks if at least one of reached
1524 : : /// nodes has \c true value in the \c nm node map. If one node
1525 : : /// with \c true value is reachable from the processed node, then the
1526 : : /// \c rnode parameter will be set to the first of such nodes.
1527 : : ///
1528 : : /// \param nm A \c bool (or convertible) node map that indicates the
1529 : : /// possible targets.
1530 : : /// \retval rnode The reached target node.
1531 : : /// It should be initially \c INVALID.
1532 : : ///
1533 : : /// \return The processed node.
1534 : : ///
1535 : : /// \pre The queue must not be empty.
1536 : : template <typename NM>
1537 : : Node processNextNode(const NM& nm, Node& rnode) {
1538 : : Node n = _list[++_list_front];
1539 : : _visitor->process(n);
1540 : : Arc e;
1541 : : for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
1542 : : Node m = _digraph->target(e);
1543 : : if (!(*_reached)[m]) {
1544 : : _visitor->discover(e);
1545 : : _visitor->reach(m);
1546 : : _reached->set(m, true);
1547 : : _list[++_list_back] = m;
1548 : : if (nm[m] && rnode == INVALID) rnode = m;
1549 : : } else {
1550 : : _visitor->examine(e);
1551 : : }
1552 : : }
1553 : : return n;
1554 : : }
1555 : :
1556 : : /// \brief The next node to be processed.
1557 : : ///
1558 : : /// Returns the next node to be processed or \c INVALID if the queue
1559 : : /// is empty.
1560 : : Node nextNode() const {
1561 : : return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
1562 : : }
1563 : :
1564 : : /// \brief Returns \c false if there are nodes
1565 : : /// to be processed.
1566 : : ///
1567 : : /// Returns \c false if there are nodes
1568 : : /// to be processed in the queue.
1569 : : bool emptyQueue() const { return _list_front == _list_back; }
1570 : :
1571 : : /// \brief Returns the number of the nodes to be processed.
1572 : : ///
1573 : : /// Returns the number of the nodes to be processed in the queue.
1574 : : int queueSize() const { return _list_back - _list_front; }
1575 : :
1576 : : /// \brief Executes the algorithm.
1577 : : ///
1578 : : /// Executes the algorithm.
1579 : : ///
1580 : : /// This method runs the %BFS algorithm from the root node(s)
1581 : : /// in order to compute the shortest path to each node.
1582 : : ///
1583 : : /// The algorithm computes
1584 : : /// - the shortest path tree (forest),
1585 : : /// - the distance of each node from the root(s).
1586 : : ///
1587 : : /// \pre init() must be called and at least one root node should be added
1588 : : /// with addSource() before using this function.
1589 : : ///
1590 : : /// \note <tt>b.start()</tt> is just a shortcut of the following code.
1591 : : /// \code
1592 : : /// while ( !b.emptyQueue() ) {
1593 : : /// b.processNextNode();
1594 : : /// }
1595 : : /// \endcode
1596 : : void start() {
1597 : : while ( !emptyQueue() ) processNextNode();
1598 : : }
1599 : :
1600 : : /// \brief Executes the algorithm until the given target node is reached.
1601 : : ///
1602 : : /// Executes the algorithm until the given target node is reached.
1603 : : ///
1604 : : /// This method runs the %BFS algorithm from the root node(s)
1605 : : /// in order to compute the shortest path to \c t.
1606 : : ///
1607 : : /// The algorithm computes
1608 : : /// - the shortest path to \c t,
1609 : : /// - the distance of \c t from the root(s).
1610 : : ///
1611 : : /// \pre init() must be called and at least one root node should be
1612 : : /// added with addSource() before using this function.
1613 : : ///
1614 : : /// \note <tt>b.start(t)</tt> is just a shortcut of the following code.
1615 : : /// \code
1616 : : /// bool reach = false;
1617 : : /// while ( !b.emptyQueue() && !reach ) {
1618 : : /// b.processNextNode(t, reach);
1619 : : /// }
1620 : : /// \endcode
1621 : : void start(Node t) {
1622 : : bool reach = false;
1623 : : while ( !emptyQueue() && !reach ) processNextNode(t, reach);
1624 : : }
1625 : :
1626 : : /// \brief Executes the algorithm until a condition is met.
1627 : : ///
1628 : : /// Executes the algorithm until a condition is met.
1629 : : ///
1630 : : /// This method runs the %BFS algorithm from the root node(s) in
1631 : : /// order to compute the shortest path to a node \c v with
1632 : : /// <tt>nm[v]</tt> true, if such a node can be found.
1633 : : ///
1634 : : /// \param nm must be a bool (or convertible) node map. The
1635 : : /// algorithm will stop when it reaches a node \c v with
1636 : : /// <tt>nm[v]</tt> true.
1637 : : ///
1638 : : /// \return The reached node \c v with <tt>nm[v]</tt> true or
1639 : : /// \c INVALID if no such node was found.
1640 : : ///
1641 : : /// \pre init() must be called and at least one root node should be
1642 : : /// added with addSource() before using this function.
1643 : : ///
1644 : : /// \note <tt>b.start(nm)</tt> is just a shortcut of the following code.
1645 : : /// \code
1646 : : /// Node rnode = INVALID;
1647 : : /// while ( !b.emptyQueue() && rnode == INVALID ) {
1648 : : /// b.processNextNode(nm, rnode);
1649 : : /// }
1650 : : /// return rnode;
1651 : : /// \endcode
1652 : : template <typename NM>
1653 : : Node start(const NM &nm) {
1654 : : Node rnode = INVALID;
1655 : : while ( !emptyQueue() && rnode == INVALID ) {
1656 : : processNextNode(nm, rnode);
1657 : : }
1658 : : return rnode;
1659 : : }
1660 : :
1661 : : /// \brief Runs the algorithm from the given source node.
1662 : : ///
1663 : : /// This method runs the %BFS algorithm from node \c s
1664 : : /// in order to compute the shortest path to each node.
1665 : : ///
1666 : : /// The algorithm computes
1667 : : /// - the shortest path tree,
1668 : : /// - the distance of each node from the root.
1669 : : ///
1670 : : /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
1671 : : ///\code
1672 : : /// b.init();
1673 : : /// b.addSource(s);
1674 : : /// b.start();
1675 : : ///\endcode
1676 : : void run(Node s) {
1677 : : init();
1678 : : addSource(s);
1679 : : start();
1680 : : }
1681 : :
1682 : : /// \brief Finds the shortest path between \c s and \c t.
1683 : : ///
1684 : : /// This method runs the %BFS algorithm from node \c s
1685 : : /// in order to compute the shortest path to node \c t
1686 : : /// (it stops searching when \c t is processed).
1687 : : ///
1688 : : /// \return \c true if \c t is reachable form \c s.
1689 : : ///
1690 : : /// \note Apart from the return value, <tt>b.run(s,t)</tt> is just a
1691 : : /// shortcut of the following code.
1692 : : ///\code
1693 : : /// b.init();
1694 : : /// b.addSource(s);
1695 : : /// b.start(t);
1696 : : ///\endcode
1697 : : bool run(Node s,Node t) {
1698 : : init();
1699 : : addSource(s);
1700 : : start(t);
1701 : : return reached(t);
1702 : : }
1703 : :
1704 : : /// \brief Runs the algorithm to visit all nodes in the digraph.
1705 : : ///
1706 : : /// This method runs the %BFS algorithm in order to visit all nodes
1707 : : /// in the digraph.
1708 : : ///
1709 : : /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
1710 : : ///\code
1711 : : /// b.init();
1712 : : /// for (NodeIt n(gr); n != INVALID; ++n) {
1713 : : /// if (!b.reached(n)) {
1714 : : /// b.addSource(n);
1715 : : /// b.start();
1716 : : /// }
1717 : : /// }
1718 : : ///\endcode
1719 : : void run() {
1720 : : init();
1721 : : for (NodeIt it(*_digraph); it != INVALID; ++it) {
1722 : : if (!reached(it)) {
1723 : : addSource(it);
1724 : : start();
1725 : : }
1726 : : }
1727 : : }
1728 : :
1729 : : ///@}
1730 : :
1731 : : /// \name Query Functions
1732 : : /// The results of the BFS algorithm can be obtained using these
1733 : : /// functions.\n
1734 : : /// Either \ref run(Node) "run()" or \ref start() should be called
1735 : : /// before using them.
1736 : :
1737 : : ///@{
1738 : :
1739 : : /// \brief Checks if the given node is reached from the root(s).
1740 : : ///
1741 : : /// Returns \c true if \c v is reached from the root(s).
1742 : : ///
1743 : : /// \pre Either \ref run(Node) "run()" or \ref init()
1744 : : /// must be called before using this function.
1745 : : bool reached(Node v) const { return (*_reached)[v]; }
1746 : :
1747 : : ///@}
1748 : :
1749 : : };
1750 : :
1751 : : } //END OF NAMESPACE LEMON
1752 : :
1753 : : #endif
|
