2 * lemon/bfs.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
22 ///\brief Bfs algorithm.
24 #include <lemon/list_graph.h>
25 #include <lemon/graph_utils.h>
26 #include <lemon/invalid.h>
27 #include <lemon/error.h>
28 #include <lemon/maps.h>
34 ///Default traits class of Bfs class.
36 ///Default traits class of Bfs class.
37 ///\param GR Graph type.
39 struct BfsDefaultTraits
41 ///The graph type the algorithm runs on.
43 ///\brief The type of the map that stores the last
44 ///edges of the shortest paths.
46 ///The type of the map that stores the last
47 ///edges of the shortest paths.
48 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
50 typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
51 ///Instantiates a PredMap.
53 ///This function instantiates a \ref PredMap.
54 ///\param G is the graph, to which we would like to define the PredMap.
55 ///\todo The graph alone may be insufficient to initialize
56 static PredMap *createPredMap(const GR &G)
58 return new PredMap(G);
60 ///The type of the map that indicates which nodes are processed.
62 ///The type of the map that indicates which nodes are processed.
63 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
64 ///\todo named parameter to set this type, function to read and write.
65 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
66 ///Instantiates a ProcessedMap.
68 ///This function instantiates a \ref ProcessedMap.
69 ///\param g is the graph, to which
70 ///we would like to define the \ref ProcessedMap
72 static ProcessedMap *createProcessedMap(const GR &g)
74 static ProcessedMap *createProcessedMap(const GR &)
77 return new ProcessedMap();
79 ///The type of the map that indicates which nodes are reached.
81 ///The type of the map that indicates which nodes are reached.
82 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
83 ///\todo named parameter to set this type, function to read and write.
84 typedef typename Graph::template NodeMap<bool> ReachedMap;
85 ///Instantiates a ReachedMap.
87 ///This function instantiates a \ref ReachedMap.
88 ///\param G is the graph, to which
89 ///we would like to define the \ref ReachedMap.
90 static ReachedMap *createReachedMap(const GR &G)
92 return new ReachedMap(G);
94 ///The type of the map that stores the dists of the nodes.
96 ///The type of the map that stores the dists of the nodes.
97 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
99 typedef typename Graph::template NodeMap<int> DistMap;
100 ///Instantiates a DistMap.
102 ///This function instantiates a \ref DistMap.
103 ///\param G is the graph, to which we would like to define the \ref DistMap
104 static DistMap *createDistMap(const GR &G)
106 return new DistMap(G);
110 ///%BFS algorithm class.
113 ///This class provides an efficient implementation of the %BFS algorithm.
115 ///\param GR The graph type the algorithm runs on. The default value is
116 ///\ref ListGraph. The value of GR is not used directly by Bfs, it
117 ///is only passed to \ref BfsDefaultTraits.
118 ///\param TR Traits class to set various data types used by the algorithm.
119 ///The default traits class is
120 ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
121 ///See \ref BfsDefaultTraits for the documentation of
122 ///a Bfs traits class.
124 ///\author Alpar Juttner
127 template <typename GR,
130 template <typename GR=ListGraph,
131 typename TR=BfsDefaultTraits<GR> >
136 * \brief \ref Exception for uninitialized parameters.
138 * This error represents problems in the initialization
139 * of the parameters of the algorithms.
141 class UninitializedParameter : public lemon::UninitializedParameter {
143 virtual const char* exceptionName() const {
144 return "lemon::Bfs::UninitializedParameter";
149 ///The type of the underlying graph.
150 typedef typename TR::Graph Graph;
152 typedef typename Graph::Node Node;
154 typedef typename Graph::NodeIt NodeIt;
156 typedef typename Graph::Edge Edge;
158 typedef typename Graph::OutEdgeIt OutEdgeIt;
160 ///\brief The type of the map that stores the last
161 ///edges of the shortest paths.
162 typedef typename TR::PredMap PredMap;
163 ///The type of the map indicating which nodes are reached.
164 typedef typename TR::ReachedMap ReachedMap;
165 ///The type of the map indicating which nodes are processed.
166 typedef typename TR::ProcessedMap ProcessedMap;
167 ///The type of the map that stores the dists of the nodes.
168 typedef typename TR::DistMap DistMap;
170 /// Pointer to the underlying graph.
172 ///Pointer to the map of predecessors edges.
174 ///Indicates if \ref _pred is locally allocated (\c true) or not.
176 ///Pointer to the map of distances.
178 ///Indicates if \ref _dist is locally allocated (\c true) or not.
180 ///Pointer to the map of reached status of the nodes.
181 ReachedMap *_reached;
182 ///Indicates if \ref _reached is locally allocated (\c true) or not.
184 ///Pointer to the map of processed status of the nodes.
185 ProcessedMap *_processed;
186 ///Indicates if \ref _processed is locally allocated (\c true) or not.
187 bool local_processed;
189 std::vector<typename Graph::Node> _queue;
190 int _queue_head,_queue_tail,_queue_next_dist;
193 ///Creates the maps if necessary.
195 ///\todo Error if \c G are \c NULL.
196 ///\todo Better memory allocation (instead of new).
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 DefPredMapTraits : public Traits {
232 static PredMap *createPredMap(const Graph &G)
234 throw UninitializedParameter();
237 ///\ref named-templ-param "Named parameter" for setting PredMap type
239 ///\ref named-templ-param "Named parameter" for setting PredMap type
242 struct DefPredMap : public Bfs< Graph, DefPredMapTraits<T> > {
243 typedef Bfs< Graph, DefPredMapTraits<T> > Create;
247 struct DefDistMapTraits : public Traits {
249 static DistMap *createDistMap(const Graph &G)
251 throw UninitializedParameter();
254 ///\ref named-templ-param "Named parameter" for setting DistMap type
256 ///\ref named-templ-param "Named parameter" for setting DistMap type
259 struct DefDistMap : public Bfs< Graph, DefDistMapTraits<T> > {
260 typedef Bfs< Graph, DefDistMapTraits<T> > Create;
264 struct DefReachedMapTraits : public Traits {
265 typedef T ReachedMap;
266 static ReachedMap *createReachedMap(const Graph &G)
268 throw UninitializedParameter();
271 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
273 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
276 struct DefReachedMap : public Bfs< Graph, DefReachedMapTraits<T> > {
277 typedef Bfs< Graph, DefReachedMapTraits<T> > Create;
281 struct DefProcessedMapTraits : public Traits {
282 typedef T ProcessedMap;
283 static ProcessedMap *createProcessedMap(const Graph &G)
285 throw UninitializedParameter();
288 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
290 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
293 struct DefProcessedMap : public Bfs< Graph, DefProcessedMapTraits<T> > {
294 typedef Bfs< Graph, DefProcessedMapTraits<T> > Create;
297 struct DefGraphProcessedMapTraits : public Traits {
298 typedef typename Graph::template NodeMap<bool> ProcessedMap;
299 static ProcessedMap *createProcessedMap(const Graph &G)
301 return new ProcessedMap(G);
304 ///\brief \ref named-templ-param "Named parameter"
305 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
307 ///\ref named-templ-param "Named parameter"
308 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
309 ///If you don't set it explicitly, it will be automatically allocated.
311 struct DefProcessedMapToBeDefaultMap :
312 public Bfs< Graph, DefGraphProcessedMapTraits> {
313 typedef Bfs< Graph, DefGraphProcessedMapTraits> Create;
322 ///\param _G the graph the algorithm will run on.
324 Bfs(const Graph& _G) :
326 _pred(NULL), local_pred(false),
327 _dist(NULL), local_dist(false),
328 _reached(NULL), local_reached(false),
329 _processed(NULL), local_processed(false)
335 if(local_pred) delete _pred;
336 if(local_dist) delete _dist;
337 if(local_reached) delete _reached;
338 if(local_processed) delete _processed;
341 ///Sets the map storing the predecessor edges.
343 ///Sets the map storing the predecessor edges.
344 ///If you don't use this function before calling \ref run(),
345 ///it will allocate one. The destructor deallocates this
346 ///automatically allocated map, of course.
347 ///\return <tt> (*this) </tt>
348 Bfs &predMap(PredMap &m)
358 ///Sets the map indicating the reached nodes.
360 ///Sets the map indicating the reached nodes.
361 ///If you don't use this function before calling \ref run(),
362 ///it will allocate one. The destructor deallocates this
363 ///automatically allocated map, of course.
364 ///\return <tt> (*this) </tt>
365 Bfs &reachedMap(ReachedMap &m)
375 ///Sets the map indicating the processed nodes.
377 ///Sets the map indicating the processed nodes.
378 ///If you don't use this function before calling \ref run(),
379 ///it will allocate one. The destructor deallocates this
380 ///automatically allocated map, of course.
381 ///\return <tt> (*this) </tt>
382 Bfs &processedMap(ProcessedMap &m)
384 if(local_processed) {
386 local_processed=false;
392 ///Sets the map storing the distances calculated by the algorithm.
394 ///Sets the map storing the distances calculated by the algorithm.
395 ///If you don't use this function before calling \ref run(),
396 ///it will allocate one. The destructor deallocates this
397 ///automatically allocated map, of course.
398 ///\return <tt> (*this) </tt>
399 Bfs &distMap(DistMap &m)
410 ///\name Execution control
411 ///The simplest way to execute the algorithm is to use
412 ///one of the member functions called \c run(...).
414 ///If you need more control on the execution,
415 ///first you must call \ref init(), then you can add several source nodes
416 ///with \ref addSource().
417 ///Finally \ref start() will perform the actual path
422 ///Initializes the internal data structures.
424 ///Initializes the internal data structures.
429 _queue.resize(countNodes(*G));
430 _queue_head=_queue_tail=0;
432 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
433 _pred->set(u,INVALID);
434 _reached->set(u,false);
435 _processed->set(u,false);
439 ///Adds a new source node.
441 ///Adds a new source node to the set of nodes to be processed.
443 void addSource(Node s)
447 _reached->set(s,true);
448 _pred->set(s,INVALID);
450 _queue[_queue_head++]=s;
451 _queue_next_dist=_queue_head;
455 ///Processes the next node.
457 ///Processes the next node.
459 ///\return The processed node.
461 ///\warning The queue must not be empty!
462 Node processNextNode()
464 if(_queue_tail==_queue_next_dist) {
466 _queue_next_dist=_queue_head;
468 Node n=_queue[_queue_tail++];
469 _processed->set(n,true);
471 for(OutEdgeIt e(*G,n);e!=INVALID;++e)
472 if(!(*_reached)[m=G->target(e)]) {
473 _queue[_queue_head++]=m;
474 _reached->set(m,true);
476 _dist->set(m,_curr_dist);
481 ///Next node to be processed.
483 ///Next node to be processed.
485 ///\return The next node to be processed or INVALID if the queue is
489 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
492 ///\brief Returns \c false if there are nodes
493 ///to be processed in the queue
495 ///Returns \c false if there are nodes
496 ///to be processed in the queue
497 bool emptyQueue() { return _queue_tail==_queue_head; }
498 ///Returns the number of the nodes to be processed.
500 ///Returns the number of the nodes to be processed in the queue.
502 int queueSize() { return _queue_head-_queue_tail; }
504 ///Executes the algorithm.
506 ///Executes the algorithm.
508 ///\pre init() must be called and at least one node should be added
509 ///with addSource() before using this function.
511 ///This method runs the %BFS algorithm from the root node(s)
514 ///shortest path to each node. The algorithm computes
515 ///- The shortest path tree.
516 ///- The distance of each node from the root(s).
520 while ( !emptyQueue() ) processNextNode();
523 ///Executes the algorithm until \c dest is reached.
525 ///Executes the algorithm until \c dest is reached.
527 ///\pre init() must be called and at least one node should be added
528 ///with addSource() before using this function.
530 ///This method runs the %BFS algorithm from the root node(s)
533 ///shortest path to \c dest. The algorithm computes
534 ///- The shortest path to \c dest.
535 ///- The distance of \c dest from the root(s).
537 void start(Node dest)
539 while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextNode();
542 ///Executes the algorithm until a condition is met.
544 ///Executes the algorithm until a condition is met.
546 ///\pre init() must be called and at least one node should be added
547 ///with addSource() before using this function.
549 ///\param nm must be a bool (or convertible) node map. The algorithm
550 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
552 void start(const NM &nm)
554 while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextNode();
557 ///Runs %BFS algorithm from node \c s.
559 ///This method runs the %BFS algorithm from a root node \c s
562 ///shortest path to each node. The algorithm computes
563 ///- The shortest path tree.
564 ///- The distance of each node from the root.
566 ///\note d.run(s) is just a shortcut of the following code.
578 ///Finds the shortest path between \c s and \c t.
580 ///Finds the shortest path between \c s and \c t.
582 ///\return The length of the shortest s---t path if there exists one,
584 ///\note Apart from the return value, d.run(s) is
585 ///just a shortcut of the following code.
591 int run(Node s,Node t) {
595 return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
600 ///\name Query Functions
601 ///The result of the %BFS algorithm can be obtained using these
603 ///Before the use of these functions,
604 ///either run() or start() must be called.
608 ///Copies the shortest path to \c t into \c p
610 ///This function copies the shortest path to \c t into \c p.
611 ///If \c t is a source itself or unreachable, then it does not
613 ///\todo Is it the right way to handle unreachable nodes?
614 ///\return Returns \c true if a path to \c t was actually copied to \c p,
615 ///\c false otherwise.
618 bool getPath(P &p,Node t)
622 typename P::Builder b(p);
623 for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
624 b.pushFront(pred(t));
631 ///The distance of a node from the root(s).
633 ///Returns the distance of a node from the root(s).
634 ///\pre \ref run() must be called before using this function.
635 ///\warning If node \c v in unreachable from the root(s) the return value
636 ///of this function is undefined.
637 int dist(Node v) const { return (*_dist)[v]; }
639 ///Returns the 'previous edge' of the shortest path tree.
641 ///For a node \c v it returns the 'previous edge'
642 ///of the shortest path tree,
643 ///i.e. it returns the last edge of a shortest path from the root(s) to \c
644 ///v. It is \ref INVALID
645 ///if \c v is unreachable from the root(s) or \c v is a root. The
646 ///shortest path tree used here is equal to the shortest path tree used in
648 ///\pre Either \ref run() or \ref start() must be called before using
650 ///\todo predEdge could be a better name.
651 Edge pred(Node v) const { return (*_pred)[v];}
653 ///Returns the 'previous node' of the shortest path tree.
655 ///For a node \c v it returns the 'previous node'
656 ///of the shortest path tree,
657 ///i.e. it returns the last but one node from a shortest path from the
659 ///It is INVALID if \c v is unreachable from the root(s) or
660 ///if \c v itself a root.
661 ///The shortest path tree used here is equal to the shortest path
662 ///tree used in \ref pred().
663 ///\pre Either \ref run() or \ref start() must be called before
664 ///using this function.
665 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
666 G->source((*_pred)[v]); }
668 ///Returns a reference to the NodeMap of distances.
670 ///Returns a reference to the NodeMap of distances.
671 ///\pre Either \ref run() or \ref init() must
672 ///be called before using this function.
673 const DistMap &distMap() const { return *_dist;}
675 ///Returns a reference to the shortest path tree map.
677 ///Returns a reference to the NodeMap of the edges of the
678 ///shortest path tree.
679 ///\pre Either \ref run() or \ref init()
680 ///must be called before using this function.
681 const PredMap &predMap() const { return *_pred;}
683 ///Checks if a node is reachable from the root.
685 ///Returns \c true if \c v is reachable from the root.
686 ///\warning The source nodes are indicated as unreached.
687 ///\pre Either \ref run() or \ref start()
688 ///must be called before using this function.
690 bool reached(Node v) { return (*_reached)[v]; }
695 ///Default traits class of Bfs function.
697 ///Default traits class of Bfs function.
698 ///\param GR Graph type.
700 struct BfsWizardDefaultTraits
702 ///The graph type the algorithm runs on.
704 ///\brief The type of the map that stores the last
705 ///edges of the shortest paths.
707 ///The type of the map that stores the last
708 ///edges of the shortest paths.
709 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
711 typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
712 ///Instantiates a PredMap.
714 ///This function instantiates a \ref PredMap.
715 ///\param g is the graph, to which we would like to define the PredMap.
716 ///\todo The graph alone may be insufficient to initialize
718 static PredMap *createPredMap(const GR &g)
720 static PredMap *createPredMap(const GR &)
723 return new PredMap();
726 ///The type of the map that indicates which nodes are processed.
728 ///The type of the map that indicates which nodes are processed.
729 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
730 ///\todo named parameter to set this type, function to read and write.
731 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
732 ///Instantiates a ProcessedMap.
734 ///This function instantiates a \ref ProcessedMap.
735 ///\param g is the graph, to which
736 ///we would like to define the \ref ProcessedMap
738 static ProcessedMap *createProcessedMap(const GR &g)
740 static ProcessedMap *createProcessedMap(const GR &)
743 return new ProcessedMap();
745 ///The type of the map that indicates which nodes are reached.
747 ///The type of the map that indicates which nodes are reached.
748 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
749 ///\todo named parameter to set this type, function to read and write.
750 typedef typename Graph::template NodeMap<bool> ReachedMap;
751 ///Instantiates a ReachedMap.
753 ///This function instantiates a \ref ReachedMap.
754 ///\param G is the graph, to which
755 ///we would like to define the \ref ReachedMap.
756 static ReachedMap *createReachedMap(const GR &G)
758 return new ReachedMap(G);
760 ///The type of the map that stores the dists of the nodes.
762 ///The type of the map that stores the dists of the nodes.
763 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
765 typedef NullMap<typename Graph::Node,int> DistMap;
766 ///Instantiates a DistMap.
768 ///This function instantiates a \ref DistMap.
769 ///\param g is the graph, to which we would like to define the \ref DistMap
771 static DistMap *createDistMap(const GR &g)
773 static DistMap *createDistMap(const GR &)
776 return new DistMap();
780 /// Default traits used by \ref BfsWizard
782 /// To make it easier to use Bfs algorithm
783 ///we have created a wizard class.
784 /// This \ref BfsWizard class needs default traits,
785 ///as well as the \ref Bfs class.
786 /// The \ref BfsWizardBase is a class to be the default traits of the
787 /// \ref BfsWizard class.
789 class BfsWizardBase : public BfsWizardDefaultTraits<GR>
792 typedef BfsWizardDefaultTraits<GR> Base;
794 /// Type of the nodes in the graph.
795 typedef typename Base::Graph::Node Node;
797 /// Pointer to the underlying graph.
799 ///Pointer to the map of reached nodes.
801 ///Pointer to the map of processed nodes.
803 ///Pointer to the map of predecessors edges.
805 ///Pointer to the map of distances.
807 ///Pointer to the source node.
813 /// This constructor does not require parameters, therefore it initiates
814 /// all of the attributes to default values (0, INVALID).
815 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
816 _dist(0), _source(INVALID) {}
820 /// This constructor requires some parameters,
821 /// listed in the parameters list.
822 /// Others are initiated to 0.
823 /// \param g is the initial value of \ref _g
824 /// \param s is the initial value of \ref _source
825 BfsWizardBase(const GR &g, Node s=INVALID) :
826 _g((void *)&g), _reached(0), _processed(0), _pred(0),
827 _dist(0), _source(s) {}
831 /// A class to make the usage of Bfs algorithm easier
833 /// This class is created to make it easier to use Bfs algorithm.
834 /// It uses the functions and features of the plain \ref Bfs,
835 /// but it is much simpler to use it.
837 /// Simplicity means that the way to change the types defined
838 /// in the traits class is based on functions that returns the new class
839 /// and not on templatable built-in classes.
840 /// When using the plain \ref Bfs
841 /// the new class with the modified type comes from
842 /// the original class by using the ::
843 /// operator. In the case of \ref BfsWizard only
844 /// a function have to be called and it will
845 /// return the needed class.
847 /// It does not have own \ref run method. When its \ref run method is called
848 /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run
851 class BfsWizard : public TR
855 ///The type of the underlying graph.
856 typedef typename TR::Graph Graph;
858 typedef typename Graph::Node Node;
860 typedef typename Graph::NodeIt NodeIt;
862 typedef typename Graph::Edge Edge;
864 typedef typename Graph::OutEdgeIt OutEdgeIt;
866 ///\brief The type of the map that stores
868 typedef typename TR::ReachedMap ReachedMap;
869 ///\brief The type of the map that stores
870 ///the processed nodes
871 typedef typename TR::ProcessedMap ProcessedMap;
872 ///\brief The type of the map that stores the last
873 ///edges of the shortest paths.
874 typedef typename TR::PredMap PredMap;
875 ///The type of the map that stores the dists of the nodes.
876 typedef typename TR::DistMap DistMap;
880 BfsWizard() : TR() {}
882 /// Constructor that requires parameters.
884 /// Constructor that requires parameters.
885 /// These parameters will be the default values for the traits class.
886 BfsWizard(const Graph &g, Node s=INVALID) :
890 BfsWizard(const TR &b) : TR(b) {}
894 ///Runs Bfs algorithm from a given node.
896 ///Runs Bfs algorithm from a given node.
897 ///The node can be given by the \ref source function.
900 if(Base::_source==INVALID) throw UninitializedParameter();
901 Bfs<Graph,TR> alg(*(Graph*)Base::_g);
903 alg.reachedMap(*(ReachedMap*)Base::_reached);
904 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
905 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
906 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
907 alg.run(Base::_source);
910 ///Runs Bfs algorithm from the given node.
912 ///Runs Bfs algorithm from the given node.
913 ///\param s is the given source.
921 struct DefPredMapBase : public Base {
923 static PredMap *createPredMap(const Graph &) { return 0; };
924 DefPredMapBase(const TR &b) : TR(b) {}
927 ///\brief \ref named-templ-param "Named parameter"
928 ///function for setting PredMap
930 /// \ref named-templ-param "Named parameter"
931 ///function for setting PredMap
934 BfsWizard<DefPredMapBase<T> > predMap(const T &t)
936 Base::_pred=(void *)&t;
937 return BfsWizard<DefPredMapBase<T> >(*this);
942 struct DefReachedMapBase : public Base {
943 typedef T ReachedMap;
944 static ReachedMap *createReachedMap(const Graph &) { return 0; };
945 DefReachedMapBase(const TR &b) : TR(b) {}
948 ///\brief \ref named-templ-param "Named parameter"
949 ///function for setting ReachedMap
951 /// \ref named-templ-param "Named parameter"
952 ///function for setting ReachedMap
955 BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
957 Base::_pred=(void *)&t;
958 return BfsWizard<DefReachedMapBase<T> >(*this);
963 struct DefProcessedMapBase : public Base {
964 typedef T ProcessedMap;
965 static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
966 DefProcessedMapBase(const TR &b) : TR(b) {}
969 ///\brief \ref named-templ-param "Named parameter"
970 ///function for setting ProcessedMap
972 /// \ref named-templ-param "Named parameter"
973 ///function for setting ProcessedMap
976 BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
978 Base::_pred=(void *)&t;
979 return BfsWizard<DefProcessedMapBase<T> >(*this);
984 struct DefDistMapBase : public Base {
986 static DistMap *createDistMap(const Graph &) { return 0; };
987 DefDistMapBase(const TR &b) : TR(b) {}
990 ///\brief \ref named-templ-param "Named parameter"
991 ///function for setting DistMap type
993 /// \ref named-templ-param "Named parameter"
994 ///function for setting DistMap type
997 BfsWizard<DefDistMapBase<T> > distMap(const T &t)
999 Base::_dist=(void *)&t;
1000 return BfsWizard<DefDistMapBase<T> >(*this);
1003 /// Sets the source node, from which the Bfs algorithm runs.
1005 /// Sets the source node, from which the Bfs algorithm runs.
1006 /// \param s is the source node.
1007 BfsWizard<TR> &source(Node s)
1015 ///Function type interface for Bfs algorithm.
1017 /// \ingroup flowalgs
1018 ///Function type interface for Bfs algorithm.
1020 ///This function also has several
1021 ///\ref named-templ-func-param "named parameters",
1022 ///they are declared as the members of class \ref BfsWizard.
1024 ///example shows how to use these parameters.
1026 /// bfs(g,source).predMap(preds).run();
1028 ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
1029 ///to the end of the parameter list.
1033 BfsWizard<BfsWizardBase<GR> >
1034 bfs(const GR &g,typename GR::Node s=INVALID)
1036 return BfsWizard<BfsWizardBase<GR> >(g,s);
1039 } //END OF NAMESPACE LEMON