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
125 ///\todo A compare object would be nice.
128 template <typename GR,
131 template <typename GR=ListGraph,
132 typename TR=BfsDefaultTraits<GR> >
137 * \brief \ref Exception for uninitialized parameters.
139 * This error represents problems in the initialization
140 * of the parameters of the algorithms.
142 class UninitializedParameter : public lemon::UninitializedParameter {
144 virtual const char* exceptionName() const {
145 return "lemon::Bfs::UninitializedParameter";
150 ///The type of the underlying graph.
151 typedef typename TR::Graph Graph;
153 typedef typename Graph::Node Node;
155 typedef typename Graph::NodeIt NodeIt;
157 typedef typename Graph::Edge Edge;
159 typedef typename Graph::OutEdgeIt OutEdgeIt;
161 ///\brief The type of the map that stores the last
162 ///edges of the shortest paths.
163 typedef typename TR::PredMap PredMap;
164 ///The type of the map indicating which nodes are reached.
165 typedef typename TR::ReachedMap ReachedMap;
166 ///The type of the map indicating which nodes are processed.
167 typedef typename TR::ProcessedMap ProcessedMap;
168 ///The type of the map that stores the dists of the nodes.
169 typedef typename TR::DistMap DistMap;
171 /// Pointer to the underlying graph.
173 ///Pointer to the map of predecessors edges.
175 ///Indicates if \ref _pred is locally allocated (\c true) or not.
177 ///Pointer to the map of distances.
179 ///Indicates if \ref _dist is locally allocated (\c true) or not.
181 ///Pointer to the map of reached status of the nodes.
182 ReachedMap *_reached;
183 ///Indicates if \ref _reached is locally allocated (\c true) or not.
185 ///Pointer to the map of processed status of the nodes.
186 ProcessedMap *_processed;
187 ///Indicates if \ref _processed is locally allocated (\c true) or not.
188 bool local_processed;
190 std::vector<typename Graph::Node> _queue;
191 int _queue_head,_queue_tail,_queue_next_dist;
194 ///Creates the maps if necessary.
196 ///\todo Error if \c G are \c NULL.
197 ///\todo Better memory allocation (instead of new).
202 _pred = Traits::createPredMap(*G);
206 _dist = Traits::createDistMap(*G);
209 local_reached = true;
210 _reached = Traits::createReachedMap(*G);
213 local_processed = true;
214 _processed = Traits::createProcessedMap(*G);
220 ///\name Named template parameters
225 struct DefPredMapTraits : public Traits {
227 static PredMap *createPredMap(const Graph &G)
229 throw UninitializedParameter();
232 ///\ref named-templ-param "Named parameter" for setting PredMap type
234 ///\ref named-templ-param "Named parameter" for setting PredMap type
237 struct DefPredMap : public Bfs< Graph, DefPredMapTraits<T> > {
238 typedef Bfs< Graph, DefPredMapTraits<T> > Create;
242 struct DefDistMapTraits : public Traits {
244 static DistMap *createDistMap(const Graph &G)
246 throw UninitializedParameter();
249 ///\ref named-templ-param "Named parameter" for setting DistMap type
251 ///\ref named-templ-param "Named parameter" for setting DistMap type
254 struct DefDistMap : public Bfs< Graph, DefDistMapTraits<T> > {
255 typedef Bfs< Graph, DefDistMapTraits<T> > Create;
259 struct DefReachedMapTraits : public Traits {
260 typedef T ReachedMap;
261 static ReachedMap *createReachedMap(const Graph &G)
263 throw UninitializedParameter();
266 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
268 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
271 struct DefReachedMap : public Bfs< Graph, DefReachedMapTraits<T> > {
272 typedef Bfs< Graph, DefReachedMapTraits<T> > Create;
276 struct DefProcessedMapTraits : public Traits {
277 typedef T ProcessedMap;
278 static ProcessedMap *createProcessedMap(const Graph &G)
280 throw UninitializedParameter();
283 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
285 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
288 struct DefProcessedMap : public Bfs< Graph, DefProcessedMapTraits<T> > {
289 typedef Bfs< Graph, DefProcessedMapTraits<T> > Create;
292 struct DefGraphProcessedMapTraits : public Traits {
293 typedef typename Graph::template NodeMap<bool> ProcessedMap;
294 static ProcessedMap *createProcessedMap(const Graph &G)
296 return new ProcessedMap(G);
299 ///\brief \ref named-templ-param "Named parameter"
300 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
302 ///\ref named-templ-param "Named parameter"
303 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
304 ///If you don't set it explicitly, it will be automatically allocated.
306 struct DefProcessedMapToBeDefaultMap :
307 public Bfs< Graph, DefGraphProcessedMapTraits> {
308 typedef Bfs< Graph, DefGraphProcessedMapTraits> Create;
317 ///\param _G the graph the algorithm will run on.
319 Bfs(const Graph& _G) :
321 _pred(NULL), local_pred(false),
322 _dist(NULL), local_dist(false),
323 _reached(NULL), local_reached(false),
324 _processed(NULL), local_processed(false)
330 if(local_pred) delete _pred;
331 if(local_dist) delete _dist;
332 if(local_reached) delete _reached;
333 if(local_processed) delete _processed;
336 ///Sets the map storing the predecessor edges.
338 ///Sets the map storing the predecessor edges.
339 ///If you don't use this function before calling \ref run(),
340 ///it will allocate one. The destructor deallocates this
341 ///automatically allocated map, of course.
342 ///\return <tt> (*this) </tt>
343 Bfs &predMap(PredMap &m)
353 ///Sets the map indicating the reached nodes.
355 ///Sets the map indicating the reached nodes.
356 ///If you don't use this function before calling \ref run(),
357 ///it will allocate one. The destructor deallocates this
358 ///automatically allocated map, of course.
359 ///\return <tt> (*this) </tt>
360 Bfs &reachedMap(ReachedMap &m)
370 ///Sets the map indicating the processed nodes.
372 ///Sets the map indicating the processed nodes.
373 ///If you don't use this function before calling \ref run(),
374 ///it will allocate one. The destructor deallocates this
375 ///automatically allocated map, of course.
376 ///\return <tt> (*this) </tt>
377 Bfs &processedMap(ProcessedMap &m)
379 if(local_processed) {
381 local_processed=false;
387 ///Sets the map storing the distances calculated by the algorithm.
389 ///Sets the map storing the distances calculated by the algorithm.
390 ///If you don't use this function before calling \ref run(),
391 ///it will allocate one. The destructor deallocates this
392 ///automatically allocated map, of course.
393 ///\return <tt> (*this) </tt>
394 Bfs &distMap(DistMap &m)
405 ///\name Execution control
406 ///The simplest way to execute the algorithm is to use
407 ///one of the member functions called \c run(...).
409 ///If you need more control on the execution,
410 ///first you must call \ref init(), then you can add several source nodes
411 ///with \ref addSource().
412 ///Finally \ref start() will perform the actual path
417 ///Initializes the internal data structures.
419 ///Initializes the internal data structures.
424 _queue.resize(countNodes(*G));
425 _queue_head=_queue_tail=0;
427 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
428 _pred->set(u,INVALID);
429 _reached->set(u,false);
430 _processed->set(u,false);
434 ///Adds a new source node.
436 ///Adds a new source node to the set of nodes to be processed.
438 void addSource(Node s)
442 _reached->set(s,true);
443 _pred->set(s,INVALID);
445 _queue[_queue_head++]=s;
446 _queue_next_dist=_queue_head;
450 ///Processes the next node.
452 ///Processes the next node.
454 ///\return The processed node.
456 ///\warning The queue must not be empty!
457 Node processNextNode()
459 if(_queue_tail==_queue_next_dist) {
461 _queue_next_dist=_queue_head;
463 Node n=_queue[_queue_tail++];
464 _processed->set(n,true);
466 for(OutEdgeIt e(*G,n);e!=INVALID;++e)
467 if(!(*_reached)[m=G->target(e)]) {
468 _queue[_queue_head++]=m;
469 _reached->set(m,true);
471 _dist->set(m,_curr_dist);
476 ///Next node to be processed.
478 ///Next node to be processed.
480 ///\return The next node to be processed or INVALID if the queue is
484 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
487 ///\brief Returns \c false if there are nodes
488 ///to be processed in the queue
490 ///Returns \c false if there are nodes
491 ///to be processed in the queue
492 bool emptyQueue() { return _queue_tail==_queue_head; }
493 ///Returns the number of the nodes to be processed.
495 ///Returns the number of the nodes to be processed in the queue.
497 int queueSize() { return _queue_head-_queue_tail; }
499 ///Executes the algorithm.
501 ///Executes the algorithm.
503 ///\pre init() must be called and at least one node should be added
504 ///with addSource() before using this function.
506 ///This method runs the %BFS algorithm from the root node(s)
509 ///shortest path to each node. The algorithm computes
510 ///- The shortest path tree.
511 ///- The distance of each node from the root(s).
515 while ( !emptyQueue() ) processNextNode();
518 ///Executes the algorithm until \c dest is reached.
520 ///Executes the algorithm until \c dest is reached.
522 ///\pre init() must be called and at least one node should be added
523 ///with addSource() before using this function.
525 ///This method runs the %BFS algorithm from the root node(s)
528 ///shortest path to \c dest. The algorithm computes
529 ///- The shortest path to \c dest.
530 ///- The distance of \c dest from the root(s).
532 void start(Node dest)
534 while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextNode();
537 ///Executes the algorithm until a condition is met.
539 ///Executes the algorithm until a condition is met.
541 ///\pre init() must be called and at least one node should be added
542 ///with addSource() before using this function.
544 ///\param nm must be a bool (or convertible) node map. The algorithm
545 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
547 void start(const NM &nm)
549 while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextNode();
552 ///Runs %BFS algorithm from node \c s.
554 ///This method runs the %BFS algorithm from a root node \c s
557 ///shortest path to each node. The algorithm computes
558 ///- The shortest path tree.
559 ///- The distance of each node from the root.
561 ///\note d.run(s) is just a shortcut of the following code.
573 ///Finds the shortest path between \c s and \c t.
575 ///Finds the shortest path between \c s and \c t.
577 ///\return The length of the shortest s---t path if there exists one,
579 ///\note Apart from the return value, d.run(s) is
580 ///just a shortcut of the following code.
586 int run(Node s,Node t) {
590 return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
595 ///\name Query Functions
596 ///The result of the %BFS algorithm can be obtained using these
598 ///Before the use of these functions,
599 ///either run() or start() must be called.
603 ///Copies the shortest path to \c t into \c p
605 ///This function copies the shortest path to \c t into \c p.
606 ///If \c t is a source itself or unreachable, then it does not
608 ///\todo Is it the right way to handle unreachable nodes?
609 ///\return Returns \c true if a path to \c t was actually copied to \c p,
610 ///\c false otherwise.
613 bool getPath(P &p,Node t)
617 typename P::Builder b(p);
618 for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
619 b.pushFront(pred(t));
626 ///The distance of a node from the root(s).
628 ///Returns the distance of a node from the root(s).
629 ///\pre \ref run() must be called before using this function.
630 ///\warning If node \c v in unreachable from the root(s) the return value
631 ///of this function is undefined.
632 int dist(Node v) const { return (*_dist)[v]; }
634 ///Returns the 'previous edge' of the shortest path tree.
636 ///For a node \c v it returns the 'previous edge'
637 ///of the shortest path tree,
638 ///i.e. it returns the last edge of a shortest path from the root(s) to \c
639 ///v. It is \ref INVALID
640 ///if \c v is unreachable from the root(s) or \c v is a root. The
641 ///shortest path tree used here is equal to the shortest path tree used in
643 ///\pre Either \ref run() or \ref start() must be called before using
645 ///\todo predEdge could be a better name.
646 Edge pred(Node v) const { return (*_pred)[v];}
648 ///Returns the 'previous node' of the shortest path tree.
650 ///For a node \c v it returns the 'previous node'
651 ///of the shortest path tree,
652 ///i.e. it returns the last but one node from a shortest path from the
654 ///It is INVALID if \c v is unreachable from the root(s) or
655 ///if \c v itself a root.
656 ///The shortest path tree used here is equal to the shortest path
657 ///tree used in \ref pred().
658 ///\pre Either \ref run() or \ref start() must be called before
659 ///using this function.
660 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
661 G->source((*_pred)[v]); }
663 ///Returns a reference to the NodeMap of distances.
665 ///Returns a reference to the NodeMap of distances.
666 ///\pre Either \ref run() or \ref init() must
667 ///be called before using this function.
668 const DistMap &distMap() const { return *_dist;}
670 ///Returns a reference to the shortest path tree map.
672 ///Returns a reference to the NodeMap of the edges of the
673 ///shortest path tree.
674 ///\pre Either \ref run() or \ref init()
675 ///must be called before using this function.
676 const PredMap &predMap() const { return *_pred;}
678 ///Checks if a node is reachable from the root.
680 ///Returns \c true if \c v is reachable from the root.
681 ///\warning The source nodes are indicated as unreached.
682 ///\pre Either \ref run() or \ref start()
683 ///must be called before using this function.
685 bool reached(Node v) { return (*_reached)[v]; }
690 ///Default traits class of Bfs function.
692 ///Default traits class of Bfs function.
693 ///\param GR Graph type.
695 struct BfsWizardDefaultTraits
697 ///The graph type the algorithm runs on.
699 ///\brief The type of the map that stores the last
700 ///edges of the shortest paths.
702 ///The type of the map that stores the last
703 ///edges of the shortest paths.
704 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
706 typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
707 ///Instantiates a PredMap.
709 ///This function instantiates a \ref PredMap.
710 ///\param g is the graph, to which we would like to define the PredMap.
711 ///\todo The graph alone may be insufficient to initialize
713 static PredMap *createPredMap(const GR &g)
715 static PredMap *createPredMap(const GR &)
718 return new PredMap();
721 ///The type of the map that indicates which nodes are processed.
723 ///The type of the map that indicates which nodes are processed.
724 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
725 ///\todo named parameter to set this type, function to read and write.
726 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
727 ///Instantiates a ProcessedMap.
729 ///This function instantiates a \ref ProcessedMap.
730 ///\param g is the graph, to which
731 ///we would like to define the \ref ProcessedMap
733 static ProcessedMap *createProcessedMap(const GR &g)
735 static ProcessedMap *createProcessedMap(const GR &)
738 return new ProcessedMap();
740 ///The type of the map that indicates which nodes are reached.
742 ///The type of the map that indicates which nodes are reached.
743 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
744 ///\todo named parameter to set this type, function to read and write.
745 typedef typename Graph::template NodeMap<bool> ReachedMap;
746 ///Instantiates a ReachedMap.
748 ///This function instantiates a \ref ReachedMap.
749 ///\param G is the graph, to which
750 ///we would like to define the \ref ReachedMap.
751 static ReachedMap *createReachedMap(const GR &G)
753 return new ReachedMap(G);
755 ///The type of the map that stores the dists of the nodes.
757 ///The type of the map that stores the dists of the nodes.
758 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
760 typedef NullMap<typename Graph::Node,int> DistMap;
761 ///Instantiates a DistMap.
763 ///This function instantiates a \ref DistMap.
764 ///\param g is the graph, to which we would like to define the \ref DistMap
766 static DistMap *createDistMap(const GR &g)
768 static DistMap *createDistMap(const GR &)
771 return new DistMap();
775 /// Default traits used by \ref BfsWizard
777 /// To make it easier to use Bfs algorithm
778 ///we have created a wizard class.
779 /// This \ref BfsWizard class needs default traits,
780 ///as well as the \ref Bfs class.
781 /// The \ref BfsWizardBase is a class to be the default traits of the
782 /// \ref BfsWizard class.
784 class BfsWizardBase : public BfsWizardDefaultTraits<GR>
787 typedef BfsWizardDefaultTraits<GR> Base;
789 /// Type of the nodes in the graph.
790 typedef typename Base::Graph::Node Node;
792 /// Pointer to the underlying graph.
794 ///Pointer to the map of reached nodes.
796 ///Pointer to the map of processed nodes.
798 ///Pointer to the map of predecessors edges.
800 ///Pointer to the map of distances.
802 ///Pointer to the source node.
808 /// This constructor does not require parameters, therefore it initiates
809 /// all of the attributes to default values (0, INVALID).
810 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
811 _dist(0), _source(INVALID) {}
815 /// This constructor requires some parameters,
816 /// listed in the parameters list.
817 /// Others are initiated to 0.
818 /// \param g is the initial value of \ref _g
819 /// \param s is the initial value of \ref _source
820 BfsWizardBase(const GR &g, Node s=INVALID) :
821 _g((void *)&g), _reached(0), _processed(0), _pred(0),
822 _dist(0), _source(s) {}
826 /// A class to make the usage of Bfs algorithm easier
828 /// This class is created to make it easier to use Bfs algorithm.
829 /// It uses the functions and features of the plain \ref Bfs,
830 /// but it is much simpler to use it.
832 /// Simplicity means that the way to change the types defined
833 /// in the traits class is based on functions that returns the new class
834 /// and not on templatable built-in classes.
835 /// When using the plain \ref Bfs
836 /// the new class with the modified type comes from
837 /// the original class by using the ::
838 /// operator. In the case of \ref BfsWizard only
839 /// a function have to be called and it will
840 /// return the needed class.
842 /// It does not have own \ref run method. When its \ref run method is called
843 /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run
846 class BfsWizard : public TR
850 ///The type of the underlying graph.
851 typedef typename TR::Graph Graph;
853 typedef typename Graph::Node Node;
855 typedef typename Graph::NodeIt NodeIt;
857 typedef typename Graph::Edge Edge;
859 typedef typename Graph::OutEdgeIt OutEdgeIt;
861 ///\brief The type of the map that stores
863 typedef typename TR::ReachedMap ReachedMap;
864 ///\brief The type of the map that stores
865 ///the processed nodes
866 typedef typename TR::ProcessedMap ProcessedMap;
867 ///\brief The type of the map that stores the last
868 ///edges of the shortest paths.
869 typedef typename TR::PredMap PredMap;
870 ///The type of the map that stores the dists of the nodes.
871 typedef typename TR::DistMap DistMap;
875 BfsWizard() : TR() {}
877 /// Constructor that requires parameters.
879 /// Constructor that requires parameters.
880 /// These parameters will be the default values for the traits class.
881 BfsWizard(const Graph &g, Node s=INVALID) :
885 BfsWizard(const TR &b) : TR(b) {}
889 ///Runs Bfs algorithm from a given node.
891 ///Runs Bfs algorithm from a given node.
892 ///The node can be given by the \ref source function.
895 if(Base::_source==INVALID) throw UninitializedParameter();
896 Bfs<Graph,TR> alg(*(Graph*)Base::_g);
898 alg.reachedMap(*(ReachedMap*)Base::_reached);
899 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
900 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
901 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
902 alg.run(Base::_source);
905 ///Runs Bfs algorithm from the given node.
907 ///Runs Bfs algorithm from the given node.
908 ///\param s is the given source.
916 struct DefPredMapBase : public Base {
918 static PredMap *createPredMap(const Graph &) { return 0; };
919 DefPredMapBase(const TR &b) : TR(b) {}
922 ///\brief \ref named-templ-param "Named parameter"
923 ///function for setting PredMap
925 /// \ref named-templ-param "Named parameter"
926 ///function for setting PredMap
929 BfsWizard<DefPredMapBase<T> > predMap(const T &t)
931 Base::_pred=(void *)&t;
932 return BfsWizard<DefPredMapBase<T> >(*this);
937 struct DefReachedMapBase : public Base {
938 typedef T ReachedMap;
939 static ReachedMap *createReachedMap(const Graph &) { return 0; };
940 DefReachedMapBase(const TR &b) : TR(b) {}
943 ///\brief \ref named-templ-param "Named parameter"
944 ///function for setting ReachedMap
946 /// \ref named-templ-param "Named parameter"
947 ///function for setting ReachedMap
950 BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
952 Base::_pred=(void *)&t;
953 return BfsWizard<DefReachedMapBase<T> >(*this);
958 struct DefProcessedMapBase : public Base {
959 typedef T ProcessedMap;
960 static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
961 DefProcessedMapBase(const TR &b) : TR(b) {}
964 ///\brief \ref named-templ-param "Named parameter"
965 ///function for setting ProcessedMap
967 /// \ref named-templ-param "Named parameter"
968 ///function for setting ProcessedMap
971 BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
973 Base::_pred=(void *)&t;
974 return BfsWizard<DefProcessedMapBase<T> >(*this);
979 struct DefDistMapBase : public Base {
981 static DistMap *createDistMap(const Graph &) { return 0; };
982 DefDistMapBase(const TR &b) : TR(b) {}
985 ///\brief \ref named-templ-param "Named parameter"
986 ///function for setting DistMap type
988 /// \ref named-templ-param "Named parameter"
989 ///function for setting DistMap type
992 BfsWizard<DefDistMapBase<T> > distMap(const T &t)
994 Base::_dist=(void *)&t;
995 return BfsWizard<DefDistMapBase<T> >(*this);
998 /// Sets the source node, from which the Bfs algorithm runs.
1000 /// Sets the source node, from which the Bfs algorithm runs.
1001 /// \param s is the source node.
1002 BfsWizard<TR> &source(Node s)
1010 ///Function type interface for Bfs algorithm.
1012 /// \ingroup flowalgs
1013 ///Function type interface for Bfs algorithm.
1015 ///This function also has several
1016 ///\ref named-templ-func-param "named parameters",
1017 ///they are declared as the members of class \ref BfsWizard.
1019 ///example shows how to use these parameters.
1021 /// bfs(g,source).predMap(preds).run();
1023 ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
1024 ///to the end of the parameter list.
1028 BfsWizard<BfsWizardBase<GR> >
1029 bfs(const GR &g,typename GR::Node s=INVALID)
1031 return BfsWizard<BfsWizardBase<GR> >(g,s);
1034 } //END OF NAMESPACE LEMON