vmap.h: Enables one to create maps with a virtual base class.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
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/graph_utils.h>
28 #include <lemon/invalid.h>
29 #include <lemon/error.h>
30 #include <lemon/maps.h>
36 ///Default traits class of Bfs class.
38 ///Default traits class of Bfs class.
39 ///\param GR Graph type.
41 struct BfsDefaultTraits
43 ///The graph type the algorithm runs on.
45 ///\brief The type of the map that stores the last
46 ///edges of the shortest paths.
48 ///The type of the map that stores the last
49 ///edges of the shortest paths.
50 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
52 typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
53 ///Instantiates a PredMap.
55 ///This function instantiates a \ref PredMap.
56 ///\param G is the graph, to which we would like to define the PredMap.
57 ///\todo The graph alone may be insufficient to initialize
58 static PredMap *createPredMap(const GR &G)
60 return new PredMap(G);
62 ///The type of the map that indicates which nodes are processed.
64 ///The type of the map that indicates which nodes are processed.
65 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
66 ///\todo named parameter to set this type, function to read and write.
67 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
68 ///Instantiates a ProcessedMap.
70 ///This function instantiates a \ref ProcessedMap.
71 ///\param g is the graph, to which
72 ///we would like to define the \ref ProcessedMap
74 static ProcessedMap *createProcessedMap(const GR &g)
76 static ProcessedMap *createProcessedMap(const GR &)
79 return new ProcessedMap();
81 ///The type of the map that indicates which nodes are reached.
83 ///The type of the map that indicates which nodes are reached.
84 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
85 ///\todo named parameter to set this type, function to read and write.
86 typedef typename Graph::template NodeMap<bool> ReachedMap;
87 ///Instantiates a ReachedMap.
89 ///This function instantiates a \ref ReachedMap.
90 ///\param G is the graph, to which
91 ///we would like to define the \ref ReachedMap.
92 static ReachedMap *createReachedMap(const GR &G)
94 return new ReachedMap(G);
96 ///The type of the map that stores the dists of the nodes.
98 ///The type of the map that stores the dists of the nodes.
99 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
101 typedef typename Graph::template NodeMap<int> DistMap;
102 ///Instantiates a DistMap.
104 ///This function instantiates a \ref DistMap.
105 ///\param G is the graph, to which we would like to define the \ref DistMap
106 static DistMap *createDistMap(const GR &G)
108 return new DistMap(G);
112 ///%BFS algorithm class.
115 ///This class provides an efficient implementation of the %BFS algorithm.
117 ///\param GR The graph type the algorithm runs on. The default value is
118 ///\ref ListGraph. The value of GR is not used directly by Bfs, it
119 ///is only passed to \ref BfsDefaultTraits.
120 ///\param TR Traits class to set various data types used by the algorithm.
121 ///The default traits class is
122 ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
123 ///See \ref BfsDefaultTraits for the documentation of
124 ///a Bfs traits class.
126 ///\author Alpar Juttner
129 template <typename GR,
132 template <typename GR=ListGraph,
133 typename TR=BfsDefaultTraits<GR> >
138 * \brief \ref Exception for uninitialized parameters.
140 * This error represents problems in the initialization
141 * of the parameters of the algorithms.
143 class UninitializedParameter : public lemon::UninitializedParameter {
145 virtual const char* exceptionName() const {
146 return "lemon::Bfs::UninitializedParameter";
151 ///The type of the underlying graph.
152 typedef typename TR::Graph Graph;
154 typedef typename Graph::Node Node;
156 typedef typename Graph::NodeIt NodeIt;
158 typedef typename Graph::Edge Edge;
160 typedef typename Graph::OutEdgeIt OutEdgeIt;
162 ///\brief The type of the map that stores the last
163 ///edges of the shortest paths.
164 typedef typename TR::PredMap PredMap;
165 ///The type of the map indicating which nodes are reached.
166 typedef typename TR::ReachedMap ReachedMap;
167 ///The type of the map indicating which nodes are processed.
168 typedef typename TR::ProcessedMap ProcessedMap;
169 ///The type of the map that stores the dists of the nodes.
170 typedef typename TR::DistMap DistMap;
172 /// Pointer to the underlying graph.
174 ///Pointer to the map of predecessors edges.
176 ///Indicates if \ref _pred is locally allocated (\c true) or not.
178 ///Pointer to the map of distances.
180 ///Indicates if \ref _dist is locally allocated (\c true) or not.
182 ///Pointer to the map of reached status of the nodes.
183 ReachedMap *_reached;
184 ///Indicates if \ref _reached is locally allocated (\c true) or not.
186 ///Pointer to the map of processed status of the nodes.
187 ProcessedMap *_processed;
188 ///Indicates if \ref _processed is locally allocated (\c true) or not.
189 bool local_processed;
191 std::vector<typename Graph::Node> _queue;
192 int _queue_head,_queue_tail,_queue_next_dist;
195 ///Creates the maps if necessary.
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);
226 ///\name Named template parameters
231 struct DefPredMapTraits : public Traits {
233 static PredMap *createPredMap(const Graph &)
235 throw UninitializedParameter();
238 ///\ref named-templ-param "Named parameter" for setting PredMap type
240 ///\ref named-templ-param "Named parameter" for setting PredMap type
243 struct DefPredMap : public Bfs< Graph, DefPredMapTraits<T> > {
244 typedef Bfs< Graph, DefPredMapTraits<T> > Create;
248 struct DefDistMapTraits : public Traits {
250 static DistMap *createDistMap(const Graph &)
252 throw UninitializedParameter();
255 ///\ref named-templ-param "Named parameter" for setting DistMap type
257 ///\ref named-templ-param "Named parameter" for setting DistMap type
260 struct DefDistMap : public Bfs< Graph, DefDistMapTraits<T> > {
261 typedef Bfs< Graph, DefDistMapTraits<T> > Create;
265 struct DefReachedMapTraits : public Traits {
266 typedef T ReachedMap;
267 static ReachedMap *createReachedMap(const Graph &)
269 throw UninitializedParameter();
272 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
274 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
277 struct DefReachedMap : public Bfs< Graph, DefReachedMapTraits<T> > {
278 typedef Bfs< Graph, DefReachedMapTraits<T> > Create;
282 struct DefProcessedMapTraits : public Traits {
283 typedef T ProcessedMap;
284 static ProcessedMap *createProcessedMap(const Graph &G)
286 throw UninitializedParameter();
289 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
291 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
294 struct DefProcessedMap : public Bfs< Graph, DefProcessedMapTraits<T> > {
295 typedef Bfs< Graph, DefProcessedMapTraits<T> > Create;
298 struct DefGraphProcessedMapTraits : public Traits {
299 typedef typename Graph::template NodeMap<bool> ProcessedMap;
300 static ProcessedMap *createProcessedMap(const Graph &G)
302 return new ProcessedMap(G);
305 ///\brief \ref named-templ-param "Named parameter"
306 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
308 ///\ref named-templ-param "Named parameter"
309 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
310 ///If you don't set it explicitly, it will be automatically allocated.
312 struct DefProcessedMapToBeDefaultMap :
313 public Bfs< Graph, DefGraphProcessedMapTraits> {
314 typedef Bfs< Graph, DefGraphProcessedMapTraits> Create;
323 ///\param _G the graph the algorithm will run on.
325 Bfs(const Graph& _G) :
327 _pred(NULL), local_pred(false),
328 _dist(NULL), local_dist(false),
329 _reached(NULL), local_reached(false),
330 _processed(NULL), local_processed(false)
336 if(local_pred) delete _pred;
337 if(local_dist) delete _dist;
338 if(local_reached) delete _reached;
339 if(local_processed) delete _processed;
342 ///Sets the map storing the predecessor edges.
344 ///Sets the map storing the predecessor edges.
345 ///If you don't use this function before calling \ref run(),
346 ///it will allocate one. The destructor deallocates this
347 ///automatically allocated map, of course.
348 ///\return <tt> (*this) </tt>
349 Bfs &predMap(PredMap &m)
359 ///Sets the map indicating the reached nodes.
361 ///Sets the map indicating the reached nodes.
362 ///If you don't use this function before calling \ref run(),
363 ///it will allocate one. The destructor deallocates this
364 ///automatically allocated map, of course.
365 ///\return <tt> (*this) </tt>
366 Bfs &reachedMap(ReachedMap &m)
376 ///Sets the map indicating the processed nodes.
378 ///Sets the map indicating the processed nodes.
379 ///If you don't use this function before calling \ref run(),
380 ///it will allocate one. The destructor deallocates this
381 ///automatically allocated map, of course.
382 ///\return <tt> (*this) </tt>
383 Bfs &processedMap(ProcessedMap &m)
385 if(local_processed) {
387 local_processed=false;
393 ///Sets the map storing the distances calculated by the algorithm.
395 ///Sets the map storing the distances calculated by the algorithm.
396 ///If you don't use this function before calling \ref run(),
397 ///it will allocate one. The destructor deallocates this
398 ///automatically allocated map, of course.
399 ///\return <tt> (*this) </tt>
400 Bfs &distMap(DistMap &m)
411 ///\name Execution control
412 ///The simplest way to execute the algorithm is to use
413 ///one of the member functions called \c run(...).
415 ///If you need more control on the execution,
416 ///first you must call \ref init(), then you can add several source nodes
417 ///with \ref addSource().
418 ///Finally \ref start() will perform the actual path
423 ///Initializes the internal data structures.
425 ///Initializes the internal data structures.
430 _queue.resize(countNodes(*G));
431 _queue_head=_queue_tail=0;
433 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
434 _pred->set(u,INVALID);
435 _reached->set(u,false);
436 _processed->set(u,false);
440 ///Adds a new source node.
442 ///Adds a new source node to the set of nodes to be processed.
444 void addSource(Node s)
448 _reached->set(s,true);
449 _pred->set(s,INVALID);
451 _queue[_queue_head++]=s;
452 _queue_next_dist=_queue_head;
456 ///Processes the next node.
458 ///Processes the next node.
460 ///\return The processed node.
462 ///\warning The queue must not be empty!
463 Node processNextNode()
465 if(_queue_tail==_queue_next_dist) {
467 _queue_next_dist=_queue_head;
469 Node n=_queue[_queue_tail++];
470 _processed->set(n,true);
472 for(OutEdgeIt e(*G,n);e!=INVALID;++e)
473 if(!(*_reached)[m=G->target(e)]) {
474 _queue[_queue_head++]=m;
475 _reached->set(m,true);
477 _dist->set(m,_curr_dist);
482 ///Next node to be processed.
484 ///Next node to be processed.
486 ///\return The next node to be processed or INVALID if the queue is
490 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
493 ///\brief Returns \c false if there are nodes
494 ///to be processed in the queue
496 ///Returns \c false if there are nodes
497 ///to be processed in the queue
498 bool emptyQueue() { return _queue_tail==_queue_head; }
499 ///Returns the number of the nodes to be processed.
501 ///Returns the number of the nodes to be processed in the queue.
503 int queueSize() { return _queue_head-_queue_tail; }
505 ///Executes the algorithm.
507 ///Executes the algorithm.
509 ///\pre init() must be called and at least one node should be added
510 ///with addSource() before using this function.
512 ///This method runs the %BFS algorithm from the root node(s)
515 ///shortest path to each node. The algorithm computes
516 ///- The shortest path tree.
517 ///- The distance of each node from the root(s).
521 while ( !emptyQueue() ) processNextNode();
524 ///Executes the algorithm until \c dest is reached.
526 ///Executes the algorithm until \c dest is reached.
528 ///\pre init() must be called and at least one node should be added
529 ///with addSource() before using this function.
531 ///This method runs the %BFS algorithm from the root node(s)
534 ///shortest path to \c dest. The algorithm computes
535 ///- The shortest path to \c dest.
536 ///- The distance of \c dest from the root(s).
538 void start(Node dest)
540 while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextNode();
543 ///Executes the algorithm until a condition is met.
545 ///Executes the algorithm until a condition is met.
547 ///\pre init() must be called and at least one node should be added
548 ///with addSource() before using this function.
550 ///\param nm must be a bool (or convertible) node map. The algorithm
551 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
553 void start(const NM &nm)
555 while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextNode();
558 ///Runs %BFS algorithm from node \c s.
560 ///This method runs the %BFS algorithm from a root node \c s
563 ///shortest path to each node. The algorithm computes
564 ///- The shortest path tree.
565 ///- The distance of each node from the root.
567 ///\note d.run(s) is just a shortcut of the following code.
579 ///Finds the shortest path between \c s and \c t.
581 ///Finds the shortest path between \c s and \c t.
583 ///\return The length of the shortest s---t path if there exists one,
585 ///\note Apart from the return value, d.run(s) is
586 ///just a shortcut of the following code.
592 int run(Node s,Node t) {
596 return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
601 ///\name Query Functions
602 ///The result of the %BFS algorithm can be obtained using these
604 ///Before the use of these functions,
605 ///either run() or start() must be called.
609 ///Copies the shortest path to \c t into \c p
611 ///This function copies the shortest path to \c t into \c p.
612 ///If \c t is a source itself or unreachable, then it does not
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);predEdge(t)!=INVALID;t=predNode(t))
624 b.pushFront(predEdge(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 Edge predEdge(Node v) const { return (*_pred)[v];}
652 ///Returns the 'previous node' of the shortest path tree.
654 ///For a node \c v it returns the 'previous node'
655 ///of the shortest path tree,
656 ///i.e. it returns the last but one node from a shortest path from the
658 ///It is INVALID if \c v is unreachable from the root(s) or
659 ///if \c v itself a root.
660 ///The shortest path tree used here is equal to the shortest path
661 ///tree used in \ref predEdge().
662 ///\pre Either \ref run() or \ref start() must be called before
663 ///using this function.
664 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
665 G->source((*_pred)[v]); }
667 ///Returns a reference to the NodeMap of distances.
669 ///Returns a reference to the NodeMap of distances.
670 ///\pre Either \ref run() or \ref init() must
671 ///be called before using this function.
672 const DistMap &distMap() const { return *_dist;}
674 ///Returns a reference to the shortest path tree map.
676 ///Returns a reference to the NodeMap of the edges of the
677 ///shortest path tree.
678 ///\pre Either \ref run() or \ref init()
679 ///must be called before using this function.
680 const PredMap &predMap() const { return *_pred;}
682 ///Checks if a node is reachable from the root.
684 ///Returns \c true if \c v is reachable from the root.
685 ///\warning The source nodes are indicated as unreached.
686 ///\pre Either \ref run() or \ref start()
687 ///must be called before using this function.
689 bool reached(Node v) { return (*_reached)[v]; }
694 ///Default traits class of Bfs function.
696 ///Default traits class of Bfs function.
697 ///\param GR Graph type.
699 struct BfsWizardDefaultTraits
701 ///The graph type the algorithm runs on.
703 ///\brief The type of the map that stores the last
704 ///edges of the shortest paths.
706 ///The type of the map that stores the last
707 ///edges of the shortest paths.
708 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
710 typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
711 ///Instantiates a PredMap.
713 ///This function instantiates a \ref PredMap.
714 ///\param g is the graph, to which we would like to define the PredMap.
715 ///\todo The graph alone may be insufficient to initialize
717 static PredMap *createPredMap(const GR &g)
719 static PredMap *createPredMap(const GR &)
722 return new PredMap();
725 ///The type of the map that indicates which nodes are processed.
727 ///The type of the map that indicates which nodes are processed.
728 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
729 ///\todo named parameter to set this type, function to read and write.
730 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
731 ///Instantiates a ProcessedMap.
733 ///This function instantiates a \ref ProcessedMap.
734 ///\param g is the graph, to which
735 ///we would like to define the \ref ProcessedMap
737 static ProcessedMap *createProcessedMap(const GR &g)
739 static ProcessedMap *createProcessedMap(const GR &)
742 return new ProcessedMap();
744 ///The type of the map that indicates which nodes are reached.
746 ///The type of the map that indicates which nodes are reached.
747 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
748 ///\todo named parameter to set this type, function to read and write.
749 typedef typename Graph::template NodeMap<bool> ReachedMap;
750 ///Instantiates a ReachedMap.
752 ///This function instantiates a \ref ReachedMap.
753 ///\param G is the graph, to which
754 ///we would like to define the \ref ReachedMap.
755 static ReachedMap *createReachedMap(const GR &G)
757 return new ReachedMap(G);
759 ///The type of the map that stores the dists of the nodes.
761 ///The type of the map that stores the dists of the nodes.
762 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
764 typedef NullMap<typename Graph::Node,int> DistMap;
765 ///Instantiates a DistMap.
767 ///This function instantiates a \ref DistMap.
768 ///\param g is the graph, to which we would like to define the \ref DistMap
770 static DistMap *createDistMap(const GR &g)
772 static DistMap *createDistMap(const GR &)
775 return new DistMap();
779 /// Default traits used by \ref BfsWizard
781 /// To make it easier to use Bfs algorithm
782 ///we have created a wizard class.
783 /// This \ref BfsWizard class needs default traits,
784 ///as well as the \ref Bfs class.
785 /// The \ref BfsWizardBase is a class to be the default traits of the
786 /// \ref BfsWizard class.
788 class BfsWizardBase : public BfsWizardDefaultTraits<GR>
791 typedef BfsWizardDefaultTraits<GR> Base;
793 /// Type of the nodes in the graph.
794 typedef typename Base::Graph::Node Node;
796 /// Pointer to the underlying graph.
798 ///Pointer to the map of reached nodes.
800 ///Pointer to the map of processed nodes.
802 ///Pointer to the map of predecessors edges.
804 ///Pointer to the map of distances.
806 ///Pointer to the source node.
812 /// This constructor does not require parameters, therefore it initiates
813 /// all of the attributes to default values (0, INVALID).
814 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
815 _dist(0), _source(INVALID) {}
819 /// This constructor requires some parameters,
820 /// listed in the parameters list.
821 /// Others are initiated to 0.
822 /// \param g is the initial value of \ref _g
823 /// \param s is the initial value of \ref _source
824 BfsWizardBase(const GR &g, Node s=INVALID) :
825 _g((void *)&g), _reached(0), _processed(0), _pred(0),
826 _dist(0), _source(s) {}
830 /// A class to make the usage of Bfs algorithm easier
832 /// This class is created to make it easier to use Bfs algorithm.
833 /// It uses the functions and features of the plain \ref Bfs,
834 /// but it is much simpler to use it.
836 /// Simplicity means that the way to change the types defined
837 /// in the traits class is based on functions that returns the new class
838 /// and not on templatable built-in classes.
839 /// When using the plain \ref Bfs
840 /// the new class with the modified type comes from
841 /// the original class by using the ::
842 /// operator. In the case of \ref BfsWizard only
843 /// a function have to be called and it will
844 /// return the needed class.
846 /// It does not have own \ref run method. When its \ref run method is called
847 /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run
850 class BfsWizard : public TR
854 ///The type of the underlying graph.
855 typedef typename TR::Graph Graph;
857 typedef typename Graph::Node Node;
859 typedef typename Graph::NodeIt NodeIt;
861 typedef typename Graph::Edge Edge;
863 typedef typename Graph::OutEdgeIt OutEdgeIt;
865 ///\brief The type of the map that stores
867 typedef typename TR::ReachedMap ReachedMap;
868 ///\brief The type of the map that stores
869 ///the processed nodes
870 typedef typename TR::ProcessedMap ProcessedMap;
871 ///\brief The type of the map that stores the last
872 ///edges of the shortest paths.
873 typedef typename TR::PredMap PredMap;
874 ///The type of the map that stores the dists of the nodes.
875 typedef typename TR::DistMap DistMap;
879 BfsWizard() : TR() {}
881 /// Constructor that requires parameters.
883 /// Constructor that requires parameters.
884 /// These parameters will be the default values for the traits class.
885 BfsWizard(const Graph &g, Node s=INVALID) :
889 BfsWizard(const TR &b) : TR(b) {}
893 ///Runs Bfs algorithm from a given node.
895 ///Runs Bfs algorithm from a given node.
896 ///The node can be given by the \ref source function.
899 if(Base::_source==INVALID) throw UninitializedParameter();
900 Bfs<Graph,TR> alg(*(Graph*)Base::_g);
902 alg.reachedMap(*(ReachedMap*)Base::_reached);
903 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
904 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
905 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
906 alg.run(Base::_source);
909 ///Runs Bfs algorithm from the given node.
911 ///Runs Bfs algorithm from the given node.
912 ///\param s is the given source.
920 struct DefPredMapBase : public Base {
922 static PredMap *createPredMap(const Graph &) { return 0; };
923 DefPredMapBase(const TR &b) : TR(b) {}
926 ///\brief \ref named-templ-param "Named parameter"
927 ///function for setting PredMap
929 /// \ref named-templ-param "Named parameter"
930 ///function for setting PredMap
933 BfsWizard<DefPredMapBase<T> > predMap(const T &t)
935 Base::_pred=(void *)&t;
936 return BfsWizard<DefPredMapBase<T> >(*this);
941 struct DefReachedMapBase : public Base {
942 typedef T ReachedMap;
943 static ReachedMap *createReachedMap(const Graph &) { return 0; };
944 DefReachedMapBase(const TR &b) : TR(b) {}
947 ///\brief \ref named-templ-param "Named parameter"
948 ///function for setting ReachedMap
950 /// \ref named-templ-param "Named parameter"
951 ///function for setting ReachedMap
954 BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
956 Base::_pred=(void *)&t;
957 return BfsWizard<DefReachedMapBase<T> >(*this);
962 struct DefProcessedMapBase : public Base {
963 typedef T ProcessedMap;
964 static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
965 DefProcessedMapBase(const TR &b) : TR(b) {}
968 ///\brief \ref named-templ-param "Named parameter"
969 ///function for setting ProcessedMap
971 /// \ref named-templ-param "Named parameter"
972 ///function for setting ProcessedMap
975 BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
977 Base::_pred=(void *)&t;
978 return BfsWizard<DefProcessedMapBase<T> >(*this);
983 struct DefDistMapBase : public Base {
985 static DistMap *createDistMap(const Graph &) { return 0; };
986 DefDistMapBase(const TR &b) : TR(b) {}
989 ///\brief \ref named-templ-param "Named parameter"
990 ///function for setting DistMap type
992 /// \ref named-templ-param "Named parameter"
993 ///function for setting DistMap type
996 BfsWizard<DefDistMapBase<T> > distMap(const T &t)
998 Base::_dist=(void *)&t;
999 return BfsWizard<DefDistMapBase<T> >(*this);
1002 /// Sets the source node, from which the Bfs algorithm runs.
1004 /// Sets the source node, from which the Bfs algorithm runs.
1005 /// \param s is the source node.
1006 BfsWizard<TR> &source(Node s)
1014 ///Function type interface for Bfs algorithm.
1016 /// \ingroup flowalgs
1017 ///Function type interface for Bfs algorithm.
1019 ///This function also has several
1020 ///\ref named-templ-func-param "named parameters",
1021 ///they are declared as the members of class \ref BfsWizard.
1023 ///example shows how to use these parameters.
1025 /// bfs(g,source).predMap(preds).run();
1027 ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
1028 ///to the end of the parameter list.
1032 BfsWizard<BfsWizardBase<GR> >
1033 bfs(const GR &g,typename GR::Node s=INVALID)
1035 return BfsWizard<BfsWizardBase<GR> >(g,s);
1038 } //END OF NAMESPACE LEMON