Get rid of undocumented members.
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 // ///\brief The type of the map that stores the last but one
61 // ///nodes of the shortest paths.
63 // ///The type of the map that stores the last but one
64 // ///nodes of the shortest paths.
65 // ///It must meet the \ref concept::WriteMap "WriteMap" concept.
67 // typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
68 // ///Instantiates a PredNodeMap.
70 // ///This function instantiates a \ref PredNodeMap.
71 // ///\param G is the graph, to which
72 // ///we would like to define the \ref PredNodeMap
73 // static PredNodeMap *createPredNodeMap(const GR &G)
75 // return new PredNodeMap();
78 ///The type of the map that indicates which nodes are processed.
80 ///The type of the map that indicates which nodes are processed.
81 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
82 ///\todo named parameter to set this type, function to read and write.
83 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
84 ///Instantiates a ProcessedMap.
86 ///This function instantiates a \ref ProcessedMap.
87 ///\param g is the graph, to which
88 ///we would like to define the \ref ProcessedMap
90 static ProcessedMap *createProcessedMap(const GR &g)
92 static ProcessedMap *createProcessedMap(const GR &)
95 return new ProcessedMap();
97 ///The type of the map that indicates which nodes are reached.
99 ///The type of the map that indicates which nodes are reached.
100 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
101 ///\todo named parameter to set this type, function to read and write.
102 typedef typename Graph::template NodeMap<bool> ReachedMap;
103 ///Instantiates a ReachedMap.
105 ///This function instantiates a \ref ReachedMap.
106 ///\param G is the graph, to which
107 ///we would like to define the \ref ReachedMap.
108 static ReachedMap *createReachedMap(const GR &G)
110 return new ReachedMap(G);
112 ///The type of the map that stores the dists of the nodes.
114 ///The type of the map that stores the dists of the nodes.
115 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
117 typedef typename Graph::template NodeMap<int> DistMap;
118 ///Instantiates a DistMap.
120 ///This function instantiates a \ref DistMap.
121 ///\param G is the graph, to which we would like to define the \ref DistMap
122 static DistMap *createDistMap(const GR &G)
124 return new DistMap(G);
128 ///%BFS algorithm class.
131 ///This class provides an efficient implementation of the %BFS algorithm.
133 ///\param GR The graph type the algorithm runs on. The default value is
134 ///\ref ListGraph. The value of GR is not used directly by Bfs, it
135 ///is only passed to \ref BfsDefaultTraits.
136 ///\param TR Traits class to set various data types used by the algorithm.
137 ///The default traits class is
138 ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
139 ///See \ref BfsDefaultTraits for the documentation of
140 ///a Bfs traits class.
142 ///\author Alpar Juttner
143 ///\todo A compare object would be nice.
146 template <typename GR,
149 template <typename GR=ListGraph,
150 typename TR=BfsDefaultTraits<GR> >
155 * \brief \ref Exception for uninitialized parameters.
157 * This error represents problems in the initialization
158 * of the parameters of the algorithms.
160 class UninitializedParameter : public lemon::UninitializedParameter {
162 virtual const char* exceptionName() const {
163 return "lemon::Bfs::UninitializedParameter";
168 ///The type of the underlying graph.
169 typedef typename TR::Graph Graph;
171 typedef typename Graph::Node Node;
173 typedef typename Graph::NodeIt NodeIt;
175 typedef typename Graph::Edge Edge;
177 typedef typename Graph::OutEdgeIt OutEdgeIt;
179 ///\brief The type of the map that stores the last
180 ///edges of the shortest paths.
181 typedef typename TR::PredMap PredMap;
182 // ///\brief The type of the map that stores the last but one
183 // ///nodes of the shortest paths.
184 // typedef typename TR::PredNodeMap PredNodeMap;
185 ///The type of the map indicating which nodes are reached.
186 typedef typename TR::ReachedMap ReachedMap;
187 ///The type of the map indicating which nodes are processed.
188 typedef typename TR::ProcessedMap ProcessedMap;
189 ///The type of the map that stores the dists of the nodes.
190 typedef typename TR::DistMap DistMap;
192 /// Pointer to the underlying graph.
194 ///Pointer to the map of predecessors edges.
196 ///Indicates if \ref _pred is locally allocated (\c true) or not.
198 // ///Pointer to the map of predecessors nodes.
199 // PredNodeMap *_predNode;
200 // ///Indicates if \ref _predNode is locally allocated (\c true) or not.
201 // bool local_predNode;
202 ///Pointer to the map of distances.
204 ///Indicates if \ref _dist is locally allocated (\c true) or not.
206 ///Pointer to the map of reached status of the nodes.
207 ReachedMap *_reached;
208 ///Indicates if \ref _reached is locally allocated (\c true) or not.
210 ///Pointer to the map of processed status of the nodes.
211 ProcessedMap *_processed;
212 ///Indicates if \ref _processed is locally allocated (\c true) or not.
213 bool local_processed;
215 std::vector<typename Graph::Node> _queue;
216 int _queue_head,_queue_tail,_queue_next_dist;
218 // ///The source node of the last execution.
221 ///Creates the maps if necessary.
223 ///\todo Error if \c G are \c NULL.
224 ///\todo Better memory allocation (instead of new).
229 _pred = Traits::createPredMap(*G);
232 // local_predNode = true;
233 // _predNode = Traits::createPredNodeMap(*G);
237 _dist = Traits::createDistMap(*G);
240 local_reached = true;
241 _reached = Traits::createReachedMap(*G);
244 local_processed = true;
245 _processed = Traits::createProcessedMap(*G);
251 ///\name Named template parameters
256 struct DefPredMapTraits : public Traits {
258 static PredMap *createPredMap(const Graph &G)
260 throw UninitializedParameter();
263 ///\ref named-templ-param "Named parameter" for setting PredMap type
265 ///\ref named-templ-param "Named parameter" for setting PredMap type
268 class DefPredMap : public Bfs< Graph,
269 DefPredMapTraits<T> > { };
271 // template <class T>
272 // struct DefPredNodeMapTraits : public Traits {
273 // typedef T PredNodeMap;
274 // static PredNodeMap *createPredNodeMap(const Graph &G)
276 // throw UninitializedParameter();
279 // ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
281 // ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
283 // template <class T>
284 // class DefPredNodeMap : public Bfs< Graph,
286 // DefPredNodeMapTraits<T> > { };
289 struct DefDistMapTraits : public Traits {
291 static DistMap *createDistMap(const Graph &G)
293 throw UninitializedParameter();
296 ///\ref named-templ-param "Named parameter" for setting DistMap type
298 ///\ref named-templ-param "Named parameter" for setting DistMap type
301 class DefDistMap : public Bfs< Graph,
302 DefDistMapTraits<T> > { };
305 struct DefReachedMapTraits : public Traits {
306 typedef T ReachedMap;
307 static ReachedMap *createReachedMap(const Graph &G)
309 throw UninitializedParameter();
312 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
314 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
317 class DefReachedMap : public Bfs< Graph,
318 DefReachedMapTraits<T> > { };
320 struct DefGraphReachedMapTraits : public Traits {
321 typedef typename Graph::template NodeMap<bool> ReachedMap;
322 static ReachedMap *createReachedMap(const Graph &G)
324 return new ReachedMap(G);
328 struct DefProcessedMapTraits : public Traits {
329 typedef T ProcessedMap;
330 static ProcessedMap *createProcessedMap(const Graph &G)
332 throw UninitializedParameter();
335 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
337 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
340 class DefProcessedMap : public Bfs< Graph,
341 DefProcessedMapTraits<T> > { };
343 struct DefGraphProcessedMapTraits : public Traits {
344 typedef typename Graph::template NodeMap<bool> ProcessedMap;
345 static ProcessedMap *createProcessedMap(const Graph &G)
347 return new ProcessedMap(G);
350 ///\brief \ref named-templ-param "Named parameter"
351 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
353 ///\ref named-templ-param "Named parameter"
354 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
355 ///If you don't set it explicitly, it will be automatically allocated.
357 class DefProcessedMapToBeDefaultMap :
359 DefGraphProcessedMapTraits> { };
367 ///\param _G the graph the algorithm will run on.
369 Bfs(const Graph& _G) :
371 _pred(NULL), local_pred(false),
372 // _predNode(NULL), local_predNode(false),
373 _dist(NULL), local_dist(false),
374 _reached(NULL), local_reached(false),
375 _processed(NULL), local_processed(false)
381 if(local_pred) delete _pred;
382 // if(local_predNode) delete _predNode;
383 if(local_dist) delete _dist;
384 if(local_reached) delete _reached;
385 if(local_processed) delete _processed;
388 ///Sets the map storing the predecessor edges.
390 ///Sets the map storing the predecessor edges.
391 ///If you don't use this function before calling \ref run(),
392 ///it will allocate one. The destructor deallocates this
393 ///automatically allocated map, of course.
394 ///\return <tt> (*this) </tt>
395 Bfs &predMap(PredMap &m)
405 ///Sets the map indicating the reached nodes.
407 ///Sets the map indicating the reached nodes.
408 ///If you don't use this function before calling \ref run(),
409 ///it will allocate one. The destructor deallocates this
410 ///automatically allocated map, of course.
411 ///\return <tt> (*this) </tt>
412 Bfs &reachedMap(ReachedMap &m)
422 ///Sets the map indicating the processed nodes.
424 ///Sets the map indicating the processed nodes.
425 ///If you don't use this function before calling \ref run(),
426 ///it will allocate one. The destructor deallocates this
427 ///automatically allocated map, of course.
428 ///\return <tt> (*this) </tt>
429 Bfs &processedMap(ProcessedMap &m)
431 if(local_processed) {
433 local_processed=false;
439 // ///Sets the map storing the predecessor nodes.
441 // ///Sets the map storing the predecessor nodes.
442 // ///If you don't use this function before calling \ref run(),
443 // ///it will allocate one. The destructor deallocates this
444 // ///automatically allocated map, of course.
445 // ///\return <tt> (*this) </tt>
446 // Bfs &predNodeMap(PredNodeMap &m)
448 // if(local_predNode) {
450 // local_predNode=false;
456 ///Sets the map storing the distances calculated by the algorithm.
458 ///Sets the map storing the distances calculated by the algorithm.
459 ///If you don't use this function before calling \ref run(),
460 ///it will allocate one. The destructor deallocates this
461 ///automatically allocated map, of course.
462 ///\return <tt> (*this) </tt>
463 Bfs &distMap(DistMap &m)
474 ///\name Execution control
475 ///The simplest way to execute the algorithm is to use
476 ///one of the member functions called \c run(...).
478 ///If you need more control on the execution,
479 ///first you must call \ref init(), then you can add several source nodes
480 ///with \ref addSource().
481 ///Finally \ref start() will perform the actual path
486 ///Initializes the internal data structures.
488 ///Initializes the internal data structures.
493 _queue.resize(countNodes(*G));
494 _queue_head=_queue_tail=0;
496 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
497 _pred->set(u,INVALID);
498 // _predNode->set(u,INVALID);
499 _reached->set(u,false);
500 _processed->set(u,false);
504 ///Adds a new source node.
506 ///Adds a new source node to the set of nodes to be processed.
508 void addSource(Node s)
512 _reached->set(s,true);
513 _pred->set(s,INVALID);
515 _queue[_queue_head++]=s;
516 _queue_next_dist=_queue_head;
520 ///Processes the next node.
522 ///Processes the next node.
524 ///\return The processed node.
526 ///\warning The queue must not be empty!
527 Node processNextNode()
529 if(_queue_tail==_queue_next_dist) {
531 _queue_next_dist=_queue_head;
533 Node n=_queue[_queue_tail++];
534 _processed->set(n,true);
536 for(OutEdgeIt e(*G,n);e!=INVALID;++e)
537 if(!(*_reached)[m=G->target(e)]) {
538 _queue[_queue_head++]=m;
539 _reached->set(m,true);
541 // _pred_node->set(m,n);
542 _dist->set(m,_curr_dist);
547 ///\brief Returns \c false if there are nodes
548 ///to be processed in the queue
550 ///Returns \c false if there are nodes
551 ///to be processed in the queue
552 bool emptyQueue() { return _queue_tail==_queue_head; }
553 ///Returns the number of the nodes to be processed.
555 ///Returns the number of the nodes to be processed in the queue.
557 int queueSize() { return _queue_head-_queue_tail; }
559 ///Executes the algorithm.
561 ///Executes the algorithm.
563 ///\pre init() must be called and at least one node should be added
564 ///with addSource() before using this function.
566 ///This method runs the %BFS algorithm from the root node(s)
569 ///shortest path to each node. The algorithm computes
570 ///- The shortest path tree.
571 ///- The distance of each node from the root(s).
575 while ( !emptyQueue() ) processNextNode();
578 ///Executes the algorithm until \c dest is reached.
580 ///Executes the algorithm until \c dest is reached.
582 ///\pre init() must be called and at least one node should be added
583 ///with addSource() before using this function.
585 ///This method runs the %BFS algorithm from the root node(s)
588 ///shortest path to \c dest. The algorithm computes
589 ///- The shortest path to \c dest.
590 ///- The distance of \c dest from the root(s).
592 void start(Node dest)
594 while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextNode();
597 ///Executes the algorithm until a condition is met.
599 ///Executes the algorithm until a condition is met.
601 ///\pre init() must be called and at least one node should be added
602 ///with addSource() before using this function.
604 ///\param nm must be a bool (or convertible) node map. The algorithm
605 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
607 void start(const NM &nm)
609 while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextNode();
612 ///Runs %BFS algorithm from node \c s.
614 ///This method runs the %BFS algorithm from a root node \c s
617 ///shortest path to each node. The algorithm computes
618 ///- The shortest path tree.
619 ///- The distance of each node from the root.
621 ///\note d.run(s) is just a shortcut of the following code.
633 ///Finds the shortest path between \c s and \c t.
635 ///Finds the shortest path between \c s and \c t.
637 ///\return The length of the shortest s---t path if there exists one,
639 ///\note Apart from the return value, d.run(s) is
640 ///just a shortcut of the following code.
646 int run(Node s,Node t) {
650 return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
655 ///\name Query Functions
656 ///The result of the %BFS algorithm can be obtained using these
658 ///Before the use of these functions,
659 ///either run() or start() must be called.
663 ///Copies the shortest path to \c t into \c p
665 ///This function copies the shortest path to \c t into \c p.
666 ///If \c t is a source itself or unreachable, then it does not
668 ///\todo Is it the right way to handle unreachable nodes?
669 ///\return Returns \c true if a path to \c t was actually copied to \c p,
670 ///\c false otherwise.
673 bool getPath(P &p,Node t)
677 typename P::Builder b(p);
678 for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
679 b.pushFront(pred(t));
686 ///The distance of a node from the root(s).
688 ///Returns the distance of a node from the root(s).
689 ///\pre \ref run() must be called before using this function.
690 ///\warning If node \c v in unreachable from the root(s) the return value
691 ///of this function is undefined.
692 int dist(Node v) const { return (*_dist)[v]; }
694 ///Returns the 'previous edge' of the shortest path tree.
696 ///For a node \c v it returns the 'previous edge'
697 ///of the shortest path tree,
698 ///i.e. it returns the last edge of a shortest path from the root(s) to \c
699 ///v. It is \ref INVALID
700 ///if \c v is unreachable from the root(s) or \c v is a root. The
701 ///shortest path tree used here is equal to the shortest path tree used in
702 ///\ref predNode(Node v).
703 ///\pre Either \ref run() or \ref start() must be called before using
705 ///\todo predEdge could be a better name.
706 Edge pred(Node v) const { return (*_pred)[v];}
708 ///Returns the 'previous node' of the shortest path tree.
710 ///For a node \c v it returns the 'previous node'
711 ///of the shortest path tree,
712 ///i.e. it returns the last but one node from a shortest path from the
714 ///It is INVALID if \c v is unreachable from the root(s) or
715 ///if \c v itself a root.
716 ///The shortest path tree used here is equal to the shortest path
717 ///tree used in \ref pred(Node v).
718 ///\pre Either \ref run() or \ref start() must be called before
719 ///using this function.
720 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
721 G->source((*_pred)[v]); }
723 ///Returns a reference to the NodeMap of distances.
725 ///Returns a reference to the NodeMap of distances.
726 ///\pre Either \ref run() or \ref init() must
727 ///be called before using this function.
728 const DistMap &distMap() const { return *_dist;}
730 ///Returns a reference to the shortest path tree map.
732 ///Returns a reference to the NodeMap of the edges of the
733 ///shortest path tree.
734 ///\pre Either \ref run() or \ref init()
735 ///must be called before using this function.
736 const PredMap &predMap() const { return *_pred;}
738 // ///Returns a reference to the map of nodes of shortest paths.
740 // ///Returns a reference to the NodeMap of the last but one nodes of the
741 // ///shortest path tree.
742 // ///\pre \ref run() must be called before using this function.
743 // const PredNodeMap &predNodeMap() const { return *_predNode;}
745 ///Checks if a node is reachable from the root.
747 ///Returns \c true if \c v is reachable from the root.
748 ///\warning The source nodes are indicated as unreached.
749 ///\pre Either \ref run() or \ref start()
750 ///must be called before using this function.
752 bool reached(Node v) { return (*_reached)[v]; }
757 ///Default traits class of Bfs function.
759 ///Default traits class of Bfs function.
760 ///\param GR Graph type.
762 struct BfsWizardDefaultTraits
764 ///The graph type the algorithm runs on.
766 ///\brief The type of the map that stores the last
767 ///edges of the shortest paths.
769 ///The type of the map that stores the last
770 ///edges of the shortest paths.
771 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
773 typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
774 ///Instantiates a PredMap.
776 ///This function instantiates a \ref PredMap.
777 ///\param g is the graph, to which we would like to define the PredMap.
778 ///\todo The graph alone may be insufficient to initialize
780 static PredMap *createPredMap(const GR &g)
782 static PredMap *createPredMap(const GR &)
785 return new PredMap();
787 // ///\brief The type of the map that stores the last but one
788 // ///nodes of the shortest paths.
790 // ///The type of the map that stores the last but one
791 // ///nodes of the shortest paths.
792 // ///It must meet the \ref concept::WriteMap "WriteMap" concept.
794 // typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
795 // ///Instantiates a PredNodeMap.
797 // ///This function instantiates a \ref PredNodeMap.
798 // ///\param G is the graph, to which
799 // ///we would like to define the \ref PredNodeMap
800 // static PredNodeMap *createPredNodeMap(const GR &G)
802 // return new PredNodeMap();
805 ///The type of the map that indicates which nodes are processed.
807 ///The type of the map that indicates which nodes are processed.
808 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
809 ///\todo named parameter to set this type, function to read and write.
810 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
811 ///Instantiates a ProcessedMap.
813 ///This function instantiates a \ref ProcessedMap.
814 ///\param g is the graph, to which
815 ///we would like to define the \ref ProcessedMap
817 static ProcessedMap *createProcessedMap(const GR &g)
819 static ProcessedMap *createProcessedMap(const GR &)
822 return new ProcessedMap();
824 ///The type of the map that indicates which nodes are reached.
826 ///The type of the map that indicates which nodes are reached.
827 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
828 ///\todo named parameter to set this type, function to read and write.
829 typedef typename Graph::template NodeMap<bool> ReachedMap;
830 ///Instantiates a ReachedMap.
832 ///This function instantiates a \ref ReachedMap.
833 ///\param G is the graph, to which
834 ///we would like to define the \ref ReachedMap.
835 static ReachedMap *createReachedMap(const GR &G)
837 return new ReachedMap(G);
839 ///The type of the map that stores the dists of the nodes.
841 ///The type of the map that stores the dists of the nodes.
842 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
844 typedef NullMap<typename Graph::Node,int> DistMap;
845 ///Instantiates a DistMap.
847 ///This function instantiates a \ref DistMap.
848 ///\param g is the graph, to which we would like to define the \ref DistMap
850 static DistMap *createDistMap(const GR &g)
852 static DistMap *createDistMap(const GR &)
855 return new DistMap();
859 /// Default traits used by \ref BfsWizard
861 /// To make it easier to use Bfs algorithm
862 ///we have created a wizard class.
863 /// This \ref BfsWizard class needs default traits,
864 ///as well as the \ref Bfs class.
865 /// The \ref BfsWizardBase is a class to be the default traits of the
866 /// \ref BfsWizard class.
868 class BfsWizardBase : public BfsWizardDefaultTraits<GR>
871 typedef BfsWizardDefaultTraits<GR> Base;
873 /// Type of the nodes in the graph.
874 typedef typename Base::Graph::Node Node;
876 /// Pointer to the underlying graph.
878 ///Pointer to the map of reached nodes.
880 ///Pointer to the map of processed nodes.
882 ///Pointer to the map of predecessors edges.
884 // ///Pointer to the map of predecessors nodes.
886 ///Pointer to the map of distances.
888 ///Pointer to the source node.
894 /// This constructor does not require parameters, therefore it initiates
895 /// all of the attributes to default values (0, INVALID).
896 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
898 _dist(0), _source(INVALID) {}
902 /// This constructor requires some parameters,
903 /// listed in the parameters list.
904 /// Others are initiated to 0.
905 /// \param g is the initial value of \ref _g
906 /// \param s is the initial value of \ref _source
907 BfsWizardBase(const GR &g, Node s=INVALID) :
908 _g((void *)&g), _reached(0), _processed(0), _pred(0),
910 _dist(0), _source(s) {}
914 /// A class to make the usage of Bfs algorithm easier
916 /// This class is created to make it easier to use Bfs algorithm.
917 /// It uses the functions and features of the plain \ref Bfs,
918 /// but it is much simpler to use it.
920 /// Simplicity means that the way to change the types defined
921 /// in the traits class is based on functions that returns the new class
922 /// and not on templatable built-in classes.
923 /// When using the plain \ref Bfs
924 /// the new class with the modified type comes from
925 /// the original class by using the ::
926 /// operator. In the case of \ref BfsWizard only
927 /// a function have to be called and it will
928 /// return the needed class.
930 /// It does not have own \ref run method. When its \ref run method is called
931 /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run
934 class BfsWizard : public TR
938 ///The type of the underlying graph.
939 typedef typename TR::Graph Graph;
941 typedef typename Graph::Node Node;
943 typedef typename Graph::NodeIt NodeIt;
945 typedef typename Graph::Edge Edge;
947 typedef typename Graph::OutEdgeIt OutEdgeIt;
949 ///\brief The type of the map that stores
951 typedef typename TR::ReachedMap ReachedMap;
952 ///\brief The type of the map that stores
953 ///the processed nodes
954 typedef typename TR::ProcessedMap ProcessedMap;
955 ///\brief The type of the map that stores the last
956 ///edges of the shortest paths.
957 typedef typename TR::PredMap PredMap;
958 // ///\brief The type of the map that stores the last but one
959 // ///nodes of the shortest paths.
960 // typedef typename TR::PredNodeMap PredNodeMap;
961 ///The type of the map that stores the dists of the nodes.
962 typedef typename TR::DistMap DistMap;
966 BfsWizard() : TR() {}
968 /// Constructor that requires parameters.
970 /// Constructor that requires parameters.
971 /// These parameters will be the default values for the traits class.
972 BfsWizard(const Graph &g, Node s=INVALID) :
976 BfsWizard(const TR &b) : TR(b) {}
980 ///Runs Bfs algorithm from a given node.
982 ///Runs Bfs algorithm from a given node.
983 ///The node can be given by the \ref source function.
986 if(Base::_source==INVALID) throw UninitializedParameter();
987 Bfs<Graph,TR> alg(*(Graph*)Base::_g);
989 alg.reachedMap(*(ReachedMap*)Base::_reached);
990 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
991 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
992 // if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
993 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
994 alg.run(Base::_source);
997 ///Runs Bfs algorithm from the given node.
999 ///Runs Bfs algorithm from the given node.
1000 ///\param s is the given source.
1008 struct DefPredMapBase : public Base {
1010 static PredMap *createPredMap(const Graph &) { return 0; };
1011 DefPredMapBase(const TR &b) : TR(b) {}
1014 ///\brief \ref named-templ-param "Named parameter"
1015 ///function for setting PredMap
1017 /// \ref named-templ-param "Named parameter"
1018 ///function for setting PredMap
1021 BfsWizard<DefPredMapBase<T> > predMap(const T &t)
1023 Base::_pred=(void *)&t;
1024 return BfsWizard<DefPredMapBase<T> >(*this);
1029 struct DefReachedMapBase : public Base {
1030 typedef T ReachedMap;
1031 static ReachedMap *createReachedMap(const Graph &) { return 0; };
1032 DefReachedMapBase(const TR &b) : TR(b) {}
1035 ///\brief \ref named-templ-param "Named parameter"
1036 ///function for setting ReachedMap
1038 /// \ref named-templ-param "Named parameter"
1039 ///function for setting ReachedMap
1042 BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1044 Base::_pred=(void *)&t;
1045 return BfsWizard<DefReachedMapBase<T> >(*this);
1050 struct DefProcessedMapBase : public Base {
1051 typedef T ProcessedMap;
1052 static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
1053 DefProcessedMapBase(const TR &b) : TR(b) {}
1056 ///\brief \ref named-templ-param "Named parameter"
1057 ///function for setting ProcessedMap
1059 /// \ref named-templ-param "Named parameter"
1060 ///function for setting ProcessedMap
1063 BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1065 Base::_pred=(void *)&t;
1066 return BfsWizard<DefProcessedMapBase<T> >(*this);
1070 // template<class T>
1071 // struct DefPredNodeMapBase : public Base {
1072 // typedef T PredNodeMap;
1073 // static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
1074 // DefPredNodeMapBase(const TR &b) : TR(b) {}
1077 // ///\brief \ref named-templ-param "Named parameter"
1078 // ///function for setting PredNodeMap type
1080 // /// \ref named-templ-param "Named parameter"
1081 // ///function for setting PredNodeMap type
1083 // template<class T>
1084 // BfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1086 // Base::_predNode=(void *)&t;
1087 // return BfsWizard<DefPredNodeMapBase<T> >(*this);
1091 struct DefDistMapBase : public Base {
1093 static DistMap *createDistMap(const Graph &) { return 0; };
1094 DefDistMapBase(const TR &b) : TR(b) {}
1097 ///\brief \ref named-templ-param "Named parameter"
1098 ///function for setting DistMap type
1100 /// \ref named-templ-param "Named parameter"
1101 ///function for setting DistMap type
1104 BfsWizard<DefDistMapBase<T> > distMap(const T &t)
1106 Base::_dist=(void *)&t;
1107 return BfsWizard<DefDistMapBase<T> >(*this);
1110 /// Sets the source node, from which the Bfs algorithm runs.
1112 /// Sets the source node, from which the Bfs algorithm runs.
1113 /// \param s is the source node.
1114 BfsWizard<TR> &source(Node s)
1122 ///Function type interface for Bfs algorithm.
1124 /// \ingroup flowalgs
1125 ///Function type interface for Bfs algorithm.
1127 ///This function also has several
1128 ///\ref named-templ-func-param "named parameters",
1129 ///they are declared as the members of class \ref BfsWizard.
1131 ///example shows how to use these parameters.
1133 /// bfs(g,source).predMap(preds).run();
1135 ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
1136 ///to the end of the parameter list.
1140 BfsWizard<BfsWizardBase<GR> >
1141 bfs(const GR &g,typename GR::Node s=INVALID)
1143 return BfsWizard<BfsWizardBase<GR> >(g,s);
1146 } //END OF NAMESPACE LEMON