1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
24 ///\brief BFS algorithm.
26 #include <lemon/list_graph.h>
27 #include <lemon/graph_utils.h>
28 #include <lemon/bits/path_dump.h>
29 #include <lemon/bits/invalid.h>
30 #include <lemon/error.h>
31 #include <lemon/maps.h>
35 ///Default traits class of Bfs class.
37 ///Default traits class of Bfs class.
38 ///\tparam GR Digraph type.
40 struct BfsDefaultTraits
42 ///The type of the digraph the algorithm runs on.
45 ///\brief The type of the map that stores the predecessor
46 ///arcs of the shortest paths.
48 ///The type of the map that stores the predecessor
49 ///arcs of the shortest paths.
50 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
52 ///Instantiates a \ref PredMap.
54 ///This function instantiates a \ref PredMap.
55 ///\param g is the digraph, to which we would like to define the
57 ///\todo The digraph alone may be insufficient to initialize
58 static PredMap *createPredMap(const Digraph &g)
60 return new PredMap(g);
63 ///The type of the map that indicates which nodes are processed.
65 ///The type of the map that indicates which nodes are processed.
66 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
67 ///By default it is a NullMap.
68 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
69 ///Instantiates a \ref ProcessedMap.
71 ///This function instantiates a \ref ProcessedMap.
72 ///\param g is the digraph, to which
73 ///we would like to define the \ref ProcessedMap
75 static ProcessedMap *createProcessedMap(const Digraph &g)
77 static ProcessedMap *createProcessedMap(const Digraph &)
80 return new ProcessedMap();
83 ///The type of the map that indicates which nodes are reached.
85 ///The type of the map that indicates which nodes are reached.
86 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
87 typedef typename Digraph::template NodeMap<bool> ReachedMap;
88 ///Instantiates a \ref ReachedMap.
90 ///This function instantiates a \ref ReachedMap.
91 ///\param g is the digraph, to which
92 ///we would like to define the \ref ReachedMap.
93 static ReachedMap *createReachedMap(const Digraph &g)
95 return new ReachedMap(g);
98 ///The type of the map that stores the distances of the nodes.
100 ///The type of the map that stores the distances of the nodes.
101 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
102 typedef typename Digraph::template NodeMap<int> DistMap;
103 ///Instantiates a \ref DistMap.
105 ///This function instantiates a \ref DistMap.
106 ///\param g is the digraph, to which we would like to define the
108 static DistMap *createDistMap(const Digraph &g)
110 return new DistMap(g);
114 ///%BFS algorithm class.
117 ///This class provides an efficient implementation of the %BFS algorithm.
119 ///There is also a \ref bfs() "function type interface" for the BFS
120 ///algorithm, which is convenient in the simplier cases and it can be
123 ///\tparam GR The type of the digraph the algorithm runs on.
124 ///The default value is \ref ListDigraph. The value of GR is not used
125 ///directly by \ref Bfs, it is only passed to \ref BfsDefaultTraits.
126 ///\tparam TR Traits class to set various data types used by the algorithm.
127 ///The default traits class is
128 ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
129 ///See \ref BfsDefaultTraits for the documentation of
130 ///a Bfs traits class.
132 template <typename GR,
135 template <typename GR=ListDigraph,
136 typename TR=BfsDefaultTraits<GR> >
140 ///\ref Exception for uninitialized parameters.
142 ///This error represents problems in the initialization of the
143 ///parameters of the algorithm.
144 class UninitializedParameter : public lemon::UninitializedParameter {
146 virtual const char* what() const throw() {
147 return "lemon::Bfs::UninitializedParameter";
151 ///The type of the digraph the algorithm runs on.
152 typedef typename TR::Digraph Digraph;
154 ///\brief The type of the map that stores the predecessor arcs of the
156 typedef typename TR::PredMap PredMap;
157 ///The type of the map that stores the distances of the nodes.
158 typedef typename TR::DistMap DistMap;
159 ///The type of the map that indicates which nodes are reached.
160 typedef typename TR::ReachedMap ReachedMap;
161 ///The type of the map that indicates which nodes are processed.
162 typedef typename TR::ProcessedMap ProcessedMap;
163 ///The type of the paths.
164 typedef PredMapPath<Digraph, PredMap> Path;
171 typedef typename Digraph::Node Node;
172 typedef typename Digraph::NodeIt NodeIt;
173 typedef typename Digraph::Arc Arc;
174 typedef typename Digraph::OutArcIt OutArcIt;
176 //Pointer to the underlying digraph.
178 //Pointer to the map of predecessor arcs.
180 //Indicates if _pred is locally allocated (true) or not.
182 //Pointer to the map of distances.
184 //Indicates if _dist is locally allocated (true) or not.
186 //Pointer to the map of reached status of the nodes.
187 ReachedMap *_reached;
188 //Indicates if _reached is locally allocated (true) or not.
190 //Pointer to the map of processed status of the nodes.
191 ProcessedMap *_processed;
192 //Indicates if _processed is locally allocated (true) or not.
193 bool local_processed;
195 std::vector<typename Digraph::Node> _queue;
196 int _queue_head,_queue_tail,_queue_next_dist;
199 ///Creates the maps if necessary.
200 ///\todo Better memory allocation (instead of new).
205 _pred = Traits::createPredMap(*G);
209 _dist = Traits::createDistMap(*G);
212 local_reached = true;
213 _reached = Traits::createReachedMap(*G);
216 local_processed = true;
217 _processed = Traits::createProcessedMap(*G);
229 ///\name Named template parameters
234 struct DefPredMapTraits : public Traits {
236 static PredMap *createPredMap(const Digraph &)
238 throw UninitializedParameter();
241 ///\brief \ref named-templ-param "Named parameter" for setting
242 ///\ref PredMap type.
244 ///\ref named-templ-param "Named parameter" for setting
245 ///\ref PredMap type.
247 struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > {
248 typedef Bfs< Digraph, DefPredMapTraits<T> > Create;
252 struct DefDistMapTraits : public Traits {
254 static DistMap *createDistMap(const Digraph &)
256 throw UninitializedParameter();
259 ///\brief \ref named-templ-param "Named parameter" for setting
260 ///\ref DistMap type.
262 ///\ref named-templ-param "Named parameter" for setting
263 ///\ref DistMap type.
265 struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > {
266 typedef Bfs< Digraph, DefDistMapTraits<T> > Create;
270 struct DefReachedMapTraits : public Traits {
271 typedef T ReachedMap;
272 static ReachedMap *createReachedMap(const Digraph &)
274 throw UninitializedParameter();
277 ///\brief \ref named-templ-param "Named parameter" for setting
278 ///\ref ReachedMap type.
280 ///\ref named-templ-param "Named parameter" for setting
281 ///\ref ReachedMap type.
283 struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > {
284 typedef Bfs< Digraph, DefReachedMapTraits<T> > Create;
288 struct DefProcessedMapTraits : public Traits {
289 typedef T ProcessedMap;
290 static ProcessedMap *createProcessedMap(const Digraph &)
292 throw UninitializedParameter();
295 ///\brief \ref named-templ-param "Named parameter" for setting
296 ///\ref ProcessedMap type.
298 ///\ref named-templ-param "Named parameter" for setting
299 ///\ref ProcessedMap type.
301 struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits<T> > {
302 typedef Bfs< Digraph, DefProcessedMapTraits<T> > Create;
305 struct DefDigraphProcessedMapTraits : public Traits {
306 typedef typename Digraph::template NodeMap<bool> ProcessedMap;
307 static ProcessedMap *createProcessedMap(const Digraph &g)
309 return new ProcessedMap(g);
312 ///\brief \ref named-templ-param "Named parameter" for setting
313 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
315 ///\ref named-templ-param "Named parameter" for setting
316 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
317 ///If you don't set it explicitly, it will be automatically allocated.
319 struct DefProcessedMapToBeDefaultMap :
320 public Bfs< Digraph, DefDigraphProcessedMapTraits> {
321 typedef Bfs< Digraph, DefDigraphProcessedMapTraits> Create;
331 ///\param g The digraph the algorithm runs on.
332 Bfs(const Digraph &g) :
334 _pred(NULL), local_pred(false),
335 _dist(NULL), local_dist(false),
336 _reached(NULL), local_reached(false),
337 _processed(NULL), local_processed(false)
343 if(local_pred) delete _pred;
344 if(local_dist) delete _dist;
345 if(local_reached) delete _reached;
346 if(local_processed) delete _processed;
349 ///Sets the map that stores the predecessor arcs.
351 ///Sets the map that stores the predecessor arcs.
352 ///If you don't use this function before calling \ref run(),
353 ///it will allocate one. The destructor deallocates this
354 ///automatically allocated map, of course.
355 ///\return <tt> (*this) </tt>
356 Bfs &predMap(PredMap &m)
366 ///Sets the map that indicates which nodes are reached.
368 ///Sets the map that indicates which nodes are reached.
369 ///If you don't use this function before calling \ref run(),
370 ///it will allocate one. The destructor deallocates this
371 ///automatically allocated map, of course.
372 ///\return <tt> (*this) </tt>
373 Bfs &reachedMap(ReachedMap &m)
383 ///Sets the map that indicates which nodes are processed.
385 ///Sets the map that indicates which nodes are processed.
386 ///If you don't use this function before calling \ref run(),
387 ///it will allocate one. The destructor deallocates this
388 ///automatically allocated map, of course.
389 ///\return <tt> (*this) </tt>
390 Bfs &processedMap(ProcessedMap &m)
392 if(local_processed) {
394 local_processed=false;
400 ///Sets the map that stores the distances of the nodes.
402 ///Sets the map that stores the distances of the nodes calculated by
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 &distMap(DistMap &m)
420 ///\name Execution control
421 ///The simplest way to execute the algorithm is to use
422 ///one of the member functions called \ref lemon::Bfs::run() "run()".
424 ///If you need more control on the execution, first you must call
425 ///\ref lemon::Bfs::init() "init()", then you can add several source
426 ///nodes with \ref lemon::Bfs::addSource() "addSource()".
427 ///Finally \ref lemon::Bfs::start() "start()" will perform the
428 ///actual path computation.
432 ///Initializes the internal data structures.
434 ///Initializes the internal data structures.
439 _queue.resize(countNodes(*G));
440 _queue_head=_queue_tail=0;
442 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
443 _pred->set(u,INVALID);
444 _reached->set(u,false);
445 _processed->set(u,false);
449 ///Adds a new source node.
451 ///Adds a new source node to the set of nodes to be processed.
453 void addSource(Node s)
457 _reached->set(s,true);
458 _pred->set(s,INVALID);
460 _queue[_queue_head++]=s;
461 _queue_next_dist=_queue_head;
465 ///Processes the next node.
467 ///Processes the next node.
469 ///\return The processed node.
471 ///\pre The queue must not be empty.
472 Node processNextNode()
474 if(_queue_tail==_queue_next_dist) {
476 _queue_next_dist=_queue_head;
478 Node n=_queue[_queue_tail++];
479 _processed->set(n,true);
481 for(OutArcIt e(*G,n);e!=INVALID;++e)
482 if(!(*_reached)[m=G->target(e)]) {
483 _queue[_queue_head++]=m;
484 _reached->set(m,true);
486 _dist->set(m,_curr_dist);
491 ///Processes the next node.
493 ///Processes the next node and checks if the given target node
494 ///is reached. If the target node is reachable from the processed
495 ///node, then the \c reach parameter will be set to \c true.
497 ///\param target The target node.
498 ///\retval reach Indicates if the target node is reached.
499 ///It should be initially \c false.
501 ///\return The processed node.
503 ///\pre The queue must not be empty.
504 Node processNextNode(Node target, bool& reach)
506 if(_queue_tail==_queue_next_dist) {
508 _queue_next_dist=_queue_head;
510 Node n=_queue[_queue_tail++];
511 _processed->set(n,true);
513 for(OutArcIt e(*G,n);e!=INVALID;++e)
514 if(!(*_reached)[m=G->target(e)]) {
515 _queue[_queue_head++]=m;
516 _reached->set(m,true);
518 _dist->set(m,_curr_dist);
519 reach = reach || (target == m);
524 ///Processes the next node.
526 ///Processes the next node and checks if at least one of reached
527 ///nodes has \c true value in the \c nm node map. If one node
528 ///with \c true value is reachable from the processed node, then the
529 ///\c rnode parameter will be set to the first of such nodes.
531 ///\param nm A \c bool (or convertible) node map that indicates the
533 ///\retval rnode The reached target node.
534 ///It should be initially \c INVALID.
536 ///\return The processed node.
538 ///\pre The queue must not be empty.
540 Node processNextNode(const NM& nm, Node& rnode)
542 if(_queue_tail==_queue_next_dist) {
544 _queue_next_dist=_queue_head;
546 Node n=_queue[_queue_tail++];
547 _processed->set(n,true);
549 for(OutArcIt e(*G,n);e!=INVALID;++e)
550 if(!(*_reached)[m=G->target(e)]) {
551 _queue[_queue_head++]=m;
552 _reached->set(m,true);
554 _dist->set(m,_curr_dist);
555 if (nm[m] && rnode == INVALID) rnode = m;
560 ///The next node to be processed.
562 ///Returns the next node to be processed or \c INVALID if the queue
564 Node nextNode() const
566 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
569 ///\brief Returns \c false if there are nodes
572 ///Returns \c false if there are nodes
573 ///to be processed in the queue.
574 bool emptyQueue() const { return _queue_tail==_queue_head; }
576 ///Returns the number of the nodes to be processed.
578 ///Returns the number of the nodes to be processed in the queue.
579 int queueSize() const { return _queue_head-_queue_tail; }
581 ///Executes the algorithm.
583 ///Executes the algorithm.
585 ///This method runs the %BFS algorithm from the root node(s)
586 ///in order to compute the shortest path to each node.
588 ///The algorithm computes
589 ///- the shortest path tree (forest),
590 ///- the distance of each node from the root(s).
592 ///\pre init() must be called and at least one root node should be
593 ///added with addSource() before using this function.
595 ///\note <tt>b.start()</tt> is just a shortcut of the following code.
597 /// while ( !b.emptyQueue() ) {
598 /// b.processNextNode();
603 while ( !emptyQueue() ) processNextNode();
606 ///Executes the algorithm until the given target node is reached.
608 ///Executes the algorithm until the given target node is reached.
610 ///This method runs the %BFS algorithm from the root node(s)
611 ///in order to compute the shortest path to \c dest.
613 ///The algorithm computes
614 ///- the shortest path to \c dest,
615 ///- the distance of \c dest from the root(s).
617 ///\pre init() must be called and at least one root node should be
618 ///added with addSource() before using this function.
620 ///\note <tt>b.start(t)</tt> is just a shortcut of the following code.
622 /// bool reach = false;
623 /// while ( !b.emptyQueue() && !reach ) {
624 /// b.processNextNode(t, reach);
627 void start(Node dest)
630 while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
633 ///Executes the algorithm until a condition is met.
635 ///Executes the algorithm until a condition is met.
637 ///This method runs the %BFS algorithm from the root node(s) in
638 ///order to compute the shortest path to a node \c v with
639 /// <tt>nm[v]</tt> true, if such a node can be found.
641 ///\param nm A \c bool (or convertible) node map. The algorithm
642 ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
644 ///\return The reached node \c v with <tt>nm[v]</tt> true or
645 ///\c INVALID if no such node was found.
647 ///\pre init() must be called and at least one root node should be
648 ///added with addSource() before using this function.
650 ///\note <tt>b.start(nm)</tt> is just a shortcut of the following code.
652 /// Node rnode = INVALID;
653 /// while ( !b.emptyQueue() && rnode == INVALID ) {
654 /// b.processNextNode(nm, rnode);
658 template<class NodeBoolMap>
659 Node start(const NodeBoolMap &nm)
661 Node rnode = INVALID;
662 while ( !emptyQueue() && rnode == INVALID ) {
663 processNextNode(nm, rnode);
668 ///Runs the algorithm from the given node.
670 ///This method runs the %BFS algorithm from node \c s
671 ///in order to compute the shortest path to each node.
673 ///The algorithm computes
674 ///- the shortest path tree,
675 ///- the distance of each node from the root.
677 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
689 ///Finds the shortest path between \c s and \c t.
691 ///This method runs the %BFS algorithm from node \c s
692 ///in order to compute the shortest path to \c t.
694 ///\return The length of the shortest <tt>s</tt>--<tt>t</tt> path,
695 ///if \c t is reachable form \c s, \c 0 otherwise.
697 ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
698 ///shortcut of the following code.
704 int run(Node s,Node t) {
708 return reached(t) ? _curr_dist : 0;
711 ///Runs the algorithm to visit all nodes in the digraph.
713 ///This method runs the %BFS algorithm in order to
714 ///compute the shortest path to each node.
716 ///The algorithm computes
717 ///- the shortest path tree (forest),
718 ///- the distance of each node from the root(s).
720 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
723 /// for (NodeIt n(gr); n != INVALID; ++n) {
724 /// if (!b.reached(n)) {
732 for (NodeIt n(*G); n != INVALID; ++n) {
742 ///\name Query Functions
743 ///The result of the %BFS algorithm can be obtained using these
745 ///Either \ref lemon::Bfs::run() "run()" or \ref lemon::Bfs::start()
746 ///"start()" must be called before using them.
750 ///The shortest path to a node.
752 ///Returns the shortest path to a node.
754 ///\warning \c t should be reachable from the root(s).
756 ///\pre Either \ref run() or \ref start() must be called before
757 ///using this function.
758 Path path(Node t) const { return Path(*G, *_pred, t); }
760 ///The distance of a node from the root(s).
762 ///Returns the distance of a node from the root(s).
764 ///\warning If node \c v is not reachable from the root(s), then
765 ///the return value of this function is undefined.
767 ///\pre Either \ref run() or \ref start() must be called before
768 ///using this function.
769 int dist(Node v) const { return (*_dist)[v]; }
771 ///Returns the 'previous arc' of the shortest path tree for a node.
773 ///This function returns the 'previous arc' of the shortest path
774 ///tree for the node \c v, i.e. it returns the last arc of a
775 ///shortest path from the root(s) to \c v. It is \c INVALID if \c v
776 ///is not reachable from the root(s) or if \c v is a root.
778 ///The shortest path tree used here is equal to the shortest path
779 ///tree used in \ref predNode().
781 ///\pre Either \ref run() or \ref start() must be called before
782 ///using this function.
783 Arc predArc(Node v) const { return (*_pred)[v];}
785 ///Returns the 'previous node' of the shortest path tree for a node.
787 ///This function returns the 'previous node' of the shortest path
788 ///tree for the node \c v, i.e. it returns the last but one node
789 ///from a shortest path from the root(s) to \c v. It is \c INVALID
790 ///if \c v is not reachable from the root(s) or if \c v is a root.
792 ///The shortest path tree used here is equal to the shortest path
793 ///tree used in \ref predArc().
795 ///\pre Either \ref run() or \ref start() must be called before
796 ///using this function.
797 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
798 G->source((*_pred)[v]); }
800 ///\brief Returns a const reference to the node map that stores the
801 /// distances of the nodes.
803 ///Returns a const reference to the node map that stores the distances
804 ///of the nodes calculated by the algorithm.
806 ///\pre Either \ref run() or \ref init()
807 ///must be called before using this function.
808 const DistMap &distMap() const { return *_dist;}
810 ///\brief Returns a const reference to the node map that stores the
813 ///Returns a const reference to the node map that stores the predecessor
814 ///arcs, which form the shortest path tree.
816 ///\pre Either \ref run() or \ref init()
817 ///must be called before using this function.
818 const PredMap &predMap() const { return *_pred;}
820 ///Checks if a node is reachable from the root(s).
822 ///Returns \c true if \c v is reachable from the root(s).
823 ///\pre Either \ref run() or \ref start()
824 ///must be called before using this function.
825 bool reached(Node v) const { return (*_reached)[v]; }
830 ///Default traits class of bfs() function.
832 ///Default traits class of bfs() function.
833 ///\tparam GR Digraph type.
835 struct BfsWizardDefaultTraits
837 ///The type of the digraph the algorithm runs on.
840 ///\brief The type of the map that stores the predecessor
841 ///arcs of the shortest paths.
843 ///The type of the map that stores the predecessor
844 ///arcs of the shortest paths.
845 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
846 typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
847 ///Instantiates a \ref PredMap.
849 ///This function instantiates a \ref PredMap.
850 ///\param g is the digraph, to which we would like to define the
852 ///\todo The digraph alone may be insufficient to initialize
854 static PredMap *createPredMap(const Digraph &g)
856 static PredMap *createPredMap(const Digraph &)
859 return new PredMap();
862 ///The type of the map that indicates which nodes are processed.
864 ///The type of the map that indicates which nodes are processed.
865 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
866 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
867 ///Instantiates a \ref ProcessedMap.
869 ///This function instantiates a \ref ProcessedMap.
870 ///\param g is the digraph, to which
871 ///we would like to define the \ref ProcessedMap.
873 static ProcessedMap *createProcessedMap(const Digraph &g)
875 static ProcessedMap *createProcessedMap(const Digraph &)
878 return new ProcessedMap();
881 ///The type of the map that indicates which nodes are reached.
883 ///The type of the map that indicates which nodes are reached.
884 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
885 typedef typename Digraph::template NodeMap<bool> ReachedMap;
886 ///Instantiates a \ref ReachedMap.
888 ///This function instantiates a \ref ReachedMap.
889 ///\param g is the digraph, to which
890 ///we would like to define the \ref ReachedMap.
891 static ReachedMap *createReachedMap(const Digraph &g)
893 return new ReachedMap(g);
896 ///The type of the map that stores the distances of the nodes.
898 ///The type of the map that stores the distances of the nodes.
899 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
901 typedef NullMap<typename Digraph::Node,int> DistMap;
902 ///Instantiates a \ref DistMap.
904 ///This function instantiates a \ref DistMap.
905 ///\param g is the digraph, to which we would like to define
908 static DistMap *createDistMap(const Digraph &g)
910 static DistMap *createDistMap(const Digraph &)
913 return new DistMap();
917 /// Default traits class used by \ref BfsWizard
919 /// To make it easier to use Bfs algorithm
920 /// we have created a wizard class.
921 /// This \ref BfsWizard class needs default traits,
922 /// as well as the \ref Bfs class.
923 /// The \ref BfsWizardBase is a class to be the default traits of the
924 /// \ref BfsWizard class.
926 class BfsWizardBase : public BfsWizardDefaultTraits<GR>
929 typedef BfsWizardDefaultTraits<GR> Base;
931 //The type of the nodes in the digraph.
932 typedef typename Base::Digraph::Node Node;
934 //Pointer to the digraph the algorithm runs on.
936 //Pointer to the map of reached nodes.
938 //Pointer to the map of processed nodes.
940 //Pointer to the map of predecessors arcs.
942 //Pointer to the map of distances.
944 //Pointer to the source node.
950 /// This constructor does not require parameters, therefore it initiates
951 /// all of the attributes to default values (0, INVALID).
952 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
953 _dist(0), _source(INVALID) {}
957 /// This constructor requires some parameters,
958 /// listed in the parameters list.
959 /// Others are initiated to 0.
960 /// \param g The digraph the algorithm runs on.
961 /// \param s The source node.
962 BfsWizardBase(const GR &g, Node s=INVALID) :
963 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
964 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
968 /// Auxiliary class for the function type interface of BFS algorithm.
970 /// This auxiliary class is created to implement the function type
971 /// interface of \ref Bfs algorithm. It uses the functions and features
972 /// of the plain \ref Bfs, but it is much simpler to use it.
973 /// It should only be used through the \ref bfs() function, which makes
974 /// it easier to use the algorithm.
976 /// Simplicity means that the way to change the types defined
977 /// in the traits class is based on functions that returns the new class
978 /// and not on templatable built-in classes.
979 /// When using the plain \ref Bfs
980 /// the new class with the modified type comes from
981 /// the original class by using the ::
982 /// operator. In the case of \ref BfsWizard only
983 /// a function have to be called, and it will
984 /// return the needed class.
986 /// It does not have own \ref run() method. When its \ref run() method
987 /// is called, it initiates a plain \ref Bfs object, and calls the
988 /// \ref Bfs::run() method of it.
990 class BfsWizard : public TR
994 ///The type of the digraph the algorithm runs on.
995 typedef typename TR::Digraph Digraph;
997 typedef typename Digraph::Node Node;
998 typedef typename Digraph::NodeIt NodeIt;
999 typedef typename Digraph::Arc Arc;
1000 typedef typename Digraph::OutArcIt OutArcIt;
1002 ///\brief The type of the map that stores the predecessor
1003 ///arcs of the shortest paths.
1004 typedef typename TR::PredMap PredMap;
1005 ///\brief The type of the map that stores the distances of the nodes.
1006 typedef typename TR::DistMap DistMap;
1007 ///\brief The type of the map that indicates which nodes are reached.
1008 typedef typename TR::ReachedMap ReachedMap;
1009 ///\brief The type of the map that indicates which nodes are processed.
1010 typedef typename TR::ProcessedMap ProcessedMap;
1015 BfsWizard() : TR() {}
1017 /// Constructor that requires parameters.
1019 /// Constructor that requires parameters.
1020 /// These parameters will be the default values for the traits class.
1021 BfsWizard(const Digraph &g, Node s=INVALID) :
1025 BfsWizard(const TR &b) : TR(b) {}
1029 ///Runs BFS algorithm from a source node.
1031 ///Runs BFS algorithm from a source node.
1032 ///The node can be given with the \ref source() function.
1035 if(Base::_source==INVALID) throw UninitializedParameter();
1036 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
1038 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
1039 if(Base::_processed)
1040 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1042 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1044 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1045 alg.run(Base::_source);
1048 ///Runs BFS algorithm from the given node.
1050 ///Runs BFS algorithm from the given node.
1051 ///\param s is the given source.
1058 /// Sets the source node, from which the Bfs algorithm runs.
1060 /// Sets the source node, from which the Bfs algorithm runs.
1061 /// \param s is the source node.
1062 BfsWizard<TR> &source(Node s)
1069 struct DefPredMapBase : public Base {
1071 static PredMap *createPredMap(const Digraph &) { return 0; };
1072 DefPredMapBase(const TR &b) : TR(b) {}
1074 ///\brief \ref named-templ-param "Named parameter"
1075 ///for setting \ref PredMap object.
1077 /// \ref named-templ-param "Named parameter"
1078 ///for setting \ref PredMap object.
1080 BfsWizard<DefPredMapBase<T> > predMap(const T &t)
1082 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1083 return BfsWizard<DefPredMapBase<T> >(*this);
1087 struct DefReachedMapBase : public Base {
1088 typedef T ReachedMap;
1089 static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1090 DefReachedMapBase(const TR &b) : TR(b) {}
1092 ///\brief \ref named-templ-param "Named parameter"
1093 ///for setting \ref ReachedMap object.
1095 /// \ref named-templ-param "Named parameter"
1096 ///for setting \ref ReachedMap object.
1098 BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1100 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
1101 return BfsWizard<DefReachedMapBase<T> >(*this);
1105 struct DefProcessedMapBase : public Base {
1106 typedef T ProcessedMap;
1107 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1108 DefProcessedMapBase(const TR &b) : TR(b) {}
1110 ///\brief \ref named-templ-param "Named parameter"
1111 ///for setting \ref ProcessedMap object.
1113 /// \ref named-templ-param "Named parameter"
1114 ///for setting \ref ProcessedMap object.
1116 BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1118 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
1119 return BfsWizard<DefProcessedMapBase<T> >(*this);
1123 struct DefDistMapBase : public Base {
1125 static DistMap *createDistMap(const Digraph &) { return 0; };
1126 DefDistMapBase(const TR &b) : TR(b) {}
1128 ///\brief \ref named-templ-param "Named parameter"
1129 ///for setting \ref DistMap object.
1131 /// \ref named-templ-param "Named parameter"
1132 ///for setting \ref DistMap object.
1134 BfsWizard<DefDistMapBase<T> > distMap(const T &t)
1136 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1137 return BfsWizard<DefDistMapBase<T> >(*this);
1142 ///Function type interface for Bfs algorithm.
1145 ///Function type interface for Bfs algorithm.
1147 ///This function also has several
1148 ///\ref named-templ-func-param "named parameters",
1149 ///they are declared as the members of class \ref BfsWizard.
1151 ///example shows how to use these parameters.
1153 /// bfs(g,source).predMap(preds).run();
1155 ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
1156 ///to the end of the parameter list.
1160 BfsWizard<BfsWizardBase<GR> >
1161 bfs(const GR &g,typename GR::Node s=INVALID)
1163 return BfsWizard<BfsWizardBase<GR> >(g,s);
1167 /// \brief Visitor class for BFS.
1169 /// This class defines the interface of the BfsVisit events, and
1170 /// it could be the base of a real visitor class.
1171 template <typename _Digraph>
1173 typedef _Digraph Digraph;
1174 typedef typename Digraph::Arc Arc;
1175 typedef typename Digraph::Node Node;
1176 /// \brief Called for the source node(s) of the BFS.
1178 /// This function is called for the source node(s) of the BFS.
1179 void start(const Node& node) {}
1180 /// \brief Called when a node is reached first time.
1182 /// This function is called when a node is reached first time.
1183 void reach(const Node& node) {}
1184 /// \brief Called when a node is processed.
1186 /// This function is called when a node is processed.
1187 void process(const Node& node) {}
1188 /// \brief Called when an arc reaches a new node.
1190 /// This function is called when the BFS finds an arc whose target node
1191 /// is not reached yet.
1192 void discover(const Arc& arc) {}
1193 /// \brief Called when an arc is examined but its target node is
1194 /// already discovered.
1196 /// This function is called when an arc is examined but its target node is
1197 /// already discovered.
1198 void examine(const Arc& arc) {}
1201 template <typename _Digraph>
1203 typedef _Digraph Digraph;
1204 typedef typename Digraph::Arc Arc;
1205 typedef typename Digraph::Node Node;
1206 void start(const Node&) {}
1207 void reach(const Node&) {}
1208 void process(const Node&) {}
1209 void discover(const Arc&) {}
1210 void examine(const Arc&) {}
1212 template <typename _Visitor>
1213 struct Constraints {
1214 void constraints() {
1217 visitor.start(node);
1218 visitor.reach(node);
1219 visitor.process(node);
1220 visitor.discover(arc);
1221 visitor.examine(arc);
1228 /// \brief Default traits class of BfsVisit class.
1230 /// Default traits class of BfsVisit class.
1231 /// \tparam _Digraph The type of the digraph the algorithm runs on.
1232 template<class _Digraph>
1233 struct BfsVisitDefaultTraits {
1235 /// \brief The type of the digraph the algorithm runs on.
1236 typedef _Digraph Digraph;
1238 /// \brief The type of the map that indicates which nodes are reached.
1240 /// The type of the map that indicates which nodes are reached.
1241 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1242 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1244 /// \brief Instantiates a \ref ReachedMap.
1246 /// This function instantiates a \ref ReachedMap.
1247 /// \param digraph is the digraph, to which
1248 /// we would like to define the \ref ReachedMap.
1249 static ReachedMap *createReachedMap(const Digraph &digraph) {
1250 return new ReachedMap(digraph);
1257 /// \brief %BFS algorithm class with visitor interface.
1259 /// This class provides an efficient implementation of the %BFS algorithm
1260 /// with visitor interface.
1262 /// The %BfsVisit class provides an alternative interface to the Bfs
1263 /// class. It works with callback mechanism, the BfsVisit object calls
1264 /// the member functions of the \c Visitor class on every BFS event.
1266 /// \tparam _Digraph The type of the digraph the algorithm runs on.
1267 /// The default value is
1268 /// \ref ListDigraph. The value of _Digraph is not used directly by
1269 /// \ref BfsVisit, it is only passed to \ref BfsVisitDefaultTraits.
1270 /// \tparam _Visitor The Visitor type that is used by the algorithm.
1271 /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty visitor, which
1272 /// does not observe the BFS events. If you want to observe the BFS
1273 /// events, you should implement your own visitor class.
1274 /// \tparam _Traits Traits class to set various data types used by the
1275 /// algorithm. The default traits class is
1276 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
1277 /// See \ref BfsVisitDefaultTraits for the documentation of
1278 /// a BFS visit traits class.
1280 template <typename _Digraph, typename _Visitor, typename _Traits>
1282 template <typename _Digraph = ListDigraph,
1283 typename _Visitor = BfsVisitor<_Digraph>,
1284 typename _Traits = BfsDefaultTraits<_Digraph> >
1289 /// \brief \ref Exception for uninitialized parameters.
1291 /// This error represents problems in the initialization
1292 /// of the parameters of the algorithm.
1293 class UninitializedParameter : public lemon::UninitializedParameter {
1295 virtual const char* what() const throw()
1297 return "lemon::BfsVisit::UninitializedParameter";
1301 ///The traits class.
1302 typedef _Traits Traits;
1304 ///The type of the digraph the algorithm runs on.
1305 typedef typename Traits::Digraph Digraph;
1307 ///The visitor type used by the algorithm.
1308 typedef _Visitor Visitor;
1310 ///The type of the map that indicates which nodes are reached.
1311 typedef typename Traits::ReachedMap ReachedMap;
1315 typedef typename Digraph::Node Node;
1316 typedef typename Digraph::NodeIt NodeIt;
1317 typedef typename Digraph::Arc Arc;
1318 typedef typename Digraph::OutArcIt OutArcIt;
1320 //Pointer to the underlying digraph.
1321 const Digraph *_digraph;
1322 //Pointer to the visitor object.
1324 //Pointer to the map of reached status of the nodes.
1325 ReachedMap *_reached;
1326 //Indicates if _reached is locally allocated (true) or not.
1329 std::vector<typename Digraph::Node> _list;
1330 int _list_front, _list_back;
1332 ///Creates the maps if necessary.
1333 ///\todo Better memory allocation (instead of new).
1334 void create_maps() {
1336 local_reached = true;
1337 _reached = Traits::createReachedMap(*_digraph);
1347 typedef BfsVisit Create;
1349 /// \name Named template parameters
1353 struct DefReachedMapTraits : public Traits {
1354 typedef T ReachedMap;
1355 static ReachedMap *createReachedMap(const Digraph &digraph) {
1356 throw UninitializedParameter();
1359 /// \brief \ref named-templ-param "Named parameter" for setting
1360 /// ReachedMap type.
1362 /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
1364 struct DefReachedMap : public BfsVisit< Digraph, Visitor,
1365 DefReachedMapTraits<T> > {
1366 typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
1372 /// \brief Constructor.
1376 /// \param digraph The digraph the algorithm runs on.
1377 /// \param visitor The visitor object of the algorithm.
1378 BfsVisit(const Digraph& digraph, Visitor& visitor)
1379 : _digraph(&digraph), _visitor(&visitor),
1380 _reached(0), local_reached(false) {}
1382 /// \brief Destructor.
1384 if(local_reached) delete _reached;
1387 /// \brief Sets the map that indicates which nodes are reached.
1389 /// Sets the map that indicates which nodes are reached.
1390 /// If you don't use this function before calling \ref run(),
1391 /// it will allocate one. The destructor deallocates this
1392 /// automatically allocated map, of course.
1393 /// \return <tt> (*this) </tt>
1394 BfsVisit &reachedMap(ReachedMap &m) {
1397 local_reached = false;
1405 /// \name Execution control
1406 /// The simplest way to execute the algorithm is to use
1407 /// one of the member functions called \ref lemon::BfsVisit::run()
1410 /// If you need more control on the execution, first you must call
1411 /// \ref lemon::BfsVisit::init() "init()", then you can add several
1412 /// source nodes with \ref lemon::BfsVisit::addSource() "addSource()".
1413 /// Finally \ref lemon::BfsVisit::start() "start()" will perform the
1414 /// actual path computation.
1418 /// \brief Initializes the internal data structures.
1420 /// Initializes the internal data structures.
1423 _list.resize(countNodes(*_digraph));
1424 _list_front = _list_back = -1;
1425 for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
1426 _reached->set(u, false);
1430 /// \brief Adds a new source node.
1432 /// Adds a new source node to the set of nodes to be processed.
1433 void addSource(Node s) {
1434 if(!(*_reached)[s]) {
1435 _reached->set(s,true);
1438 _list[++_list_back] = s;
1442 /// \brief Processes the next node.
1444 /// Processes the next node.
1446 /// \return The processed node.
1448 /// \pre The queue must not be empty.
1449 Node processNextNode() {
1450 Node n = _list[++_list_front];
1451 _visitor->process(n);
1453 for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
1454 Node m = _digraph->target(e);
1455 if (!(*_reached)[m]) {
1456 _visitor->discover(e);
1458 _reached->set(m, true);
1459 _list[++_list_back] = m;
1461 _visitor->examine(e);
1467 /// \brief Processes the next node.
1469 /// Processes the next node and checks if the given target node
1470 /// is reached. If the target node is reachable from the processed
1471 /// node, then the \c reach parameter will be set to \c true.
1473 /// \param target The target node.
1474 /// \retval reach Indicates if the target node is reached.
1475 /// It should be initially \c false.
1477 /// \return The processed node.
1479 /// \pre The queue must not be empty.
1480 Node processNextNode(Node target, bool& reach) {
1481 Node n = _list[++_list_front];
1482 _visitor->process(n);
1484 for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
1485 Node m = _digraph->target(e);
1486 if (!(*_reached)[m]) {
1487 _visitor->discover(e);
1489 _reached->set(m, true);
1490 _list[++_list_back] = m;
1491 reach = reach || (target == m);
1493 _visitor->examine(e);
1499 /// \brief Processes the next node.
1501 /// Processes the next node and checks if at least one of reached
1502 /// nodes has \c true value in the \c nm node map. If one node
1503 /// with \c true value is reachable from the processed node, then the
1504 /// \c rnode parameter will be set to the first of such nodes.
1506 /// \param nm A \c bool (or convertible) node map that indicates the
1507 /// possible targets.
1508 /// \retval rnode The reached target node.
1509 /// It should be initially \c INVALID.
1511 /// \return The processed node.
1513 /// \pre The queue must not be empty.
1514 template <typename NM>
1515 Node processNextNode(const NM& nm, Node& rnode) {
1516 Node n = _list[++_list_front];
1517 _visitor->process(n);
1519 for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
1520 Node m = _digraph->target(e);
1521 if (!(*_reached)[m]) {
1522 _visitor->discover(e);
1524 _reached->set(m, true);
1525 _list[++_list_back] = m;
1526 if (nm[m] && rnode == INVALID) rnode = m;
1528 _visitor->examine(e);
1534 /// \brief The next node to be processed.
1536 /// Returns the next node to be processed or \c INVALID if the queue
1538 Node nextNode() const {
1539 return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
1542 /// \brief Returns \c false if there are nodes
1543 /// to be processed.
1545 /// Returns \c false if there are nodes
1546 /// to be processed in the queue.
1547 bool emptyQueue() const { return _list_front == _list_back; }
1549 /// \brief Returns the number of the nodes to be processed.
1551 /// Returns the number of the nodes to be processed in the queue.
1552 int queueSize() const { return _list_back - _list_front; }
1554 /// \brief Executes the algorithm.
1556 /// Executes the algorithm.
1558 /// This method runs the %BFS algorithm from the root node(s)
1559 /// in order to compute the shortest path to each node.
1561 /// The algorithm computes
1562 /// - the shortest path tree (forest),
1563 /// - the distance of each node from the root(s).
1565 /// \pre init() must be called and at least one root node should be added
1566 /// with addSource() before using this function.
1568 /// \note <tt>b.start()</tt> is just a shortcut of the following code.
1570 /// while ( !b.emptyQueue() ) {
1571 /// b.processNextNode();
1575 while ( !emptyQueue() ) processNextNode();
1578 /// \brief Executes the algorithm until the given target node is reached.
1580 /// Executes the algorithm until the given target node is reached.
1582 /// This method runs the %BFS algorithm from the root node(s)
1583 /// in order to compute the shortest path to \c dest.
1585 /// The algorithm computes
1586 /// - the shortest path to \c dest,
1587 /// - the distance of \c dest from the root(s).
1589 /// \pre init() must be called and at least one root node should be
1590 /// added with addSource() before using this function.
1592 /// \note <tt>b.start(t)</tt> is just a shortcut of the following code.
1594 /// bool reach = false;
1595 /// while ( !b.emptyQueue() && !reach ) {
1596 /// b.processNextNode(t, reach);
1599 void start(Node dest) {
1601 while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
1604 /// \brief Executes the algorithm until a condition is met.
1606 /// Executes the algorithm until a condition is met.
1608 /// This method runs the %BFS algorithm from the root node(s) in
1609 /// order to compute the shortest path to a node \c v with
1610 /// <tt>nm[v]</tt> true, if such a node can be found.
1612 /// \param nm must be a bool (or convertible) node map. The
1613 /// algorithm will stop when it reaches a node \c v with
1614 /// <tt>nm[v]</tt> true.
1616 /// \return The reached node \c v with <tt>nm[v]</tt> true or
1617 /// \c INVALID if no such node was found.
1619 /// \pre init() must be called and at least one root node should be
1620 /// added with addSource() before using this function.
1622 /// \note <tt>b.start(nm)</tt> is just a shortcut of the following code.
1624 /// Node rnode = INVALID;
1625 /// while ( !b.emptyQueue() && rnode == INVALID ) {
1626 /// b.processNextNode(nm, rnode);
1630 template <typename NM>
1631 Node start(const NM &nm) {
1632 Node rnode = INVALID;
1633 while ( !emptyQueue() && rnode == INVALID ) {
1634 processNextNode(nm, rnode);
1639 /// \brief Runs the algorithm from the given node.
1641 /// This method runs the %BFS algorithm from node \c s
1642 /// in order to compute the shortest path to each node.
1644 /// The algorithm computes
1645 /// - the shortest path tree,
1646 /// - the distance of each node from the root.
1648 /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
1660 /// \brief Runs the algorithm to visit all nodes in the digraph.
1662 /// This method runs the %BFS algorithm in order to
1663 /// compute the shortest path to each node.
1665 /// The algorithm computes
1666 /// - the shortest path tree (forest),
1667 /// - the distance of each node from the root(s).
1669 /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
1672 /// for (NodeIt n(gr); n != INVALID; ++n) {
1673 /// if (!b.reached(n)) {
1681 for (NodeIt it(*_digraph); it != INVALID; ++it) {
1691 /// \name Query Functions
1692 /// The result of the %BFS algorithm can be obtained using these
1694 /// Either \ref lemon::BfsVisit::run() "run()" or
1695 /// \ref lemon::BfsVisit::start() "start()" must be called before
1699 /// \brief Checks if a node is reachable from the root(s).
1701 /// Returns \c true if \c v is reachable from the root(s).
1702 /// \pre Either \ref run() or \ref start()
1703 /// must be called before using this function.
1704 bool reached(Node v) { return (*_reached)[v]; }
1710 } //END OF NAMESPACE LEMON