1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
24 ///\brief BFS algorithm.
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>
34 ///Default traits class of Bfs class.
36 ///Default traits class of Bfs class.
37 ///\tparam GR Digraph type.
39 struct BfsDefaultTraits
41 ///The type of the digraph the algorithm runs on.
44 ///\brief The type of the map that stores the predecessor
45 ///arcs of the shortest paths.
47 ///The type of the map that stores the predecessor
48 ///arcs of the shortest paths.
49 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
50 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
51 ///Instantiates a \ref PredMap.
53 ///This function instantiates a \ref PredMap.
54 ///\param g is the digraph, to which we would like to define the
56 ///\todo The digraph alone may be insufficient to initialize
57 static PredMap *createPredMap(const Digraph &g)
59 return new PredMap(g);
62 ///The type of the map that indicates which nodes are processed.
64 ///The type of the map that indicates which nodes are processed.
65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
66 ///By default it is a NullMap.
67 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
68 ///Instantiates a \ref ProcessedMap.
70 ///This function instantiates a \ref ProcessedMap.
71 ///\param g is the digraph, to which
72 ///we would like to define the \ref ProcessedMap
74 static ProcessedMap *createProcessedMap(const Digraph &g)
76 static ProcessedMap *createProcessedMap(const Digraph &)
79 return new ProcessedMap();
82 ///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::ReadWriteMap "ReadWriteMap" concept.
86 typedef typename Digraph::template NodeMap<bool> ReachedMap;
87 ///Instantiates a \ref ReachedMap.
89 ///This function instantiates a \ref ReachedMap.
90 ///\param g is the digraph, to which
91 ///we would like to define the \ref ReachedMap.
92 static ReachedMap *createReachedMap(const Digraph &g)
94 return new ReachedMap(g);
97 ///The type of the map that stores the distances of the nodes.
99 ///The type of the map that stores the distances of the nodes.
100 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
101 typedef typename Digraph::template NodeMap<int> DistMap;
102 ///Instantiates a \ref DistMap.
104 ///This function instantiates a \ref DistMap.
105 ///\param g is the digraph, to which we would like to define the
107 static DistMap *createDistMap(const Digraph &g)
109 return new DistMap(g);
113 ///%BFS algorithm class.
116 ///This class provides an efficient implementation of the %BFS algorithm.
118 ///There is also a \ref bfs() "function type interface" for the BFS
119 ///algorithm, which is convenient in the simplier cases and it can be
122 ///\tparam GR The type of the digraph the algorithm runs on.
123 ///The default value is \ref ListDigraph. The value of GR is not used
124 ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
125 ///\tparam TR Traits class to set various data types used by the algorithm.
126 ///The default traits class is
127 ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
128 ///See \ref BfsDefaultTraits for the documentation of
129 ///a Bfs traits class.
131 template <typename GR,
134 template <typename GR=ListDigraph,
135 typename TR=BfsDefaultTraits<GR> >
139 ///\ref Exception for uninitialized parameters.
141 ///This error represents problems in the initialization of the
142 ///parameters of the algorithm.
143 class UninitializedParameter : public lemon::UninitializedParameter {
145 virtual const char* what() const throw() {
146 return "lemon::Bfs::UninitializedParameter";
150 ///The type of the digraph the algorithm runs on.
151 typedef typename TR::Digraph Digraph;
153 ///\brief The type of the map that stores the predecessor arcs of the
155 typedef typename TR::PredMap PredMap;
156 ///The type of the map that stores the distances of the nodes.
157 typedef typename TR::DistMap DistMap;
158 ///The type of the map that indicates which nodes are reached.
159 typedef typename TR::ReachedMap ReachedMap;
160 ///The type of the map that indicates which nodes are processed.
161 typedef typename TR::ProcessedMap ProcessedMap;
162 ///The type of the paths.
163 typedef PredMapPath<Digraph, PredMap> Path;
170 typedef typename Digraph::Node Node;
171 typedef typename Digraph::NodeIt NodeIt;
172 typedef typename Digraph::Arc Arc;
173 typedef typename Digraph::OutArcIt OutArcIt;
175 //Pointer to the underlying digraph.
177 //Pointer to the map of predecessor arcs.
179 //Indicates if _pred is locally allocated (true) or not.
181 //Pointer to the map of distances.
183 //Indicates if _dist is locally allocated (true) or not.
185 //Pointer to the map of reached status of the nodes.
186 ReachedMap *_reached;
187 //Indicates if _reached is locally allocated (true) or not.
189 //Pointer to the map of processed status of the nodes.
190 ProcessedMap *_processed;
191 //Indicates if _processed is locally allocated (true) or not.
192 bool local_processed;
194 std::vector<typename Digraph::Node> _queue;
195 int _queue_head,_queue_tail,_queue_next_dist;
198 ///Creates the maps if necessary.
199 ///\todo Better memory allocation (instead of new).
204 _pred = Traits::createPredMap(*G);
208 _dist = Traits::createDistMap(*G);
211 local_reached = true;
212 _reached = Traits::createReachedMap(*G);
215 local_processed = true;
216 _processed = Traits::createProcessedMap(*G);
228 ///\name Named template parameters
233 struct SetPredMapTraits : public Traits {
235 static PredMap *createPredMap(const Digraph &)
237 throw UninitializedParameter();
240 ///\brief \ref named-templ-param "Named parameter" for setting
241 ///\ref PredMap type.
243 ///\ref named-templ-param "Named parameter" for setting
244 ///\ref PredMap type.
246 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
247 typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
251 struct SetDistMapTraits : public Traits {
253 static DistMap *createDistMap(const Digraph &)
255 throw UninitializedParameter();
258 ///\brief \ref named-templ-param "Named parameter" for setting
259 ///\ref DistMap type.
261 ///\ref named-templ-param "Named parameter" for setting
262 ///\ref DistMap type.
264 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
265 typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
269 struct SetReachedMapTraits : public Traits {
270 typedef T ReachedMap;
271 static ReachedMap *createReachedMap(const Digraph &)
273 throw UninitializedParameter();
276 ///\brief \ref named-templ-param "Named parameter" for setting
277 ///\ref ReachedMap type.
279 ///\ref named-templ-param "Named parameter" for setting
280 ///\ref ReachedMap type.
282 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
283 typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
287 struct SetProcessedMapTraits : public Traits {
288 typedef T ProcessedMap;
289 static ProcessedMap *createProcessedMap(const Digraph &)
291 throw UninitializedParameter();
294 ///\brief \ref named-templ-param "Named parameter" for setting
295 ///\ref ProcessedMap type.
297 ///\ref named-templ-param "Named parameter" for setting
298 ///\ref ProcessedMap type.
300 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
301 typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
304 struct SetStandardProcessedMapTraits : public Traits {
305 typedef typename Digraph::template NodeMap<bool> ProcessedMap;
306 static ProcessedMap *createProcessedMap(const Digraph &g)
308 return new ProcessedMap(g);
311 ///\brief \ref named-templ-param "Named parameter" for setting
312 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
314 ///\ref named-templ-param "Named parameter" for setting
315 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
316 ///If you don't set it explicitly, it will be automatically allocated.
317 struct SetStandardProcessedMap :
318 public Bfs< Digraph, SetStandardProcessedMapTraits > {
319 typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;
329 ///\param g The digraph the algorithm runs on.
330 Bfs(const Digraph &g) :
332 _pred(NULL), local_pred(false),
333 _dist(NULL), local_dist(false),
334 _reached(NULL), local_reached(false),
335 _processed(NULL), local_processed(false)
341 if(local_pred) delete _pred;
342 if(local_dist) delete _dist;
343 if(local_reached) delete _reached;
344 if(local_processed) delete _processed;
347 ///Sets the map that stores the predecessor arcs.
349 ///Sets the map that stores the predecessor arcs.
350 ///If you don't use this function before calling \ref run(),
351 ///it will allocate one. The destructor deallocates this
352 ///automatically allocated map, of course.
353 ///\return <tt> (*this) </tt>
354 Bfs &predMap(PredMap &m)
364 ///Sets the map that indicates which nodes are reached.
366 ///Sets the map that indicates which nodes are reached.
367 ///If you don't use this function before calling \ref run(),
368 ///it will allocate one. The destructor deallocates this
369 ///automatically allocated map, of course.
370 ///\return <tt> (*this) </tt>
371 Bfs &reachedMap(ReachedMap &m)
381 ///Sets the map that indicates which nodes are processed.
383 ///Sets the map that indicates which nodes are processed.
384 ///If you don't use this function before calling \ref run(),
385 ///it will allocate one. The destructor deallocates this
386 ///automatically allocated map, of course.
387 ///\return <tt> (*this) </tt>
388 Bfs &processedMap(ProcessedMap &m)
390 if(local_processed) {
392 local_processed=false;
398 ///Sets the map that stores the distances of the nodes.
400 ///Sets the map that stores the distances of the nodes calculated by
402 ///If you don't use this function before calling \ref run(),
403 ///it will allocate one. The destructor deallocates this
404 ///automatically allocated map, of course.
405 ///\return <tt> (*this) </tt>
406 Bfs &distMap(DistMap &m)
418 ///\name Execution control
419 ///The simplest way to execute the algorithm is to use
420 ///one of the member functions called \ref lemon::Bfs::run() "run()".
422 ///If you need more control on the execution, first you must call
423 ///\ref lemon::Bfs::init() "init()", then you can add several source
424 ///nodes with \ref lemon::Bfs::addSource() "addSource()".
425 ///Finally \ref lemon::Bfs::start() "start()" will perform the
426 ///actual path computation.
430 ///Initializes the internal data structures.
432 ///Initializes the internal data structures.
437 _queue.resize(countNodes(*G));
438 _queue_head=_queue_tail=0;
440 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
441 _pred->set(u,INVALID);
442 _reached->set(u,false);
443 _processed->set(u,false);
447 ///Adds a new source node.
449 ///Adds a new source node to the set of nodes to be processed.
451 void addSource(Node s)
455 _reached->set(s,true);
456 _pred->set(s,INVALID);
458 _queue[_queue_head++]=s;
459 _queue_next_dist=_queue_head;
463 ///Processes the next node.
465 ///Processes the next node.
467 ///\return The processed node.
469 ///\pre The queue must not be empty.
470 Node processNextNode()
472 if(_queue_tail==_queue_next_dist) {
474 _queue_next_dist=_queue_head;
476 Node n=_queue[_queue_tail++];
477 _processed->set(n,true);
479 for(OutArcIt e(*G,n);e!=INVALID;++e)
480 if(!(*_reached)[m=G->target(e)]) {
481 _queue[_queue_head++]=m;
482 _reached->set(m,true);
484 _dist->set(m,_curr_dist);
489 ///Processes the next node.
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.
495 ///\param target The target node.
496 ///\retval reach Indicates if the target node is reached.
497 ///It should be initially \c false.
499 ///\return The processed node.
501 ///\pre The queue must not be empty.
502 Node processNextNode(Node target, bool& reach)
504 if(_queue_tail==_queue_next_dist) {
506 _queue_next_dist=_queue_head;
508 Node n=_queue[_queue_tail++];
509 _processed->set(n,true);
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);
516 _dist->set(m,_curr_dist);
517 reach = reach || (target == m);
522 ///Processes the next node.
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.
529 ///\param nm A \c bool (or convertible) node map that indicates the
531 ///\retval rnode The reached target node.
532 ///It should be initially \c INVALID.
534 ///\return The processed node.
536 ///\pre The queue must not be empty.
538 Node processNextNode(const NM& nm, Node& rnode)
540 if(_queue_tail==_queue_next_dist) {
542 _queue_next_dist=_queue_head;
544 Node n=_queue[_queue_tail++];
545 _processed->set(n,true);
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);
552 _dist->set(m,_curr_dist);
553 if (nm[m] && rnode == INVALID) rnode = m;
558 ///The next node to be processed.
560 ///Returns the next node to be processed or \c INVALID if the queue
562 Node nextNode() const
564 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
567 ///\brief Returns \c false if there are nodes
570 ///Returns \c false if there are nodes
571 ///to be processed in the queue.
572 bool emptyQueue() const { return _queue_tail==_queue_head; }
574 ///Returns the number of the nodes to be processed.
576 ///Returns the number of the nodes to be processed in the queue.
577 int queueSize() const { return _queue_head-_queue_tail; }
579 ///Executes the algorithm.
581 ///Executes the algorithm.
583 ///This method runs the %BFS algorithm from the root node(s)
584 ///in order to compute the shortest path to each node.
586 ///The algorithm computes
587 ///- the shortest path tree (forest),
588 ///- the distance of each node from the root(s).
590 ///\pre init() must be called and at least one root node should be
591 ///added with addSource() before using this function.
593 ///\note <tt>b.start()</tt> is just a shortcut of the following code.
595 /// while ( !b.emptyQueue() ) {
596 /// b.processNextNode();
601 while ( !emptyQueue() ) processNextNode();
604 ///Executes the algorithm until the given target node is reached.
606 ///Executes the algorithm until the given target node is reached.
608 ///This method runs the %BFS algorithm from the root node(s)
609 ///in order to compute the shortest path to \c dest.
611 ///The algorithm computes
612 ///- the shortest path to \c dest,
613 ///- the distance of \c dest from the root(s).
615 ///\pre init() must be called and at least one root node should be
616 ///added with addSource() before using this function.
618 ///\note <tt>b.start(t)</tt> is just a shortcut of the following code.
620 /// bool reach = false;
621 /// while ( !b.emptyQueue() && !reach ) {
622 /// b.processNextNode(t, reach);
625 void start(Node dest)
628 while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
631 ///Executes the algorithm until a condition is met.
633 ///Executes the algorithm until a condition is met.
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.
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.
642 ///\return The reached node \c v with <tt>nm[v]</tt> true or
643 ///\c INVALID if no such node was found.
645 ///\pre init() must be called and at least one root node should be
646 ///added with addSource() before using this function.
648 ///\note <tt>b.start(nm)</tt> is just a shortcut of the following code.
650 /// Node rnode = INVALID;
651 /// while ( !b.emptyQueue() && rnode == INVALID ) {
652 /// b.processNextNode(nm, rnode);
656 template<class NodeBoolMap>
657 Node start(const NodeBoolMap &nm)
659 Node rnode = INVALID;
660 while ( !emptyQueue() && rnode == INVALID ) {
661 processNextNode(nm, rnode);
666 ///Runs the algorithm from the given node.
668 ///This method runs the %BFS algorithm from node \c s
669 ///in order to compute the shortest path to each node.
671 ///The algorithm computes
672 ///- the shortest path tree,
673 ///- the distance of each node from the root.
675 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
687 ///Finds the shortest path between \c s and \c t.
689 ///This method runs the %BFS algorithm from node \c s
690 ///in order to compute the shortest path to \c t.
692 ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
693 ///if \c t is reachable form \c s, \c 0 otherwise.
695 ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
696 ///shortcut of the following code.
702 int run(Node s,Node t) {
706 return reached(t) ? _curr_dist : 0;
709 ///Runs the algorithm to visit all nodes in the digraph.
711 ///This method runs the %BFS algorithm in order to
712 ///compute the shortest path to each node.
714 ///The algorithm computes
715 ///- the shortest path tree (forest),
716 ///- the distance of each node from the root(s).
718 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
721 /// for (NodeIt n(gr); n != INVALID; ++n) {
722 /// if (!b.reached(n)) {
730 for (NodeIt n(*G); n != INVALID; ++n) {
740 ///\name Query Functions
741 ///The result of the %BFS algorithm can be obtained using these
743 ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
744 ///"start()" must be called before using them.
748 ///The shortest path to a node.
750 ///Returns the shortest path to a node.
752 ///\warning \c t should be reachable from the root(s).
754 ///\pre Either \ref run() or \ref start() must be called before
755 ///using this function.
756 Path path(Node t) const { return Path(*G, *_pred, t); }
758 ///The distance of a node from the root(s).
760 ///Returns the distance of a node from the root(s).
762 ///\warning If node \c v is not reachable from the root(s), then
763 ///the return value of this function is undefined.
765 ///\pre Either \ref run() or \ref start() must be called before
766 ///using this function.
767 int dist(Node v) const { return (*_dist)[v]; }
769 ///Returns the 'previous arc' of the shortest path tree for a node.
771 ///This function returns the 'previous arc' of the shortest path
772 ///tree for the node \c v, i.e. it returns the last arc of a
773 ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
774 ///is not reachable from the root(s) or if \c v is a root.
776 ///The shortest path tree used here is equal to the shortest path
777 ///tree used in \ref predNode().
779 ///\pre Either \ref run() or \ref start() must be called before
780 ///using this function.
781 Arc predArc(Node v) const { return (*_pred)[v];}
783 ///Returns the 'previous node' of the shortest path tree for a node.
785 ///This function returns the 'previous node' of the shortest path
786 ///tree for the node \c v, i.e. it returns the last but one node
787 ///from a shortest path from the root(s) to \c v. It is \c INVALID
788 ///if \c v is not reachable from the root(s) or if \c v is a root.
790 ///The shortest path tree used here is equal to the shortest path
791 ///tree used in \ref predArc().
793 ///\pre Either \ref run() or \ref start() must be called before
794 ///using this function.
795 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
796 G->source((*_pred)[v]); }
798 ///\brief Returns a const reference to the node map that stores the
799 /// distances of the nodes.
801 ///Returns a const reference to the node map that stores the distances
802 ///of the nodes calculated by the algorithm.
804 ///\pre Either \ref run() or \ref init()
805 ///must be called before using this function.
806 const DistMap &distMap() const { return *_dist;}
808 ///\brief Returns a const reference to the node map that stores the
811 ///Returns a const reference to the node map that stores the predecessor
812 ///arcs, which form the shortest path tree.
814 ///\pre Either \ref run() or \ref init()
815 ///must be called before using this function.
816 const PredMap &predMap() const { return *_pred;}
818 ///Checks if a node is reachable from the root(s).
820 ///Returns \c true if \c v is reachable from the root(s).
821 ///\pre Either \ref run() or \ref start()
822 ///must be called before using this function.
823 bool reached(Node v) const { return (*_reached)[v]; }
828 ///Default traits class of bfs() function.
830 ///Default traits class of bfs() function.
831 ///\tparam GR Digraph type.
833 struct BfsWizardDefaultTraits
835 ///The type of the digraph the algorithm runs on.
838 ///\brief The type of the map that stores the predecessor
839 ///arcs of the shortest paths.
841 ///The type of the map that stores the predecessor
842 ///arcs of the shortest paths.
843 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
844 typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
845 ///Instantiates a \ref PredMap.
847 ///This function instantiates a \ref PredMap.
848 ///\param g is the digraph, to which we would like to define the
850 ///\todo The digraph alone may be insufficient to initialize
852 static PredMap *createPredMap(const Digraph &g)
854 static PredMap *createPredMap(const Digraph &)
857 return new PredMap();
860 ///The type of the map that indicates which nodes are processed.
862 ///The type of the map that indicates which nodes are processed.
863 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
864 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
865 ///Instantiates a \ref ProcessedMap.
867 ///This function instantiates a \ref ProcessedMap.
868 ///\param g is the digraph, to which
869 ///we would like to define the \ref ProcessedMap.
871 static ProcessedMap *createProcessedMap(const Digraph &g)
873 static ProcessedMap *createProcessedMap(const Digraph &)
876 return new ProcessedMap();
879 ///The type of the map that indicates which nodes are reached.
881 ///The type of the map that indicates which nodes are reached.
882 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
883 typedef typename Digraph::template NodeMap<bool> ReachedMap;
884 ///Instantiates a \ref ReachedMap.
886 ///This function instantiates a \ref ReachedMap.
887 ///\param g is the digraph, to which
888 ///we would like to define the \ref ReachedMap.
889 static ReachedMap *createReachedMap(const Digraph &g)
891 return new ReachedMap(g);
894 ///The type of the map that stores the distances of the nodes.
896 ///The type of the map that stores the distances of the nodes.
897 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
899 typedef NullMap<typename Digraph::Node,int> DistMap;
900 ///Instantiates a \ref DistMap.
902 ///This function instantiates a \ref DistMap.
903 ///\param g is the digraph, to which we would like to define
906 static DistMap *createDistMap(const Digraph &g)
908 static DistMap *createDistMap(const Digraph &)
911 return new DistMap();
915 /// Default traits class used by \ref BfsWizard
917 /// To make it easier to use Bfs algorithm
918 /// we have created a wizard class.
919 /// This \ref BfsWizard class needs default traits,
920 /// as well as the \ref Bfs class.
921 /// The \ref BfsWizardBase is a class to be the default traits of the
922 /// \ref BfsWizard class.
924 class BfsWizardBase : public BfsWizardDefaultTraits<GR>
927 typedef BfsWizardDefaultTraits<GR> Base;
929 //The type of the nodes in the digraph.
930 typedef typename Base::Digraph::Node Node;
932 //Pointer to the digraph the algorithm runs on.
934 //Pointer to the map of reached nodes.
936 //Pointer to the map of processed nodes.
938 //Pointer to the map of predecessors arcs.
940 //Pointer to the map of distances.
942 //Pointer to the source node.
948 /// This constructor does not require parameters, therefore it initiates
949 /// all of the attributes to default values (0, INVALID).
950 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
951 _dist(0), _source(INVALID) {}
955 /// This constructor requires some parameters,
956 /// listed in the parameters list.
957 /// Others are initiated to 0.
958 /// \param g The digraph the algorithm runs on.
959 /// \param s The source node.
960 BfsWizardBase(const GR &g, Node s=INVALID) :
961 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
962 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
966 /// Auxiliary class for the function type interface of BFS algorithm.
968 /// This auxiliary class is created to implement the function type
969 /// interface of \ref Bfs algorithm. It uses the functions and features
970 /// of the plain \ref Bfs, but it is much simpler to use it.
971 /// It should only be used through the \ref bfs() function, which makes
972 /// it easier to use the algorithm.
974 /// Simplicity means that the way to change the types defined
975 /// in the traits class is based on functions that returns the new class
976 /// and not on templatable built-in classes.
977 /// When using the plain \ref Bfs
978 /// the new class with the modified type comes from
979 /// the original class by using the ::
980 /// operator. In the case of \ref BfsWizard only
981 /// a function have to be called, and it will
982 /// return the needed class.
984 /// It does not have own \ref run() method. When its \ref run() method
985 /// is called, it initiates a plain \ref Bfs object, and calls the
986 /// \ref Bfs::run() method of it.
988 class BfsWizard : public TR
992 ///The type of the digraph the algorithm runs on.
993 typedef typename TR::Digraph Digraph;
995 typedef typename Digraph::Node Node;
996 typedef typename Digraph::NodeIt NodeIt;
997 typedef typename Digraph::Arc Arc;
998 typedef typename Digraph::OutArcIt OutArcIt;
1000 ///\brief The type of the map that stores the predecessor
1001 ///arcs of the shortest paths.
1002 typedef typename TR::PredMap PredMap;
1003 ///\brief The type of the map that stores the distances of the nodes.
1004 typedef typename TR::DistMap DistMap;
1005 ///\brief The type of the map that indicates which nodes are reached.
1006 typedef typename TR::ReachedMap ReachedMap;
1007 ///\brief The type of the map that indicates which nodes are processed.
1008 typedef typename TR::ProcessedMap ProcessedMap;
1013 BfsWizard() : TR() {}
1015 /// Constructor that requires parameters.
1017 /// Constructor that requires parameters.
1018 /// These parameters will be the default values for the traits class.
1019 BfsWizard(const Digraph &g, Node s=INVALID) :
1023 BfsWizard(const TR &b) : TR(b) {}
1027 ///Runs BFS algorithm from a source node.
1029 ///Runs BFS algorithm from a source node.
1030 ///The node can be given with the \ref source() function.
1033 if(Base::_source==INVALID) throw UninitializedParameter();
1034 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
1036 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
1037 if(Base::_processed)
1038 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1040 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1042 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1043 alg.run(Base::_source);
1046 ///Runs BFS algorithm from the given node.
1048 ///Runs BFS algorithm from the given node.
1049 ///\param s is the given source.
1056 /// Sets the source node, from which the Bfs algorithm runs.
1058 /// Sets the source node, from which the Bfs algorithm runs.
1059 /// \param s is the source node.
1060 BfsWizard<TR> &source(Node s)
1067 struct SetPredMapBase : public Base {
1069 static PredMap *createPredMap(const Digraph &) { return 0; };
1070 SetPredMapBase(const TR &b) : TR(b) {}
1072 ///\brief \ref named-templ-param "Named parameter"
1073 ///for setting \ref PredMap object.
1075 /// \ref named-templ-param "Named parameter"
1076 ///for setting \ref PredMap object.
1078 BfsWizard<SetPredMapBase<T> > predMap(const T &t)
1080 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1081 return BfsWizard<SetPredMapBase<T> >(*this);
1085 struct SetReachedMapBase : public Base {
1086 typedef T ReachedMap;
1087 static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1088 SetReachedMapBase(const TR &b) : TR(b) {}
1090 ///\brief \ref named-templ-param "Named parameter"
1091 ///for setting \ref ReachedMap object.
1093 /// \ref named-templ-param "Named parameter"
1094 ///for setting \ref ReachedMap object.
1096 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
1098 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
1099 return BfsWizard<SetReachedMapBase<T> >(*this);
1103 struct SetProcessedMapBase : public Base {
1104 typedef T ProcessedMap;
1105 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1106 SetProcessedMapBase(const TR &b) : TR(b) {}
1108 ///\brief \ref named-templ-param "Named parameter"
1109 ///for setting \ref ProcessedMap object.
1111 /// \ref named-templ-param "Named parameter"
1112 ///for setting \ref ProcessedMap object.
1114 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1116 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
1117 return BfsWizard<SetProcessedMapBase<T> >(*this);
1121 struct SetDistMapBase : public Base {
1123 static DistMap *createDistMap(const Digraph &) { return 0; };
1124 SetDistMapBase(const TR &b) : TR(b) {}
1126 ///\brief \ref named-templ-param "Named parameter"
1127 ///for setting \ref DistMap object.
1129 /// \ref named-templ-param "Named parameter"
1130 ///for setting \ref DistMap object.
1132 BfsWizard<SetDistMapBase<T> > distMap(const T &t)
1134 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1135 return BfsWizard<SetDistMapBase<T> >(*this);
1140 ///Function type interface for Bfs algorithm.
1143 ///Function type interface for Bfs algorithm.
1145 ///This function also has several
1146 ///\ref named-templ-func-param "named parameters",
1147 ///they are declared as the members of class \ref BfsWizard.
1149 ///example shows how to use these parameters.
1151 /// bfs(g,source).predMap(preds).run();
1153 ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
1154 ///to the end of the parameter list.
1158 BfsWizard<BfsWizardBase<GR> >
1159 bfs(const GR &g,typename GR::Node s=INVALID)
1161 return BfsWizard<BfsWizardBase<GR> >(g,s);
1165 /// \brief Visitor class for BFS.
1167 /// This class defines the interface of the BfsVisit events, and
1168 /// it could be the base of a real visitor class.
1169 template <typename _Digraph>
1171 typedef _Digraph Digraph;
1172 typedef typename Digraph::Arc Arc;
1173 typedef typename Digraph::Node Node;
1174 /// \brief Called for the source node(s) of the BFS.
1176 /// This function is called for the source node(s) of the BFS.
1177 void start(const Node& node) {}
1178 /// \brief Called when a node is reached first time.
1180 /// This function is called when a node is reached first time.
1181 void reach(const Node& node) {}
1182 /// \brief Called when a node is processed.
1184 /// This function is called when a node is processed.
1185 void process(const Node& node) {}
1186 /// \brief Called when an arc reaches a new node.
1188 /// This function is called when the BFS finds an arc whose target node
1189 /// is not reached yet.
1190 void discover(const Arc& arc) {}
1191 /// \brief Called when an arc is examined but its target node is
1192 /// already discovered.
1194 /// This function is called when an arc is examined but its target node is
1195 /// already discovered.
1196 void examine(const Arc& arc) {}
1199 template <typename _Digraph>
1201 typedef _Digraph Digraph;
1202 typedef typename Digraph::Arc Arc;
1203 typedef typename Digraph::Node Node;
1204 void start(const Node&) {}
1205 void reach(const Node&) {}
1206 void process(const Node&) {}
1207 void discover(const Arc&) {}
1208 void examine(const Arc&) {}
1210 template <typename _Visitor>
1211 struct Constraints {
1212 void constraints() {
1215 visitor.start(node);
1216 visitor.reach(node);
1217 visitor.process(node);
1218 visitor.discover(arc);
1219 visitor.examine(arc);
1226 /// \brief Default traits class of BfsVisit class.
1228 /// Default traits class of BfsVisit class.
1229 /// \tparam _Digraph The type of the digraph the algorithm runs on.
1230 template<class _Digraph>
1231 struct BfsVisitDefaultTraits {
1233 /// \brief The type of the digraph the algorithm runs on.
1234 typedef _Digraph Digraph;
1236 /// \brief The type of the map that indicates which nodes are reached.
1238 /// The type of the map that indicates which nodes are reached.
1239 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1240 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1242 /// \brief Instantiates a \ref ReachedMap.
1244 /// This function instantiates a \ref ReachedMap.
1245 /// \param digraph is the digraph, to which
1246 /// we would like to define the \ref ReachedMap.
1247 static ReachedMap *createReachedMap(const Digraph &digraph) {
1248 return new ReachedMap(digraph);
1255 /// \brief %BFS algorithm class with visitor interface.
1257 /// This class provides an efficient implementation of the %BFS algorithm
1258 /// with visitor interface.
1260 /// The %BfsVisit class provides an alternative interface to the Bfs
1261 /// class. It works with callback mechanism, the BfsVisit object calls
1262 /// the member functions of the \c Visitor class on every BFS event.
1264 /// \tparam _Digraph The type of the digraph the algorithm runs on.
1265 /// The default value is
1266 /// \ref ListDigraph. The value of _Digraph is not used directly by
1267 /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
1268 /// \tparam _Visitor The Visitor type that is used by the algorithm.
1269 /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
1270 /// does not observe the BFS events. If you want to observe the BFS
1271 /// events, you should implement your own visitor class.
1272 /// \tparam _Traits Traits class to set various data types used by the
1273 /// algorithm. The default traits class is
1274 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
1275 /// See \ref BfsVisitDefaultTraits for the documentation of
1276 /// a BFS visit traits class.
1278 template <typename _Digraph, typename _Visitor, typename _Traits>
1280 template <typename _Digraph = ListDigraph,
1281 typename _Visitor = BfsVisitor<_Digraph>,
1282 typename _Traits = BfsDefaultTraits<_Digraph> >
1287 /// \brief \ref Exception for uninitialized parameters.
1289 /// This error represents problems in the initialization
1290 /// of the parameters of the algorithm.
1291 class UninitializedParameter : public lemon::UninitializedParameter {
1293 virtual const char* what() const throw()
1295 return "lemon::BfsVisit::UninitializedParameter";
1299 ///The traits class.
1300 typedef _Traits Traits;
1302 ///The type of the digraph the algorithm runs on.
1303 typedef typename Traits::Digraph Digraph;
1305 ///The visitor type used by the algorithm.
1306 typedef _Visitor Visitor;
1308 ///The type of the map that indicates which nodes are reached.
1309 typedef typename Traits::ReachedMap ReachedMap;
1313 typedef typename Digraph::Node Node;
1314 typedef typename Digraph::NodeIt NodeIt;
1315 typedef typename Digraph::Arc Arc;
1316 typedef typename Digraph::OutArcIt OutArcIt;
1318 //Pointer to the underlying digraph.
1319 const Digraph *_digraph;
1320 //Pointer to the visitor object.
1322 //Pointer to the map of reached status of the nodes.
1323 ReachedMap *_reached;
1324 //Indicates if _reached is locally allocated (true) or not.
1327 std::vector<typename Digraph::Node> _list;
1328 int _list_front, _list_back;
1330 ///Creates the maps if necessary.
1331 ///\todo Better memory allocation (instead of new).
1332 void create_maps() {
1334 local_reached = true;
1335 _reached = Traits::createReachedMap(*_digraph);
1345 typedef BfsVisit Create;
1347 /// \name Named template parameters
1351 struct SetReachedMapTraits : public Traits {
1352 typedef T ReachedMap;
1353 static ReachedMap *createReachedMap(const Digraph &digraph) {
1354 throw UninitializedParameter();
1357 /// \brief \ref named-templ-param "Named parameter" for setting
1358 /// ReachedMap type.
1360 /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
1362 struct SetReachedMap : public BfsVisit< Digraph, Visitor,
1363 SetReachedMapTraits<T> > {
1364 typedef BfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
1370 /// \brief Constructor.
1374 /// \param digraph The digraph the algorithm runs on.
1375 /// \param visitor The visitor object of the algorithm.
1376 BfsVisit(const Digraph& digraph, Visitor& visitor)
1377 : _digraph(&digraph), _visitor(&visitor),
1378 _reached(0), local_reached(false) {}
1380 /// \brief Destructor.
1382 if(local_reached) delete _reached;
1385 /// \brief Sets the map that indicates which nodes are reached.
1387 /// Sets the map that indicates which nodes are reached.
1388 /// If you don't use this function before calling \ref run(),
1389 /// it will allocate one. The destructor deallocates this
1390 /// automatically allocated map, of course.
1391 /// \return <tt> (*this) </tt>
1392 BfsVisit &reachedMap(ReachedMap &m) {
1395 local_reached = false;
1403 /// \name Execution control
1404 /// The simplest way to execute the algorithm is to use
1405 /// one of the member functions called \ref lemon::BfsVisit::run()
1408 /// If you need more control on the execution, first you must call
1409 /// \ref lemon::BfsVisit::init() "init()", then you can add several
1410 /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
1411 /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
1412 /// actual path computation.
1416 /// \brief Initializes the internal data structures.
1418 /// Initializes the internal data structures.
1421 _list.resize(countNodes(*_digraph));
1422 _list_front = _list_back = -1;
1423 for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
1424 _reached->set(u, false);
1428 /// \brief Adds a new source node.
1430 /// Adds a new source node to the set of nodes to be processed.
1431 void addSource(Node s) {
1432 if(!(*_reached)[s]) {
1433 _reached->set(s,true);
1436 _list[++_list_back] = s;
1440 /// \brief Processes the next node.
1442 /// Processes the next node.
1444 /// \return The processed node.
1446 /// \pre The queue must not be empty.
1447 Node processNextNode() {
1448 Node n = _list[++_list_front];
1449 _visitor->process(n);
1451 for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
1452 Node m = _digraph->target(e);
1453 if (!(*_reached)[m]) {
1454 _visitor->discover(e);
1456 _reached->set(m, true);
1457 _list[++_list_back] = m;
1459 _visitor->examine(e);
1465 /// \brief Processes the next node.
1467 /// Processes the next node and checks if the given target node
1468 /// is reached. If the target node is reachable from the processed
1469 /// node, then the \c reach parameter will be set to \c true.
1471 /// \param target The target node.
1472 /// \retval reach Indicates if the target node is reached.
1473 /// It should be initially \c false.
1475 /// \return The processed node.
1477 /// \pre The queue must not be empty.
1478 Node processNextNode(Node target, bool& reach) {
1479 Node n = _list[++_list_front];
1480 _visitor->process(n);
1482 for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
1483 Node m = _digraph->target(e);
1484 if (!(*_reached)[m]) {
1485 _visitor->discover(e);
1487 _reached->set(m, true);
1488 _list[++_list_back] = m;
1489 reach = reach || (target == m);
1491 _visitor->examine(e);
1497 /// \brief Processes the next node.
1499 /// Processes the next node and checks if at least one of reached
1500 /// nodes has \c true value in the \c nm node map. If one node
1501 /// with \c true value is reachable from the processed node, then the
1502 /// \c rnode parameter will be set to the first of such nodes.
1504 /// \param nm A \c bool (or convertible) node map that indicates the
1505 /// possible targets.
1506 /// \retval rnode The reached target node.
1507 /// It should be initially \c INVALID.
1509 /// \return The processed node.
1511 /// \pre The queue must not be empty.
1512 template <typename NM>
1513 Node processNextNode(const NM& nm, Node& rnode) {
1514 Node n = _list[++_list_front];
1515 _visitor->process(n);
1517 for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
1518 Node m = _digraph->target(e);
1519 if (!(*_reached)[m]) {
1520 _visitor->discover(e);
1522 _reached->set(m, true);
1523 _list[++_list_back] = m;
1524 if (nm[m] && rnode == INVALID) rnode = m;
1526 _visitor->examine(e);
1532 /// \brief The next node to be processed.
1534 /// Returns the next node to be processed or \c INVALID if the queue
1536 Node nextNode() const {
1537 return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
1540 /// \brief Returns \c false if there are nodes
1541 /// to be processed.
1543 /// Returns \c false if there are nodes
1544 /// to be processed in the queue.
1545 bool emptyQueue() const { return _list_front == _list_back; }
1547 /// \brief Returns the number of the nodes to be processed.
1549 /// Returns the number of the nodes to be processed in the queue.
1550 int queueSize() const { return _list_back - _list_front; }
1552 /// \brief Executes the algorithm.
1554 /// Executes the algorithm.
1556 /// This method runs the %BFS algorithm from the root node(s)
1557 /// in order to compute the shortest path to each node.
1559 /// The algorithm computes
1560 /// - the shortest path tree (forest),
1561 /// - the distance of each node from the root(s).
1563 /// \pre init() must be called and at least one root node should be added
1564 /// with addSource() before using this function.
1566 /// \note <tt>b.start()</tt> is just a shortcut of the following code.
1568 /// while ( !b.emptyQueue() ) {
1569 /// b.processNextNode();
1573 while ( !emptyQueue() ) processNextNode();
1576 /// \brief Executes the algorithm until the given target node is reached.
1578 /// Executes the algorithm until the given target node is reached.
1580 /// This method runs the %BFS algorithm from the root node(s)
1581 /// in order to compute the shortest path to \c dest.
1583 /// The algorithm computes
1584 /// - the shortest path to \c dest,
1585 /// - the distance of \c dest from the root(s).
1587 /// \pre init() must be called and at least one root node should be
1588 /// added with addSource() before using this function.
1590 /// \note <tt>b.start(t)</tt> is just a shortcut of the following code.
1592 /// bool reach = false;
1593 /// while ( !b.emptyQueue() && !reach ) {
1594 /// b.processNextNode(t, reach);
1597 void start(Node dest) {
1599 while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
1602 /// \brief Executes the algorithm until a condition is met.
1604 /// Executes the algorithm until a condition is met.
1606 /// This method runs the %BFS algorithm from the root node(s) in
1607 /// order to compute the shortest path to a node \c v with
1608 /// <tt>nm[v]</tt> true, if such a node can be found.
1610 /// \param nm must be a bool (or convertible) node map. The
1611 /// algorithm will stop when it reaches a node \c v with
1612 /// <tt>nm[v]</tt> true.
1614 /// \return The reached node \c v with <tt>nm[v]</tt> true or
1615 /// \c INVALID if no such node was found.
1617 /// \pre init() must be called and at least one root node should be
1618 /// added with addSource() before using this function.
1620 /// \note <tt>b.start(nm)</tt> is just a shortcut of the following code.
1622 /// Node rnode = INVALID;
1623 /// while ( !b.emptyQueue() && rnode == INVALID ) {
1624 /// b.processNextNode(nm, rnode);
1628 template <typename NM>
1629 Node start(const NM &nm) {
1630 Node rnode = INVALID;
1631 while ( !emptyQueue() && rnode == INVALID ) {
1632 processNextNode(nm, rnode);
1637 /// \brief Runs the algorithm from the given node.
1639 /// This method runs the %BFS algorithm from node \c s
1640 /// in order to compute the shortest path to each node.
1642 /// The algorithm computes
1643 /// - the shortest path tree,
1644 /// - the distance of each node from the root.
1646 /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
1658 /// \brief Runs the algorithm to visit all nodes in the digraph.
1660 /// This method runs the %BFS algorithm in order to
1661 /// compute the shortest path to each node.
1663 /// The algorithm computes
1664 /// - the shortest path tree (forest),
1665 /// - the distance of each node from the root(s).
1667 /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
1670 /// for (NodeIt n(gr); n != INVALID; ++n) {
1671 /// if (!b.reached(n)) {
1679 for (NodeIt it(*_digraph); it != INVALID; ++it) {
1689 /// \name Query Functions
1690 /// The result of the %BFS algorithm can be obtained using these
1692 /// Either \ref lemon::BfsVisit::run() "run()" or
1693 /// \ref lemon::BfsVisit::start() "start()" must be called before
1697 /// \brief Checks if a node is reachable from the root(s).
1699 /// Returns \c true if \c v is reachable from the root(s).
1700 /// \pre Either \ref run() or \ref start()
1701 /// must be called before using this function.
1702 bool reached(Node v) { return (*_reached)[v]; }
1708 } //END OF NAMESPACE LEMON