Fix wrong iteration in ListGraph snapshot, part II. (#598)
1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2013
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>
31 #include <lemon/path.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 conform to the \ref concepts::WriteMap "WriteMap" concept.
51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
52 ///Instantiates a \c PredMap.
54 ///This function instantiates a \ref PredMap.
55 ///\param g is the digraph, to which we would like to define the
57 static PredMap *createPredMap(const Digraph &g)
59 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 conform to the \ref concepts::WriteMap "WriteMap" concept.
66 ///By default, it is a NullMap.
67 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
68 ///Instantiates a \c 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 Digraph &g)
76 static ProcessedMap *createProcessedMap(const Digraph &)
79 return new ProcessedMap();
82 ///The type of the map that indicates which nodes are reached.
84 ///The type of the map that indicates which nodes are reached.
86 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
87 typedef typename Digraph::template NodeMap<bool> ReachedMap;
88 ///Instantiates a \c 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 conform to the \ref concepts::WriteMap "WriteMap" concept.
102 typedef typename Digraph::template NodeMap<int> DistMap;
103 ///Instantiates a \c 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 type is \ref ListDigraph.
125 ///\tparam TR The traits class that defines various types used by the
126 ///algorithm. By default, it is \ref BfsDefaultTraits
127 ///"BfsDefaultTraits<GR>".
128 ///In most cases, this parameter should not be set directly,
129 ///consider to use the named template parameters instead.
131 template <typename GR,
134 template <typename GR=ListDigraph,
135 typename TR=BfsDefaultTraits<GR> >
140 ///The type of the digraph the algorithm runs on.
141 typedef typename TR::Digraph Digraph;
143 ///\brief The type of the map that stores the predecessor arcs of the
145 typedef typename TR::PredMap PredMap;
146 ///The type of the map that stores the distances of the nodes.
147 typedef typename TR::DistMap DistMap;
148 ///The type of the map that indicates which nodes are reached.
149 typedef typename TR::ReachedMap ReachedMap;
150 ///The type of the map that indicates which nodes are processed.
151 typedef typename TR::ProcessedMap ProcessedMap;
152 ///The type of the paths.
153 typedef PredMapPath<Digraph, PredMap> Path;
155 ///The \ref lemon::BfsDefaultTraits "traits class" of the algorithm.
160 typedef typename Digraph::Node Node;
161 typedef typename Digraph::NodeIt NodeIt;
162 typedef typename Digraph::Arc Arc;
163 typedef typename Digraph::OutArcIt OutArcIt;
165 //Pointer to the underlying digraph.
167 //Pointer to the map of predecessor arcs.
169 //Indicates if _pred is locally allocated (true) or not.
171 //Pointer to the map of distances.
173 //Indicates if _dist is locally allocated (true) or not.
175 //Pointer to the map of reached status of the nodes.
176 ReachedMap *_reached;
177 //Indicates if _reached is locally allocated (true) or not.
179 //Pointer to the map of processed status of the nodes.
180 ProcessedMap *_processed;
181 //Indicates if _processed is locally allocated (true) or not.
182 bool local_processed;
184 std::vector<typename Digraph::Node> _queue;
185 int _queue_head,_queue_tail,_queue_next_dist;
188 //Creates the maps if necessary.
193 _pred = Traits::createPredMap(*G);
197 _dist = Traits::createDistMap(*G);
200 local_reached = true;
201 _reached = Traits::createReachedMap(*G);
204 local_processed = true;
205 _processed = Traits::createProcessedMap(*G);
217 ///\name Named Template Parameters
222 struct SetPredMapTraits : public Traits {
224 static PredMap *createPredMap(const Digraph &)
226 LEMON_ASSERT(false, "PredMap is not initialized");
227 return 0; // ignore warnings
230 ///\brief \ref named-templ-param "Named parameter" for setting
233 ///\ref named-templ-param "Named parameter" for setting
235 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
237 struct SetPredMap : public Bfs< Digraph, SetPredMapTraits<T> > {
238 typedef Bfs< Digraph, SetPredMapTraits<T> > Create;
242 struct SetDistMapTraits : public Traits {
244 static DistMap *createDistMap(const Digraph &)
246 LEMON_ASSERT(false, "DistMap is not initialized");
247 return 0; // ignore warnings
250 ///\brief \ref named-templ-param "Named parameter" for setting
253 ///\ref named-templ-param "Named parameter" for setting
255 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
257 struct SetDistMap : public Bfs< Digraph, SetDistMapTraits<T> > {
258 typedef Bfs< Digraph, SetDistMapTraits<T> > Create;
262 struct SetReachedMapTraits : public Traits {
263 typedef T ReachedMap;
264 static ReachedMap *createReachedMap(const Digraph &)
266 LEMON_ASSERT(false, "ReachedMap is not initialized");
267 return 0; // ignore warnings
270 ///\brief \ref named-templ-param "Named parameter" for setting
271 ///\c ReachedMap type.
273 ///\ref named-templ-param "Named parameter" for setting
274 ///\c ReachedMap type.
275 ///It must conform to
276 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
278 struct SetReachedMap : public Bfs< Digraph, SetReachedMapTraits<T> > {
279 typedef Bfs< Digraph, SetReachedMapTraits<T> > Create;
283 struct SetProcessedMapTraits : public Traits {
284 typedef T ProcessedMap;
285 static ProcessedMap *createProcessedMap(const Digraph &)
287 LEMON_ASSERT(false, "ProcessedMap is not initialized");
288 return 0; // ignore warnings
291 ///\brief \ref named-templ-param "Named parameter" for setting
292 ///\c ProcessedMap type.
294 ///\ref named-templ-param "Named parameter" for setting
295 ///\c ProcessedMap type.
296 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
298 struct SetProcessedMap : public Bfs< Digraph, SetProcessedMapTraits<T> > {
299 typedef Bfs< Digraph, SetProcessedMapTraits<T> > Create;
302 struct SetStandardProcessedMapTraits : public Traits {
303 typedef typename Digraph::template NodeMap<bool> ProcessedMap;
304 static ProcessedMap *createProcessedMap(const Digraph &g)
306 return new ProcessedMap(g);
307 return 0; // ignore warnings
310 ///\brief \ref named-templ-param "Named parameter" for setting
311 ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
313 ///\ref named-templ-param "Named parameter" for setting
314 ///\c ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
315 ///If you don't set it explicitly, it will be automatically allocated.
316 struct SetStandardProcessedMap :
317 public Bfs< Digraph, SetStandardProcessedMapTraits > {
318 typedef Bfs< Digraph, SetStandardProcessedMapTraits > Create;
328 ///\param g The digraph the algorithm runs on.
329 Bfs(const Digraph &g) :
331 _pred(NULL), local_pred(false),
332 _dist(NULL), local_dist(false),
333 _reached(NULL), local_reached(false),
334 _processed(NULL), local_processed(false)
340 if(local_pred) delete _pred;
341 if(local_dist) delete _dist;
342 if(local_reached) delete _reached;
343 if(local_processed) delete _processed;
346 ///Sets the map that stores the predecessor arcs.
348 ///Sets the map that stores the predecessor arcs.
349 ///If you don't use this function before calling \ref run(Node) "run()"
350 ///or \ref init(), an instance will be allocated automatically.
351 ///The destructor deallocates this automatically allocated map,
353 ///\return <tt> (*this) </tt>
354 Bfs &predMap(PredMap &m)
364 ///Sets the map that indicates which nodes are reached.
366 ///Sets the map that indicates which nodes are reached.
367 ///If you don't use this function before calling \ref run(Node) "run()"
368 ///or \ref init(), an instance will be allocated automatically.
369 ///The destructor deallocates this automatically allocated map,
371 ///\return <tt> (*this) </tt>
372 Bfs &reachedMap(ReachedMap &m)
382 ///Sets the map that indicates which nodes are processed.
384 ///Sets the map that indicates which nodes are processed.
385 ///If you don't use this function before calling \ref run(Node) "run()"
386 ///or \ref init(), an instance will be allocated automatically.
387 ///The destructor deallocates this automatically allocated map,
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(Node) "run()"
405 ///or \ref init(), an instance will be allocated automatically.
406 ///The destructor deallocates this automatically allocated map,
408 ///\return <tt> (*this) </tt>
409 Bfs &distMap(DistMap &m)
421 ///\name Execution Control
422 ///The simplest way to execute the BFS algorithm is to use one of the
423 ///member functions called \ref run(Node) "run()".\n
424 ///If you need better control on the execution, you have to call
425 ///\ref init() first, then you can add several source nodes with
426 ///\ref addSource(). Finally the actual path computation can be
427 ///performed with one of the \ref start() functions.
431 ///\brief Initializes the internal data structures.
433 ///Initializes the internal data structures.
437 _queue.resize(countNodes(*G));
438 _queue_head=_queue_tail=0;
440 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
441 _pred->set(u,INVALID);
442 _reached->set(u,false);
443 _processed->set(u,false);
447 ///Adds a new source node.
449 ///Adds a new source node to the set of nodes to be processed.
451 void addSource(Node s)
455 _reached->set(s,true);
456 _pred->set(s,INVALID);
458 _queue[_queue_head++]=s;
459 _queue_next_dist=_queue_head;
463 ///Processes the next node.
465 ///Processes the next node.
467 ///\return The processed node.
469 ///\pre The queue must not be empty.
470 Node processNextNode()
472 if(_queue_tail==_queue_next_dist) {
474 _queue_next_dist=_queue_head;
476 Node n=_queue[_queue_tail++];
477 _processed->set(n,true);
479 for(OutArcIt e(*G,n);e!=INVALID;++e)
480 if(!(*_reached)[m=G->target(e)]) {
481 _queue[_queue_head++]=m;
482 _reached->set(m,true);
484 _dist->set(m,_curr_dist);
489 ///Processes the next node.
491 ///Processes the next node and checks if the given target node
492 ///is reached. If the target node is reachable from the processed
493 ///node, then the \c reach parameter will be set to \c true.
495 ///\param target The target node.
496 ///\retval reach Indicates if the target node is reached.
497 ///It should be initially \c false.
499 ///\return The processed node.
501 ///\pre The queue must not be empty.
502 Node processNextNode(Node target, bool& reach)
504 if(_queue_tail==_queue_next_dist) {
506 _queue_next_dist=_queue_head;
508 Node n=_queue[_queue_tail++];
509 _processed->set(n,true);
511 for(OutArcIt e(*G,n);e!=INVALID;++e)
512 if(!(*_reached)[m=G->target(e)]) {
513 _queue[_queue_head++]=m;
514 _reached->set(m,true);
516 _dist->set(m,_curr_dist);
517 reach = reach || (target == m);
522 ///Processes the next node.
524 ///Processes the next node and checks if at least one of reached
525 ///nodes has \c true value in the \c nm node map. If one node
526 ///with \c true value is reachable from the processed node, then the
527 ///\c rnode parameter will be set to the first of such nodes.
529 ///\param nm A \c bool (or convertible) node map that indicates the
531 ///\retval rnode The reached target node.
532 ///It should be initially \c INVALID.
534 ///\return The processed node.
536 ///\pre The queue must not be empty.
538 Node processNextNode(const NM& nm, Node& rnode)
540 if(_queue_tail==_queue_next_dist) {
542 _queue_next_dist=_queue_head;
544 Node n=_queue[_queue_tail++];
545 _processed->set(n,true);
547 for(OutArcIt e(*G,n);e!=INVALID;++e)
548 if(!(*_reached)[m=G->target(e)]) {
549 _queue[_queue_head++]=m;
550 _reached->set(m,true);
552 _dist->set(m,_curr_dist);
553 if (nm[m] && rnode == INVALID) rnode = m;
558 ///The next node to be processed.
560 ///Returns the next node to be processed or \c INVALID if the queue
562 Node nextNode() const
564 return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
567 ///Returns \c false if there are nodes to be processed.
569 ///Returns \c false if there are nodes to be processed
571 bool emptyQueue() const { return _queue_tail==_queue_head; }
573 ///Returns the number of the nodes to be processed.
575 ///Returns the number of the nodes to be processed
577 int queueSize() const { return _queue_head-_queue_tail; }
579 ///Executes the algorithm.
581 ///Executes the algorithm.
583 ///This method runs the %BFS algorithm from the root node(s)
584 ///in order to compute the shortest path to each node.
586 ///The algorithm computes
587 ///- the shortest path tree (forest),
588 ///- the distance of each node from the root(s).
590 ///\pre init() must be called and at least one root node should be
591 ///added with addSource() before using this function.
593 ///\note <tt>b.start()</tt> is just a shortcut of the following code.
595 /// while ( !b.emptyQueue() ) {
596 /// b.processNextNode();
601 while ( !emptyQueue() ) processNextNode();
604 ///Executes the algorithm until the given target node is reached.
606 ///Executes the algorithm until the given target node is reached.
608 ///This method runs the %BFS algorithm from the root node(s)
609 ///in order to compute the shortest path to \c t.
611 ///The algorithm computes
612 ///- the shortest path to \c t,
613 ///- the distance of \c t from the root(s).
615 ///\pre init() must be called and at least one root node should be
616 ///added with addSource() before using this function.
618 ///\note <tt>b.start(t)</tt> is just a shortcut of the following code.
620 /// bool reach = false;
621 /// while ( !b.emptyQueue() && !reach ) {
622 /// b.processNextNode(t, reach);
628 while ( !emptyQueue() && !reach ) processNextNode(t, reach);
631 ///Executes the algorithm until a condition is met.
633 ///Executes the algorithm until a condition is met.
635 ///This method runs the %BFS algorithm from the root node(s) in
636 ///order to compute the shortest path to a node \c v with
637 /// <tt>nm[v]</tt> true, if such a node can be found.
639 ///\param nm A \c bool (or convertible) node map. The algorithm
640 ///will stop when it reaches a node \c v with <tt>nm[v]</tt> true.
642 ///\return The reached node \c v with <tt>nm[v]</tt> true or
643 ///\c INVALID if no such node was found.
645 ///\pre init() must be called and at least one root node should be
646 ///added with addSource() before using this function.
648 ///\note <tt>b.start(nm)</tt> is just a shortcut of the following code.
650 /// Node rnode = INVALID;
651 /// while ( !b.emptyQueue() && rnode == INVALID ) {
652 /// b.processNextNode(nm, rnode);
656 template<class NodeBoolMap>
657 Node start(const NodeBoolMap &nm)
659 Node rnode = INVALID;
660 while ( !emptyQueue() && rnode == INVALID ) {
661 processNextNode(nm, rnode);
666 ///Runs the algorithm from the given source node.
668 ///This method runs the %BFS algorithm from node \c s
669 ///in order to compute the shortest path to each node.
671 ///The algorithm computes
672 ///- the shortest path tree,
673 ///- the distance of each node from the root.
675 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
687 ///Finds the shortest path between \c s and \c t.
689 ///This method runs the %BFS algorithm from node \c s
690 ///in order to compute the shortest path to node \c t
691 ///(it stops searching when \c t is processed).
693 ///\return \c true if \c t is reachable form \c s.
695 ///\note Apart from the return value, <tt>b.run(s,t)</tt> is just a
696 ///shortcut of the following code.
702 bool run(Node s,Node t) {
709 ///Runs the algorithm to visit all nodes in the digraph.
711 ///This method runs the %BFS algorithm in order to visit all nodes
714 ///\note <tt>b.run(s)</tt> is just a shortcut of the following code.
717 /// for (NodeIt n(gr); n != INVALID; ++n) {
718 /// if (!b.reached(n)) {
726 for (NodeIt n(*G); n != INVALID; ++n) {
736 ///\name Query Functions
737 ///The results of the BFS algorithm can be obtained using these
739 ///Either \ref run(Node) "run()" or \ref start() should be called
740 ///before using them.
744 ///The shortest path to the given node.
746 ///Returns the shortest path to the given node from the root(s).
748 ///\warning \c t should be reached from the root(s).
750 ///\pre Either \ref run(Node) "run()" or \ref init()
751 ///must be called before using this function.
752 Path path(Node t) const { return Path(*G, *_pred, t); }
754 ///The distance of the given node from the root(s).
756 ///Returns the distance of the given node from the root(s).
758 ///\warning If node \c v is not reached from the root(s), then
759 ///the return value of this function is undefined.
761 ///\pre Either \ref run(Node) "run()" or \ref init()
762 ///must be called before using this function.
763 int dist(Node v) const { return (*_dist)[v]; }
765 ///\brief Returns the 'previous arc' of the shortest path tree for
768 ///This function returns the 'previous arc' of the shortest path
769 ///tree for the node \c v, i.e. it returns the last arc of a
770 ///shortest path from a root to \c v. It is \c INVALID if \c v
771 ///is not reached from the root(s) or if \c v is a root.
773 ///The shortest path tree used here is equal to the shortest path
774 ///tree used in \ref predNode() and \ref predMap().
776 ///\pre Either \ref run(Node) "run()" or \ref init()
777 ///must be called before using this function.
778 Arc predArc(Node v) const { return (*_pred)[v];}
780 ///\brief Returns the 'previous node' of the shortest path tree for
783 ///This function returns the 'previous node' of the shortest path
784 ///tree for the node \c v, i.e. it returns the last but one node
785 ///of a shortest path from a root to \c v. It is \c INVALID
786 ///if \c v is not reached from the root(s) or if \c v is a root.
788 ///The shortest path tree used here is equal to the shortest path
789 ///tree used in \ref predArc() and \ref predMap().
791 ///\pre Either \ref run(Node) "run()" or \ref init()
792 ///must be called before using this function.
793 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
794 G->source((*_pred)[v]); }
796 ///\brief Returns a const reference to the node map that stores the
797 /// distances of the nodes.
799 ///Returns a const reference to the node map that stores the distances
800 ///of the nodes calculated by the algorithm.
802 ///\pre Either \ref run(Node) "run()" or \ref init()
803 ///must be called before using this function.
804 const DistMap &distMap() const { return *_dist;}
806 ///\brief Returns a const reference to the node map that stores the
809 ///Returns a const reference to the node map that stores the predecessor
810 ///arcs, which form the shortest path tree (forest).
812 ///\pre Either \ref run(Node) "run()" or \ref init()
813 ///must be called before using this function.
814 const PredMap &predMap() const { return *_pred;}
816 ///Checks if the given node is reached from the root(s).
818 ///Returns \c true if \c v is reached from the root(s).
820 ///\pre Either \ref run(Node) "run()" or \ref init()
821 ///must be called before using this function.
822 bool reached(Node v) const { return (*_reached)[v]; }
827 ///Default traits class of bfs() function.
829 ///Default traits class of bfs() function.
830 ///\tparam GR Digraph type.
832 struct BfsWizardDefaultTraits
834 ///The type of the digraph the algorithm runs on.
837 ///\brief The type of the map that stores the predecessor
838 ///arcs of the shortest paths.
840 ///The type of the map that stores the predecessor
841 ///arcs of the shortest paths.
842 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
843 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
844 ///Instantiates a PredMap.
846 ///This function instantiates a PredMap.
847 ///\param g is the digraph, to which we would like to define the
849 static PredMap *createPredMap(const Digraph &g)
851 return new PredMap(g);
854 ///The type of the map that indicates which nodes are processed.
856 ///The type of the map that indicates which nodes are processed.
857 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
858 ///By default, it is a NullMap.
859 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
860 ///Instantiates a ProcessedMap.
862 ///This function instantiates a ProcessedMap.
863 ///\param g is the digraph, to which
864 ///we would like to define the ProcessedMap.
866 static ProcessedMap *createProcessedMap(const Digraph &g)
868 static ProcessedMap *createProcessedMap(const Digraph &)
871 return new ProcessedMap();
874 ///The type of the map that indicates which nodes are reached.
876 ///The type of the map that indicates which nodes are reached.
877 ///It must conform to
878 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
879 typedef typename Digraph::template NodeMap<bool> ReachedMap;
880 ///Instantiates a ReachedMap.
882 ///This function instantiates a ReachedMap.
883 ///\param g is the digraph, to which
884 ///we would like to define the ReachedMap.
885 static ReachedMap *createReachedMap(const Digraph &g)
887 return new ReachedMap(g);
890 ///The type of the map that stores the distances of the nodes.
892 ///The type of the map that stores the distances of the nodes.
893 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
894 typedef typename Digraph::template NodeMap<int> DistMap;
895 ///Instantiates a DistMap.
897 ///This function instantiates a DistMap.
898 ///\param g is the digraph, to which we would like to define
900 static DistMap *createDistMap(const Digraph &g)
902 return new DistMap(g);
905 ///The type of the shortest paths.
907 ///The type of the shortest paths.
908 ///It must conform to the \ref concepts::Path "Path" concept.
909 typedef lemon::Path<Digraph> Path;
912 /// Default traits class used by BfsWizard
914 /// Default traits class used by BfsWizard.
915 /// \tparam GR The type of the digraph.
917 class BfsWizardBase : public BfsWizardDefaultTraits<GR>
920 typedef BfsWizardDefaultTraits<GR> Base;
922 //The type of the nodes in the digraph.
923 typedef typename Base::Digraph::Node Node;
925 //Pointer to the digraph the algorithm runs on.
927 //Pointer to the map of reached nodes.
929 //Pointer to the map of processed nodes.
931 //Pointer to the map of predecessors arcs.
933 //Pointer to the map of distances.
935 //Pointer to the shortest path to the target node.
937 //Pointer to the distance of the target node.
943 /// This constructor does not require parameters, it initiates
944 /// all of the attributes to \c 0.
945 BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
946 _dist(0), _path(0), _di(0) {}
950 /// This constructor requires one parameter,
951 /// others are initiated to \c 0.
952 /// \param g The digraph the algorithm runs on.
953 BfsWizardBase(const GR &g) :
954 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
955 _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {}
959 /// Auxiliary class for the function-type interface of BFS algorithm.
961 /// This auxiliary class is created to implement the
962 /// \ref bfs() "function-type interface" of \ref Bfs algorithm.
963 /// It does not have own \ref run(Node) "run()" method, it uses the
964 /// functions and features of the plain \ref Bfs.
966 /// This class should only be used through the \ref bfs() function,
967 /// which makes it easier to use the algorithm.
969 /// \tparam TR The traits class that defines various types used by the
972 class BfsWizard : public TR
976 typedef typename TR::Digraph Digraph;
978 typedef typename Digraph::Node Node;
979 typedef typename Digraph::NodeIt NodeIt;
980 typedef typename Digraph::Arc Arc;
981 typedef typename Digraph::OutArcIt OutArcIt;
983 typedef typename TR::PredMap PredMap;
984 typedef typename TR::DistMap DistMap;
985 typedef typename TR::ReachedMap ReachedMap;
986 typedef typename TR::ProcessedMap ProcessedMap;
987 typedef typename TR::Path Path;
992 BfsWizard() : TR() {}
994 /// Constructor that requires parameters.
996 /// Constructor that requires parameters.
997 /// These parameters will be the default values for the traits class.
998 /// \param g The digraph the algorithm runs on.
999 BfsWizard(const Digraph &g) :
1003 BfsWizard(const TR &b) : TR(b) {}
1007 ///Runs BFS algorithm from the given source node.
1009 ///This method runs BFS algorithm from node \c s
1010 ///in order to compute the shortest path to each node.
1013 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
1015 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1017 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1019 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
1020 if (Base::_processed)
1021 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1028 ///Finds the shortest path between \c s and \c t.
1030 ///This method runs BFS algorithm from node \c s
1031 ///in order to compute the shortest path to node \c t
1032 ///(it stops searching when \c t is processed).
1034 ///\return \c true if \c t is reachable form \c s.
1035 bool run(Node s, Node t)
1037 Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
1039 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
1041 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
1043 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
1044 if (Base::_processed)
1045 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
1048 *reinterpret_cast<Path*>(Base::_path) = alg.path(t);
1050 *Base::_di = alg.dist(t);
1051 return alg.reached(t);
1054 ///Runs BFS algorithm to visit all nodes in the digraph.
1056 ///This method runs BFS algorithm in order to visit all nodes
1064 struct SetPredMapBase : public Base {
1066 static PredMap *createPredMap(const Digraph &) { return 0; };
1067 SetPredMapBase(const TR &b) : TR(b) {}
1070 ///\brief \ref named-templ-param "Named parameter" for setting
1071 ///the predecessor map.
1073 ///\ref named-templ-param "Named parameter" function for setting
1074 ///the map that stores the predecessor arcs of the nodes.
1076 BfsWizard<SetPredMapBase<T> > predMap(const T &t)
1078 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1079 return BfsWizard<SetPredMapBase<T> >(*this);
1083 struct SetReachedMapBase : public Base {
1084 typedef T ReachedMap;
1085 static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1086 SetReachedMapBase(const TR &b) : TR(b) {}
1089 ///\brief \ref named-templ-param "Named parameter" for setting
1092 ///\ref named-templ-param "Named parameter" function for setting
1093 ///the map that indicates which nodes are reached.
1095 BfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
1097 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
1098 return BfsWizard<SetReachedMapBase<T> >(*this);
1102 struct SetDistMapBase : public Base {
1104 static DistMap *createDistMap(const Digraph &) { return 0; };
1105 SetDistMapBase(const TR &b) : TR(b) {}
1108 ///\brief \ref named-templ-param "Named parameter" for setting
1109 ///the distance map.
1111 ///\ref named-templ-param "Named parameter" function for setting
1112 ///the map that stores the distances of the nodes calculated
1113 ///by the algorithm.
1115 BfsWizard<SetDistMapBase<T> > distMap(const T &t)
1117 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1118 return BfsWizard<SetDistMapBase<T> >(*this);
1122 struct SetProcessedMapBase : public Base {
1123 typedef T ProcessedMap;
1124 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1125 SetProcessedMapBase(const TR &b) : TR(b) {}
1128 ///\brief \ref named-func-param "Named parameter" for setting
1129 ///the processed map.
1131 ///\ref named-templ-param "Named parameter" function for setting
1132 ///the map that indicates which nodes are processed.
1134 BfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1136 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
1137 return BfsWizard<SetProcessedMapBase<T> >(*this);
1141 struct SetPathBase : public Base {
1143 SetPathBase(const TR &b) : TR(b) {}
1145 ///\brief \ref named-func-param "Named parameter"
1146 ///for getting the shortest path to the target node.
1148 ///\ref named-func-param "Named parameter"
1149 ///for getting the shortest path to the target node.
1151 BfsWizard<SetPathBase<T> > path(const T &t)
1153 Base::_path=reinterpret_cast<void*>(const_cast<T*>(&t));
1154 return BfsWizard<SetPathBase<T> >(*this);
1157 ///\brief \ref named-func-param "Named parameter"
1158 ///for getting the distance of the target node.
1160 ///\ref named-func-param "Named parameter"
1161 ///for getting the distance of the target node.
1162 BfsWizard dist(const int &d)
1164 Base::_di=const_cast<int*>(&d);
1170 ///Function-type interface for BFS algorithm.
1173 ///Function-type interface for BFS algorithm.
1175 ///This function also has several \ref named-func-param "named parameters",
1176 ///they are declared as the members of class \ref BfsWizard.
1177 ///The following examples show how to use these parameters.
1179 /// // Compute shortest path from node s to each node
1180 /// bfs(g).predMap(preds).distMap(dists).run(s);
1182 /// // Compute shortest path from s to t
1183 /// bool reached = bfs(g).path(p).dist(d).run(s,t);
1185 ///\warning Don't forget to put the \ref BfsWizard::run(Node) "run()"
1186 ///to the end of the parameter list.
1190 BfsWizard<BfsWizardBase<GR> >
1191 bfs(const GR &digraph)
1193 return BfsWizard<BfsWizardBase<GR> >(digraph);
1197 /// \brief Visitor class for BFS.
1199 /// This class defines the interface of the BfsVisit events, and
1200 /// it could be the base of a real visitor class.
1201 template <typename GR>
1204 typedef typename Digraph::Arc Arc;
1205 typedef typename Digraph::Node Node;
1206 /// \brief Called for the source node(s) of the BFS.
1208 /// This function is called for the source node(s) of the BFS.
1209 void start(const Node& node) {}
1210 /// \brief Called when a node is reached first time.
1212 /// This function is called when a node is reached first time.
1213 void reach(const Node& node) {}
1214 /// \brief Called when a node is processed.
1216 /// This function is called when a node is processed.
1217 void process(const Node& node) {}
1218 /// \brief Called when an arc reaches a new node.
1220 /// This function is called when the BFS finds an arc whose target node
1221 /// is not reached yet.
1222 void discover(const Arc& arc) {}
1223 /// \brief Called when an arc is examined but its target node is
1224 /// already discovered.
1226 /// This function is called when an arc is examined but its target node is
1227 /// already discovered.
1228 void examine(const Arc& arc) {}
1231 template <typename GR>
1234 typedef typename Digraph::Arc Arc;
1235 typedef typename Digraph::Node Node;
1236 void start(const Node&) {}
1237 void reach(const Node&) {}
1238 void process(const Node&) {}
1239 void discover(const Arc&) {}
1240 void examine(const Arc&) {}
1242 template <typename _Visitor>
1243 struct Constraints {
1244 void constraints() {
1247 visitor.start(node);
1248 visitor.reach(node);
1249 visitor.process(node);
1250 visitor.discover(arc);
1251 visitor.examine(arc);
1259 /// \brief Default traits class of BfsVisit class.
1261 /// Default traits class of BfsVisit class.
1262 /// \tparam GR The type of the digraph the algorithm runs on.
1264 struct BfsVisitDefaultTraits {
1266 /// \brief The type of the digraph the algorithm runs on.
1269 /// \brief The type of the map that indicates which nodes are reached.
1271 /// The type of the map that indicates which nodes are reached.
1272 /// It must conform to
1273 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1274 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1276 /// \brief Instantiates a ReachedMap.
1278 /// This function instantiates a ReachedMap.
1279 /// \param digraph is the digraph, to which
1280 /// we would like to define the ReachedMap.
1281 static ReachedMap *createReachedMap(const Digraph &digraph) {
1282 return new ReachedMap(digraph);
1289 /// \brief BFS algorithm class with visitor interface.
1291 /// This class provides an efficient implementation of the BFS algorithm
1292 /// with visitor interface.
1294 /// The BfsVisit class provides an alternative interface to the Bfs
1295 /// class. It works with callback mechanism, the BfsVisit object calls
1296 /// the member functions of the \c Visitor class on every BFS event.
1298 /// This interface of the BFS algorithm should be used in special cases
1299 /// when extra actions have to be performed in connection with certain
1300 /// events of the BFS algorithm. Otherwise consider to use Bfs or bfs()
1303 /// \tparam GR The type of the digraph the algorithm runs on.
1304 /// The default type is \ref ListDigraph.
1305 /// The value of GR is not used directly by \ref BfsVisit,
1306 /// it is only passed to \ref BfsVisitDefaultTraits.
1307 /// \tparam VS The Visitor type that is used by the algorithm.
1308 /// \ref BfsVisitor "BfsVisitor<GR>" is an empty visitor, which
1309 /// does not observe the BFS events. If you want to observe the BFS
1310 /// events, you should implement your own visitor class.
1311 /// \tparam TR The traits class that defines various types used by the
1312 /// algorithm. By default, it is \ref BfsVisitDefaultTraits
1313 /// "BfsVisitDefaultTraits<GR>".
1314 /// In most cases, this parameter should not be set directly,
1315 /// consider to use the named template parameters instead.
1317 template <typename GR, typename VS, typename TR>
1319 template <typename GR = ListDigraph,
1320 typename VS = BfsVisitor<GR>,
1321 typename TR = BfsVisitDefaultTraits<GR> >
1326 ///The traits class.
1329 ///The type of the digraph the algorithm runs on.
1330 typedef typename Traits::Digraph Digraph;
1332 ///The visitor type used by the algorithm.
1335 ///The type of the map that indicates which nodes are reached.
1336 typedef typename Traits::ReachedMap ReachedMap;
1340 typedef typename Digraph::Node Node;
1341 typedef typename Digraph::NodeIt NodeIt;
1342 typedef typename Digraph::Arc Arc;
1343 typedef typename Digraph::OutArcIt OutArcIt;
1345 //Pointer to the underlying digraph.
1346 const Digraph *_digraph;
1347 //Pointer to the visitor object.
1349 //Pointer to the map of reached status of the nodes.
1350 ReachedMap *_reached;
1351 //Indicates if _reached is locally allocated (true) or not.
1354 std::vector<typename Digraph::Node> _list;
1355 int _list_front, _list_back;
1357 //Creates the maps if necessary.
1358 void create_maps() {
1360 local_reached = true;
1361 _reached = Traits::createReachedMap(*_digraph);
1371 typedef BfsVisit Create;
1373 /// \name Named Template Parameters
1377 struct SetReachedMapTraits : public Traits {
1378 typedef T ReachedMap;
1379 static ReachedMap *createReachedMap(const Digraph &digraph) {
1380 LEMON_ASSERT(false, "ReachedMap is not initialized");
1381 return 0; // ignore warnings
1384 /// \brief \ref named-templ-param "Named parameter" for setting
1385 /// ReachedMap type.
1387 /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
1389 struct SetReachedMap : public BfsVisit< Digraph, Visitor,
1390 SetReachedMapTraits<T> > {
1391 typedef BfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
1397 /// \brief Constructor.
1401 /// \param digraph The digraph the algorithm runs on.
1402 /// \param visitor The visitor object of the algorithm.
1403 BfsVisit(const Digraph& digraph, Visitor& visitor)
1404 : _digraph(&digraph), _visitor(&visitor),
1405 _reached(0), local_reached(false) {}
1407 /// \brief Destructor.
1409 if(local_reached) delete _reached;
1412 /// \brief Sets the map that indicates which nodes are reached.
1414 /// Sets the map that indicates which nodes are reached.
1415 /// If you don't use this function before calling \ref run(Node) "run()"
1416 /// or \ref init(), an instance will be allocated automatically.
1417 /// The destructor deallocates this automatically allocated map,
1419 /// \return <tt> (*this) </tt>
1420 BfsVisit &reachedMap(ReachedMap &m) {
1423 local_reached = false;
1431 /// \name Execution Control
1432 /// The simplest way to execute the BFS algorithm is to use one of the
1433 /// member functions called \ref run(Node) "run()".\n
1434 /// If you need better control on the execution, you have to call
1435 /// \ref init() first, then you can add several source nodes with
1436 /// \ref addSource(). Finally the actual path computation can be
1437 /// performed with one of the \ref start() functions.
1441 /// \brief Initializes the internal data structures.
1443 /// Initializes the internal data structures.
1446 _list.resize(countNodes(*_digraph));
1447 _list_front = _list_back = -1;
1448 for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
1449 _reached->set(u, false);
1453 /// \brief Adds a new source node.
1455 /// Adds a new source node to the set of nodes to be processed.
1456 void addSource(Node s) {
1457 if(!(*_reached)[s]) {
1458 _reached->set(s,true);
1461 _list[++_list_back] = s;
1465 /// \brief Processes the next node.
1467 /// Processes the next node.
1469 /// \return The processed node.
1471 /// \pre The queue must not be empty.
1472 Node processNextNode() {
1473 Node n = _list[++_list_front];
1474 _visitor->process(n);
1476 for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
1477 Node m = _digraph->target(e);
1478 if (!(*_reached)[m]) {
1479 _visitor->discover(e);
1481 _reached->set(m, true);
1482 _list[++_list_back] = m;
1484 _visitor->examine(e);
1490 /// \brief Processes the next node.
1492 /// Processes the next node and checks if the given target node
1493 /// is reached. If the target node is reachable from the processed
1494 /// node, then the \c reach parameter will be set to \c true.
1496 /// \param target The target node.
1497 /// \retval reach Indicates if the target node is reached.
1498 /// It should be initially \c false.
1500 /// \return The processed node.
1502 /// \pre The queue must not be empty.
1503 Node processNextNode(Node target, bool& reach) {
1504 Node n = _list[++_list_front];
1505 _visitor->process(n);
1507 for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
1508 Node m = _digraph->target(e);
1509 if (!(*_reached)[m]) {
1510 _visitor->discover(e);
1512 _reached->set(m, true);
1513 _list[++_list_back] = m;
1514 reach = reach || (target == m);
1516 _visitor->examine(e);
1522 /// \brief Processes the next node.
1524 /// Processes the next node and checks if at least one of reached
1525 /// nodes has \c true value in the \c nm node map. If one node
1526 /// with \c true value is reachable from the processed node, then the
1527 /// \c rnode parameter will be set to the first of such nodes.
1529 /// \param nm A \c bool (or convertible) node map that indicates the
1530 /// possible targets.
1531 /// \retval rnode The reached target node.
1532 /// It should be initially \c INVALID.
1534 /// \return The processed node.
1536 /// \pre The queue must not be empty.
1537 template <typename NM>
1538 Node processNextNode(const NM& nm, Node& rnode) {
1539 Node n = _list[++_list_front];
1540 _visitor->process(n);
1542 for (_digraph->firstOut(e, n); e != INVALID; _digraph->nextOut(e)) {
1543 Node m = _digraph->target(e);
1544 if (!(*_reached)[m]) {
1545 _visitor->discover(e);
1547 _reached->set(m, true);
1548 _list[++_list_back] = m;
1549 if (nm[m] && rnode == INVALID) rnode = m;
1551 _visitor->examine(e);
1557 /// \brief The next node to be processed.
1559 /// Returns the next node to be processed or \c INVALID if the queue
1561 Node nextNode() const {
1562 return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
1565 /// \brief Returns \c false if there are nodes
1566 /// to be processed.
1568 /// Returns \c false if there are nodes
1569 /// to be processed in the queue.
1570 bool emptyQueue() const { return _list_front == _list_back; }
1572 /// \brief Returns the number of the nodes to be processed.
1574 /// Returns the number of the nodes to be processed in the queue.
1575 int queueSize() const { return _list_back - _list_front; }
1577 /// \brief Executes the algorithm.
1579 /// Executes the algorithm.
1581 /// This method runs the %BFS algorithm from the root node(s)
1582 /// in order to compute the shortest path to each node.
1584 /// The algorithm computes
1585 /// - the shortest path tree (forest),
1586 /// - the distance of each node from the root(s).
1588 /// \pre init() must be called and at least one root node should be added
1589 /// with addSource() before using this function.
1591 /// \note <tt>b.start()</tt> is just a shortcut of the following code.
1593 /// while ( !b.emptyQueue() ) {
1594 /// b.processNextNode();
1598 while ( !emptyQueue() ) processNextNode();
1601 /// \brief Executes the algorithm until the given target node is reached.
1603 /// Executes the algorithm until the given target node is reached.
1605 /// This method runs the %BFS algorithm from the root node(s)
1606 /// in order to compute the shortest path to \c t.
1608 /// The algorithm computes
1609 /// - the shortest path to \c t,
1610 /// - the distance of \c t from the root(s).
1612 /// \pre init() must be called and at least one root node should be
1613 /// added with addSource() before using this function.
1615 /// \note <tt>b.start(t)</tt> is just a shortcut of the following code.
1617 /// bool reach = false;
1618 /// while ( !b.emptyQueue() && !reach ) {
1619 /// b.processNextNode(t, reach);
1622 void start(Node t) {
1624 while ( !emptyQueue() && !reach ) processNextNode(t, reach);
1627 /// \brief Executes the algorithm until a condition is met.
1629 /// Executes the algorithm until a condition is met.
1631 /// This method runs the %BFS algorithm from the root node(s) in
1632 /// order to compute the shortest path to a node \c v with
1633 /// <tt>nm[v]</tt> true, if such a node can be found.
1635 /// \param nm must be a bool (or convertible) node map. The
1636 /// algorithm will stop when it reaches a node \c v with
1637 /// <tt>nm[v]</tt> true.
1639 /// \return The reached node \c v with <tt>nm[v]</tt> true or
1640 /// \c INVALID if no such node was found.
1642 /// \pre init() must be called and at least one root node should be
1643 /// added with addSource() before using this function.
1645 /// \note <tt>b.start(nm)</tt> is just a shortcut of the following code.
1647 /// Node rnode = INVALID;
1648 /// while ( !b.emptyQueue() && rnode == INVALID ) {
1649 /// b.processNextNode(nm, rnode);
1653 template <typename NM>
1654 Node start(const NM &nm) {
1655 Node rnode = INVALID;
1656 while ( !emptyQueue() && rnode == INVALID ) {
1657 processNextNode(nm, rnode);
1662 /// \brief Runs the algorithm from the given source node.
1664 /// This method runs the %BFS algorithm from node \c s
1665 /// in order to compute the shortest path to each node.
1667 /// The algorithm computes
1668 /// - the shortest path tree,
1669 /// - the distance of each node from the root.
1671 /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
1683 /// \brief Finds the shortest path between \c s and \c t.
1685 /// This method runs the %BFS algorithm from node \c s
1686 /// in order to compute the shortest path to node \c t
1687 /// (it stops searching when \c t is processed).
1689 /// \return \c true if \c t is reachable form \c s.
1691 /// \note Apart from the return value, <tt>b.run(s,t)</tt> is just a
1692 /// shortcut of the following code.
1698 bool run(Node s,Node t) {
1705 /// \brief Runs the algorithm to visit all nodes in the digraph.
1707 /// This method runs the %BFS algorithm in order to visit all nodes
1710 /// \note <tt>b.run(s)</tt> is just a shortcut of the following code.
1713 /// for (NodeIt n(gr); n != INVALID; ++n) {
1714 /// if (!b.reached(n)) {
1722 for (NodeIt it(*_digraph); it != INVALID; ++it) {
1732 /// \name Query Functions
1733 /// The results of the BFS algorithm can be obtained using these
1735 /// Either \ref run(Node) "run()" or \ref start() should be called
1736 /// before using them.
1740 /// \brief Checks if the given node is reached from the root(s).
1742 /// Returns \c true if \c v is reached from the root(s).
1744 /// \pre Either \ref run(Node) "run()" or \ref init()
1745 /// must be called before using this function.
1746 bool reached(Node v) const { return (*_reached)[v]; }
1752 } //END OF NAMESPACE LEMON