NewMapWin has become Dialog instead of Window. Therefore it is created dynamically, when there is need for it, instead of keeping one instance in memory. This solution is slower, but more correct than before.
2 * lemon/dfs.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
22 ///\brief Dfs algorithm.
24 #include <lemon/list_graph.h>
25 #include <lemon/graph_utils.h>
26 #include <lemon/invalid.h>
27 #include <lemon/error.h>
28 #include <lemon/maps.h>
30 #include <lemon/concept_check.h>
35 ///Default traits class of Dfs class.
37 ///Default traits class of Dfs class.
38 ///\param GR Graph type.
40 struct DfsDefaultTraits
42 ///The graph type the algorithm runs on.
44 ///\brief The type of the map that stores the last
45 ///edges of the %DFS paths.
47 ///The type of the map that stores the last
48 ///edges of the %DFS paths.
49 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
51 typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
52 ///Instantiates a PredMap.
54 ///This function instantiates a \ref PredMap.
55 ///\param G is the graph, to which we would like to define the PredMap.
56 ///\todo The graph alone may be insufficient to initialize
57 static PredMap *createPredMap(const GR &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 meet the \ref concept::WriteMap "WriteMap" concept.
66 ///\todo named parameter to set this type, function to read and write.
67 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
68 ///Instantiates a ProcessedMap.
70 ///This function instantiates a \ref ProcessedMap.
71 ///\param g is the graph, 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 concept::WriteMap "WriteMap" concept.
85 ///\todo named parameter to set this type, function to read and write.
86 typedef typename Graph::template NodeMap<bool> ReachedMap;
87 ///Instantiates a ReachedMap.
89 ///This function instantiates a \ref ReachedMap.
90 ///\param G is the graph, 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 concept::WriteMap "WriteMap" concept.
101 typedef typename Graph::template NodeMap<int> DistMap;
102 ///Instantiates a DistMap.
104 ///This function instantiates a \ref DistMap.
105 ///\param G is the graph, to which we would like to define the \ref DistMap
106 static DistMap *createDistMap(const GR &G)
108 return new DistMap(G);
112 ///%DFS algorithm class.
115 ///This class provides an efficient implementation of the %DFS algorithm.
117 ///\param GR The graph type the algorithm runs on. The default value is
118 ///\ref ListGraph. The value of GR is not used directly by Dfs, it
119 ///is only passed to \ref DfsDefaultTraits.
120 ///\param TR Traits class to set various data types used by the algorithm.
121 ///The default traits class is
122 ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
123 ///See \ref DfsDefaultTraits for the documentation of
124 ///a Dfs traits class.
126 ///\author Jacint Szabo and Alpar Juttner
128 template <typename GR,
131 template <typename GR=ListGraph,
132 typename TR=DfsDefaultTraits<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* exceptionName() const {
145 return "lemon::Dfs::UninitializedParameter";
150 ///The type of the underlying graph.
151 typedef typename TR::Graph Graph;
153 typedef typename Graph::Node Node;
155 typedef typename Graph::NodeIt NodeIt;
157 typedef typename Graph::Edge Edge;
159 typedef typename Graph::OutEdgeIt OutEdgeIt;
161 ///\brief The type of the map that stores the last
162 ///edges of the %DFS paths.
163 typedef typename TR::PredMap PredMap;
164 ///The type of the map indicating which nodes are reached.
165 typedef typename TR::ReachedMap ReachedMap;
166 ///The type of the map indicating which nodes are processed.
167 typedef typename TR::ProcessedMap ProcessedMap;
168 ///The type of the map that stores the dists of the nodes.
169 typedef typename TR::DistMap DistMap;
171 /// Pointer to the underlying graph.
173 ///Pointer to the map of predecessors edges.
175 ///Indicates if \ref _pred is locally allocated (\c true) or not.
177 ///Pointer to the map of distances.
179 ///Indicates if \ref _dist is locally allocated (\c true) or not.
181 ///Pointer to the map of reached status of the nodes.
182 ReachedMap *_reached;
183 ///Indicates if \ref _reached is locally allocated (\c true) or not.
185 ///Pointer to the map of processed status of the nodes.
186 ProcessedMap *_processed;
187 ///Indicates if \ref _processed is locally allocated (\c true) or not.
188 bool local_processed;
190 std::vector<typename Graph::OutEdgeIt> _stack;
193 ///Creates the maps if necessary.
195 ///\todo Better memory allocation (instead of new).
200 _pred = Traits::createPredMap(*G);
204 _dist = Traits::createDistMap(*G);
207 local_reached = true;
208 _reached = Traits::createReachedMap(*G);
211 local_processed = true;
212 _processed = Traits::createProcessedMap(*G);
224 ///\name Named template parameters
229 struct DefPredMapTraits : public Traits {
231 static PredMap *createPredMap(const Graph &G)
233 throw UninitializedParameter();
236 ///\ref named-templ-param "Named parameter" for setting PredMap type
238 ///\ref named-templ-param "Named parameter" for setting PredMap type
241 struct DefPredMap : public Dfs<Graph, DefPredMapTraits<T> > {
242 typedef Dfs<Graph, DefPredMapTraits<T> > Create;
247 struct DefDistMapTraits : public Traits {
249 static DistMap *createDistMap(const Graph &G)
251 throw UninitializedParameter();
254 ///\ref named-templ-param "Named parameter" for setting DistMap type
256 ///\ref named-templ-param "Named parameter" for setting DistMap type
260 typedef Dfs<Graph, DefDistMapTraits<T> > Create;
264 struct DefReachedMapTraits : public Traits {
265 typedef T ReachedMap;
266 static ReachedMap *createReachedMap(const Graph &G)
268 throw UninitializedParameter();
271 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
273 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
276 struct DefReachedMap : public Dfs< Graph, DefReachedMapTraits<T> > {
277 typedef Dfs< Graph, DefReachedMapTraits<T> > Create;
281 struct DefProcessedMapTraits : public Traits {
282 typedef T ProcessedMap;
283 static ProcessedMap *createProcessedMap(const Graph &G)
285 throw UninitializedParameter();
288 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
290 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
293 struct DefProcessedMap : public Dfs< Graph, DefProcessedMapTraits<T> > {
294 typedef Dfs< Graph, DefProcessedMapTraits<T> > Create;
297 struct DefGraphProcessedMapTraits : public Traits {
298 typedef typename Graph::template NodeMap<bool> ProcessedMap;
299 static ProcessedMap *createProcessedMap(const Graph &G)
301 return new ProcessedMap(G);
304 ///\brief \ref named-templ-param "Named parameter"
305 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
307 ///\ref named-templ-param "Named parameter"
308 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
309 ///If you don't set it explicitely, it will be automatically allocated.
311 class DefProcessedMapToBeDefaultMap :
312 public Dfs< Graph, DefGraphProcessedMapTraits> {
313 typedef Dfs< Graph, DefGraphProcessedMapTraits> Create;
322 ///\param _G the graph the algorithm will run on.
324 Dfs(const Graph& _G) :
326 _pred(NULL), local_pred(false),
327 _dist(NULL), local_dist(false),
328 _reached(NULL), local_reached(false),
329 _processed(NULL), local_processed(false)
335 if(local_pred) delete _pred;
336 if(local_dist) delete _dist;
337 if(local_reached) delete _reached;
338 if(local_processed) delete _processed;
341 ///Sets the map storing the predecessor edges.
343 ///Sets the map storing the predecessor edges.
344 ///If you don't use this function before calling \ref run(),
345 ///it will allocate one. The destuctor deallocates this
346 ///automatically allocated map, of course.
347 ///\return <tt> (*this) </tt>
348 Dfs &predMap(PredMap &m)
358 ///Sets the map storing the distances calculated by the algorithm.
360 ///Sets the map storing the distances calculated by the algorithm.
361 ///If you don't use this function before calling \ref run(),
362 ///it will allocate one. The destuctor deallocates this
363 ///automatically allocated map, of course.
364 ///\return <tt> (*this) </tt>
365 Dfs &distMap(DistMap &m)
375 ///Sets the map indicating if a node is reached.
377 ///Sets the map indicating if a node is reached.
378 ///If you don't use this function before calling \ref run(),
379 ///it will allocate one. The destuctor deallocates this
380 ///automatically allocated map, of course.
381 ///\return <tt> (*this) </tt>
382 Dfs &reachedMap(ReachedMap &m)
392 ///Sets the map indicating if a node is processed.
394 ///Sets the map indicating if a node is processed.
395 ///If you don't use this function before calling \ref run(),
396 ///it will allocate one. The destuctor deallocates this
397 ///automatically allocated map, of course.
398 ///\return <tt> (*this) </tt>
399 Dfs &processedMap(ProcessedMap &m)
401 if(local_processed) {
403 local_processed=false;
410 ///\name Execution control
411 ///The simplest way to execute the algorithm is to use
412 ///one of the member functions called \c run(...).
414 ///If you need more control on the execution,
415 ///first you must call \ref init(), then you can add a source node
416 ///with \ref addSource().
417 ///Finally \ref start() will perform the actual path
422 ///Initializes the internal data structures.
424 ///Initializes the internal data structures.
429 _stack.resize(countNodes(*G));
431 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
432 _pred->set(u,INVALID);
433 // _predNode->set(u,INVALID);
434 _reached->set(u,false);
435 _processed->set(u,false);
439 ///Adds a new source node.
441 ///Adds a new source node to the set of nodes to be processed.
443 ///\bug dists are wrong (or at least strange) in case of multiple sources.
444 void addSource(Node s)
448 _reached->set(s,true);
449 _pred->set(s,INVALID);
452 _stack[++_stack_head]=e;
453 _dist->set(s,_stack_head);
456 _processed->set(s,true);
462 ///Processes the next edge.
464 ///Processes the next edge.
466 ///\return The processed edge.
468 ///\pre The stack must not be empty!
469 Edge processNextEdge()
472 Edge e=_stack[_stack_head];
473 if(!(*_reached)[m=G->target(e)]) {
475 _reached->set(m,true);
477 _stack[_stack_head] = OutEdgeIt(*G, m);
478 _dist->set(m,_stack_head);
482 ++_stack[_stack_head];
484 while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
485 _processed->set(m,true);
488 m=G->source(_stack[_stack_head]);
489 ++_stack[_stack_head];
494 ///Next edge to be processed.
496 ///Next edge to be processed.
498 ///\return The next edge to be processed or INVALID if the stack is
502 return _stack_head>=0?_stack[_stack_head]:INVALID;
505 ///\brief Returns \c false if there are nodes
506 ///to be processed in the queue
508 ///Returns \c false if there are nodes
509 ///to be processed in the queue
510 bool emptyQueue() { return _stack_head<0; }
511 ///Returns the number of the nodes to be processed.
513 ///Returns the number of the nodes to be processed in the queue.
514 int queueSize() { return _stack_head+1; }
516 ///Executes the algorithm.
518 ///Executes the algorithm.
520 ///\pre init() must be called and at least one node should be added
521 ///with addSource() before using this function.
523 ///This method runs the %DFS algorithm from the root node(s)
526 ///%DFS path to each node. The algorithm computes
528 ///- The distance of each node from the root(s) in the %DFS tree.
532 while ( !emptyQueue() ) processNextEdge();
535 ///Executes the algorithm until \c dest is reached.
537 ///Executes the algorithm until \c dest is reached.
539 ///\pre init() must be called and at least one node should be added
540 ///with addSource() before using this function.
542 ///This method runs the %DFS algorithm from the root node(s)
545 ///%DFS path to \c dest. The algorithm computes
546 ///- The %DFS path to \c dest.
547 ///- The distance of \c dest from the root(s) in the %DFS tree.
549 void start(Node dest)
551 while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
555 ///Executes the algorithm until a condition is met.
557 ///Executes the algorithm until a condition is met.
559 ///\pre init() must be called and at least one node should be added
560 ///with addSource() before using this function.
562 ///\param nm must be a bool (or convertible) edge map. The algorithm
563 ///will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>.
565 ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c em is an edge map,
568 void start(const EM &em)
570 while ( !emptyQueue() && !em[_stack[_stack_head]] ) processNextEdge();
573 ///Runs %DFS algorithm from node \c s.
575 ///This method runs the %DFS algorithm from a root node \c s
578 ///%DFS path to each node. The algorithm computes
580 ///- The distance of each node from the root in the %DFS tree.
582 ///\note d.run(s) is just a shortcut of the following code.
594 ///Finds the %DFS path between \c s and \c t.
596 ///Finds the %DFS path between \c s and \c t.
598 ///\return The length of the %DFS s---t path if there exists one,
600 ///\note Apart from the return value, d.run(s,t) is
601 ///just a shortcut of the following code.
607 int run(Node s,Node t) {
611 return reached(t)?_stack_head+1:0;
616 ///\name Query Functions
617 ///The result of the %DFS algorithm can be obtained using these
619 ///Before the use of these functions,
620 ///either run() or start() must be called.
624 ///Copies the path to \c t on the DFS tree into \c p
626 ///This function copies the path to \c t on the DFS tree into \c p.
627 ///If \c t is a source itself or unreachable, then it does not
630 ///\return Returns \c true if a path to \c t was actually copied to \c p,
631 ///\c false otherwise.
634 bool getPath(P &p,Node t)
638 typename P::Builder b(p);
639 for(b.setStartNode(t);predEdge(t)!=INVALID;t=predNode(t))
640 b.pushFront(predEdge(t));
647 ///The distance of a node from the root(s).
649 ///Returns the distance of a node from the root(s).
650 ///\pre \ref run() must be called before using this function.
651 ///\warning If node \c v is unreachable from the root(s) then the return value
652 ///of this funcion is undefined.
653 int dist(Node v) const { return (*_dist)[v]; }
655 ///Returns the 'previous edge' of the %DFS tree.
657 ///For a node \c v it returns the 'previous edge'
659 ///i.e. it returns the last edge of a %DFS path from the root(s) to \c
660 ///v. It is \ref INVALID
661 ///if \c v is unreachable from the root(s) or \c v is a root. The
662 ///%DFS tree used here is equal to the %DFS tree used in
664 ///\pre Either \ref run() or \ref start() must be called before using
666 Edge predEdge(Node v) const { return (*_pred)[v];}
668 ///Returns the 'previous node' of the %DFS tree.
670 ///For a node \c v it returns the 'previous node'
672 ///i.e. it returns the last but one node from a %DFS path from the
674 ///It is INVALID if \c v is unreachable from the root(s) or
675 ///if \c v itself a root.
676 ///The %DFS tree used here is equal to the %DFS
677 ///tree used in \ref predEdge().
678 ///\pre Either \ref run() or \ref start() must be called before
679 ///using this function.
680 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
681 G->source((*_pred)[v]); }
683 ///Returns a reference to the NodeMap of distances.
685 ///Returns a reference to the NodeMap of distances.
686 ///\pre Either \ref run() or \ref init() must
687 ///be called before using this function.
688 const DistMap &distMap() const { return *_dist;}
690 ///Returns a reference to the %DFS edge-tree map.
692 ///Returns a reference to the NodeMap of the edges of the
694 ///\pre Either \ref run() or \ref init()
695 ///must be called before using this function.
696 const PredMap &predMap() const { return *_pred;}
698 ///Checks if a node is reachable from the root.
700 ///Returns \c true if \c v is reachable from the root(s).
701 ///\warning The source nodes are inditated as unreachable.
702 ///\pre Either \ref run() or \ref start()
703 ///must be called before using this function.
705 bool reached(Node v) { return (*_reached)[v]; }
710 ///Default traits class of Dfs function.
712 ///Default traits class of Dfs function.
713 ///\param GR Graph type.
715 struct DfsWizardDefaultTraits
717 ///The graph type the algorithm runs on.
719 ///\brief The type of the map that stores the last
720 ///edges of the %DFS paths.
722 ///The type of the map that stores the last
723 ///edges of the %DFS paths.
724 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
726 typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
727 ///Instantiates a PredMap.
729 ///This function instantiates a \ref PredMap.
730 ///\param g is the graph, to which we would like to define the PredMap.
731 ///\todo The graph alone may be insufficient to initialize
733 static PredMap *createPredMap(const GR &g)
735 static PredMap *createPredMap(const GR &)
738 return new PredMap();
741 ///The type of the map that indicates which nodes are processed.
743 ///The type of the map that indicates which nodes are processed.
744 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
745 ///\todo named parameter to set this type, function to read and write.
746 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
747 ///Instantiates a ProcessedMap.
749 ///This function instantiates a \ref ProcessedMap.
750 ///\param g is the graph, to which
751 ///we would like to define the \ref ProcessedMap
753 static ProcessedMap *createProcessedMap(const GR &g)
755 static ProcessedMap *createProcessedMap(const GR &)
758 return new ProcessedMap();
760 ///The type of the map that indicates which nodes are reached.
762 ///The type of the map that indicates which nodes are reached.
763 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
764 ///\todo named parameter to set this type, function to read and write.
765 typedef typename Graph::template NodeMap<bool> ReachedMap;
766 ///Instantiates a ReachedMap.
768 ///This function instantiates a \ref ReachedMap.
769 ///\param G is the graph, to which
770 ///we would like to define the \ref ReachedMap.
771 static ReachedMap *createReachedMap(const GR &G)
773 return new ReachedMap(G);
775 ///The type of the map that stores the dists of the nodes.
777 ///The type of the map that stores the dists of the nodes.
778 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
780 typedef NullMap<typename Graph::Node,int> DistMap;
781 ///Instantiates a DistMap.
783 ///This function instantiates a \ref DistMap.
784 ///\param g is the graph, to which we would like to define the \ref DistMap
786 static DistMap *createDistMap(const GR &g)
788 static DistMap *createDistMap(const GR &)
791 return new DistMap();
795 /// Default traits used by \ref DfsWizard
797 /// To make it easier to use Dfs algorithm
798 ///we have created a wizard class.
799 /// This \ref DfsWizard class needs default traits,
800 ///as well as the \ref Dfs class.
801 /// The \ref DfsWizardBase is a class to be the default traits of the
802 /// \ref DfsWizard class.
804 class DfsWizardBase : public DfsWizardDefaultTraits<GR>
807 typedef DfsWizardDefaultTraits<GR> Base;
809 /// Type of the nodes in the graph.
810 typedef typename Base::Graph::Node Node;
812 /// Pointer to the underlying graph.
814 ///Pointer to the map of reached nodes.
816 ///Pointer to the map of processed nodes.
818 ///Pointer to the map of predecessors edges.
820 ///Pointer to the map of distances.
822 ///Pointer to the source node.
828 /// This constructor does not require parameters, therefore it initiates
829 /// all of the attributes to default values (0, INVALID).
830 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
831 _dist(0), _source(INVALID) {}
835 /// This constructor requires some parameters,
836 /// listed in the parameters list.
837 /// Others are initiated to 0.
838 /// \param g is the initial value of \ref _g
839 /// \param s is the initial value of \ref _source
840 DfsWizardBase(const GR &g, Node s=INVALID) :
841 _g((void *)&g), _reached(0), _processed(0), _pred(0),
842 _dist(0), _source(s) {}
846 /// A class to make the usage of the Dfs algorithm easier
848 /// This class is created to make it easier to use the Dfs algorithm.
849 /// It uses the functions and features of the plain \ref Dfs,
850 /// but it is much simpler to use it.
852 /// Simplicity means that the way to change the types defined
853 /// in the traits class is based on functions that returns the new class
854 /// and not on templatable built-in classes.
855 /// When using the plain \ref Dfs
856 /// the new class with the modified type comes from
857 /// the original class by using the ::
858 /// operator. In the case of \ref DfsWizard only
859 /// a function have to be called and it will
860 /// return the needed class.
862 /// It does not have own \ref run method. When its \ref run method is called
863 /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run
866 class DfsWizard : public TR
870 ///The type of the underlying graph.
871 typedef typename TR::Graph Graph;
873 typedef typename Graph::Node Node;
875 typedef typename Graph::NodeIt NodeIt;
877 typedef typename Graph::Edge Edge;
879 typedef typename Graph::OutEdgeIt OutEdgeIt;
881 ///\brief The type of the map that stores
883 typedef typename TR::ReachedMap ReachedMap;
884 ///\brief The type of the map that stores
885 ///the processed nodes
886 typedef typename TR::ProcessedMap ProcessedMap;
887 ///\brief The type of the map that stores the last
888 ///edges of the %DFS paths.
889 typedef typename TR::PredMap PredMap;
890 ///The type of the map that stores the distances of the nodes.
891 typedef typename TR::DistMap DistMap;
895 DfsWizard() : TR() {}
897 /// Constructor that requires parameters.
899 /// Constructor that requires parameters.
900 /// These parameters will be the default values for the traits class.
901 DfsWizard(const Graph &g, Node s=INVALID) :
905 DfsWizard(const TR &b) : TR(b) {}
909 ///Runs Dfs algorithm from a given node.
911 ///Runs Dfs algorithm from a given node.
912 ///The node can be given by the \ref source function.
915 if(Base::_source==INVALID) throw UninitializedParameter();
916 Dfs<Graph,TR> alg(*(Graph*)Base::_g);
917 if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached);
918 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
919 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
920 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
921 alg.run(Base::_source);
924 ///Runs Dfs algorithm from the given node.
926 ///Runs Dfs algorithm from the given node.
927 ///\param s is the given source.
935 struct DefPredMapBase : public Base {
937 static PredMap *createPredMap(const Graph &) { return 0; };
938 DefPredMapBase(const TR &b) : TR(b) {}
941 ///\brief \ref named-templ-param "Named parameter"
942 ///function for setting PredMap type
944 /// \ref named-templ-param "Named parameter"
945 ///function for setting PredMap type
948 DfsWizard<DefPredMapBase<T> > predMap(const T &t)
950 Base::_pred=(void *)&t;
951 return DfsWizard<DefPredMapBase<T> >(*this);
956 struct DefReachedMapBase : public Base {
957 typedef T ReachedMap;
958 static ReachedMap *createReachedMap(const Graph &) { return 0; };
959 DefReachedMapBase(const TR &b) : TR(b) {}
962 ///\brief \ref named-templ-param "Named parameter"
963 ///function for setting ReachedMap
965 /// \ref named-templ-param "Named parameter"
966 ///function for setting ReachedMap
969 DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
971 Base::_pred=(void *)&t;
972 return DfsWizard<DefReachedMapBase<T> >(*this);
977 struct DefProcessedMapBase : public Base {
978 typedef T ProcessedMap;
979 static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
980 DefProcessedMapBase(const TR &b) : TR(b) {}
983 ///\brief \ref named-templ-param "Named parameter"
984 ///function for setting ProcessedMap
986 /// \ref named-templ-param "Named parameter"
987 ///function for setting ProcessedMap
990 DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
992 Base::_pred=(void *)&t;
993 return DfsWizard<DefProcessedMapBase<T> >(*this);
997 struct DefDistMapBase : public Base {
999 static DistMap *createDistMap(const Graph &) { return 0; };
1000 DefDistMapBase(const TR &b) : TR(b) {}
1003 ///\brief \ref named-templ-param "Named parameter"
1004 ///function for setting DistMap type
1006 /// \ref named-templ-param "Named parameter"
1007 ///function for setting DistMap type
1010 DfsWizard<DefDistMapBase<T> > distMap(const T &t)
1012 Base::_dist=(void *)&t;
1013 return DfsWizard<DefDistMapBase<T> >(*this);
1016 /// Sets the source node, from which the Dfs algorithm runs.
1018 /// Sets the source node, from which the Dfs algorithm runs.
1019 /// \param s is the source node.
1020 DfsWizard<TR> &source(Node s)
1028 ///Function type interface for Dfs algorithm.
1030 /// \ingroup flowalgs
1031 ///Function type interface for Dfs algorithm.
1033 ///This function also has several
1034 ///\ref named-templ-func-param "named parameters",
1035 ///they are declared as the members of class \ref DfsWizard.
1037 ///example shows how to use these parameters.
1039 /// dfs(g,source).predMap(preds).run();
1041 ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
1042 ///to the end of the parameter list.
1046 DfsWizard<DfsWizardBase<GR> >
1047 dfs(const GR &g,typename GR::Node s=INVALID)
1049 return DfsWizard<DfsWizardBase<GR> >(g,s);
1053 /// \brief Visitor class for dfs.
1055 /// It gives a simple interface for a functional interface for dfs
1056 /// traversal. The traversal on a linear data structure.
1057 template <typename _Graph>
1059 typedef _Graph Graph;
1060 typedef typename Graph::Edge Edge;
1061 typedef typename Graph::Node Node;
1062 /// \brief Called when the edge reach a node.
1064 /// It is called when the dfs find an edge which target is not
1066 void discover(const Edge& edge) {}
1067 /// \brief Called when the node reached first time.
1069 /// It is Called when the node reached first time.
1070 void reach(const Node& node) {}
1071 /// \brief Called when we step back on an edge.
1073 /// It is called when the dfs should step back on the edge.
1074 void backtrack(const Edge& edge) {}
1075 /// \brief Called when we step back from the node.
1077 /// It is called when we step back from the node.
1078 void leave(const Node& node) {}
1079 /// \brief Called when the edge examined but target of the edge
1080 /// already discovered.
1082 /// It called when the edge examined but the target of the edge
1083 /// already discovered.
1084 void examine(const Edge& edge) {}
1085 /// \brief Called for the source node of the dfs.
1087 /// It is called for the source node of the dfs.
1088 void start(const Node& node) {}
1089 /// \brief Called when we leave the source node of the dfs.
1091 /// It is called when we leave the source node of the dfs.
1092 void stop(const Node& node) {}
1096 template <typename _Graph>
1098 typedef _Graph Graph;
1099 typedef typename Graph::Edge Edge;
1100 typedef typename Graph::Node Node;
1101 void discover(const Edge&) {}
1102 void reach(const Node&) {}
1103 void backtrack(const Edge&) {}
1104 void leave(const Node&) {}
1105 void examine(const Edge&) {}
1106 void start(const Node&) {}
1107 void stop(const Node&) {}
1109 template <typename _Visitor>
1110 struct Constraints {
1111 void constraints() {
1114 visitor.discover(edge);
1115 visitor.reach(node);
1116 visitor.backtrack(edge);
1117 visitor.leave(node);
1118 visitor.examine(edge);
1119 visitor.start(node);
1127 /// \brief Default traits class of DfsVisit class.
1129 /// Default traits class of DfsVisit class.
1130 /// \param _Graph Graph type.
1131 template<class _Graph>
1132 struct DfsVisitDefaultTraits {
1134 /// \brief The graph type the algorithm runs on.
1135 typedef _Graph Graph;
1137 /// \brief The type of the map that indicates which nodes are reached.
1139 /// The type of the map that indicates which nodes are reached.
1140 /// It must meet the \ref concept::WriteMap "WriteMap" concept.
1141 /// \todo named parameter to set this type, function to read and write.
1142 typedef typename Graph::template NodeMap<bool> ReachedMap;
1144 /// \brief Instantiates a ReachedMap.
1146 /// This function instantiates a \ref ReachedMap.
1147 /// \param G is the graph, to which
1148 /// we would like to define the \ref ReachedMap.
1149 static ReachedMap *createReachedMap(const Graph &graph) {
1150 return new ReachedMap(graph);
1155 /// %DFS Visit algorithm class.
1157 /// \ingroup flowalgs
1158 /// This class provides an efficient implementation of the %DFS algorithm
1159 /// with visitor interface.
1161 /// The %DfsVisit class provides an alternative interface to the Dfs
1162 /// class. It works with callback mechanism, the DfsVisit object calls
1163 /// on every dfs event the \c Visitor class member functions.
1165 /// \param _Graph The graph type the algorithm runs on. The default value is
1166 /// \ref ListGraph. The value of _Graph is not used directly by Dfs, it
1167 /// is only passed to \ref DfsDefaultTraits.
1168 /// \param _Visitor The Visitor object for the algorithm. The
1169 /// \ref DfsVisitor "DfsVisitor<_Graph>" is an empty Visitor which
1170 /// does not observe the Dfs events. If you want to observe the dfs
1171 /// events you should implement your own Visitor class.
1172 /// \param _Traits Traits class to set various data types used by the
1173 /// algorithm. The default traits class is
1174 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Graph>".
1175 /// See \ref DfsVisitDefaultTraits for the documentation of
1176 /// a Dfs visit traits class.
1178 /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
1180 template <typename _Graph, typename _Visitor, typename _Traits>
1182 template <typename _Graph = ListGraph,
1183 typename _Visitor = DfsVisitor<_Graph>,
1184 typename _Traits = DfsDefaultTraits<_Graph> >
1189 /// \brief \ref Exception for uninitialized parameters.
1191 /// This error represents problems in the initialization
1192 /// of the parameters of the algorithms.
1193 class UninitializedParameter : public lemon::UninitializedParameter {
1195 virtual const char* exceptionName() const {
1196 return "lemon::DfsVisit::UninitializedParameter";
1200 typedef _Traits Traits;
1202 typedef typename Traits::Graph Graph;
1204 typedef _Visitor Visitor;
1206 ///The type of the map indicating which nodes are reached.
1207 typedef typename Traits::ReachedMap ReachedMap;
1211 typedef typename Graph::Node Node;
1212 typedef typename Graph::NodeIt NodeIt;
1213 typedef typename Graph::Edge Edge;
1214 typedef typename Graph::OutEdgeIt OutEdgeIt;
1216 /// Pointer to the underlying graph.
1217 const Graph *_graph;
1218 /// Pointer to the visitor object.
1220 ///Pointer to the map of reached status of the nodes.
1221 ReachedMap *_reached;
1222 ///Indicates if \ref _reached is locally allocated (\c true) or not.
1225 std::vector<typename Graph::Edge> _stack;
1228 /// \brief Creates the maps if necessary.
1230 /// Creates the maps if necessary.
1231 void create_maps() {
1233 local_reached = true;
1234 _reached = Traits::createReachedMap(*_graph);
1244 typedef DfsVisit Create;
1246 /// \name Named template parameters
1250 struct DefReachedMapTraits : public Traits {
1251 typedef T ReachedMap;
1252 static ReachedMap *createReachedMap(const Graph &graph) {
1253 throw UninitializedParameter();
1256 /// \brief \ref named-templ-param "Named parameter" for setting
1259 /// \ref named-templ-param "Named parameter" for setting ReachedMap type
1261 struct DefReachedMap : public DfsVisit< Graph, Visitor,
1262 DefReachedMapTraits<T> > {
1263 typedef DfsVisit< Graph, Visitor, DefReachedMapTraits<T> > Create;
1269 /// \brief Constructor.
1273 /// \param graph the graph the algorithm will run on.
1274 /// \param visitor The visitor of the algorithm.
1276 DfsVisit(const Graph& graph, Visitor& visitor)
1277 : _graph(&graph), _visitor(&visitor),
1278 _reached(0), local_reached(false) {}
1280 /// \brief Destructor.
1284 if(local_reached) delete _reached;
1287 /// \brief Sets the map indicating if a node is reached.
1289 /// Sets the map indicating if a node is reached.
1290 /// If you don't use this function before calling \ref run(),
1291 /// it will allocate one. The destuctor deallocates this
1292 /// automatically allocated map, of course.
1293 /// \return <tt> (*this) </tt>
1294 DfsVisit &reachedMap(ReachedMap &m) {
1297 local_reached=false;
1304 /// \name Execution control
1305 /// The simplest way to execute the algorithm is to use
1306 /// one of the member functions called \c run(...).
1308 /// If you need more control on the execution,
1309 /// first you must call \ref init(), then you can adda source node
1310 /// with \ref addSource().
1311 /// Finally \ref start() will perform the actual path
1315 /// \brief Initializes the internal data structures.
1317 /// Initializes the internal data structures.
1321 _stack.resize(countNodes(*_graph));
1323 for (NodeIt u(*_graph) ; u != INVALID ; ++u) {
1324 _reached->set(u, false);
1328 /// \brief Adds a new source node.
1330 /// Adds a new source node to the set of nodes to be processed.
1331 void addSource(Node s) {
1332 if(!(*_reached)[s]) {
1333 _reached->set(s,true);
1337 _graph->firstOut(e, s);
1339 _stack[++_stack_head] = e;
1346 /// \brief Processes the next edge.
1348 /// Processes the next edge.
1350 /// \return The processed edge.
1352 /// \pre The stack must not be empty!
1353 Edge processNextEdge() {
1354 Edge e = _stack[_stack_head];
1355 Node m = _graph->target(e);
1356 if(!(*_reached)[m]) {
1357 _visitor->discover(e);
1359 _reached->set(m, true);
1360 _graph->firstOut(_stack[++_stack_head], m);
1362 _visitor->examine(e);
1363 m = _graph->source(e);
1364 _graph->nextOut(_stack[_stack_head]);
1366 while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
1369 if (_stack_head >= 0) {
1370 _visitor->backtrack(_stack[_stack_head]);
1371 m = _graph->source(_stack[_stack_head]);
1372 _graph->nextOut(_stack[_stack_head]);
1380 /// \brief Next edge to be processed.
1382 /// Next edge to be processed.
1384 /// \return The next edge to be processed or INVALID if the stack is
1387 return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
1390 /// \brief Returns \c false if there are nodes
1391 /// to be processed in the queue
1393 /// Returns \c false if there are nodes
1394 /// to be processed in the queue
1395 bool emptyQueue() { return _stack_head < 0; }
1397 /// \brief Returns the number of the nodes to be processed.
1399 /// Returns the number of the nodes to be processed in the queue.
1400 int queueSize() { return _stack_head + 1; }
1402 /// \brief Executes the algorithm.
1404 /// Executes the algorithm.
1406 /// \pre init() must be called and at least one node should be added
1407 /// with addSource() before using this function.
1409 while ( !emptyQueue() ) processNextEdge();
1412 /// \brief Executes the algorithm until \c dest is reached.
1414 /// Executes the algorithm until \c dest is reached.
1416 /// \pre init() must be called and at least one node should be added
1417 /// with addSource() before using this function.
1418 void start(Node dest) {
1419 while ( !emptyQueue() && _graph->target(_stack[_stack_head]) != dest)
1423 /// \brief Executes the algorithm until a condition is met.
1425 /// Executes the algorithm until a condition is met.
1427 /// \pre init() must be called and at least one node should be added
1428 /// with addSource() before using this function.
1430 /// \param nm must be a bool (or convertible) edge map. The algorithm
1431 /// will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>.
1433 /// \warning Contrary to \ref Dfs and \ref Dijkstra, \c em is an edge map,
1435 template <typename EM>
1436 void start(const EM &em) {
1437 while (!emptyQueue() && !em[_stack[_stack_head]]) processNextEdge();
1440 /// \brief Runs %DFS algorithm from node \c s.
1442 /// This method runs the %DFS algorithm from a root node \c s.
1443 /// \note d.run(s) is just a shortcut of the following code.
1456 /// \name Query Functions
1457 /// The result of the %DFS algorithm can be obtained using these
1459 /// Before the use of these functions,
1460 /// either run() or start() must be called.
1462 /// \brief Checks if a node is reachable from the root.
1464 /// Returns \c true if \c v is reachable from the root(s).
1465 /// \warning The source nodes are inditated as unreachable.
1466 /// \pre Either \ref run() or \ref start()
1467 /// must be called before using this function.
1469 bool reached(Node v) { return (*_reached)[v]; }
1474 } //END OF NAMESPACE LEMON