Added copyright header and description.
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, DefPredMapTraits<T> > { };
270 // template <class T>
271 // struct DefPredNodeMapTraits : public Traits {
272 // typedef T PredNodeMap;
273 // static PredNodeMap *createPredNodeMap(const Graph &G)
275 // throw UninitializedParameter();
278 // ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
280 // ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
282 // template <class T>
283 // class DefPredNodeMap : public Bfs< Graph,
285 // DefPredNodeMapTraits<T> > { };
288 struct DefDistMapTraits : public Traits {
290 static DistMap *createDistMap(const Graph &G)
292 throw UninitializedParameter();
295 ///\ref named-templ-param "Named parameter" for setting DistMap type
297 ///\ref named-templ-param "Named parameter" for setting DistMap type
300 class DefDistMap : public Bfs< Graph,
301 DefDistMapTraits<T> > { };
304 struct DefReachedMapTraits : public Traits {
305 typedef T ReachedMap;
306 static ReachedMap *createReachedMap(const Graph &G)
308 throw UninitializedParameter();
311 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
313 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
316 class DefReachedMap : public Bfs< Graph,
317 DefReachedMapTraits<T> > { };
319 struct DefGraphReachedMapTraits : public Traits {
320 typedef typename Graph::template NodeMap<bool> ReachedMap;
321 static ReachedMap *createReachedMap(const Graph &G)
323 return new ReachedMap(G);
327 struct DefProcessedMapTraits : public Traits {
328 typedef T ProcessedMap;
329 static ProcessedMap *createProcessedMap(const Graph &G)
331 throw UninitializedParameter();
334 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
336 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
339 class DefProcessedMap : public Bfs< Graph,
340 DefProcessedMapTraits<T> > { };
342 struct DefGraphProcessedMapTraits : public Traits {
343 typedef typename Graph::template NodeMap<bool> ProcessedMap;
344 static ProcessedMap *createProcessedMap(const Graph &G)
346 return new ProcessedMap(G);
349 ///\brief \ref named-templ-param "Named parameter"
350 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
352 ///\ref named-templ-param "Named parameter"
353 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
354 ///If you don't set it explicitly, it will be automatically allocated.
356 class DefProcessedMapToBeDefaultMap :
358 DefGraphProcessedMapTraits> { };
366 ///\param _G the graph the algorithm will run on.
368 Bfs(const Graph& _G) :
370 _pred(NULL), local_pred(false),
371 // _predNode(NULL), local_predNode(false),
372 _dist(NULL), local_dist(false),
373 _reached(NULL), local_reached(false),
374 _processed(NULL), local_processed(false)
380 if(local_pred) delete _pred;
381 // if(local_predNode) delete _predNode;
382 if(local_dist) delete _dist;
383 if(local_reached) delete _reached;
384 if(local_processed) delete _processed;
387 ///Sets the map storing the predecessor edges.
389 ///Sets the map storing the predecessor edges.
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 &predMap(PredMap &m)
404 ///Sets the map indicating the reached nodes.
406 ///Sets the map indicating the reached nodes.
407 ///If you don't use this function before calling \ref run(),
408 ///it will allocate one. The destructor deallocates this
409 ///automatically allocated map, of course.
410 ///\return <tt> (*this) </tt>
411 Bfs &reachedMap(ReachedMap &m)
421 ///Sets the map indicating the processed nodes.
423 ///Sets the map indicating the processed nodes.
424 ///If you don't use this function before calling \ref run(),
425 ///it will allocate one. The destructor deallocates this
426 ///automatically allocated map, of course.
427 ///\return <tt> (*this) </tt>
428 Bfs &processedMap(ProcessedMap &m)
430 if(local_processed) {
432 local_processed=false;
438 // ///Sets the map storing the predecessor nodes.
440 // ///Sets the map storing the predecessor nodes.
441 // ///If you don't use this function before calling \ref run(),
442 // ///it will allocate one. The destructor deallocates this
443 // ///automatically allocated map, of course.
444 // ///\return <tt> (*this) </tt>
445 // Bfs &predNodeMap(PredNodeMap &m)
447 // if(local_predNode) {
449 // local_predNode=false;
455 ///Sets the map storing the distances calculated by the algorithm.
457 ///Sets the map storing the distances calculated by the algorithm.
458 ///If you don't use this function before calling \ref run(),
459 ///it will allocate one. The destructor deallocates this
460 ///automatically allocated map, of course.
461 ///\return <tt> (*this) </tt>
462 Bfs &distMap(DistMap &m)
473 ///\name Execution control
474 ///The simplest way to execute the algorithm is to use
475 ///one of the member functions called \c run(...).
477 ///If you need more control on the execution,
478 ///first you must call \ref init(), then you can add several source nodes
479 ///with \ref addSource().
480 ///Finally \ref start() will perform the actual path
485 ///Initializes the internal data structures.
487 ///Initializes the internal data structures.
492 _queue.resize(countNodes(*G));
493 _queue_head=_queue_tail=0;
495 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
496 _pred->set(u,INVALID);
497 // _predNode->set(u,INVALID);
498 _reached->set(u,false);
499 _processed->set(u,false);
503 ///Adds a new source node.
505 ///Adds a new source node to the set of nodes to be processed.
507 void addSource(Node s)
511 _reached->set(s,true);
512 _pred->set(s,INVALID);
514 _queue[_queue_head++]=s;
515 _queue_next_dist=_queue_head;
519 ///Processes the next node.
521 ///Processes the next node.
523 ///\return The processed node.
525 ///\warning The queue must not be empty!
526 Node processNextNode()
528 if(_queue_tail==_queue_next_dist) {
530 _queue_next_dist=_queue_head;
532 Node n=_queue[_queue_tail++];
533 _processed->set(n,true);
535 for(OutEdgeIt e(*G,n);e!=INVALID;++e)
536 if(!(*_reached)[m=G->target(e)]) {
537 _queue[_queue_head++]=m;
538 _reached->set(m,true);
540 // _pred_node->set(m,n);
541 _dist->set(m,_curr_dist);
546 ///\brief Returns \c false if there are nodes
547 ///to be processed in the queue
549 ///Returns \c false if there are nodes
550 ///to be processed in the queue
551 bool emptyQueue() { return _queue_tail==_queue_head; }
552 ///Returns the number of the nodes to be processed.
554 ///Returns the number of the nodes to be processed in the queue.
556 int queueSize() { return _queue_head-_queue_tail; }
558 ///Executes the algorithm.
560 ///Executes the algorithm.
562 ///\pre init() must be called and at least one node should be added
563 ///with addSource() before using this function.
565 ///This method runs the %BFS algorithm from the root node(s)
568 ///shortest path to each node. The algorithm computes
569 ///- The shortest path tree.
570 ///- The distance of each node from the root(s).
574 while ( !emptyQueue() ) processNextNode();
577 ///Executes the algorithm until \c dest is reached.
579 ///Executes the algorithm until \c dest is reached.
581 ///\pre init() must be called and at least one node should be added
582 ///with addSource() before using this function.
584 ///This method runs the %BFS algorithm from the root node(s)
587 ///shortest path to \c dest. The algorithm computes
588 ///- The shortest path to \c dest.
589 ///- The distance of \c dest from the root(s).
591 void start(Node dest)
593 while ( !emptyQueue() && _queue[_queue_tail]!=dest ) processNextNode();
596 ///Executes the algorithm until a condition is met.
598 ///Executes the algorithm until a condition is met.
600 ///\pre init() must be called and at least one node should be added
601 ///with addSource() before using this function.
603 ///\param nm must be a bool (or convertible) node map. The algorithm
604 ///will stop when it reaches a node \c v with <tt>nm[v]==true</tt>.
606 void start(const NM &nm)
608 while ( !emptyQueue() && !nm[_queue[_queue_tail]] ) processNextNode();
611 ///Runs %BFS algorithm from node \c s.
613 ///This method runs the %BFS algorithm from a root node \c s
616 ///shortest path to each node. The algorithm computes
617 ///- The shortest path tree.
618 ///- The distance of each node from the root.
620 ///\note d.run(s) is just a shortcut of the following code.
632 ///Finds the shortest path between \c s and \c t.
634 ///Finds the shortest path between \c s and \c t.
636 ///\return The length of the shortest s---t path if there exists one,
638 ///\note Apart from the return value, d.run(s) is
639 ///just a shortcut of the following code.
645 int run(Node s,Node t) {
649 return reached(t)?_curr_dist-1+(_queue_tail==_queue_next_dist):0;
654 ///\name Query Functions
655 ///The result of the %BFS algorithm can be obtained using these
657 ///Before the use of these functions,
658 ///either run() or start() must be called.
662 ///Copies the shortest path to \c t into \c p
664 ///This function copies the shortest path to \c t into \c p.
665 ///If \c t is a source itself or unreachable, then it does not
667 ///\todo Is it the right way to handle unreachable nodes?
668 ///\return Returns \c true if a path to \c t was actually copied to \c p,
669 ///\c false otherwise.
672 bool getPath(P &p,Node t)
676 typename P::Builder b(p);
677 for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
678 b.pushFront(pred(t));
685 ///The distance of a node from the root(s).
687 ///Returns the distance of a node from the root(s).
688 ///\pre \ref run() must be called before using this function.
689 ///\warning If node \c v in unreachable from the root(s) the return value
690 ///of this function is undefined.
691 int dist(Node v) const { return (*_dist)[v]; }
693 ///Returns the 'previous edge' of the shortest path tree.
695 ///For a node \c v it returns the 'previous edge'
696 ///of the shortest path tree,
697 ///i.e. it returns the last edge of a shortest path from the root(s) to \c
698 ///v. It is \ref INVALID
699 ///if \c v is unreachable from the root(s) or \c v is a root. The
700 ///shortest path tree used here is equal to the shortest path tree used in
701 ///\ref predNode(Node v).
702 ///\pre Either \ref run() or \ref start() must be called before using
704 ///\todo predEdge could be a better name.
705 Edge pred(Node v) const { return (*_pred)[v];}
707 ///Returns the 'previous node' of the shortest path tree.
709 ///For a node \c v it returns the 'previous node'
710 ///of the shortest path tree,
711 ///i.e. it returns the last but one node from a shortest path from the
713 ///It is INVALID if \c v is unreachable from the root(s) or
714 ///if \c v itself a root.
715 ///The shortest path tree used here is equal to the shortest path
716 ///tree used in \ref pred(Node v).
717 ///\pre Either \ref run() or \ref start() must be called before
718 ///using this function.
719 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
720 G->source((*_pred)[v]); }
722 ///Returns a reference to the NodeMap of distances.
724 ///Returns a reference to the NodeMap of distances.
725 ///\pre Either \ref run() or \ref init() must
726 ///be called before using this function.
727 const DistMap &distMap() const { return *_dist;}
729 ///Returns a reference to the shortest path tree map.
731 ///Returns a reference to the NodeMap of the edges of the
732 ///shortest path tree.
733 ///\pre Either \ref run() or \ref init()
734 ///must be called before using this function.
735 const PredMap &predMap() const { return *_pred;}
737 // ///Returns a reference to the map of nodes of shortest paths.
739 // ///Returns a reference to the NodeMap of the last but one nodes of the
740 // ///shortest path tree.
741 // ///\pre \ref run() must be called before using this function.
742 // const PredNodeMap &predNodeMap() const { return *_predNode;}
744 ///Checks if a node is reachable from the root.
746 ///Returns \c true if \c v is reachable from the root.
747 ///\warning The source nodes are indicated as unreached.
748 ///\pre Either \ref run() or \ref start()
749 ///must be called before using this function.
751 bool reached(Node v) { return (*_reached)[v]; }
756 ///Default traits class of Bfs function.
758 ///Default traits class of Bfs function.
759 ///\param GR Graph type.
761 struct BfsWizardDefaultTraits
763 ///The graph type the algorithm runs on.
765 ///\brief The type of the map that stores the last
766 ///edges of the shortest paths.
768 ///The type of the map that stores the last
769 ///edges of the shortest paths.
770 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
772 typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
773 ///Instantiates a PredMap.
775 ///This function instantiates a \ref PredMap.
776 ///\param g is the graph, to which we would like to define the PredMap.
777 ///\todo The graph alone may be insufficient to initialize
779 static PredMap *createPredMap(const GR &g)
781 static PredMap *createPredMap(const GR &)
784 return new PredMap();
786 // ///\brief The type of the map that stores the last but one
787 // ///nodes of the shortest paths.
789 // ///The type of the map that stores the last but one
790 // ///nodes of the shortest paths.
791 // ///It must meet the \ref concept::WriteMap "WriteMap" concept.
793 // typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
794 // ///Instantiates a PredNodeMap.
796 // ///This function instantiates a \ref PredNodeMap.
797 // ///\param G is the graph, to which
798 // ///we would like to define the \ref PredNodeMap
799 // static PredNodeMap *createPredNodeMap(const GR &G)
801 // return new PredNodeMap();
804 ///The type of the map that indicates which nodes are processed.
806 ///The type of the map that indicates which nodes are processed.
807 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
808 ///\todo named parameter to set this type, function to read and write.
809 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
810 ///Instantiates a ProcessedMap.
812 ///This function instantiates a \ref ProcessedMap.
813 ///\param g is the graph, to which
814 ///we would like to define the \ref ProcessedMap
816 static ProcessedMap *createProcessedMap(const GR &g)
818 static ProcessedMap *createProcessedMap(const GR &)
821 return new ProcessedMap();
823 ///The type of the map that indicates which nodes are reached.
825 ///The type of the map that indicates which nodes are reached.
826 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
827 ///\todo named parameter to set this type, function to read and write.
828 typedef typename Graph::template NodeMap<bool> ReachedMap;
829 ///Instantiates a ReachedMap.
831 ///This function instantiates a \ref ReachedMap.
832 ///\param G is the graph, to which
833 ///we would like to define the \ref ReachedMap.
834 static ReachedMap *createReachedMap(const GR &G)
836 return new ReachedMap(G);
838 ///The type of the map that stores the dists of the nodes.
840 ///The type of the map that stores the dists of the nodes.
841 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
843 typedef NullMap<typename Graph::Node,int> DistMap;
844 ///Instantiates a DistMap.
846 ///This function instantiates a \ref DistMap.
847 ///\param g is the graph, to which we would like to define the \ref DistMap
849 static DistMap *createDistMap(const GR &g)
851 static DistMap *createDistMap(const GR &)
854 return new DistMap();
858 /// Default traits used by \ref BfsWizard
860 /// To make it easier to use Bfs algorithm
861 ///we have created a wizard class.
862 /// This \ref BfsWizard class needs default traits,
863 ///as well as the \ref Bfs class.
864 /// The \ref BfsWizardBase is a class to be the default traits of the
865 /// \ref BfsWizard class.
867 class BfsWizardBase : public BfsWizardDefaultTraits<GR>
870 typedef BfsWizardDefaultTraits<GR> Base;
872 /// Type of the nodes in the graph.
873 typedef typename Base::Graph::Node Node;
875 /// Pointer to the underlying graph.
877 ///Pointer to the map of reached nodes.
879 ///Pointer to the map of processed nodes.
881 ///Pointer to the map of predecessors edges.
883 // ///Pointer to the map of predecessors nodes.
885 ///Pointer to the map of distances.
887 ///Pointer to the source node.
893 /// This constructor does not require parameters, therefore it initiates
894 /// all of the attributes to default values (0, INVALID).
895 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
897 _dist(0), _source(INVALID) {}
901 /// This constructor requires some parameters,
902 /// listed in the parameters list.
903 /// Others are initiated to 0.
904 /// \param g is the initial value of \ref _g
905 /// \param s is the initial value of \ref _source
906 BfsWizardBase(const GR &g, Node s=INVALID) :
907 _g((void *)&g), _reached(0), _processed(0), _pred(0),
909 _dist(0), _source(s) {}
913 /// A class to make the usage of Bfs algorithm easier
915 /// This class is created to make it easier to use Bfs algorithm.
916 /// It uses the functions and features of the plain \ref Bfs,
917 /// but it is much simpler to use it.
919 /// Simplicity means that the way to change the types defined
920 /// in the traits class is based on functions that returns the new class
921 /// and not on templatable built-in classes.
922 /// When using the plain \ref Bfs
923 /// the new class with the modified type comes from
924 /// the original class by using the ::
925 /// operator. In the case of \ref BfsWizard only
926 /// a function have to be called and it will
927 /// return the needed class.
929 /// It does not have own \ref run method. When its \ref run method is called
930 /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run
933 class BfsWizard : public TR
937 ///The type of the underlying graph.
938 typedef typename TR::Graph Graph;
940 typedef typename Graph::Node Node;
942 typedef typename Graph::NodeIt NodeIt;
944 typedef typename Graph::Edge Edge;
946 typedef typename Graph::OutEdgeIt OutEdgeIt;
948 ///\brief The type of the map that stores
950 typedef typename TR::ReachedMap ReachedMap;
951 ///\brief The type of the map that stores
952 ///the processed nodes
953 typedef typename TR::ProcessedMap ProcessedMap;
954 ///\brief The type of the map that stores the last
955 ///edges of the shortest paths.
956 typedef typename TR::PredMap PredMap;
957 // ///\brief The type of the map that stores the last but one
958 // ///nodes of the shortest paths.
959 // typedef typename TR::PredNodeMap PredNodeMap;
960 ///The type of the map that stores the dists of the nodes.
961 typedef typename TR::DistMap DistMap;
965 BfsWizard() : TR() {}
967 /// Constructor that requires parameters.
969 /// Constructor that requires parameters.
970 /// These parameters will be the default values for the traits class.
971 BfsWizard(const Graph &g, Node s=INVALID) :
975 BfsWizard(const TR &b) : TR(b) {}
979 ///Runs Bfs algorithm from a given node.
981 ///Runs Bfs algorithm from a given node.
982 ///The node can be given by the \ref source function.
985 if(Base::_source==INVALID) throw UninitializedParameter();
986 Bfs<Graph,TR> alg(*(Graph*)Base::_g);
988 alg.reachedMap(*(ReachedMap*)Base::_reached);
989 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
990 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
991 // if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
992 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
993 alg.run(Base::_source);
996 ///Runs Bfs algorithm from the given node.
998 ///Runs Bfs algorithm from the given node.
999 ///\param s is the given source.
1007 struct DefPredMapBase : public Base {
1009 static PredMap *createPredMap(const Graph &) { return 0; };
1010 DefPredMapBase(const TR &b) : TR(b) {}
1013 ///\brief \ref named-templ-param "Named parameter"
1014 ///function for setting PredMap
1016 /// \ref named-templ-param "Named parameter"
1017 ///function for setting PredMap
1020 BfsWizard<DefPredMapBase<T> > predMap(const T &t)
1022 Base::_pred=(void *)&t;
1023 return BfsWizard<DefPredMapBase<T> >(*this);
1028 struct DefReachedMapBase : public Base {
1029 typedef T ReachedMap;
1030 static ReachedMap *createReachedMap(const Graph &) { return 0; };
1031 DefReachedMapBase(const TR &b) : TR(b) {}
1034 ///\brief \ref named-templ-param "Named parameter"
1035 ///function for setting ReachedMap
1037 /// \ref named-templ-param "Named parameter"
1038 ///function for setting ReachedMap
1041 BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1043 Base::_pred=(void *)&t;
1044 return BfsWizard<DefReachedMapBase<T> >(*this);
1049 struct DefProcessedMapBase : public Base {
1050 typedef T ProcessedMap;
1051 static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
1052 DefProcessedMapBase(const TR &b) : TR(b) {}
1055 ///\brief \ref named-templ-param "Named parameter"
1056 ///function for setting ProcessedMap
1058 /// \ref named-templ-param "Named parameter"
1059 ///function for setting ProcessedMap
1062 BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1064 Base::_pred=(void *)&t;
1065 return BfsWizard<DefProcessedMapBase<T> >(*this);
1069 // template<class T>
1070 // struct DefPredNodeMapBase : public Base {
1071 // typedef T PredNodeMap;
1072 // static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
1073 // DefPredNodeMapBase(const TR &b) : TR(b) {}
1076 // ///\brief \ref named-templ-param "Named parameter"
1077 // ///function for setting PredNodeMap type
1079 // /// \ref named-templ-param "Named parameter"
1080 // ///function for setting PredNodeMap type
1082 // template<class T>
1083 // BfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1085 // Base::_predNode=(void *)&t;
1086 // return BfsWizard<DefPredNodeMapBase<T> >(*this);
1090 struct DefDistMapBase : public Base {
1092 static DistMap *createDistMap(const Graph &) { return 0; };
1093 DefDistMapBase(const TR &b) : TR(b) {}
1096 ///\brief \ref named-templ-param "Named parameter"
1097 ///function for setting DistMap type
1099 /// \ref named-templ-param "Named parameter"
1100 ///function for setting DistMap type
1103 BfsWizard<DefDistMapBase<T> > distMap(const T &t)
1105 Base::_dist=(void *)&t;
1106 return BfsWizard<DefDistMapBase<T> >(*this);
1109 /// Sets the source node, from which the Bfs algorithm runs.
1111 /// Sets the source node, from which the Bfs algorithm runs.
1112 /// \param s is the source node.
1113 BfsWizard<TR> &source(Node s)
1121 ///Function type interface for Bfs algorithm.
1123 /// \ingroup flowalgs
1124 ///Function type interface for Bfs algorithm.
1126 ///This function also has several
1127 ///\ref named-templ-func-param "named parameters",
1128 ///they are declared as the members of class \ref BfsWizard.
1130 ///example shows how to use these parameters.
1132 /// bfs(g,source).predMap(preds).run();
1134 ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
1135 ///to the end of the parameter list.
1139 BfsWizard<BfsWizardBase<GR> >
1140 bfs(const GR &g,typename GR::Node s=INVALID)
1142 return BfsWizard<BfsWizardBase<GR> >(g,s);
1145 } //END OF NAMESPACE LEMON