Unionfind changes induced some bugs here. Also some augmentations made.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
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 Dfs algorithm.
26 #include <lemon/list_graph.h>
27 #include <lemon/graph_utils.h>
28 #include <lemon/bits/invalid.h>
29 #include <lemon/error.h>
30 #include <lemon/maps.h>
32 #include <lemon/concept_check.h>
37 ///Default traits class of Dfs class.
39 ///Default traits class of Dfs class.
40 ///\param GR Graph type.
42 struct DfsDefaultTraits
44 ///The graph type the algorithm runs on.
46 ///\brief The type of the map that stores the last
47 ///edges of the %DFS paths.
49 ///The type of the map that stores the last
50 ///edges of the %DFS paths.
51 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
53 typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
54 ///Instantiates a PredMap.
56 ///This function instantiates a \ref PredMap.
57 ///\param G is the graph, to which we would like to define the PredMap.
58 ///\todo The graph alone may be insufficient to initialize
59 static PredMap *createPredMap(const GR &G)
61 return new PredMap(G);
64 ///The type of the map that indicates which nodes are processed.
66 ///The type of the map that indicates which nodes are processed.
67 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
68 ///\todo named parameter to set this type, function to read and write.
69 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
70 ///Instantiates a ProcessedMap.
72 ///This function instantiates a \ref ProcessedMap.
73 ///\param g is the graph, to which
74 ///we would like to define the \ref ProcessedMap
76 static ProcessedMap *createProcessedMap(const GR &g)
78 static ProcessedMap *createProcessedMap(const GR &)
81 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 concept::WriteMap "WriteMap" concept.
87 ///\todo named parameter to set this type, function to read and write.
88 typedef typename Graph::template NodeMap<bool> ReachedMap;
89 ///Instantiates a ReachedMap.
91 ///This function instantiates a \ref ReachedMap.
92 ///\param G is the graph, to which
93 ///we would like to define the \ref ReachedMap.
94 static ReachedMap *createReachedMap(const GR &G)
96 return new ReachedMap(G);
98 ///The type of the map that stores the dists of the nodes.
100 ///The type of the map that stores the dists of the nodes.
101 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
103 typedef typename Graph::template NodeMap<int> DistMap;
104 ///Instantiates a DistMap.
106 ///This function instantiates a \ref DistMap.
107 ///\param G is the graph, to which we would like to define the \ref DistMap
108 static DistMap *createDistMap(const GR &G)
110 return new DistMap(G);
114 ///%DFS algorithm class.
117 ///This class provides an efficient implementation of the %DFS algorithm.
119 ///\param GR The graph type the algorithm runs on. The default value is
120 ///\ref ListGraph. The value of GR is not used directly by Dfs, it
121 ///is only passed to \ref DfsDefaultTraits.
122 ///\param TR Traits class to set various data types used by the algorithm.
123 ///The default traits class is
124 ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
125 ///See \ref DfsDefaultTraits for the documentation of
126 ///a Dfs traits class.
128 ///\author Jacint Szabo and Alpar Juttner
130 template <typename GR,
133 template <typename GR=ListGraph,
134 typename TR=DfsDefaultTraits<GR> >
139 * \brief \ref Exception for uninitialized parameters.
141 * This error represents problems in the initialization
142 * of the parameters of the algorithms.
144 class UninitializedParameter : public lemon::UninitializedParameter {
146 virtual const char* exceptionName() const {
147 return "lemon::Dfs::UninitializedParameter";
152 ///The type of the underlying graph.
153 typedef typename TR::Graph Graph;
155 typedef typename Graph::Node Node;
157 typedef typename Graph::NodeIt NodeIt;
159 typedef typename Graph::Edge Edge;
161 typedef typename Graph::OutEdgeIt OutEdgeIt;
163 ///\brief The type of the map that stores the last
164 ///edges of the %DFS paths.
165 typedef typename TR::PredMap PredMap;
166 ///The type of the map indicating which nodes are reached.
167 typedef typename TR::ReachedMap ReachedMap;
168 ///The type of the map indicating which nodes are processed.
169 typedef typename TR::ProcessedMap ProcessedMap;
170 ///The type of the map that stores the dists of the nodes.
171 typedef typename TR::DistMap DistMap;
173 /// Pointer to the underlying graph.
175 ///Pointer to the map of predecessors edges.
177 ///Indicates if \ref _pred is locally allocated (\c true) or not.
179 ///Pointer to the map of distances.
181 ///Indicates if \ref _dist is locally allocated (\c true) or not.
183 ///Pointer to the map of reached status of the nodes.
184 ReachedMap *_reached;
185 ///Indicates if \ref _reached is locally allocated (\c true) or not.
187 ///Pointer to the map of processed status of the nodes.
188 ProcessedMap *_processed;
189 ///Indicates if \ref _processed is locally allocated (\c true) or not.
190 bool local_processed;
192 std::vector<typename Graph::OutEdgeIt> _stack;
195 ///Creates the maps if necessary.
197 ///\todo Better memory allocation (instead of new).
202 _pred = Traits::createPredMap(*G);
206 _dist = Traits::createDistMap(*G);
209 local_reached = true;
210 _reached = Traits::createReachedMap(*G);
213 local_processed = true;
214 _processed = Traits::createProcessedMap(*G);
226 ///\name Named template parameters
231 struct DefPredMapTraits : public Traits {
233 static PredMap *createPredMap(const Graph &G)
235 throw UninitializedParameter();
238 ///\ref named-templ-param "Named parameter" for setting PredMap type
240 ///\ref named-templ-param "Named parameter" for setting PredMap type
243 struct DefPredMap : public Dfs<Graph, DefPredMapTraits<T> > {
244 typedef Dfs<Graph, DefPredMapTraits<T> > Create;
249 struct DefDistMapTraits : public Traits {
251 static DistMap *createDistMap(const Graph &G)
253 throw UninitializedParameter();
256 ///\ref named-templ-param "Named parameter" for setting DistMap type
258 ///\ref named-templ-param "Named parameter" for setting DistMap type
262 typedef Dfs<Graph, DefDistMapTraits<T> > Create;
266 struct DefReachedMapTraits : public Traits {
267 typedef T ReachedMap;
268 static ReachedMap *createReachedMap(const Graph &G)
270 throw UninitializedParameter();
273 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
275 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
278 struct DefReachedMap : public Dfs< Graph, DefReachedMapTraits<T> > {
279 typedef Dfs< Graph, DefReachedMapTraits<T> > Create;
283 struct DefProcessedMapTraits : public Traits {
284 typedef T ProcessedMap;
285 static ProcessedMap *createProcessedMap(const Graph &G)
287 throw UninitializedParameter();
290 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
292 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
295 struct DefProcessedMap : public Dfs< Graph, DefProcessedMapTraits<T> > {
296 typedef Dfs< Graph, DefProcessedMapTraits<T> > Create;
299 struct DefGraphProcessedMapTraits : public Traits {
300 typedef typename Graph::template NodeMap<bool> ProcessedMap;
301 static ProcessedMap *createProcessedMap(const Graph &G)
303 return new ProcessedMap(G);
306 ///\brief \ref named-templ-param "Named parameter"
307 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
309 ///\ref named-templ-param "Named parameter"
310 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
311 ///If you don't set it explicitely, it will be automatically allocated.
313 class DefProcessedMapToBeDefaultMap :
314 public Dfs< Graph, DefGraphProcessedMapTraits> {
315 typedef Dfs< Graph, DefGraphProcessedMapTraits> Create;
324 ///\param _G the graph the algorithm will run on.
326 Dfs(const Graph& _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 edges.
345 ///Sets the map storing the predecessor edges.
346 ///If you don't use this function before calling \ref run(),
347 ///it will allocate one. The destuctor deallocates this
348 ///automatically allocated map, of course.
349 ///\return <tt> (*this) </tt>
350 Dfs &predMap(PredMap &m)
360 ///Sets the map storing the distances calculated by the algorithm.
362 ///Sets the map storing the distances calculated by the algorithm.
363 ///If you don't use this function before calling \ref run(),
364 ///it will allocate one. The destuctor deallocates this
365 ///automatically allocated map, of course.
366 ///\return <tt> (*this) </tt>
367 Dfs &distMap(DistMap &m)
377 ///Sets the map indicating if a node is reached.
379 ///Sets the map indicating if a node is reached.
380 ///If you don't use this function before calling \ref run(),
381 ///it will allocate one. The destuctor deallocates this
382 ///automatically allocated map, of course.
383 ///\return <tt> (*this) </tt>
384 Dfs &reachedMap(ReachedMap &m)
394 ///Sets the map indicating if a node is processed.
396 ///Sets the map indicating if a node is processed.
397 ///If you don't use this function before calling \ref run(),
398 ///it will allocate one. The destuctor deallocates this
399 ///automatically allocated map, of course.
400 ///\return <tt> (*this) </tt>
401 Dfs &processedMap(ProcessedMap &m)
403 if(local_processed) {
405 local_processed=false;
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 a source node
418 ///with \ref addSource().
419 ///Finally \ref start() will perform the actual path
424 ///Initializes the internal data structures.
426 ///Initializes the internal data structures.
431 _stack.resize(countNodes(*G));
433 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
434 _pred->set(u,INVALID);
435 // _predNode->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 ///\warning dists are wrong (or at least strange)
446 ///in case of multiple sources.
447 void addSource(Node s)
451 _reached->set(s,true);
452 _pred->set(s,INVALID);
455 _stack[++_stack_head]=e;
456 _dist->set(s,_stack_head);
459 _processed->set(s,true);
465 ///Processes the next edge.
467 ///Processes the next edge.
469 ///\return The processed edge.
471 ///\pre The stack must not be empty!
472 Edge processNextEdge()
475 Edge e=_stack[_stack_head];
476 if(!(*_reached)[m=G->target(e)]) {
478 _reached->set(m,true);
480 _stack[_stack_head] = OutEdgeIt(*G, m);
481 _dist->set(m,_stack_head);
485 ++_stack[_stack_head];
487 while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
488 _processed->set(m,true);
491 m=G->source(_stack[_stack_head]);
492 ++_stack[_stack_head];
497 ///Next edge to be processed.
499 ///Next edge to be processed.
501 ///\return The next edge to be processed or INVALID if the stack is
505 return _stack_head>=0?_stack[_stack_head]:INVALID;
508 ///\brief Returns \c false if there are nodes
509 ///to be processed in the queue
511 ///Returns \c false if there are nodes
512 ///to be processed in the queue
513 bool emptyQueue() { return _stack_head<0; }
514 ///Returns the number of the nodes to be processed.
516 ///Returns the number of the nodes to be processed in the queue.
517 int queueSize() { return _stack_head+1; }
519 ///Executes the algorithm.
521 ///Executes the algorithm.
523 ///\pre init() must be called and at least one node should be added
524 ///with addSource() before using this function.
526 ///This method runs the %DFS algorithm from the root node(s)
529 ///%DFS path to each node. The algorithm computes
531 ///- The distance of each node from the root(s) in the %DFS tree.
535 while ( !emptyQueue() ) processNextEdge();
538 ///Executes the algorithm until \c dest is reached.
540 ///Executes the algorithm until \c dest is reached.
542 ///\pre init() must be called and at least one node should be added
543 ///with addSource() before using this function.
545 ///This method runs the %DFS algorithm from the root node(s)
548 ///%DFS path to \c dest. The algorithm computes
549 ///- The %DFS path to \c dest.
550 ///- The distance of \c dest from the root(s) in the %DFS tree.
552 void start(Node dest)
554 while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
558 ///Executes the algorithm until a condition is met.
560 ///Executes the algorithm until a condition is met.
562 ///\pre init() must be called and at least one node should be added
563 ///with addSource() before using this function.
565 ///\param em must be a bool (or convertible) edge map. The algorithm
566 ///will stop when it reaches an edge \c e with \code em[e]==true \endcode.
568 ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c em is an edge map,
571 void start(const EM &em)
573 while ( !emptyQueue() && !em[_stack[_stack_head]] ) processNextEdge();
576 ///Runs %DFS algorithm to visit all nodes in the graph.
578 ///This method runs the %DFS algorithm in order to
580 ///%DFS path to each node. The algorithm computes
582 ///- The distance of each node from the root in the %DFS tree.
584 ///\note d.run() is just a shortcut of the following code.
587 /// for (NodeIt it(graph); it != INVALID; ++it) {
588 /// if (!d.reached(it)) {
596 for (NodeIt it(*G); it != INVALID; ++it) {
604 ///Runs %DFS algorithm from node \c s.
606 ///This method runs the %DFS algorithm from a root node \c s
609 ///%DFS path to each node. The algorithm computes
611 ///- The distance of each node from the root in the %DFS tree.
613 ///\note d.run(s) is just a shortcut of the following code.
625 ///Finds the %DFS path between \c s and \c t.
627 ///Finds the %DFS path between \c s and \c t.
629 ///\return The length of the %DFS s---t path if there exists one,
631 ///\note Apart from the return value, d.run(s,t) is
632 ///just a shortcut of the following code.
638 int run(Node s,Node t) {
642 return reached(t)?_stack_head+1:0;
647 ///\name Query Functions
648 ///The result of the %DFS algorithm can be obtained using these
650 ///Before the use of these functions,
651 ///either run() or start() must be called.
655 ///Copies the path to \c t on the DFS tree into \c p
657 ///This function copies the path to \c t on the DFS tree into \c p.
658 ///If \c t is a source itself or unreachable, then it does not
661 ///\return Returns \c true if a path to \c t was actually copied to \c p,
662 ///\c false otherwise.
665 bool getPath(P &p,Node t)
669 typename P::Builder b(p);
670 for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
671 b.pushFront(predEdge(t));
678 ///The distance of a node from the root(s).
680 ///Returns the distance of a node from the root(s).
681 ///\pre \ref run() must be called before using this function.
682 ///\warning If node \c v is unreachable from the root(s) then the return
683 ///value of this funcion is undefined.
684 int dist(Node v) const { return (*_dist)[v]; }
686 ///Returns the 'previous edge' of the %DFS tree.
688 ///For a node \c v it returns the 'previous edge'
690 ///i.e. it returns the last edge of a %DFS path from the root(s) to \c
691 ///v. It is \ref INVALID
692 ///if \c v is unreachable from the root(s) or \c v is a root. The
693 ///%DFS tree used here is equal to the %DFS tree used in
695 ///\pre Either \ref run() or \ref start() must be called before using
697 Edge predEdge(Node v) const { return (*_pred)[v];}
699 ///Returns the 'previous node' of the %DFS tree.
701 ///For a node \c v it returns the 'previous node'
703 ///i.e. it returns the last but one node from a %DFS path from the
705 ///It is INVALID if \c v is unreachable from the root(s) or
706 ///if \c v itself a root.
707 ///The %DFS tree used here is equal to the %DFS
708 ///tree used in \ref predEdge().
709 ///\pre Either \ref run() or \ref start() must be called before
710 ///using this function.
711 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
712 G->source((*_pred)[v]); }
714 ///Returns a reference to the NodeMap of distances.
716 ///Returns a reference to the NodeMap of distances.
717 ///\pre Either \ref run() or \ref init() must
718 ///be called before using this function.
719 const DistMap &distMap() const { return *_dist;}
721 ///Returns a reference to the %DFS edge-tree map.
723 ///Returns a reference to the NodeMap of the edges of the
725 ///\pre Either \ref run() or \ref init()
726 ///must be called before using this function.
727 const PredMap &predMap() const { return *_pred;}
729 ///Checks if a node is reachable from the root.
731 ///Returns \c true if \c v is reachable from the root(s).
732 ///\warning The source nodes are inditated as unreachable.
733 ///\pre Either \ref run() or \ref start()
734 ///must be called before using this function.
736 bool reached(Node v) { return (*_reached)[v]; }
741 ///Default traits class of Dfs function.
743 ///Default traits class of Dfs function.
744 ///\param GR Graph type.
746 struct DfsWizardDefaultTraits
748 ///The graph type the algorithm runs on.
750 ///\brief The type of the map that stores the last
751 ///edges of the %DFS paths.
753 ///The type of the map that stores the last
754 ///edges of the %DFS paths.
755 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
757 typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
758 ///Instantiates a PredMap.
760 ///This function instantiates a \ref PredMap.
761 ///\param g is the graph, to which we would like to define the PredMap.
762 ///\todo The graph alone may be insufficient to initialize
764 static PredMap *createPredMap(const GR &g)
766 static PredMap *createPredMap(const GR &)
769 return new PredMap();
772 ///The type of the map that indicates which nodes are processed.
774 ///The type of the map that indicates which nodes are processed.
775 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
776 ///\todo named parameter to set this type, function to read and write.
777 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
778 ///Instantiates a ProcessedMap.
780 ///This function instantiates a \ref ProcessedMap.
781 ///\param g is the graph, to which
782 ///we would like to define the \ref ProcessedMap
784 static ProcessedMap *createProcessedMap(const GR &g)
786 static ProcessedMap *createProcessedMap(const GR &)
789 return new ProcessedMap();
791 ///The type of the map that indicates which nodes are reached.
793 ///The type of the map that indicates which nodes are reached.
794 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
795 ///\todo named parameter to set this type, function to read and write.
796 typedef typename Graph::template NodeMap<bool> ReachedMap;
797 ///Instantiates a ReachedMap.
799 ///This function instantiates a \ref ReachedMap.
800 ///\param G is the graph, to which
801 ///we would like to define the \ref ReachedMap.
802 static ReachedMap *createReachedMap(const GR &G)
804 return new ReachedMap(G);
806 ///The type of the map that stores the dists of the nodes.
808 ///The type of the map that stores the dists of the nodes.
809 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
811 typedef NullMap<typename Graph::Node,int> DistMap;
812 ///Instantiates a DistMap.
814 ///This function instantiates a \ref DistMap.
815 ///\param g is the graph, to which we would like to define the \ref DistMap
817 static DistMap *createDistMap(const GR &g)
819 static DistMap *createDistMap(const GR &)
822 return new DistMap();
826 /// Default traits used by \ref DfsWizard
828 /// To make it easier to use Dfs algorithm
829 ///we have created a wizard class.
830 /// This \ref DfsWizard class needs default traits,
831 ///as well as the \ref Dfs class.
832 /// The \ref DfsWizardBase is a class to be the default traits of the
833 /// \ref DfsWizard class.
835 class DfsWizardBase : public DfsWizardDefaultTraits<GR>
838 typedef DfsWizardDefaultTraits<GR> Base;
840 /// Type of the nodes in the graph.
841 typedef typename Base::Graph::Node Node;
843 /// Pointer to the underlying graph.
845 ///Pointer to the map of reached nodes.
847 ///Pointer to the map of processed nodes.
849 ///Pointer to the map of predecessors edges.
851 ///Pointer to the map of distances.
853 ///Pointer to the source node.
859 /// This constructor does not require parameters, therefore it initiates
860 /// all of the attributes to default values (0, INVALID).
861 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
862 _dist(0), _source(INVALID) {}
866 /// This constructor requires some parameters,
867 /// listed in the parameters list.
868 /// Others are initiated to 0.
869 /// \param g is the initial value of \ref _g
870 /// \param s is the initial value of \ref _source
871 DfsWizardBase(const GR &g, Node s=INVALID) :
872 _g((void *)&g), _reached(0), _processed(0), _pred(0),
873 _dist(0), _source(s) {}
877 /// A class to make the usage of the Dfs algorithm easier
879 /// This class is created to make it easier to use the Dfs algorithm.
880 /// It uses the functions and features of the plain \ref Dfs,
881 /// but it is much simpler to use it.
883 /// Simplicity means that the way to change the types defined
884 /// in the traits class is based on functions that returns the new class
885 /// and not on templatable built-in classes.
886 /// When using the plain \ref Dfs
887 /// the new class with the modified type comes from
888 /// the original class by using the ::
889 /// operator. In the case of \ref DfsWizard only
890 /// a function have to be called and it will
891 /// return the needed class.
893 /// It does not have own \ref run method. When its \ref run method is called
894 /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run
897 class DfsWizard : public TR
901 ///The type of the underlying graph.
902 typedef typename TR::Graph Graph;
904 typedef typename Graph::Node Node;
906 typedef typename Graph::NodeIt NodeIt;
908 typedef typename Graph::Edge Edge;
910 typedef typename Graph::OutEdgeIt OutEdgeIt;
912 ///\brief The type of the map that stores
914 typedef typename TR::ReachedMap ReachedMap;
915 ///\brief The type of the map that stores
916 ///the processed nodes
917 typedef typename TR::ProcessedMap ProcessedMap;
918 ///\brief The type of the map that stores the last
919 ///edges of the %DFS paths.
920 typedef typename TR::PredMap PredMap;
921 ///The type of the map that stores the distances of the nodes.
922 typedef typename TR::DistMap DistMap;
926 DfsWizard() : TR() {}
928 /// Constructor that requires parameters.
930 /// Constructor that requires parameters.
931 /// These parameters will be the default values for the traits class.
932 DfsWizard(const Graph &g, Node s=INVALID) :
936 DfsWizard(const TR &b) : TR(b) {}
940 ///Runs Dfs algorithm from a given node.
942 ///Runs Dfs algorithm from a given node.
943 ///The node can be given by the \ref source function.
946 if(Base::_source==INVALID) throw UninitializedParameter();
947 Dfs<Graph,TR> alg(*(Graph*)Base::_g);
948 if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached);
949 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
950 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
951 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
952 alg.run(Base::_source);
955 ///Runs Dfs algorithm from the given node.
957 ///Runs Dfs algorithm from the given node.
958 ///\param s is the given source.
966 struct DefPredMapBase : public Base {
968 static PredMap *createPredMap(const Graph &) { return 0; };
969 DefPredMapBase(const TR &b) : TR(b) {}
972 ///\brief \ref named-templ-param "Named parameter"
973 ///function for setting PredMap type
975 /// \ref named-templ-param "Named parameter"
976 ///function for setting PredMap type
979 DfsWizard<DefPredMapBase<T> > predMap(const T &t)
981 Base::_pred=(void *)&t;
982 return DfsWizard<DefPredMapBase<T> >(*this);
987 struct DefReachedMapBase : public Base {
988 typedef T ReachedMap;
989 static ReachedMap *createReachedMap(const Graph &) { return 0; };
990 DefReachedMapBase(const TR &b) : TR(b) {}
993 ///\brief \ref named-templ-param "Named parameter"
994 ///function for setting ReachedMap
996 /// \ref named-templ-param "Named parameter"
997 ///function for setting ReachedMap
1000 DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1002 Base::_pred=(void *)&t;
1003 return DfsWizard<DefReachedMapBase<T> >(*this);
1008 struct DefProcessedMapBase : public Base {
1009 typedef T ProcessedMap;
1010 static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
1011 DefProcessedMapBase(const TR &b) : TR(b) {}
1014 ///\brief \ref named-templ-param "Named parameter"
1015 ///function for setting ProcessedMap
1017 /// \ref named-templ-param "Named parameter"
1018 ///function for setting ProcessedMap
1021 DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1023 Base::_pred=(void *)&t;
1024 return DfsWizard<DefProcessedMapBase<T> >(*this);
1028 struct DefDistMapBase : public Base {
1030 static DistMap *createDistMap(const Graph &) { return 0; };
1031 DefDistMapBase(const TR &b) : TR(b) {}
1034 ///\brief \ref named-templ-param "Named parameter"
1035 ///function for setting DistMap type
1037 /// \ref named-templ-param "Named parameter"
1038 ///function for setting DistMap type
1041 DfsWizard<DefDistMapBase<T> > distMap(const T &t)
1043 Base::_dist=(void *)&t;
1044 return DfsWizard<DefDistMapBase<T> >(*this);
1047 /// Sets the source node, from which the Dfs algorithm runs.
1049 /// Sets the source node, from which the Dfs algorithm runs.
1050 /// \param s is the source node.
1051 DfsWizard<TR> &source(Node s)
1059 ///Function type interface for Dfs algorithm.
1061 /// \ingroup flowalgs
1062 ///Function type interface for Dfs algorithm.
1064 ///This function also has several
1065 ///\ref named-templ-func-param "named parameters",
1066 ///they are declared as the members of class \ref DfsWizard.
1068 ///example shows how to use these parameters.
1070 /// dfs(g,source).predMap(preds).run();
1072 ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
1073 ///to the end of the parameter list.
1077 DfsWizard<DfsWizardBase<GR> >
1078 dfs(const GR &g,typename GR::Node s=INVALID)
1080 return DfsWizard<DfsWizardBase<GR> >(g,s);
1084 /// \brief Visitor class for dfs.
1086 /// It gives a simple interface for a functional interface for dfs
1087 /// traversal. The traversal on a linear data structure.
1088 template <typename _Graph>
1090 typedef _Graph Graph;
1091 typedef typename Graph::Edge Edge;
1092 typedef typename Graph::Node Node;
1093 /// \brief Called when the edge reach a node.
1095 /// It is called when the dfs find an edge which target is not
1097 void discover(const Edge& edge) {}
1098 /// \brief Called when the node reached first time.
1100 /// It is Called when the node reached first time.
1101 void reach(const Node& node) {}
1102 /// \brief Called when we step back on an edge.
1104 /// It is called when the dfs should step back on the edge.
1105 void backtrack(const Edge& edge) {}
1106 /// \brief Called when we step back from the node.
1108 /// It is called when we step back from the node.
1109 void leave(const Node& node) {}
1110 /// \brief Called when the edge examined but target of the edge
1111 /// already discovered.
1113 /// It called when the edge examined but the target of the edge
1114 /// already discovered.
1115 void examine(const Edge& edge) {}
1116 /// \brief Called for the source node of the dfs.
1118 /// It is called for the source node of the dfs.
1119 void start(const Node& node) {}
1120 /// \brief Called when we leave the source node of the dfs.
1122 /// It is called when we leave the source node of the dfs.
1123 void stop(const Node& node) {}
1127 template <typename _Graph>
1129 typedef _Graph Graph;
1130 typedef typename Graph::Edge Edge;
1131 typedef typename Graph::Node Node;
1132 void discover(const Edge&) {}
1133 void reach(const Node&) {}
1134 void backtrack(const Edge&) {}
1135 void leave(const Node&) {}
1136 void examine(const Edge&) {}
1137 void start(const Node&) {}
1138 void stop(const Node&) {}
1140 template <typename _Visitor>
1141 struct Constraints {
1142 void constraints() {
1145 visitor.discover(edge);
1146 visitor.reach(node);
1147 visitor.backtrack(edge);
1148 visitor.leave(node);
1149 visitor.examine(edge);
1150 visitor.start(node);
1158 /// \brief Default traits class of DfsVisit class.
1160 /// Default traits class of DfsVisit class.
1161 /// \param _Graph Graph type.
1162 template<class _Graph>
1163 struct DfsVisitDefaultTraits {
1165 /// \brief The graph type the algorithm runs on.
1166 typedef _Graph Graph;
1168 /// \brief The type of the map that indicates which nodes are reached.
1170 /// The type of the map that indicates which nodes are reached.
1171 /// It must meet the \ref concept::WriteMap "WriteMap" concept.
1172 /// \todo named parameter to set this type, function to read and write.
1173 typedef typename Graph::template NodeMap<bool> ReachedMap;
1175 /// \brief Instantiates a ReachedMap.
1177 /// This function instantiates a \ref ReachedMap.
1178 /// \param graph is the graph, to which
1179 /// we would like to define the \ref ReachedMap.
1180 static ReachedMap *createReachedMap(const Graph &graph) {
1181 return new ReachedMap(graph);
1186 /// %DFS Visit algorithm class.
1188 /// \ingroup flowalgs
1189 /// This class provides an efficient implementation of the %DFS algorithm
1190 /// with visitor interface.
1192 /// The %DfsVisit class provides an alternative interface to the Dfs
1193 /// class. It works with callback mechanism, the DfsVisit object calls
1194 /// on every dfs event the \c Visitor class member functions.
1196 /// \param _Graph The graph type the algorithm runs on. The default value is
1197 /// \ref ListGraph. The value of _Graph is not used directly by Dfs, it
1198 /// is only passed to \ref DfsDefaultTraits.
1199 /// \param _Visitor The Visitor object for the algorithm. The
1200 /// \ref DfsVisitor "DfsVisitor<_Graph>" is an empty Visitor which
1201 /// does not observe the Dfs events. If you want to observe the dfs
1202 /// events you should implement your own Visitor class.
1203 /// \param _Traits Traits class to set various data types used by the
1204 /// algorithm. The default traits class is
1205 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Graph>".
1206 /// See \ref DfsVisitDefaultTraits for the documentation of
1207 /// a Dfs visit traits class.
1209 /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
1211 template <typename _Graph, typename _Visitor, typename _Traits>
1213 template <typename _Graph = ListGraph,
1214 typename _Visitor = DfsVisitor<_Graph>,
1215 typename _Traits = DfsDefaultTraits<_Graph> >
1220 /// \brief \ref Exception for uninitialized parameters.
1222 /// This error represents problems in the initialization
1223 /// of the parameters of the algorithms.
1224 class UninitializedParameter : public lemon::UninitializedParameter {
1226 virtual const char* exceptionName() const {
1227 return "lemon::DfsVisit::UninitializedParameter";
1231 typedef _Traits Traits;
1233 typedef typename Traits::Graph Graph;
1235 typedef _Visitor Visitor;
1237 ///The type of the map indicating which nodes are reached.
1238 typedef typename Traits::ReachedMap ReachedMap;
1242 typedef typename Graph::Node Node;
1243 typedef typename Graph::NodeIt NodeIt;
1244 typedef typename Graph::Edge Edge;
1245 typedef typename Graph::OutEdgeIt OutEdgeIt;
1247 /// Pointer to the underlying graph.
1248 const Graph *_graph;
1249 /// Pointer to the visitor object.
1251 ///Pointer to the map of reached status of the nodes.
1252 ReachedMap *_reached;
1253 ///Indicates if \ref _reached is locally allocated (\c true) or not.
1256 std::vector<typename Graph::Edge> _stack;
1259 /// \brief Creates the maps if necessary.
1261 /// Creates the maps if necessary.
1262 void create_maps() {
1264 local_reached = true;
1265 _reached = Traits::createReachedMap(*_graph);
1275 typedef DfsVisit Create;
1277 /// \name Named template parameters
1281 struct DefReachedMapTraits : public Traits {
1282 typedef T ReachedMap;
1283 static ReachedMap *createReachedMap(const Graph &graph) {
1284 throw UninitializedParameter();
1287 /// \brief \ref named-templ-param "Named parameter" for setting
1290 /// \ref named-templ-param "Named parameter" for setting ReachedMap type
1292 struct DefReachedMap : public DfsVisit< Graph, Visitor,
1293 DefReachedMapTraits<T> > {
1294 typedef DfsVisit< Graph, Visitor, DefReachedMapTraits<T> > Create;
1300 /// \brief Constructor.
1304 /// \param graph the graph the algorithm will run on.
1305 /// \param visitor The visitor of the algorithm.
1307 DfsVisit(const Graph& graph, Visitor& visitor)
1308 : _graph(&graph), _visitor(&visitor),
1309 _reached(0), local_reached(false) {}
1311 /// \brief Destructor.
1315 if(local_reached) delete _reached;
1318 /// \brief Sets the map indicating if a node is reached.
1320 /// Sets the map indicating if a node is reached.
1321 /// If you don't use this function before calling \ref run(),
1322 /// it will allocate one. The destuctor deallocates this
1323 /// automatically allocated map, of course.
1324 /// \return <tt> (*this) </tt>
1325 DfsVisit &reachedMap(ReachedMap &m) {
1328 local_reached=false;
1335 /// \name Execution control
1336 /// The simplest way to execute the algorithm is to use
1337 /// one of the member functions called \c run(...).
1339 /// If you need more control on the execution,
1340 /// first you must call \ref init(), then you can adda source node
1341 /// with \ref addSource().
1342 /// Finally \ref start() will perform the actual path
1346 /// \brief Initializes the internal data structures.
1348 /// Initializes the internal data structures.
1352 _stack.resize(countNodes(*_graph));
1354 for (NodeIt u(*_graph) ; u != INVALID ; ++u) {
1355 _reached->set(u, false);
1359 /// \brief Adds a new source node.
1361 /// Adds a new source node to the set of nodes to be processed.
1362 void addSource(Node s) {
1363 if(!(*_reached)[s]) {
1364 _reached->set(s,true);
1368 _graph->firstOut(e, s);
1370 _stack[++_stack_head] = e;
1377 /// \brief Processes the next edge.
1379 /// Processes the next edge.
1381 /// \return The processed edge.
1383 /// \pre The stack must not be empty!
1384 Edge processNextEdge() {
1385 Edge e = _stack[_stack_head];
1386 Node m = _graph->target(e);
1387 if(!(*_reached)[m]) {
1388 _visitor->discover(e);
1390 _reached->set(m, true);
1391 _graph->firstOut(_stack[++_stack_head], m);
1393 _visitor->examine(e);
1394 m = _graph->source(e);
1395 _graph->nextOut(_stack[_stack_head]);
1397 while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
1400 if (_stack_head >= 0) {
1401 _visitor->backtrack(_stack[_stack_head]);
1402 m = _graph->source(_stack[_stack_head]);
1403 _graph->nextOut(_stack[_stack_head]);
1411 /// \brief Next edge to be processed.
1413 /// Next edge to be processed.
1415 /// \return The next edge to be processed or INVALID if the stack is
1418 return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
1421 /// \brief Returns \c false if there are nodes
1422 /// to be processed in the queue
1424 /// Returns \c false if there are nodes
1425 /// to be processed in the queue
1426 bool emptyQueue() { return _stack_head < 0; }
1428 /// \brief Returns the number of the nodes to be processed.
1430 /// Returns the number of the nodes to be processed in the queue.
1431 int queueSize() { return _stack_head + 1; }
1433 /// \brief Executes the algorithm.
1435 /// Executes the algorithm.
1437 /// \pre init() must be called and at least one node should be added
1438 /// with addSource() before using this function.
1440 while ( !emptyQueue() ) processNextEdge();
1443 /// \brief Executes the algorithm until \c dest is reached.
1445 /// Executes the algorithm until \c dest is reached.
1447 /// \pre init() must be called and at least one node should be added
1448 /// with addSource() before using this function.
1449 void start(Node dest) {
1450 while ( !emptyQueue() && _graph->target(_stack[_stack_head]) != dest)
1454 /// \brief Executes the algorithm until a condition is met.
1456 /// Executes the algorithm until a condition is met.
1458 /// \pre init() must be called and at least one node should be added
1459 /// with addSource() before using this function.
1461 /// \param em must be a bool (or convertible) edge map. The algorithm
1462 /// will stop when it reaches an edge \c e with \code nm[e]==true \endcode.
1464 /// \warning Contrary to \ref Dfs and \ref Dijkstra, \c em is an edge map,
1466 template <typename EM>
1467 void start(const EM &em) {
1468 while (!emptyQueue() && !em[_stack[_stack_head]]) processNextEdge();
1471 /// \brief Runs %DFSVisit algorithm from node \c s.
1473 /// This method runs the %DFS algorithm from a root node \c s.
1474 /// \note d.run(s) is just a shortcut of the following code.
1486 /// \brief Runs %DFSVisit algorithm to visit all nodes in the graph.
1488 /// This method runs the %DFS algorithm in order to
1489 /// compute the %DFS path to each node. The algorithm computes
1490 /// - The %DFS tree.
1491 /// - The distance of each node from the root in the %DFS tree.
1493 ///\note d.run() is just a shortcut of the following code.
1496 /// for (NodeIt it(graph); it != INVALID; ++it) {
1497 /// if (!d.reached(it)) {
1498 /// d.addSource(it);
1505 for (NodeIt it(*_graph); it != INVALID; ++it) {
1514 /// \name Query Functions
1515 /// The result of the %DFS algorithm can be obtained using these
1517 /// Before the use of these functions,
1518 /// either run() or start() must be called.
1520 /// \brief Checks if a node is reachable from the root.
1522 /// Returns \c true if \c v is reachable from the root(s).
1523 /// \warning The source nodes are inditated as unreachable.
1524 /// \pre Either \ref run() or \ref start()
1525 /// must be called before using this function.
1527 bool reached(Node v) { return (*_reached)[v]; }
1532 } //END OF NAMESPACE LEMON