Hmmm...
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
89 static ProcessedMap *createProcessedMap(const GR &)
91 return new ProcessedMap();
93 ///The type of the map that indicates which nodes are reached.
95 ///The type of the map that indicates which nodes are reached.
96 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
97 ///\todo named parameter to set this type, function to read and write.
98 typedef typename Graph::template NodeMap<bool> ReachedMap;
99 ///Instantiates a ReachedMap.
101 ///This function instantiates a \ref ReachedMap.
102 ///\param G is the graph, to which
103 ///we would like to define the \ref ReachedMap.
104 static ReachedMap *createReachedMap(const GR &G)
106 return new ReachedMap(G);
108 ///The type of the map that stores the dists of the nodes.
110 ///The type of the map that stores the dists of the nodes.
111 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
113 typedef typename Graph::template NodeMap<int> DistMap;
114 ///Instantiates a DistMap.
116 ///This function instantiates a \ref DistMap.
117 ///\param G is the graph, to which we would like to define the \ref DistMap
118 static DistMap *createDistMap(const GR &G)
120 return new DistMap(G);
124 ///%BFS algorithm class.
127 ///This class provides an efficient implementation of the %BFS algorithm.
129 ///\param GR The graph type the algorithm runs on. The default value is
130 ///\ref ListGraph. The value of GR is not used directly by Bfs, it
131 ///is only passed to \ref BfsDefaultTraits.
132 ///\param TR Traits class to set various data types used by the algorithm.
133 ///The default traits class is
134 ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
135 ///See \ref BfsDefaultTraits for the documentation of
136 ///a Bfs traits class.
138 ///\author Alpar Juttner
139 ///\todo A compare object would be nice.
142 template <typename GR,
145 template <typename GR=ListGraph,
146 typename TR=BfsDefaultTraits<GR> >
151 * \brief \ref Exception for uninitialized parameters.
153 * This error represents problems in the initialization
154 * of the parameters of the algorithms.
156 class UninitializedParameter : public lemon::UninitializedParameter {
158 virtual const char* exceptionName() const {
159 return "lemon::Bfs::UninitializedParameter";
164 ///The type of the underlying graph.
165 typedef typename TR::Graph Graph;
167 typedef typename Graph::Node Node;
169 typedef typename Graph::NodeIt NodeIt;
171 typedef typename Graph::Edge Edge;
173 typedef typename Graph::OutEdgeIt OutEdgeIt;
175 ///\brief The type of the map that stores the last
176 ///edges of the shortest paths.
177 typedef typename TR::PredMap PredMap;
178 // ///\brief The type of the map that stores the last but one
179 // ///nodes of the shortest paths.
180 // typedef typename TR::PredNodeMap PredNodeMap;
181 ///The type of the map indicating which nodes are reached.
182 typedef typename TR::ReachedMap ReachedMap;
183 ///The type of the map indicating which nodes are processed.
184 typedef typename TR::ProcessedMap ProcessedMap;
185 ///The type of the map that stores the dists of the nodes.
186 typedef typename TR::DistMap DistMap;
188 /// Pointer to the underlying graph.
190 ///Pointer to the map of predecessors edges.
192 ///Indicates if \ref _pred is locally allocated (\c true) or not.
194 // ///Pointer to the map of predecessors nodes.
195 // PredNodeMap *_predNode;
196 // ///Indicates if \ref _predNode is locally allocated (\c true) or not.
197 // bool local_predNode;
198 ///Pointer to the map of distances.
200 ///Indicates if \ref _dist is locally allocated (\c true) or not.
202 ///Pointer to the map of reached status of the nodes.
203 ReachedMap *_reached;
204 ///Indicates if \ref _reached is locally allocated (\c true) or not.
206 ///Pointer to the map of processed status of the nodes.
207 ProcessedMap *_processed;
208 ///Indicates if \ref _processed is locally allocated (\c true) or not.
209 bool local_processed;
211 std::vector<typename Graph::Node> _queue;
212 int _queue_head,_queue_tail,_queue_next_dist;
214 // ///The source node of the last execution.
217 ///Creates the maps if necessary.
219 ///\todo Error if \c G are \c NULL.
220 ///\todo Better memory allocation (instead of new).
225 _pred = Traits::createPredMap(*G);
228 // local_predNode = true;
229 // _predNode = Traits::createPredNodeMap(*G);
233 _dist = Traits::createDistMap(*G);
236 local_reached = true;
237 _reached = Traits::createReachedMap(*G);
240 local_processed = true;
241 _processed = Traits::createProcessedMap(*G);
247 ///\name Named template parameters
252 struct DefPredMapTraits : public Traits {
254 static PredMap *createPredMap(const Graph &G)
256 throw UninitializedParameter();
259 ///\ref named-templ-param "Named parameter" for setting PredMap type
261 ///\ref named-templ-param "Named parameter" for setting PredMap type
264 class DefPredMap : public Bfs< Graph,
265 DefPredMapTraits<T> > { };
267 // template <class T>
268 // struct DefPredNodeMapTraits : public Traits {
269 // typedef T PredNodeMap;
270 // static PredNodeMap *createPredNodeMap(const Graph &G)
272 // throw UninitializedParameter();
275 // ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
277 // ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
279 // template <class T>
280 // class DefPredNodeMap : public Bfs< Graph,
282 // DefPredNodeMapTraits<T> > { };
285 struct DefDistMapTraits : public Traits {
287 static DistMap *createDistMap(const Graph &G)
289 throw UninitializedParameter();
292 ///\ref named-templ-param "Named parameter" for setting DistMap type
294 ///\ref named-templ-param "Named parameter" for setting DistMap type
297 class DefDistMap : public Bfs< Graph,
298 DefDistMapTraits<T> > { };
301 struct DefReachedMapTraits : public Traits {
302 typedef T ReachedMap;
303 static ReachedMap *createReachedMap(const Graph &G)
305 throw UninitializedParameter();
308 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
310 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
313 class DefReachedMap : public Bfs< Graph,
314 DefReachedMapTraits<T> > { };
316 struct DefGraphReachedMapTraits : public Traits {
317 typedef typename Graph::template NodeMap<bool> ReachedMap;
318 static ReachedMap *createReachedMap(const Graph &G)
320 return new ReachedMap(G);
324 struct DefProcessedMapTraits : public Traits {
325 typedef T ProcessedMap;
326 static ProcessedMap *createProcessedMap(const Graph &G)
328 throw UninitializedParameter();
331 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
333 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
336 class DefProcessedMap : public Bfs< Graph,
337 DefProcessedMapTraits<T> > { };
339 struct DefGraphProcessedMapTraits : public Traits {
340 typedef typename Graph::template NodeMap<bool> ProcessedMap;
341 static ProcessedMap *createProcessedMap(const Graph &G)
343 return new ProcessedMap(G);
346 ///\brief \ref named-templ-param "Named parameter"
347 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
349 ///\ref named-templ-param "Named parameter"
350 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
351 ///If you don't set it explicitly, it will be automatically allocated.
353 class DefProcessedMapToBeDefaultMap :
355 DefGraphProcessedMapTraits> { };
363 ///\param _G the graph the algorithm will run on.
365 Bfs(const Graph& _G) :
367 _pred(NULL), local_pred(false),
368 // _predNode(NULL), local_predNode(false),
369 _dist(NULL), local_dist(false),
370 _reached(NULL), local_reached(false),
371 _processed(NULL), local_processed(false)
377 if(local_pred) delete _pred;
378 // if(local_predNode) delete _predNode;
379 if(local_dist) delete _dist;
380 if(local_reached) delete _reached;
381 if(local_processed) delete _processed;
384 ///Sets the map storing the predecessor edges.
386 ///Sets the map storing the predecessor edges.
387 ///If you don't use this function before calling \ref run(),
388 ///it will allocate one. The destructor deallocates this
389 ///automatically allocated map, of course.
390 ///\return <tt> (*this) </tt>
391 Bfs &predMap(PredMap &m)
401 ///Sets the map indicating the reached nodes.
403 ///Sets the map indicating the reached nodes.
404 ///If you don't use this function before calling \ref run(),
405 ///it will allocate one. The destructor deallocates this
406 ///automatically allocated map, of course.
407 ///\return <tt> (*this) </tt>
408 Bfs &reachedMap(ReachedMap &m)
418 ///Sets the map indicating the processed nodes.
420 ///Sets the map indicating the processed nodes.
421 ///If you don't use this function before calling \ref run(),
422 ///it will allocate one. The destructor deallocates this
423 ///automatically allocated map, of course.
424 ///\return <tt> (*this) </tt>
425 Bfs &processedMap(ProcessedMap &m)
427 if(local_processed) {
429 local_processed=false;
435 // ///Sets the map storing the predecessor nodes.
437 // ///Sets the map storing the predecessor nodes.
438 // ///If you don't use this function before calling \ref run(),
439 // ///it will allocate one. The destructor deallocates this
440 // ///automatically allocated map, of course.
441 // ///\return <tt> (*this) </tt>
442 // Bfs &predNodeMap(PredNodeMap &m)
444 // if(local_predNode) {
446 // local_predNode=false;
452 ///Sets the map storing the distances calculated by the algorithm.
454 ///Sets the map storing the distances calculated by the algorithm.
455 ///If you don't use this function before calling \ref run(),
456 ///it will allocate one. The destructor deallocates this
457 ///automatically allocated map, of course.
458 ///\return <tt> (*this) </tt>
459 Bfs &distMap(DistMap &m)
470 ///\name Execution control
471 ///The simplest way to execute the algorithm is to use
472 ///one of the member functions called \c run(...).
474 ///If you need more control on the execution,
475 ///first you must call \ref init(), then you can add several source nodes
476 ///with \ref addSource().
477 ///Finally \ref start() will perform the actual path
482 ///Initializes the internal data structures.
484 ///Initializes the internal data structures.
489 _queue.resize(countNodes(*G));
490 _queue_head=_queue_tail=0;
492 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
493 _pred->set(u,INVALID);
494 // _predNode->set(u,INVALID);
495 _reached->set(u,false);
496 _processed->set(u,false);
500 ///Adds a new source node.
502 ///Adds a new source node to the set of nodes to be processed.
504 void addSource(Node s)
508 _reached->set(s,true);
509 _pred->set(s,INVALID);
511 _queue[_queue_head++]=s;
512 _queue_next_dist=_queue_head;
516 ///Processes the next node.
518 ///Processes the next node.
520 ///\return The processed node.
522 ///\warning The queue must not be empty!
523 Node processNextNode()
525 if(_queue_tail==_queue_next_dist) {
527 _queue_next_dist=_queue_head;
529 Node n=_queue[_queue_tail++];
530 _processed->set(n,true);
532 for(OutEdgeIt e(*G,n);e!=INVALID;++e)
533 if(!(*_reached)[m=G->target(e)]) {
534 _queue[_queue_head++]=m;
535 _reached->set(m,true);
537 // _pred_node->set(m,n);
538 _dist->set(m,_curr_dist);
543 ///\brief Returns \c false if there are nodes
544 ///to be processed in the queue
546 ///Returns \c false if there are nodes
547 ///to be processed in the queue
548 bool emptyQueue() { return _queue_tail==_queue_head; }
549 ///Returns the number of the nodes to be processed.
551 ///Returns the number of the nodes to be processed in the queue.
553 int queueSize() { return _queue_head-_queue_tail; }
555 ///Executes the algorithm.
557 ///Executes the algorithm.
559 ///\pre init() must be called and at least one node should be added
560 ///with addSource() before using this function.
562 ///This method runs the %BFS algorithm from the root node(s)
565 ///shortest path to each node. The algorithm computes
566 ///- The shortest path tree.
567 ///- The distance of each node from the root(s).
571 while ( !emptyQueue() ) processNextNode();
574 ///Executes the algorithm until \c dest is reached.
576 ///Executes the algorithm until \c dest is reached.
578 ///\pre init() must be called and at least one node should be added
579 ///with addSource() before using this function.
581 ///This method runs the %BFS algorithm from the root node(s)
584 ///shortest path to \c dest. The algorithm computes
585 ///- The shortest path to \c dest.
586 ///- The distance of \c dest from the root(s).
588 void start(Node dest)
590 while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextNode();
593 ///Executes the algorithm until a condition is met.
595 ///Executes the algorithm until a condition is met.
597 ///\pre init() must be called and at least one node should be added
598 ///with addSource() before using this function.
600 ///\param nm must be a bool (or convertible) node map. The algorithm
601 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
603 void start(const NM &nm)
605 while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextNode();
608 ///Runs %BFS algorithm from node \c s.
610 ///This method runs the %BFS algorithm from a root node \c s
613 ///shortest path to each node. The algorithm computes
614 ///- The shortest path tree.
615 ///- The distance of each node from the root.
617 ///\note d.run(s) is just a shortcut of the following code.
629 ///Finds the shortest path between \c s and \c t.
631 ///Finds the shortest path between \c s and \c t.
633 ///\return The length of the shortest s---t path if there exists one,
635 ///\note Apart from the return value, d.run(s) is
636 ///just a shortcut of the following code.
642 int run(Node s,Node t) {
646 return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
651 ///\name Query Functions
652 ///The result of the %BFS algorithm can be obtained using these
654 ///Before the use of these functions,
655 ///either run() or start() must be called.
659 ///Copies the shortest path to \c t into \c p
661 ///This function copies the shortest path to \c t into \c p.
662 ///If it \c \t is a source itself or unreachable, then it does not
664 ///\todo Is it the right way to handle unreachable nodes?
665 ///\return Returns \c true if a path to \c t was actually copied to \c p,
666 ///\c false otherwise.
669 bool getPath(P &p,Node t)
673 typename P::Builder b(p);
674 for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
675 b.pushFront(pred(t));
682 ///The distance of a node from the root(s).
684 ///Returns the distance of a node from the root(s).
685 ///\pre \ref run() must be called before using this function.
686 ///\warning If node \c v in unreachable from the root(s) the return value
687 ///of this function is undefined.
688 int dist(Node v) const { return (*_dist)[v]; }
690 ///Returns the 'previous edge' of the shortest path tree.
692 ///For a node \c v it returns the 'previous edge'
693 ///of the shortest path tree,
694 ///i.e. it returns the last edge of a shortest path from the root(s) to \c
695 ///v. It is \ref INVALID
696 ///if \c v is unreachable from the root(s) or \c v is a root. The
697 ///shortest path tree used here is equal to the shortest path tree used in
698 ///\ref predNode(Node v).
699 ///\pre Either \ref run() or \ref start() must be called before using
701 ///\todo predEdge could be a better name.
702 Edge pred(Node v) const { return (*_pred)[v];}
704 ///Returns the 'previous node' of the shortest path tree.
706 ///For a node \c v it returns the 'previous node'
707 ///of the shortest path tree,
708 ///i.e. it returns the last but one node from a shortest path from the
710 ///It is INVALID if \c v is unreachable from the root(s) or
711 ///if \c v itself a root.
712 ///The shortest path tree used here is equal to the shortest path
713 ///tree used in \ref pred(Node v).
714 ///\pre Either \ref run() or \ref start() must be called before
715 ///using this function.
716 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
717 G->source((*_pred)[v]); }
719 ///Returns a reference to the NodeMap of distances.
721 ///Returns a reference to the NodeMap of distances.
722 ///\pre Either \ref run() or \ref init() must
723 ///be called before using this function.
724 const DistMap &distMap() const { return *_dist;}
726 ///Returns a reference to the shortest path tree map.
728 ///Returns a reference to the NodeMap of the edges of the
729 ///shortest path tree.
730 ///\pre Either \ref run() or \ref init()
731 ///must be called before using this function.
732 const PredMap &predMap() const { return *_pred;}
734 // ///Returns a reference to the map of nodes of shortest paths.
736 // ///Returns a reference to the NodeMap of the last but one nodes of the
737 // ///shortest path tree.
738 // ///\pre \ref run() must be called before using this function.
739 // const PredNodeMap &predNodeMap() const { return *_predNode;}
741 ///Checks if a node is reachable from the root.
743 ///Returns \c true if \c v is reachable from the root.
744 ///\warning The source nodes are indicated as unreached.
745 ///\pre Either \ref run() or \ref start()
746 ///must be called before using this function.
748 bool reached(Node v) { return (*_reached)[v]; }
753 ///Default traits class of Bfs function.
755 ///Default traits class of Bfs function.
756 ///\param GR Graph type.
758 struct BfsWizardDefaultTraits
760 ///The graph type the algorithm runs on.
762 ///\brief The type of the map that stores the last
763 ///edges of the shortest paths.
765 ///The type of the map that stores the last
766 ///edges of the shortest paths.
767 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
769 typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
770 ///Instantiates a PredMap.
772 ///This function instantiates a \ref PredMap.
773 ///\param G is the graph, to which we would like to define the PredMap.
774 ///\todo The graph alone may be insufficient to initialize
775 static PredMap *createPredMap(const GR &)
777 return new PredMap();
779 // ///\brief The type of the map that stores the last but one
780 // ///nodes of the shortest paths.
782 // ///The type of the map that stores the last but one
783 // ///nodes of the shortest paths.
784 // ///It must meet the \ref concept::WriteMap "WriteMap" concept.
786 // typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
787 // ///Instantiates a PredNodeMap.
789 // ///This function instantiates a \ref PredNodeMap.
790 // ///\param G is the graph, to which
791 // ///we would like to define the \ref PredNodeMap
792 // static PredNodeMap *createPredNodeMap(const GR &G)
794 // return new PredNodeMap();
797 ///The type of the map that indicates which nodes are processed.
799 ///The type of the map that indicates which nodes are processed.
800 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
801 ///\todo named parameter to set this type, function to read and write.
802 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
803 ///Instantiates a ProcessedMap.
805 ///This function instantiates a \ref ProcessedMap.
806 ///\param G is the graph, to which
807 ///we would like to define the \ref ProcessedMap
808 static ProcessedMap *createProcessedMap(const GR &)
810 return new ProcessedMap();
812 ///The type of the map that indicates which nodes are reached.
814 ///The type of the map that indicates which nodes are reached.
815 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
816 ///\todo named parameter to set this type, function to read and write.
817 typedef typename Graph::template NodeMap<bool> ReachedMap;
818 ///Instantiates a ReachedMap.
820 ///This function instantiates a \ref ReachedMap.
821 ///\param G is the graph, to which
822 ///we would like to define the \ref ReachedMap.
823 static ReachedMap *createReachedMap(const GR &G)
825 return new ReachedMap(G);
827 ///The type of the map that stores the dists of the nodes.
829 ///The type of the map that stores the dists of the nodes.
830 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
832 typedef NullMap<typename Graph::Node,int> DistMap;
833 ///Instantiates a DistMap.
835 ///This function instantiates a \ref DistMap.
836 ///\param G is the graph, to which we would like to define the \ref DistMap
837 static DistMap *createDistMap(const GR &)
839 return new DistMap();
843 /// Default traits used by \ref BfsWizard
845 /// To make it easier to use Bfs algorithm
846 ///we have created a wizard class.
847 /// This \ref BfsWizard class needs default traits,
848 ///as well as the \ref Bfs class.
849 /// The \ref BfsWizardBase is a class to be the default traits of the
850 /// \ref BfsWizard class.
852 class BfsWizardBase : public BfsWizardDefaultTraits<GR>
855 typedef BfsWizardDefaultTraits<GR> Base;
857 /// Type of the nodes in the graph.
858 typedef typename Base::Graph::Node Node;
860 /// Pointer to the underlying graph.
862 ///Pointer to the map of reached nodes.
864 ///Pointer to the map of processed nodes.
866 ///Pointer to the map of predecessors edges.
868 // ///Pointer to the map of predecessors nodes.
870 ///Pointer to the map of distances.
872 ///Pointer to the source node.
878 /// This constructor does not require parameters, therefore it initiates
879 /// all of the attributes to default values (0, INVALID).
880 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
882 _dist(0), _source(INVALID) {}
886 /// This constructor requires some parameters,
887 /// listed in the parameters list.
888 /// Others are initiated to 0.
889 /// \param g is the initial value of \ref _g
890 /// \param s is the initial value of \ref _source
891 BfsWizardBase(const GR &g, Node s=INVALID) :
892 _g((void *)&g), _reached(0), _processed(0), _pred(0),
894 _dist(0), _source(s) {}
898 /// A class to make the usage of Bfs algorithm easier
900 /// This class is created to make it easier to use Bfs algorithm.
901 /// It uses the functions and features of the plain \ref Bfs,
902 /// but it is much simpler to use it.
904 /// Simplicity means that the way to change the types defined
905 /// in the traits class is based on functions that returns the new class
906 /// and not on templatable built-in classes.
907 /// When using the plain \ref Bfs
908 /// the new class with the modified type comes from
909 /// the original class by using the ::
910 /// operator. In the case of \ref BfsWizard only
911 /// a function have to be called and it will
912 /// return the needed class.
914 /// It does not have own \ref run method. When its \ref run method is called
915 /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run
918 class BfsWizard : public TR
922 ///The type of the underlying graph.
923 typedef typename TR::Graph Graph;
925 typedef typename Graph::Node Node;
927 typedef typename Graph::NodeIt NodeIt;
929 typedef typename Graph::Edge Edge;
931 typedef typename Graph::OutEdgeIt OutEdgeIt;
933 ///\brief The type of the map that stores
935 typedef typename TR::ReachedMap ReachedMap;
936 ///\brief The type of the map that stores
937 ///the processed nodes
938 typedef typename TR::ProcessedMap ProcessedMap;
939 ///\brief The type of the map that stores the last
940 ///edges of the shortest paths.
941 typedef typename TR::PredMap PredMap;
942 // ///\brief The type of the map that stores the last but one
943 // ///nodes of the shortest paths.
944 // typedef typename TR::PredNodeMap PredNodeMap;
945 ///The type of the map that stores the dists of the nodes.
946 typedef typename TR::DistMap DistMap;
950 BfsWizard() : TR() {}
952 /// Constructor that requires parameters.
954 /// Constructor that requires parameters.
955 /// These parameters will be the default values for the traits class.
956 BfsWizard(const Graph &g, Node s=INVALID) :
960 BfsWizard(const TR &b) : TR(b) {}
964 ///Runs Bfs algorithm from a given node.
966 ///Runs Bfs algorithm from a given node.
967 ///The node can be given by the \ref source function.
970 if(Base::_source==INVALID) throw UninitializedParameter();
971 Bfs<Graph,TR> alg(*(Graph*)Base::_g);
973 alg.reachedMap(*(ReachedMap*)Base::_reached);
974 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
975 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
976 // if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
977 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
978 alg.run(Base::_source);
981 ///Runs Bfs algorithm from the given node.
983 ///Runs Bfs algorithm from the given node.
984 ///\param s is the given source.
992 struct DefPredMapBase : public Base {
994 static PredMap *createPredMap(const Graph &) { return 0; };
995 DefPredMapBase(const TR &b) : TR(b) {}
998 ///\brief \ref named-templ-param "Named parameter"
999 ///function for setting PredMap
1001 /// \ref named-templ-param "Named parameter"
1002 ///function for setting PredMap
1005 BfsWizard<DefPredMapBase<T> > predMap(const T &t)
1007 Base::_pred=(void *)&t;
1008 return BfsWizard<DefPredMapBase<T> >(*this);
1013 struct DefReachedMapBase : public Base {
1014 typedef T ReachedMap;
1015 static ReachedMap *createReachedMap(const Graph &) { return 0; };
1016 DefReachedMapBase(const TR &b) : TR(b) {}
1019 ///\brief \ref named-templ-param "Named parameter"
1020 ///function for setting ReachedMap
1022 /// \ref named-templ-param "Named parameter"
1023 ///function for setting ReachedMap
1026 BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1028 Base::_pred=(void *)&t;
1029 return BfsWizard<DefReachedMapBase<T> >(*this);
1034 struct DefProcessedMapBase : public Base {
1035 typedef T ProcessedMap;
1036 static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
1037 DefProcessedMapBase(const TR &b) : TR(b) {}
1040 ///\brief \ref named-templ-param "Named parameter"
1041 ///function for setting ProcessedMap
1043 /// \ref named-templ-param "Named parameter"
1044 ///function for setting ProcessedMap
1047 BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1049 Base::_pred=(void *)&t;
1050 return BfsWizard<DefProcessedMapBase<T> >(*this);
1054 // template<class T>
1055 // struct DefPredNodeMapBase : public Base {
1056 // typedef T PredNodeMap;
1057 // static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
1058 // DefPredNodeMapBase(const TR &b) : TR(b) {}
1061 // ///\brief \ref named-templ-param "Named parameter"
1062 // ///function for setting PredNodeMap type
1064 // /// \ref named-templ-param "Named parameter"
1065 // ///function for setting PredNodeMap type
1067 // template<class T>
1068 // BfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1070 // Base::_predNode=(void *)&t;
1071 // return BfsWizard<DefPredNodeMapBase<T> >(*this);
1075 struct DefDistMapBase : public Base {
1077 static DistMap *createDistMap(const Graph &) { return 0; };
1078 DefDistMapBase(const TR &b) : TR(b) {}
1081 ///\brief \ref named-templ-param "Named parameter"
1082 ///function for setting DistMap type
1084 /// \ref named-templ-param "Named parameter"
1085 ///function for setting DistMap type
1088 BfsWizard<DefDistMapBase<T> > distMap(const T &t)
1090 Base::_dist=(void *)&t;
1091 return BfsWizard<DefDistMapBase<T> >(*this);
1094 /// Sets the source node, from which the Bfs algorithm runs.
1096 /// Sets the source node, from which the Bfs algorithm runs.
1097 /// \param s is the source node.
1098 BfsWizard<TR> &source(Node s)
1106 ///Function type interface for Bfs algorithm.
1108 /// \ingroup flowalgs
1109 ///Function type interface for Bfs algorithm.
1111 ///This function also has several
1112 ///\ref named-templ-func-param "named parameters",
1113 ///they are declared as the members of class \ref BfsWizard.
1115 ///example shows how to use these parameters.
1117 /// bfs(g,source).predMap(preds).run();
1119 ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
1120 ///to the end of the parameter list.
1124 BfsWizard<BfsWizardBase<GR> >
1125 bfs(const GR &g,typename GR::Node s=INVALID)
1127 return BfsWizard<BfsWizardBase<GR> >(g,s);
1130 } //END OF NAMESPACE LEMON