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 static PredMap *createPredMap(const Digraph &g)
58 return new PredMap(g);
61 ///The type of the map that indicates which nodes are processed.
63 ///The type of the map that indicates which nodes are processed.
64 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
65 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
66 ///Instantiates a \ref ProcessedMap.
68 ///This function instantiates a \ref ProcessedMap.
69 ///\param g is the digraph, to which
70 ///we would like to define the \ref ProcessedMap
72 static ProcessedMap *createProcessedMap(const Digraph &g)
74 static ProcessedMap *createProcessedMap(const Digraph &)
77 return new ProcessedMap();
80 ///The type of the map that indicates which nodes are reached.
82 ///The type of the map that indicates which nodes are reached.
83 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
84 typedef typename Digraph::template NodeMap<bool> ReachedMap;
85 ///Instantiates a \ref ReachedMap.
87 ///This function instantiates a \ref ReachedMap.
88 ///\param g is the digraph, to which
89 ///we would like to define the \ref ReachedMap.
90 static ReachedMap *createReachedMap(const Digraph &g)
92 return new ReachedMap(g);
95 ///The type of the map that stores the distances of the nodes.
97 ///The type of the map that stores the distances of the nodes.
98 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
99 typedef typename Digraph::template NodeMap<int> DistMap;
100 ///Instantiates a \ref DistMap.
102 ///This function instantiates a \ref DistMap.
103 ///\param g is the digraph, to which we would like to define the
105 static DistMap *createDistMap(const Digraph &g)
107 return new DistMap(g);
111 ///%BFS algorithm class.
114 ///This class provides an efficient implementation of the %BFS algorithm.
116 ///There is also a \ref bfs() "function type interface" for the BFS
117 ///algorithm, which is convenient in the simplier cases and it can be
120 ///\tparam GR The type of the digraph the algorithm runs on.
121 ///The default value is \ref ListDigraph. The value of GR is not used
122 ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
123 ///\tparam TR Traits class to set various data types used by the algorithm.
124 ///The default traits class is
125 ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
126 ///See \ref BfsDefaultTraits for the documentation of
127 ///a Bfs traits class.
129 template <typename GR,
132 template <typename GR=ListDigraph,
133 typename TR=BfsDefaultTraits<GR> >
137 ///\ref Exception for uninitialized parameters.
139 ///This error represents problems in the initialization of the
140 ///parameters of the algorithm.
141 class UninitializedParameter : public lemon::UninitializedParameter {
143 virtual const char* what() const throw() {
144 return "lemon::Bfs::UninitializedParameter";
148 ///The type of the digraph the algorithm runs on.
149 typedef typename TR::Digraph Digraph;
151 ///\brief The type of the map that stores the predecessor arcs of the
153 typedef typename TR::PredMap PredMap;
154 ///The type of the map that stores the distances of the nodes.
155 typedef typename TR::DistMap DistMap;
156 ///The type of the map that indicates which nodes are reached.
157 typedef typename TR::ReachedMap ReachedMap;
158 ///The type of the map that indicates which nodes are processed.
159 typedef typename TR::ProcessedMap ProcessedMap;
160 ///The type of the paths.
161 typedef PredMapPath<Digraph, PredMap> Path;
168 typedef typename Digraph::Node Node;
169 typedef typename Digraph::NodeIt NodeIt;
170 typedef typename Digraph::Arc Arc;
171 typedef typename Digraph::OutArcIt OutArcIt;
173 //Pointer to the underlying digraph.
175 //Pointer to the map of predecessor arcs.
177 //Indicates if _pred is locally allocated (true) or not.
179 //Pointer to the map of distances.
181 //Indicates if _dist is locally allocated (true) or not.
183 //Pointer to the map of reached status of the nodes.
184 ReachedMap *_reached;
185 //Indicates if _reached is locally allocated (true) or not.
187 //Pointer to the map of processed status of the nodes.
188 ProcessedMap *_processed;
189 //Indicates if _processed is locally allocated (true) or not.
190 bool local_processed;
192 std::vector<typename Digraph::Node> _queue;
193 int _queue_head,_queue_tail,_queue_next_dist;
196 //Creates the maps if necessary.
201 _pred = Traits::createPredMap(*G);
205 _dist = Traits::createDistMap(*G);
208 local_reached = true;
209 _reached = Traits::createReachedMap(*G);
212 local_processed = true;
213 _processed = Traits::createProcessedMap(*G);
225 ///\name Named template parameters
230 struct SetPredMapTraits : public Traits {
232 static PredMap *createPredMap(const Digraph &)
234 throw UninitializedParameter();
237 ///\brief \ref named-templ-param "Named parameter" for setting
238 ///\ref PredMap type.
240 ///\ref named-templ-param "Named parameter" for setting
241 ///\ref PredMap type.
243 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
244 typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
248 struct SetDistMapTraits : public Traits {
250 static DistMap *createDistMap(const Digraph &)
252 throw UninitializedParameter();
255 ///\brief \ref named-templ-param "Named parameter" for setting
256 ///\ref DistMap type.
258 ///\ref named-templ-param "Named parameter" for setting
259 ///\ref DistMap type.
261 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
262 typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
266 struct SetReachedMapTraits : public Traits {
267 typedef T ReachedMap;
268 static ReachedMap *createReachedMap(const Digraph &)
270 throw UninitializedParameter();
273 ///\brief \ref named-templ-param "Named parameter" for setting
274 ///\ref ReachedMap type.
276 ///\ref named-templ-param "Named parameter" for setting
277 ///\ref ReachedMap type.
279 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
280 typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
284 struct SetProcessedMapTraits : public Traits {
285 typedef T ProcessedMap;
286 static ProcessedMap *createProcessedMap(const Digraph &)
288 throw UninitializedParameter();
291 ///\brief \ref named-templ-param "Named parameter" for setting
292 ///\ref ProcessedMap type.
294 ///\ref named-templ-param "Named parameter" for setting
295 ///\ref ProcessedMap type.
297 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
298 typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
301 struct SetStandardProcessedMapTraits : public Traits {
302 typedef typename Digraph::template NodeMap<bool> ProcessedMap;
303 static ProcessedMap *createProcessedMap(const Digraph &g)
305 return new ProcessedMap(g);
308 ///\brief \ref named-templ-param "Named parameter" for setting
309 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
311 ///\ref named-templ-param "Named parameter" for setting
312 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
313 ///If you don't set it explicitly, it will be automatically allocated.
314 struct SetStandardProcessedMap :
315 public Bfs< Digraph, SetStandardProcessedMapTraits > {
316 typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;
326 ///\param g The digraph the algorithm runs on.
327 Bfs(const Digraph &g) :
329 _pred(NULL), local_pred(false),
330 _dist(NULL), local_dist(false),
331 _reached(NULL), local_reached(false),
332 _processed(NULL), local_processed(false)
338 if(local_pred) delete _pred;
339 if(local_dist) delete _dist;
340 if(local_reached) delete _reached;
341 if(local_processed) delete _processed;
344 ///Sets the map that stores the predecessor arcs.
346 ///Sets the map that stores the predecessor arcs.
347 ///If you don't use this function before calling \ref run(),
348 ///it will allocate one. The destructor deallocates this
349 ///automatically allocated map, of course.
350 ///\return <tt> (*this) </tt>
351 Bfs &predMap(PredMap &m)
361 ///Sets the map that indicates which nodes are reached.
363 ///Sets the map that indicates which nodes are reached.
364 ///If you don't use this function before calling \ref run(),
365 ///it will allocate one. The destructor deallocates this
366 ///automatically allocated map, of course.
367 ///\return <tt> (*this) </tt>
368 Bfs &reachedMap(ReachedMap &m)
378 ///Sets the map that indicates which nodes are processed.
380 ///Sets the map that indicates which nodes are processed.
381 ///If you don't use this function before calling \ref run(),
382 ///it will allocate one. The destructor deallocates this
383 ///automatically allocated map, of course.
384 ///\return <tt> (*this) </tt>
385 Bfs &processedMap(ProcessedMap &m)
387 if(local_processed) {
389 local_processed=false;
395 ///Sets the map that stores the distances of the nodes.
397 ///Sets the map that stores the distances of the nodes calculated by
399 ///If you don't use this function before calling \ref run(),
400 ///it will allocate one. The destructor deallocates this
401 ///automatically allocated map, of course.
402 ///\return <tt> (*this) </tt>
403 Bfs &distMap(DistMap &m)
415 ///\name Execution control
416 ///The simplest way to execute the algorithm is to use
417 ///one of the member functions called \ref lemon::Bfs::run() "run()".
419 ///If you need more control on the execution, first you must call
420 ///\ref lemon::Bfs::init() "init()", then you can add several source
421 ///nodes with \ref lemon::Bfs::addSource() "addSource()".
422 ///Finally \ref lemon::Bfs::start() "start()" will perform the
423 ///actual path computation.
427 ///Initializes the internal data structures.
429 ///Initializes the internal data structures.
434 _queue.resize(countNodes(*G));
435 _queue_head=_queue_tail=0;
437 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
438 _pred->set(u,INVALID);
439 _reached->set(u,false);
440 _processed->set(u,false);
444 ///Adds a new source node.
446 ///Adds a new source node to the set of nodes to be processed.
448 void addSource(Node s)
452 _reached->set(s,true);
453 _pred->set(s,INVALID);
455 _queue[_queue_head++]=s;
456 _queue_next_dist=_queue_head;
460 ///Processes the next node.
462 ///Processes the next node.
464 ///\return The processed node.
466 ///\pre The queue must not be empty.
467 Node processNextNode()
469 if(_queue_tail==_queue_next_dist) {
471 _queue_next_dist=_queue_head;
473 Node n=_queue[_queue_tail++];
474 _processed->set(n,true);
476 for(OutArcIt e(*G,n);e!=INVALID;++e)
477 if(!(*_reached)[m=G->target(e)]) {
478 _queue[_queue_head++]=m;
479 _reached->set(m,true);
481 _dist->set(m,_curr_dist);
486 ///Processes the next node.
488 ///Processes the next node and checks if the given target node
489 ///is reached. If the target node is reachable from the processed
490 ///node, then the \c reach parameter will be set to \c true.
492 ///\param target The target node.
493 ///\retval reach Indicates if the target node is reached.
494 ///It should be initially \c false.
496 ///\return The processed node.
498 ///\pre The queue must not be empty.
499 Node processNextNode(Node target, bool& reach)
501 if(_queue_tail==_queue_next_dist) {
503 _queue_next_dist=_queue_head;
505 Node n=_queue[_queue_tail++];
506 _processed->set(n,true);
508 for(OutArcIt e(*G,n);e!=INVALID;++e)
509 if(!(*_reached)[m=G->target(e)]) {
510 _queue[_queue_head++]=m;
511 _reached->set(m,true);
513 _dist->set(m,_curr_dist);
514 reach = reach || (target == m);
519 ///Processes the next node.
521 ///Processes the next node and checks if at least one of reached
522 ///nodes has \c true value in the \c nm node map. If one node
523 ///with \c true value is reachable from the processed node, then the
524 ///\c rnode parameter will be set to the first of such nodes.
526 ///\param nm A \c bool (or convertible) node map that indicates the
528 ///\retval rnode The reached target node.
529 ///It should be initially \c INVALID.
531 ///\return The processed node.
533 ///\pre The queue must not be empty.
535 Node processNextNode(const NM& nm, Node& rnode)
537 if(_queue_tail==_queue_next_dist) {
539 _queue_next_dist=_queue_head;
541 Node n=_queue[_queue_tail++];
542 _processed->set(n,true);
544 for(OutArcIt e(*G,n);e!=INVALID;++e)
545 if(!(*_reached)[m=G->target(e)]) {
546 _queue[_queue_head++]=m;
547 _reached->set(m,true);
549 _dist->set(m,_curr_dist);
550 if (nm[m] && rnode == INVALID) rnode = m;
555 ///The next node to be processed.
557 ///Returns the next node to be processed or \c INVALID if the queue
559 Node nextNode() const
561 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
564 ///\brief Returns \c false if there are nodes
567 ///Returns \c false if there are nodes
568 ///to be processed in the queue.
569 bool emptyQueue() const { return _queue_tail==_queue_head; }
571 ///Returns the number of the nodes to be processed.
573 ///Returns the number of the nodes to be processed in the queue.
574 int queueSize() const { return _queue_head-_queue_tail; }
576 ///Executes the algorithm.
578 ///Executes the algorithm.
580 ///This method runs the %BFS algorithm from the root node(s)
581 ///in order to compute the shortest path to each node.
583 ///The algorithm computes
584 ///- the shortest path tree (forest),
585 ///- the distance of each node from the root(s).
587 ///\pre init() must be called and at least one root node should be
588 ///added with addSource() before using this function.
590 ///\note <tt>b.start()</tt> is just a shortcut of the following code.
592 /// while ( !b.emptyQueue() ) {
593 /// b.processNextNode();
598 while ( !emptyQueue() ) processNextNode();
601 ///Executes the algorithm until the given target node is reached.
603 ///Executes the algorithm until the given target node is reached.
605 ///This method runs the %BFS algorithm from the root node(s)
606 ///in order to compute the shortest path to \c dest.
608 ///The algorithm computes
609 ///- the shortest path to \c dest,
610 ///- the distance of \c dest from the root(s).
612 ///\pre init() must be called and at least one root node should be
613 ///added with addSource() before using this function.
615 ///\note <tt>b.start(t)</tt> is just a shortcut of the following code.
617 /// bool reach = false;
618 /// while ( !b.emptyQueue() && !reach ) {
619 /// b.processNextNode(t, reach);
622 void start(Node dest)
625 while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
628 ///Executes the algorithm until a condition is met.
630 ///Executes the algorithm until a condition is met.
632 ///This method runs the %BFS algorithm from the root node(s) in
633 ///order to compute the shortest path to a node \c v with
634 /// <tt>nm[v]</tt> true, if such a node can be found.
636 ///\param nm A \c bool (or convertible) node map. The algorithm
637 ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
639 ///\return The reached node \c v with <tt>nm[v]</tt> true or
640 ///\c INVALID if no such node was found.
642 ///\pre init() must be called and at least one root node should be
643 ///added with addSource() before using this function.
645 ///\note <tt>b.start(nm)</tt> is just a shortcut of the following code.
647 /// Node rnode = INVALID;
648 /// while ( !b.emptyQueue() && rnode == INVALID ) {
649 /// b.processNextNode(nm, rnode);
653 template<class NodeBoolMap>
654 Node start(const NodeBoolMap &nm)
656 Node rnode = INVALID;
657 while ( !emptyQueue() && rnode == INVALID ) {
658 processNextNode(nm, rnode);
663 ///Runs the algorithm from the given node.
665 ///This method runs the %BFS algorithm from node \c s
666 ///in order to compute the shortest path to each node.
668 ///The algorithm computes
669 ///- the shortest path tree,
670 ///- the distance of each node from the root.
672 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
684 ///Finds the shortest path between \c s and \c t.
686 ///This method runs the %BFS algorithm from node \c s
687 ///in order to compute the shortest path to \c t.
689 ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
690 ///if \c t is reachable form \c s, \c 0 otherwise.
692 ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
693 ///shortcut of the following code.
699 int run(Node s,Node t) {
703 return reached(t) ? _curr_dist : 0;
706 ///Runs the algorithm to visit all nodes in the digraph.
708 ///This method runs the %BFS algorithm in order to
709 ///compute the shortest path to each node.
711 ///The algorithm computes
712 ///- the shortest path tree (forest),
713 ///- the distance of each node from the root(s).
715 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
718 /// for (NodeIt n(gr); n != INVALID; ++n) {
719 /// if (!b.reached(n)) {
727 for (NodeIt n(*G); n != INVALID; ++n) {
737 ///\name Query Functions
738 ///The result of the %BFS algorithm can be obtained using these
740 ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
741 ///"start()" must be called before using them.
745 ///The shortest path to a node.
747 ///Returns the shortest path to a node.
749 ///\warning \c t should be reachable from the root(s).
751 ///\pre Either \ref run() or \ref start() must be called before
752 ///using this function.
753 Path path(Node t) const { return Path(*G, *_pred, t); }
755 ///The distance of a node from the root(s).
757 ///Returns the distance of a node from the root(s).
759 ///\warning If node \c v is not reachable from the root(s), then
760 ///the return value of this function is undefined.
762 ///\pre Either \ref run() or \ref start() must be called before
763 ///using this function.
764 int dist(Node v) const { return (*_dist)[v]; }
766 ///Returns the 'previous arc' of the shortest path tree for a node.
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 the root(s) to \c v. It is \c INVALID if \c v
771 ///is not reachable from the root(s) or if \c v is a root.
773 ///The shortest path tree used here is equal to the shortest path
774 ///tree used in \ref predNode().
776 ///\pre Either \ref run() or \ref start() must be called before
777 ///using this function.
778 Arc predArc(Node v) const { return (*_pred)[v];}
780 ///Returns the 'previous node' of the shortest path tree for a node.
782 ///This function returns the 'previous node' of the shortest path
783 ///tree for the node \c v, i.e. it returns the last but one node
784 ///from a shortest path from the root(s) to \c v. It is \c INVALID
785 ///if \c v is not reachable from the root(s) or if \c v is a root.
787 ///The shortest path tree used here is equal to the shortest path
788 ///tree used in \ref predArc().
790 ///\pre Either \ref run() or \ref start() must be called before
791 ///using this function.
792 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
793 G->source((*_pred)[v]); }
795 ///\brief Returns a const reference to the node map that stores the
796 /// distances of the nodes.
798 ///Returns a const reference to the node map that stores the distances
799 ///of the nodes calculated by the algorithm.
801 ///\pre Either \ref run() or \ref init()
802 ///must be called before using this function.
803 const DistMap &distMap() const { return *_dist;}
805 ///\brief Returns a const reference to the node map that stores the
808 ///Returns a const reference to the node map that stores the predecessor
809 ///arcs, which form the shortest path tree.
811 ///\pre Either \ref run() or \ref init()
812 ///must be called before using this function.
813 const PredMap &predMap() const { return *_pred;}
815 ///Checks if a node is reachable from the root(s).
817 ///Returns \c true if \c v is reachable from the root(s).
818 ///\pre Either \ref run() or \ref start()
819 ///must be called before using this function.
820 bool reached(Node v) const { return (*_reached)[v]; }
825 ///Default traits class of bfs() function.
827 ///Default traits class of bfs() function.
828 ///\tparam GR Digraph type.
830 struct BfsWizardDefaultTraits
832 ///The type of the digraph the algorithm runs on.
835 ///\brief The type of the map that stores the predecessor
836 ///arcs of the shortest paths.
838 ///The type of the map that stores the predecessor
839 ///arcs of the shortest paths.
840 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
841 typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
842 ///Instantiates a \ref PredMap.
844 ///This function instantiates a \ref PredMap.
845 ///\param g is the digraph, to which we would like to define the
848 static PredMap *createPredMap(const Digraph &g)
850 static PredMap *createPredMap(const Digraph &)
853 return new PredMap();
856 ///The type of the map that indicates which nodes are processed.
858 ///The type of the map that indicates which nodes are processed.
859 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
860 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
861 ///Instantiates a \ref ProcessedMap.
863 ///This function instantiates a \ref ProcessedMap.
864 ///\param g is the digraph, to which
865 ///we would like to define the \ref ProcessedMap.
867 static ProcessedMap *createProcessedMap(const Digraph &g)
869 static ProcessedMap *createProcessedMap(const Digraph &)
872 return new ProcessedMap();
875 ///The type of the map that indicates which nodes are reached.
877 ///The type of the map that indicates which nodes are reached.
878 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
879 typedef typename Digraph::template NodeMap<bool> ReachedMap;
880 ///Instantiates a \ref ReachedMap.
882 ///This function instantiates a \ref ReachedMap.
883 ///\param g is the digraph, to which
884 ///we would like to define the \ref ReachedMap.
885 static ReachedMap *createReachedMap(const Digraph &g)
887 return new ReachedMap(g);
890 ///The type of the map that stores the distances of the nodes.
892 ///The type of the map that stores the distances of the nodes.
893 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
895 typedef NullMap<typename Digraph::Node,int> DistMap;
896 ///Instantiates a \ref DistMap.
898 ///This function instantiates a \ref DistMap.
899 ///\param g is the digraph, to which we would like to define
902 static DistMap *createDistMap(const Digraph &g)
904 static DistMap *createDistMap(const Digraph &)
907 return new DistMap();
911 /// Default traits class used by \ref BfsWizard
913 /// To make it easier to use Bfs algorithm
914 /// we have created a wizard class.
915 /// This \ref BfsWizard class needs default traits,
916 /// as well as the \ref Bfs class.
917 /// The \ref BfsWizardBase is a class to be the default traits of the
918 /// \ref BfsWizard class.
920 class BfsWizardBase : public BfsWizardDefaultTraits<GR>
923 typedef BfsWizardDefaultTraits<GR> Base;
925 //The type of the nodes in the digraph.
926 typedef typename Base::Digraph::Node Node;
928 //Pointer to the digraph the algorithm runs on.
930 //Pointer to the map of reached nodes.
932 //Pointer to the map of processed nodes.
934 //Pointer to the map of predecessors arcs.
936 //Pointer to the map of distances.
938 //Pointer to the source node.
944 /// This constructor does not require parameters, therefore it initiates
945 /// all of the attributes to default values (0, INVALID).
946 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
947 _dist(0), _source(INVALID) {}
951 /// This constructor requires some parameters,
952 /// listed in the parameters list.
953 /// Others are initiated to 0.
954 /// \param g The digraph the algorithm runs on.
955 /// \param s The source node.
956 BfsWizardBase(const GR &g, Node s=INVALID) :
957 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
958 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
962 /// Auxiliary class for the function type interface of BFS algorithm.
964 /// This auxiliary class is created to implement the function type
965 /// interface of \ref Bfs algorithm. It uses the functions and features
966 /// of the plain \ref Bfs, but it is much simpler to use it.
967 /// It should only be used through the \ref bfs() function, which makes
968 /// it easier to use the algorithm.
970 /// Simplicity means that the way to change the types defined
971 /// in the traits class is based on functions that returns the new class
972 /// and not on templatable built-in classes.
973 /// When using the plain \ref Bfs
974 /// the new class with the modified type comes from
975 /// the original class by using the ::
976 /// operator. In the case of \ref BfsWizard only
977 /// a function have to be called, and it will
978 /// return the needed class.
980 /// It does not have own \ref run() method. When its \ref run() method
981 /// is called, it initiates a plain \ref Bfs object, and calls the
982 /// \ref Bfs::run() method of it.
984 class BfsWizard : public TR
988 ///The type of the digraph the algorithm runs on.
989 typedef typename TR::Digraph Digraph;
991 typedef typename Digraph::Node Node;
992 typedef typename Digraph::NodeIt NodeIt;
993 typedef typename Digraph::Arc Arc;
994 typedef typename Digraph::OutArcIt OutArcIt;
996 ///\brief The type of the map that stores the predecessor
997 ///arcs of the shortest paths.
998 typedef typename TR::PredMap PredMap;
999 ///\brief The type of the map that stores the distances of the nodes.
1000 typedef typename TR::DistMap DistMap;
1001 ///\brief The type of the map that indicates which nodes are reached.
1002 typedef typename TR::ReachedMap ReachedMap;
1003 ///\brief The type of the map that indicates which nodes are processed.
1004 typedef typename TR::ProcessedMap ProcessedMap;
1009 BfsWizard() : TR() {}
1011 /// Constructor that requires parameters.
1013 /// Constructor that requires parameters.
1014 /// These parameters will be the default values for the traits class.
1015 BfsWizard(const Digraph &g, Node s=INVALID) :
1019 BfsWizard(const TR &b) : TR(b) {}
1023 ///Runs BFS algorithm from a source node.
1025 ///Runs BFS algorithm from a source node.
1026 ///The node can be given with the \ref source() function.
1029 if(Base::_source==INVALID) throw UninitializedParameter();
1030 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
1032 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
1033 if(Base::_processed)
1034 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1036 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1038 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1039 alg.run(Base::_source);
1042 ///Runs BFS algorithm from the given node.
1044 ///Runs BFS algorithm from the given node.
1045 ///\param s is the given source.
1052 /// Sets the source node, from which the Bfs algorithm runs.
1054 /// Sets the source node, from which the Bfs algorithm runs.
1055 /// \param s is the source node.
1056 BfsWizard<TR> &source(Node s)
1063 struct SetPredMapBase : public Base {
1065 static PredMap *createPredMap(const Digraph &) { return 0; };
1066 SetPredMapBase(const TR &b) : TR(b) {}
1068 ///\brief \ref named-templ-param "Named parameter"
1069 ///for setting \ref PredMap object.
1071 /// \ref named-templ-param "Named parameter"
1072 ///for setting \ref PredMap object.
1074 BfsWizard<SetPredMapBase<T> > predMap(const T &t)
1076 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1077 return BfsWizard<SetPredMapBase<T> >(*this);
1081 struct SetReachedMapBase : public Base {
1082 typedef T ReachedMap;
1083 static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1084 SetReachedMapBase(const TR &b) : TR(b) {}
1086 ///\brief \ref named-templ-param "Named parameter"
1087 ///for setting \ref ReachedMap object.
1089 /// \ref named-templ-param "Named parameter"
1090 ///for setting \ref ReachedMap object.
1092 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
1094 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
1095 return BfsWizard<SetReachedMapBase<T> >(*this);
1099 struct SetProcessedMapBase : public Base {
1100 typedef T ProcessedMap;
1101 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1102 SetProcessedMapBase(const TR &b) : TR(b) {}
1104 ///\brief \ref named-templ-param "Named parameter"
1105 ///for setting \ref ProcessedMap object.
1107 /// \ref named-templ-param "Named parameter"
1108 ///for setting \ref ProcessedMap object.
1110 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1112 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
1113 return BfsWizard<SetProcessedMapBase<T> >(*this);
1117 struct SetDistMapBase : public Base {
1119 static DistMap *createDistMap(const Digraph &) { return 0; };
1120 SetDistMapBase(const TR &b) : TR(b) {}
1122 ///\brief \ref named-templ-param "Named parameter"
1123 ///for setting \ref DistMap object.
1125 /// \ref named-templ-param "Named parameter"
1126 ///for setting \ref DistMap object.
1128 BfsWizard<SetDistMapBase<T> > distMap(const T &t)
1130 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1131 return BfsWizard<SetDistMapBase<T> >(*this);
1136 ///Function type interface for Bfs algorithm.
1139 ///Function type interface for Bfs algorithm.
1141 ///This function also has several
1142 ///\ref named-templ-func-param "named parameters",
1143 ///they are declared as the members of class \ref BfsWizard.
1145 ///example shows how to use these parameters.
1147 /// bfs(g,source).predMap(preds).run();
1149 ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
1150 ///to the end of the parameter list.
1154 BfsWizard<BfsWizardBase<GR> >
1155 bfs(const GR &g,typename GR::Node s=INVALID)
1157 return BfsWizard<BfsWizardBase<GR> >(g,s);
1161 /// \brief Visitor class for BFS.
1163 /// This class defines the interface of the BfsVisit events, and
1164 /// it could be the base of a real visitor class.
1165 template <typename _Digraph>
1167 typedef _Digraph Digraph;
1168 typedef typename Digraph::Arc Arc;
1169 typedef typename Digraph::Node Node;
1170 /// \brief Called for the source node(s) of the BFS.
1172 /// This function is called for the source node(s) of the BFS.
1173 void start(const Node& node) {}
1174 /// \brief Called when a node is reached first time.
1176 /// This function is called when a node is reached first time.
1177 void reach(const Node& node) {}
1178 /// \brief Called when a node is processed.
1180 /// This function is called when a node is processed.
1181 void process(const Node& node) {}
1182 /// \brief Called when an arc reaches a new node.
1184 /// This function is called when the BFS finds an arc whose target node
1185 /// is not reached yet.
1186 void discover(const Arc& arc) {}
1187 /// \brief Called when an arc is examined but its target node is
1188 /// already discovered.
1190 /// This function is called when an arc is examined but its target node is
1191 /// already discovered.
1192 void examine(const Arc& arc) {}
1195 template <typename _Digraph>
1197 typedef _Digraph Digraph;
1198 typedef typename Digraph::Arc Arc;
1199 typedef typename Digraph::Node Node;
1200 void start(const Node&) {}
1201 void reach(const Node&) {}
1202 void process(const Node&) {}
1203 void discover(const Arc&) {}
1204 void examine(const Arc&) {}
1206 template <typename _Visitor>
1207 struct Constraints {
1208 void constraints() {
1211 visitor.start(node);
1212 visitor.reach(node);
1213 visitor.process(node);
1214 visitor.discover(arc);
1215 visitor.examine(arc);
1222 /// \brief Default traits class of BfsVisit class.
1224 /// Default traits class of BfsVisit class.
1225 /// \tparam _Digraph The type of the digraph the algorithm runs on.
1226 template<class _Digraph>
1227 struct BfsVisitDefaultTraits {
1229 /// \brief The type of the digraph the algorithm runs on.
1230 typedef _Digraph Digraph;
1232 /// \brief The type of the map that indicates which nodes are reached.
1234 /// The type of the map that indicates which nodes are reached.
1235 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1236 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1238 /// \brief Instantiates a \ref ReachedMap.
1240 /// This function instantiates a \ref ReachedMap.
1241 /// \param digraph is the digraph, to which
1242 /// we would like to define the \ref ReachedMap.
1243 static ReachedMap *createReachedMap(const Digraph &digraph) {
1244 return new ReachedMap(digraph);
1251 /// \brief %BFS algorithm class with visitor interface.
1253 /// This class provides an efficient implementation of the %BFS algorithm
1254 /// with visitor interface.
1256 /// The %BfsVisit class provides an alternative interface to the Bfs
1257 /// class. It works with callback mechanism, the BfsVisit object calls
1258 /// the member functions of the \c Visitor class on every BFS event.
1260 /// This interface of the BFS algorithm should be used in special cases
1261 /// when extra actions have to be performed in connection with certain
1262 /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()
1265 /// \tparam _Digraph The type of the digraph the algorithm runs on.
1266 /// The default value is
1267 /// \ref ListDigraph. The value of _Digraph is not used directly by
1268 /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
1269 /// \tparam _Visitor The Visitor type that is used by the algorithm.
1270 /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
1271 /// does not observe the BFS events. If you want to observe the BFS
1272 /// events, you should implement your own visitor class.
1273 /// \tparam _Traits Traits class to set various data types used by the
1274 /// algorithm. The default traits class is
1275 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
1276 /// See \ref BfsVisitDefaultTraits for the documentation of
1277 /// a BFS visit traits class.
1279 template <typename _Digraph, typename _Visitor, typename _Traits>
1281 template <typename _Digraph = ListDigraph,
1282 typename _Visitor = BfsVisitor<_Digraph>,
1283 typename _Traits = BfsDefaultTraits<_Digraph> >
1288 /// \brief \ref Exception for uninitialized parameters.
1290 /// This error represents problems in the initialization
1291 /// of the parameters of the algorithm.
1292 class UninitializedParameter : public lemon::UninitializedParameter {
1294 virtual const char* what() const throw()
1296 return "lemon::BfsVisit::UninitializedParameter";
1300 ///The traits class.
1301 typedef _Traits Traits;
1303 ///The type of the digraph the algorithm runs on.
1304 typedef typename Traits::Digraph Digraph;
1306 ///The visitor type used by the algorithm.
1307 typedef _Visitor Visitor;
1309 ///The type of the map that indicates which nodes are reached.
1310 typedef typename Traits::ReachedMap ReachedMap;
1314 typedef typename Digraph::Node Node;
1315 typedef typename Digraph::NodeIt NodeIt;
1316 typedef typename Digraph::Arc Arc;
1317 typedef typename Digraph::OutArcIt OutArcIt;
1319 //Pointer to the underlying digraph.
1320 const Digraph *_digraph;
1321 //Pointer to the visitor object.
1323 //Pointer to the map of reached status of the nodes.
1324 ReachedMap *_reached;
1325 //Indicates if _reached is locally allocated (true) or not.
1328 std::vector<typename Digraph::Node> _list;
1329 int _list_front, _list_back;
1331 //Creates the maps if necessary.
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