Update INSTALL file.
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/bits/path_dump.h>
28 #include <lemon/core.h>
29 #include <lemon/error.h>
30 #include <lemon/maps.h>
36 ///Default traits class of Bfs class.
38 ///Default traits class of Bfs class.
39 ///\tparam GR Digraph type.
41 struct BfsDefaultTraits
43 ///The digraph type the algorithm runs on.
45 ///\brief The type of the map that stores the last
46 ///arcs of the shortest paths.
48 ///The type of the map that stores the last
49 ///arcs of the shortest paths.
50 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
52 typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
53 ///Instantiates a PredMap.
55 ///This function instantiates a \ref PredMap.
56 ///\param G is the digraph, to which we would like to define the PredMap.
57 ///\todo The digraph alone may be insufficient to initialize
58 static PredMap *createPredMap(const GR &G)
60 return new PredMap(G);
62 ///The type of the map that indicates which nodes are processed.
64 ///The type of the map that indicates which nodes are processed.
65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
66 ///\todo named parameter to set this type, function to read and write.
67 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
68 ///Instantiates a ProcessedMap.
70 ///This function instantiates a \ref ProcessedMap.
71 ///\param g is the digraph, to which
72 ///we would like to define the \ref ProcessedMap
74 static ProcessedMap *createProcessedMap(const GR &g)
76 static ProcessedMap *createProcessedMap(const GR &)
79 return new ProcessedMap();
81 ///The type of the map that indicates which nodes are reached.
83 ///The type of the map that indicates which nodes are reached.
84 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
85 ///\todo named parameter to set this type, function to read and write.
86 typedef typename Digraph::template NodeMap<bool> ReachedMap;
87 ///Instantiates a ReachedMap.
89 ///This function instantiates a \ref ReachedMap.
90 ///\param G is the digraph, to which
91 ///we would like to define the \ref ReachedMap.
92 static ReachedMap *createReachedMap(const GR &G)
94 return new ReachedMap(G);
96 ///The type of the map that stores the dists of the nodes.
98 ///The type of the map that stores the dists of the nodes.
99 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
101 typedef typename Digraph::template NodeMap<int> DistMap;
102 ///Instantiates a DistMap.
104 ///This function instantiates a \ref DistMap.
105 ///\param G is the digraph, to which we would like to define
107 static DistMap *createDistMap(const GR &G)
109 return new DistMap(G);
113 ///%BFS algorithm class.
116 ///This class provides an efficient implementation of the %BFS algorithm.
118 ///\tparam GR The digraph type the algorithm runs on. The default value is
119 ///\ref ListDigraph. The value of GR is not used directly by Bfs, it
120 ///is only passed to \ref BfsDefaultTraits.
121 ///\tparam TR Traits class to set various data types used by the algorithm.
122 ///The default traits class is
123 ///\ref BfsDefaultTraits "BfsDefaultTraits<GR>".
124 ///See \ref BfsDefaultTraits for the documentation of
125 ///a Bfs traits class.
128 template <typename GR,
131 template <typename GR=ListDigraph,
132 typename TR=BfsDefaultTraits<GR> >
137 * \brief \ref Exception for uninitialized parameters.
139 * This error represents problems in the initialization
140 * of the parameters of the algorithms.
142 class UninitializedParameter : public lemon::UninitializedParameter {
144 virtual const char* what() const throw() {
145 return "lemon::Bfs::UninitializedParameter";
150 ///The type of the underlying digraph.
151 typedef typename TR::Digraph Digraph;
153 ///\brief The type of the map that stores the last
154 ///arcs of the shortest paths.
155 typedef typename TR::PredMap PredMap;
156 ///The type of the map indicating which nodes are reached.
157 typedef typename TR::ReachedMap ReachedMap;
158 ///The type of the map indicating which nodes are processed.
159 typedef typename TR::ProcessedMap ProcessedMap;
160 ///The type of the map that stores the dists of the nodes.
161 typedef typename TR::DistMap DistMap;
164 typedef typename Digraph::Node Node;
165 typedef typename Digraph::NodeIt NodeIt;
166 typedef typename Digraph::Arc Arc;
167 typedef typename Digraph::OutArcIt OutArcIt;
169 /// Pointer to the underlying digraph.
171 ///Pointer to the map of predecessors arcs.
173 ///Indicates if \ref _pred is locally allocated (\c true) or not.
175 ///Pointer to the map of distances.
177 ///Indicates if \ref _dist is locally allocated (\c true) or not.
179 ///Pointer to the map of reached status of the nodes.
180 ReachedMap *_reached;
181 ///Indicates if \ref _reached is locally allocated (\c true) or not.
183 ///Pointer to the map of processed status of the nodes.
184 ProcessedMap *_processed;
185 ///Indicates if \ref _processed is locally allocated (\c true) or not.
186 bool local_processed;
188 std::vector<typename Digraph::Node> _queue;
189 int _queue_head,_queue_tail,_queue_next_dist;
192 ///Creates the maps if necessary.
194 ///\todo Better memory allocation (instead of new).
199 _pred = Traits::createPredMap(*G);
203 _dist = Traits::createDistMap(*G);
206 local_reached = true;
207 _reached = Traits::createReachedMap(*G);
210 local_processed = true;
211 _processed = Traits::createProcessedMap(*G);
223 ///\name Named template parameters
228 struct DefPredMapTraits : public Traits {
230 static PredMap *createPredMap(const Digraph &)
232 throw UninitializedParameter();
235 ///\brief \ref named-templ-param "Named parameter" for setting
238 ///\ref named-templ-param "Named parameter" for setting PredMap type
241 struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > {
242 typedef Bfs< Digraph, DefPredMapTraits<T> > Create;
246 struct DefDistMapTraits : public Traits {
248 static DistMap *createDistMap(const Digraph &)
250 throw UninitializedParameter();
253 ///\brief \ref named-templ-param "Named parameter" for setting
256 ///\ref named-templ-param "Named parameter" for setting DistMap type
259 struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > {
260 typedef Bfs< Digraph, DefDistMapTraits<T> > Create;
264 struct DefReachedMapTraits : public Traits {
265 typedef T ReachedMap;
266 static ReachedMap *createReachedMap(const Digraph &)
268 throw UninitializedParameter();
271 ///\brief \ref named-templ-param "Named parameter" for setting
274 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
277 struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > {
278 typedef Bfs< Digraph, DefReachedMapTraits<T> > Create;
282 struct DefProcessedMapTraits : public Traits {
283 typedef T ProcessedMap;
284 static ProcessedMap *createProcessedMap(const Digraph &)
286 throw UninitializedParameter();
289 ///\brief \ref named-templ-param "Named parameter" for setting
292 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
295 struct DefProcessedMap : public Bfs< Digraph, DefProcessedMapTraits<T> > {
296 typedef Bfs< Digraph, DefProcessedMapTraits<T> > Create;
299 struct DefDigraphProcessedMapTraits : public Traits {
300 typedef typename Digraph::template NodeMap<bool> ProcessedMap;
301 static ProcessedMap *createProcessedMap(const Digraph &G)
303 return new ProcessedMap(G);
306 ///\brief \ref named-templ-param "Named parameter"
307 ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
309 ///\ref named-templ-param "Named parameter"
310 ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
311 ///If you don't set it explicitly, it will be automatically allocated.
313 struct DefProcessedMapToBeDefaultMap :
314 public Bfs< Digraph, DefDigraphProcessedMapTraits> {
315 typedef Bfs< Digraph, DefDigraphProcessedMapTraits> Create;
324 ///\param _G the digraph the algorithm will run on.
326 Bfs(const Digraph& _G) :
328 _pred(NULL), local_pred(false),
329 _dist(NULL), local_dist(false),
330 _reached(NULL), local_reached(false),
331 _processed(NULL), local_processed(false)
337 if(local_pred) delete _pred;
338 if(local_dist) delete _dist;
339 if(local_reached) delete _reached;
340 if(local_processed) delete _processed;
343 ///Sets the map storing the predecessor arcs.
345 ///Sets the map storing the predecessor arcs.
346 ///If you don't use this function before calling \ref run(),
347 ///it will allocate one. The destructor deallocates this
348 ///automatically allocated map, of course.
349 ///\return <tt> (*this) </tt>
350 Bfs &predMap(PredMap &m)
360 ///Sets the map indicating the reached nodes.
362 ///Sets the map indicating the reached nodes.
363 ///If you don't use this function before calling \ref run(),
364 ///it will allocate one. The destructor deallocates this
365 ///automatically allocated map, of course.
366 ///\return <tt> (*this) </tt>
367 Bfs &reachedMap(ReachedMap &m)
377 ///Sets the map indicating the processed nodes.
379 ///Sets the map indicating the processed nodes.
380 ///If you don't use this function before calling \ref run(),
381 ///it will allocate one. The destructor deallocates this
382 ///automatically allocated map, of course.
383 ///\return <tt> (*this) </tt>
384 Bfs &processedMap(ProcessedMap &m)
386 if(local_processed) {
388 local_processed=false;
394 ///Sets the map storing the distances calculated by the algorithm.
396 ///Sets the map storing the distances calculated by the algorithm.
397 ///If you don't use this function before calling \ref run(),
398 ///it will allocate one. The destructor deallocates this
399 ///automatically allocated map, of course.
400 ///\return <tt> (*this) </tt>
401 Bfs &distMap(DistMap &m)
412 ///\name Execution control
413 ///The simplest way to execute the algorithm is to use
414 ///one of the member functions called \c run(...).
416 ///If you need more control on the execution,
417 ///first you must call \ref init(), then you can add several source nodes
418 ///with \ref addSource().
419 ///Finally \ref start() will perform the actual path
424 ///\brief Initializes the internal data structures.
426 ///Initializes the internal data structures.
431 _queue.resize(countNodes(*G));
432 _queue_head=_queue_tail=0;
434 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
435 _pred->set(u,INVALID);
436 _reached->set(u,false);
437 _processed->set(u,false);
441 ///Adds a new source node.
443 ///Adds a new source node to the set of nodes to be processed.
445 void addSource(Node s)
449 _reached->set(s,true);
450 _pred->set(s,INVALID);
452 _queue[_queue_head++]=s;
453 _queue_next_dist=_queue_head;
457 ///Processes the next node.
459 ///Processes the next node.
461 ///\return The processed node.
463 ///\warning The queue must not be empty!
464 Node processNextNode()
466 if(_queue_tail==_queue_next_dist) {
468 _queue_next_dist=_queue_head;
470 Node n=_queue[_queue_tail++];
471 _processed->set(n,true);
473 for(OutArcIt e(*G,n);e!=INVALID;++e)
474 if(!(*_reached)[m=G->target(e)]) {
475 _queue[_queue_head++]=m;
476 _reached->set(m,true);
478 _dist->set(m,_curr_dist);
483 ///Processes the next node.
485 ///Processes the next node. And checks that the given target node
486 ///is reached. If the target node is reachable from the processed
487 ///node then the reached parameter will be set true. The reached
488 ///parameter should be initially false.
490 ///\param target The target node.
491 ///\retval reach Indicates that the target node is reached.
492 ///\return The processed node.
494 ///\warning The queue must not be empty!
495 Node processNextNode(Node target, bool& reach)
497 if(_queue_tail==_queue_next_dist) {
499 _queue_next_dist=_queue_head;
501 Node n=_queue[_queue_tail++];
502 _processed->set(n,true);
504 for(OutArcIt e(*G,n);e!=INVALID;++e)
505 if(!(*_reached)[m=G->target(e)]) {
506 _queue[_queue_head++]=m;
507 _reached->set(m,true);
509 _dist->set(m,_curr_dist);
510 reach = reach || (target == m);
515 ///Processes the next node.
517 ///Processes the next node. And checks that at least one of
518 ///reached node has true value in the \c nm node map. If one node
519 ///with true value is reachable from the processed node then the
520 ///rnode parameter will be set to the first of such nodes.
522 ///\param nm The node map of possible targets.
523 ///\retval rnode The reached target node.
524 ///\return The processed node.
526 ///\warning The queue must not be empty!
528 Node processNextNode(const NM& nm, Node& rnode)
530 if(_queue_tail==_queue_next_dist) {
532 _queue_next_dist=_queue_head;
534 Node n=_queue[_queue_tail++];
535 _processed->set(n,true);
537 for(OutArcIt e(*G,n);e!=INVALID;++e)
538 if(!(*_reached)[m=G->target(e)]) {
539 _queue[_queue_head++]=m;
540 _reached->set(m,true);
542 _dist->set(m,_curr_dist);
543 if (nm[m] && rnode == INVALID) rnode = m;
548 ///Next node to be processed.
550 ///Next node to be processed.
552 ///\return The next node to be processed or INVALID if the queue is
556 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
559 ///\brief Returns \c false if there are nodes
560 ///to be processed in the queue
562 ///Returns \c false if there are nodes
563 ///to be processed in the queue
564 bool emptyQueue() { return _queue_tail==_queue_head; }
565 ///Returns the number of the nodes to be processed.
567 ///Returns the number of the nodes to be processed in the queue.
568 int queueSize() { return _queue_head-_queue_tail; }
570 ///Executes the algorithm.
572 ///Executes the algorithm.
574 ///\pre init() must be called and at least one node should be added
575 ///with addSource() before using this function.
577 ///This method runs the %BFS algorithm from the root node(s)
580 ///shortest path to each node. The algorithm computes
581 ///- The shortest path tree.
582 ///- The distance of each node from the root(s).
585 while ( !emptyQueue() ) processNextNode();
588 ///Executes the algorithm until \c dest is reached.
590 ///Executes the algorithm until \c dest is reached.
592 ///\pre init() must be called and at least one node should be added
593 ///with addSource() before using this function.
595 ///This method runs the %BFS algorithm from the root node(s)
596 ///in order to compute the shortest path to \c dest.
597 ///The algorithm computes
598 ///- The shortest path to \c dest.
599 ///- The distance of \c dest from the root(s).
600 void start(Node dest)
603 while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
606 ///Executes the algorithm until a condition is met.
608 ///Executes the algorithm until a condition is met.
610 ///\pre init() must be called and at least one node should be added
611 ///with addSource() before using this function.
613 ///\param nm must be a bool (or convertible) node map. The
614 ///algorithm will stop when it reaches a node \c v with
615 /// <tt>nm[v]</tt> true.
617 ///\return The reached node \c v with <tt>nm[v]</tt> true or
618 ///\c INVALID if no such node was found.
620 Node start(const NM &nm)
622 Node rnode = INVALID;
623 while ( !emptyQueue() && rnode == INVALID ) {
624 processNextNode(nm, rnode);
629 ///Runs %BFS algorithm from node \c s.
631 ///This method runs the %BFS algorithm from a root node \c s
634 ///shortest path to each node. The algorithm computes
635 ///- The shortest path tree.
636 ///- The distance of each node from the root.
638 ///\note b.run(s) is just a shortcut of the following code.
650 ///Finds the shortest path between \c s and \c t.
652 ///Finds the shortest path between \c s and \c t.
654 ///\return The length of the shortest s---t path if there exists one,
656 ///\note Apart from the return value, b.run(s) is
657 ///just a shortcut of the following code.
663 int run(Node s,Node t) {
667 return reached(t) ? _curr_dist : 0;
672 ///\name Query Functions
673 ///The result of the %BFS algorithm can be obtained using these
675 ///Before the use of these functions,
676 ///either run() or start() must be calleb.
680 typedef PredMapPath<Digraph, PredMap> Path;
682 ///Gives back the shortest path.
684 ///Gives back the shortest path.
685 ///\pre The \c t should be reachable from the source.
688 return Path(*G, *_pred, t);
691 ///The distance of a node from the root(s).
693 ///Returns the distance of a node from the root(s).
694 ///\pre \ref run() must be called before using this function.
695 ///\warning If node \c v in unreachable from the root(s) the return value
696 ///of this function is undefined.
697 int dist(Node v) const { return (*_dist)[v]; }
699 ///Returns the 'previous arc' of the shortest path tree.
701 ///For a node \c v it returns the 'previous arc'
702 ///of the shortest path tree,
703 ///i.e. it returns the last arc of a shortest path from the root(s) to \c
704 ///v. It is \ref INVALID
705 ///if \c v is unreachable from the root(s) or \c v is a root. The
706 ///shortest path tree used here is equal to the shortest path tree used in
708 ///\pre Either \ref run() or \ref start() must be called before using
710 Arc predArc(Node v) const { return (*_pred)[v];}
712 ///Returns the 'previous node' of the shortest path tree.
714 ///For a node \c v it returns the 'previous node'
715 ///of the shortest path tree,
716 ///i.e. it returns the last but one node from a shortest path from the
718 ///It is INVALID if \c v is unreachable from the root(s) or
719 ///if \c v itself a root.
720 ///The shortest path tree used here is equal to the shortest path
721 ///tree used in \ref predArc().
722 ///\pre Either \ref run() or \ref start() must be called before
723 ///using this function.
724 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
725 G->source((*_pred)[v]); }
727 ///Returns a reference to the NodeMap of distances.
729 ///Returns a reference to the NodeMap of distances.
730 ///\pre Either \ref run() or \ref init() must
731 ///be called before using this function.
732 const DistMap &distMap() const { return *_dist;}
734 ///Returns a reference to the shortest path tree map.
736 ///Returns a reference to the NodeMap of the arcs of the
737 ///shortest path tree.
738 ///\pre Either \ref run() or \ref init()
739 ///must be called before using this function.
740 const PredMap &predMap() const { return *_pred;}
742 ///Checks if a node is reachable from the root.
744 ///Returns \c true if \c v is reachable from the root.
745 ///\warning The source nodes are indicated as unreached.
746 ///\pre Either \ref run() or \ref start()
747 ///must be called before using this function.
749 bool reached(Node v) { return (*_reached)[v]; }
754 ///Default traits class of Bfs function.
756 ///Default traits class of Bfs function.
757 ///\tparam GR Digraph type.
759 struct BfsWizardDefaultTraits
761 ///The digraph type the algorithm runs on.
763 ///\brief The type of the map that stores the last
764 ///arcs of the shortest paths.
766 ///The type of the map that stores the last
767 ///arcs of the shortest paths.
768 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
770 typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
771 ///Instantiates a PredMap.
773 ///This function instantiates a \ref PredMap.
774 ///\param g is the digraph, to which we would like to define the PredMap.
775 ///\todo The digraph alone may be insufficient to initialize
777 static PredMap *createPredMap(const GR &g)
779 static PredMap *createPredMap(const GR &)
782 return new PredMap();
785 ///The type of the map that indicates which nodes are processed.
787 ///The type of the map that indicates which nodes are processed.
788 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
789 ///\todo named parameter to set this type, function to read and write.
790 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
791 ///Instantiates a ProcessedMap.
793 ///This function instantiates a \ref ProcessedMap.
794 ///\param g is the digraph, to which
795 ///we would like to define the \ref ProcessedMap
797 static ProcessedMap *createProcessedMap(const GR &g)
799 static ProcessedMap *createProcessedMap(const GR &)
802 return new ProcessedMap();
804 ///The type of the map that indicates which nodes are reached.
806 ///The type of the map that indicates which nodes are reached.
807 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
808 ///\todo named parameter to set this type, function to read and write.
809 typedef typename Digraph::template NodeMap<bool> ReachedMap;
810 ///Instantiates a ReachedMap.
812 ///This function instantiates a \ref ReachedMap.
813 ///\param G is the digraph, to which
814 ///we would like to define the \ref ReachedMap.
815 static ReachedMap *createReachedMap(const GR &G)
817 return new ReachedMap(G);
819 ///The type of the map that stores the dists of the nodes.
821 ///The type of the map that stores the dists of the nodes.
822 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
824 typedef NullMap<typename Digraph::Node,int> DistMap;
825 ///Instantiates a DistMap.
827 ///This function instantiates a \ref DistMap.
828 ///\param g is the digraph, to which we would like to define
831 static DistMap *createDistMap(const GR &g)
833 static DistMap *createDistMap(const GR &)
836 return new DistMap();
840 /// Default traits used by \ref BfsWizard
842 /// To make it easier to use Bfs algorithm
843 ///we have created a wizard class.
844 /// This \ref BfsWizard class needs default traits,
845 ///as well as the \ref Bfs class.
846 /// The \ref BfsWizardBase is a class to be the default traits of the
847 /// \ref BfsWizard class.
849 class BfsWizardBase : public BfsWizardDefaultTraits<GR>
852 typedef BfsWizardDefaultTraits<GR> Base;
854 /// Type of the nodes in the digraph.
855 typedef typename Base::Digraph::Node Node;
857 /// Pointer to the underlying digraph.
859 ///Pointer to the map of reached nodes.
861 ///Pointer to the map of processed nodes.
863 ///Pointer to the map of predecessors arcs.
865 ///Pointer to the map of distances.
867 ///Pointer to the source node.
873 /// This constructor does not require parameters, therefore it initiates
874 /// all of the attributes to default values (0, INVALID).
875 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
876 _dist(0), _source(INVALID) {}
880 /// This constructor requires some parameters,
881 /// listed in the parameters list.
882 /// Others are initiated to 0.
883 /// \param g is the initial value of \ref _g
884 /// \param s is the initial value of \ref _source
885 BfsWizardBase(const GR &g, Node s=INVALID) :
886 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
887 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
891 /// A class to make the usage of Bfs algorithm easier
893 /// This class is created to make it easier to use Bfs algorithm.
894 /// It uses the functions and features of the plain \ref Bfs,
895 /// but it is much simpler to use it.
897 /// Simplicity means that the way to change the types defined
898 /// in the traits class is based on functions that returns the new class
899 /// and not on templatable built-in classes.
900 /// When using the plain \ref Bfs
901 /// the new class with the modified type comes from
902 /// the original class by using the ::
903 /// operator. In the case of \ref BfsWizard only
904 /// a function have to be called and it will
905 /// return the needed class.
907 /// It does not have own \ref run method. When its \ref run method is called
908 /// it initiates a plain \ref Bfs class, and calls the \ref Bfs::run
911 class BfsWizard : public TR
915 ///The type of the underlying digraph.
916 typedef typename TR::Digraph Digraph;
918 typedef typename Digraph::Node Node;
920 typedef typename Digraph::NodeIt NodeIt;
922 typedef typename Digraph::Arc Arc;
924 typedef typename Digraph::OutArcIt OutArcIt;
926 ///\brief The type of the map that stores
928 typedef typename TR::ReachedMap ReachedMap;
929 ///\brief The type of the map that stores
930 ///the processed nodes
931 typedef typename TR::ProcessedMap ProcessedMap;
932 ///\brief The type of the map that stores the last
933 ///arcs of the shortest paths.
934 typedef typename TR::PredMap PredMap;
935 ///The type of the map that stores the dists of the nodes.
936 typedef typename TR::DistMap DistMap;
940 BfsWizard() : TR() {}
942 /// Constructor that requires parameters.
944 /// Constructor that requires parameters.
945 /// These parameters will be the default values for the traits class.
946 BfsWizard(const Digraph &g, Node s=INVALID) :
950 BfsWizard(const TR &b) : TR(b) {}
954 ///Runs Bfs algorithm from a given node.
956 ///Runs Bfs algorithm from a given node.
957 ///The node can be given by the \ref source function.
960 if(Base::_source==INVALID) throw UninitializedParameter();
961 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
963 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
965 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
967 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
969 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
970 alg.run(Base::_source);
973 ///Runs Bfs algorithm from the given node.
975 ///Runs Bfs algorithm from the given node.
976 ///\param s is the given source.
984 struct DefPredMapBase : public Base {
986 static PredMap *createPredMap(const Digraph &) { return 0; };
987 DefPredMapBase(const TR &b) : TR(b) {}
990 ///\brief \ref named-templ-param "Named parameter"
991 ///function for setting PredMap
993 /// \ref named-templ-param "Named parameter"
994 ///function for setting PredMap
997 BfsWizard<DefPredMapBase<T> > predMap(const T &t)
999 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1000 return BfsWizard<DefPredMapBase<T> >(*this);
1005 struct DefReachedMapBase : public Base {
1006 typedef T ReachedMap;
1007 static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1008 DefReachedMapBase(const TR &b) : TR(b) {}
1011 ///\brief \ref named-templ-param "Named parameter"
1012 ///function for setting ReachedMap
1014 /// \ref named-templ-param "Named parameter"
1015 ///function for setting ReachedMap
1018 BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1020 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
1021 return BfsWizard<DefReachedMapBase<T> >(*this);
1026 struct DefProcessedMapBase : public Base {
1027 typedef T ProcessedMap;
1028 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1029 DefProcessedMapBase(const TR &b) : TR(b) {}
1032 ///\brief \ref named-templ-param "Named parameter"
1033 ///function for setting ProcessedMap
1035 /// \ref named-templ-param "Named parameter"
1036 ///function for setting ProcessedMap
1039 BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1041 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
1042 return BfsWizard<DefProcessedMapBase<T> >(*this);
1047 struct DefDistMapBase : public Base {
1049 static DistMap *createDistMap(const Digraph &) { return 0; };
1050 DefDistMapBase(const TR &b) : TR(b) {}
1053 ///\brief \ref named-templ-param "Named parameter"
1054 ///function for setting DistMap type
1056 /// \ref named-templ-param "Named parameter"
1057 ///function for setting DistMap type
1060 BfsWizard<DefDistMapBase<T> > distMap(const T &t)
1062 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1063 return BfsWizard<DefDistMapBase<T> >(*this);
1066 /// Sets the source node, from which the Bfs algorithm runs.
1068 /// Sets the source node, from which the Bfs algorithm runs.
1069 /// \param s is the source node.
1070 BfsWizard<TR> &source(Node s)
1078 ///Function type interface for Bfs algorithm.
1081 ///Function type interface for Bfs algorithm.
1083 ///This function also has several
1084 ///\ref named-templ-func-param "named parameters",
1085 ///they are declared as the members of class \ref BfsWizard.
1087 ///example shows how to use these parameters.
1089 /// bfs(g,source).predMap(preds).run();
1091 ///\warning Don't forget to put the \ref BfsWizard::run() "run()"
1092 ///to the end of the parameter list.
1096 BfsWizard<BfsWizardBase<GR> >
1097 bfs(const GR &g,typename GR::Node s=INVALID)
1099 return BfsWizard<BfsWizardBase<GR> >(g,s);
1103 /// \brief Visitor class for bfs.
1105 /// This class defines the interface of the BfsVisit events, and
1106 /// it could be the base of a real Visitor class.
1107 template <typename _Digraph>
1109 typedef _Digraph Digraph;
1110 typedef typename Digraph::Arc Arc;
1111 typedef typename Digraph::Node Node;
1112 /// \brief Called when the arc reach a node.
1114 /// It is called when the bfs find an arc which target is not
1116 void discover(const Arc& arc) {}
1117 /// \brief Called when the node reached first time.
1119 /// It is Called when the node reached first time.
1120 void reach(const Node& node) {}
1121 /// \brief Called when the arc examined but target of the arc
1122 /// already discovered.
1124 /// It called when the arc examined but the target of the arc
1125 /// already discovered.
1126 void examine(const Arc& arc) {}
1127 /// \brief Called for the source node of the bfs.
1129 /// It is called for the source node of the bfs.
1130 void start(const Node& node) {}
1131 /// \brief Called when the node processed.
1133 /// It is Called when the node processed.
1134 void process(const Node& node) {}
1137 template <typename _Digraph>
1139 typedef _Digraph Digraph;
1140 typedef typename Digraph::Arc Arc;
1141 typedef typename Digraph::Node Node;
1142 void discover(const Arc&) {}
1143 void reach(const Node&) {}
1144 void examine(const Arc&) {}
1145 void start(const Node&) {}
1146 void process(const Node&) {}
1148 template <typename _Visitor>
1149 struct Constraints {
1150 void constraints() {
1153 visitor.discover(arc);
1154 visitor.reach(node);
1155 visitor.examine(arc);
1156 visitor.start(node);
1157 visitor.process(node);
1164 /// \brief Default traits class of BfsVisit class.
1166 /// Default traits class of BfsVisit class.
1167 /// \tparam _Digraph Digraph type.
1168 template<class _Digraph>
1169 struct BfsVisitDefaultTraits {
1171 /// \brief The digraph type the algorithm runs on.
1172 typedef _Digraph Digraph;
1174 /// \brief The type of the map that indicates which nodes are reached.
1176 /// The type of the map that indicates which nodes are reached.
1177 /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
1178 /// \todo named parameter to set this type, function to read and write.
1179 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1181 /// \brief Instantiates a ReachedMap.
1183 /// This function instantiates a \ref ReachedMap.
1184 /// \param digraph is the digraph, to which
1185 /// we would like to define the \ref ReachedMap.
1186 static ReachedMap *createReachedMap(const Digraph &digraph) {
1187 return new ReachedMap(digraph);
1194 /// \brief %BFS Visit algorithm class.
1196 /// This class provides an efficient implementation of the %BFS algorithm
1197 /// with visitor interface.
1199 /// The %BfsVisit class provides an alternative interface to the Bfs
1200 /// class. It works with callback mechanism, the BfsVisit object calls
1201 /// on every bfs event the \c Visitor class member functions.
1203 /// \tparam _Digraph The digraph type the algorithm runs on.
1204 /// The default value is
1205 /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it
1206 /// is only passed to \ref BfsDefaultTraits.
1207 /// \tparam _Visitor The Visitor object for the algorithm. The
1208 /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitor which
1209 /// does not observe the Bfs events. If you want to observe the bfs
1210 /// events you should implement your own Visitor class.
1211 /// \tparam _Traits Traits class to set various data types used by the
1212 /// algorithm. The default traits class is
1213 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
1214 /// See \ref BfsVisitDefaultTraits for the documentation of
1215 /// a Bfs visit traits class.
1217 template <typename _Digraph, typename _Visitor, typename _Traits>
1219 template <typename _Digraph = ListDigraph,
1220 typename _Visitor = BfsVisitor<_Digraph>,
1221 typename _Traits = BfsDefaultTraits<_Digraph> >
1226 /// \brief \ref Exception for uninitialized parameters.
1228 /// This error represents problems in the initialization
1229 /// of the parameters of the algorithms.
1230 class UninitializedParameter : public lemon::UninitializedParameter {
1232 virtual const char* what() const throw()
1234 return "lemon::BfsVisit::UninitializedParameter";
1238 typedef _Traits Traits;
1240 typedef typename Traits::Digraph Digraph;
1242 typedef _Visitor Visitor;
1244 ///The type of the map indicating which nodes are reached.
1245 typedef typename Traits::ReachedMap ReachedMap;
1249 typedef typename Digraph::Node Node;
1250 typedef typename Digraph::NodeIt NodeIt;
1251 typedef typename Digraph::Arc Arc;
1252 typedef typename Digraph::OutArcIt OutArcIt;
1254 /// Pointer to the underlying digraph.
1255 const Digraph *_digraph;
1256 /// Pointer to the visitor object.
1258 ///Pointer to the map of reached status of the nodes.
1259 ReachedMap *_reached;
1260 ///Indicates if \ref _reached is locally allocated (\c true) or not.
1263 std::vector<typename Digraph::Node> _list;
1264 int _list_front, _list_back;
1266 /// \brief Creates the maps if necessary.
1268 /// Creates the maps if necessary.
1269 void create_maps() {
1271 local_reached = true;
1272 _reached = Traits::createReachedMap(*_digraph);
1282 typedef BfsVisit Create;
1284 /// \name Named template parameters
1288 struct DefReachedMapTraits : public Traits {
1289 typedef T ReachedMap;
1290 static ReachedMap *createReachedMap(const Digraph &digraph) {
1291 throw UninitializedParameter();
1294 /// \brief \ref named-templ-param "Named parameter" for setting
1297 /// \ref named-templ-param "Named parameter" for setting ReachedMap type
1299 struct DefReachedMap : public BfsVisit< Digraph, Visitor,
1300 DefReachedMapTraits<T> > {
1301 typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
1307 /// \brief Constructor.
1311 /// \param digraph the digraph the algorithm will run on.
1312 /// \param visitor The visitor of the algorithm.
1314 BfsVisit(const Digraph& digraph, Visitor& visitor)
1315 : _digraph(&digraph), _visitor(&visitor),
1316 _reached(0), local_reached(false) {}
1318 /// \brief Destructor.
1322 if(local_reached) delete _reached;
1325 /// \brief Sets the map indicating if a node is reached.
1327 /// Sets the map indicating if a node is reached.
1328 /// If you don't use this function before calling \ref run(),
1329 /// it will allocate one. The destuctor deallocates this
1330 /// automatically allocated map, of course.
1331 /// \return <tt> (*this) </tt>
1332 BfsVisit &reachedMap(ReachedMap &m) {
1335 local_reached = false;
1342 /// \name Execution control
1343 /// The simplest way to execute the algorithm is to use
1344 /// one of the member functions called \c run(...).
1346 /// If you need more control on the execution,
1347 /// first you must call \ref init(), then you can adda source node
1348 /// with \ref addSource().
1349 /// Finally \ref start() will perform the actual path
1353 /// \brief Initializes the internal data structures.
1355 /// Initializes the internal data structures.
1359 _list.resize(countNodes(*_digraph));
1360 _list_front = _list_back = -1;
1361 for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
1362 _reached->set(u, false);
1366 /// \brief Adds a new source node.
1368 /// Adds a new source node to the set of nodes to be processed.
1369 void addSource(Node s) {
1370 if(!(*_reached)[s]) {
1371 _reached->set(s,true);
1374 _list[++_list_back] = s;
1378 /// \brief Processes the next node.
1380 /// Processes the next node.
1382 /// \return The processed node.
1384 /// \pre The queue must not be empty!
1385 Node processNextNode() {
1386 Node n = _list[++_list_front];
1387 _visitor->process(n);
1389 for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
1390 Node m = _digraph->target(e);
1391 if (!(*_reached)[m]) {
1392 _visitor->discover(e);
1394 _reached->set(m, true);
1395 _list[++_list_back] = m;
1397 _visitor->examine(e);
1403 /// \brief Processes the next node.
1405 /// Processes the next node. And checks that the given target node
1406 /// is reached. If the target node is reachable from the processed
1407 /// node then the reached parameter will be set true. The reached
1408 /// parameter should be initially false.
1410 /// \param target The target node.
1411 /// \retval reach Indicates that the target node is reached.
1412 /// \return The processed node.
1414 /// \warning The queue must not be empty!
1415 Node processNextNode(Node target, bool& reach) {
1416 Node n = _list[++_list_front];
1417 _visitor->process(n);
1419 for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
1420 Node m = _digraph->target(e);
1421 if (!(*_reached)[m]) {
1422 _visitor->discover(e);
1424 _reached->set(m, true);
1425 _list[++_list_back] = m;
1426 reach = reach || (target == m);
1428 _visitor->examine(e);
1434 /// \brief Processes the next node.
1436 /// Processes the next node. And checks that at least one of
1437 /// reached node has true value in the \c nm node map. If one node
1438 /// with true value is reachable from the processed node then the
1439 /// rnode parameter will be set to the first of such nodes.
1441 /// \param nm The node map of possible targets.
1442 /// \retval rnode The reached target node.
1443 /// \return The processed node.
1445 /// \warning The queue must not be empty!
1446 template <typename NM>
1447 Node processNextNode(const NM& nm, Node& rnode) {
1448 Node n = _list[++_list_front];
1449 _visitor->process(n);
1451 for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
1452 Node m = _digraph->target(e);
1453 if (!(*_reached)[m]) {
1454 _visitor->discover(e);
1456 _reached->set(m, true);
1457 _list[++_list_back] = m;
1458 if (nm[m] && rnode == INVALID) rnode = m;
1460 _visitor->examine(e);
1466 /// \brief Next node to be processed.
1468 /// Next node to be processed.
1470 /// \return The next node to be processed or INVALID if the stack is
1473 return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
1476 /// \brief Returns \c false if there are nodes
1477 /// to be processed in the queue
1479 /// Returns \c false if there are nodes
1480 /// to be processed in the queue
1481 bool emptyQueue() { return _list_front == _list_back; }
1483 /// \brief Returns the number of the nodes to be processed.
1485 /// Returns the number of the nodes to be processed in the queue.
1486 int queueSize() { return _list_back - _list_front; }
1488 /// \brief Executes the algorithm.
1490 /// Executes the algorithm.
1492 /// \pre init() must be called and at least one node should be added
1493 /// with addSource() before using this function.
1495 while ( !emptyQueue() ) processNextNode();
1498 /// \brief Executes the algorithm until \c dest is reached.
1500 /// Executes the algorithm until \c dest is reached.
1502 /// \pre init() must be called and at least one node should be added
1503 /// with addSource() before using this function.
1504 void start(Node dest) {
1506 while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
1509 /// \brief Executes the algorithm until a condition is met.
1511 /// Executes the algorithm until a condition is met.
1513 /// \pre init() must be called and at least one node should be added
1514 /// with addSource() before using this function.
1516 ///\param nm must be a bool (or convertible) node map. The
1517 ///algorithm will stop when it reaches a node \c v with
1518 /// <tt>nm[v]</tt> true.
1520 ///\return The reached node \c v with <tt>nm[v]</tt> true or
1521 ///\c INVALID if no such node was found.
1522 template <typename NM>
1523 Node start(const NM &nm) {
1524 Node rnode = INVALID;
1525 while ( !emptyQueue() && rnode == INVALID ) {
1526 processNextNode(nm, rnode);
1531 /// \brief Runs %BFSVisit algorithm from node \c s.
1533 /// This method runs the %BFS algorithm from a root node \c s.
1534 /// \note b.run(s) is just a shortcut of the following code.
1546 /// \brief Runs %BFSVisit algorithm to visit all nodes in the digraph.
1548 /// This method runs the %BFS algorithm in order to
1549 /// compute the %BFS path to each node. The algorithm computes
1550 /// - The %BFS tree.
1551 /// - The distance of each node from the root in the %BFS tree.
1553 ///\note b.run() is just a shortcut of the following code.
1556 /// for (NodeIt it(digraph); it != INVALID; ++it) {
1557 /// if (!b.reached(it)) {
1558 /// b.addSource(it);
1565 for (NodeIt it(*_digraph); it != INVALID; ++it) {
1574 /// \name Query Functions
1575 /// The result of the %BFS algorithm can be obtained using these
1577 /// Before the use of these functions,
1578 /// either run() or start() must be called.
1581 /// \brief Checks if a node is reachable from the root.
1583 /// Returns \c true if \c v is reachable from the root(s).
1584 /// \warning The source nodes are inditated as unreachable.
1585 /// \pre Either \ref run() or \ref start()
1586 /// must be called before using this function.
1588 bool reached(Node v) { return (*_reached)[v]; }
1592 } //END OF NAMESPACE LEMON