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>
34 ///Default traits class of Dfs class.
36 ///Default traits class of Dfs class.
37 ///\param GR Graph type.
39 struct DfsDefaultTraits
41 ///The graph type the algorithm runs on.
43 ///\brief The type of the map that stores the last
44 ///edges of the %DFS paths.
46 ///The type of the map that stores the last
47 ///edges of the %DFS paths.
48 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
50 typedef typename Graph::template NodeMap<typename GR::Edge> PredMap;
51 ///Instantiates a PredMap.
53 ///This function instantiates a \ref PredMap.
54 ///\param G is the graph, to which we would like to define the PredMap.
55 ///\todo The graph alone may be insufficient to initialize
56 static PredMap *createPredMap(const GR &G)
58 return new PredMap(G);
61 ///The type of the map that indicates which nodes are processed.
63 ///The type of the map that indicates which nodes are processed.
64 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
65 ///\todo named parameter to set this type, function to read and write.
66 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
67 ///Instantiates a ProcessedMap.
69 ///This function instantiates a \ref ProcessedMap.
70 ///\param g is the graph, to which
71 ///we would like to define the \ref ProcessedMap
73 static ProcessedMap *createProcessedMap(const GR &g)
75 static ProcessedMap *createProcessedMap(const GR &)
78 return new ProcessedMap();
80 ///The type of the map that indicates which nodes are reached.
82 ///The type of the map that indicates which nodes are reached.
83 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
84 ///\todo named parameter to set this type, function to read and write.
85 typedef typename Graph::template NodeMap<bool> ReachedMap;
86 ///Instantiates a ReachedMap.
88 ///This function instantiates a \ref ReachedMap.
89 ///\param G is the graph, to which
90 ///we would like to define the \ref ReachedMap.
91 static ReachedMap *createReachedMap(const GR &G)
93 return new ReachedMap(G);
95 ///The type of the map that stores the dists of the nodes.
97 ///The type of the map that stores the dists of the nodes.
98 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
100 typedef typename Graph::template NodeMap<int> DistMap;
101 ///Instantiates a DistMap.
103 ///This function instantiates a \ref DistMap.
104 ///\param G is the graph, to which we would like to define the \ref DistMap
105 static DistMap *createDistMap(const GR &G)
107 return new DistMap(G);
111 ///%DFS algorithm class.
114 ///This class provides an efficient implementation of the %DFS algorithm.
116 ///\param GR The graph type the algorithm runs on. The default value is
117 ///\ref ListGraph. The value of GR is not used directly by Dfs, it
118 ///is only passed to \ref DfsDefaultTraits.
119 ///\param TR Traits class to set various data types used by the algorithm.
120 ///The default traits class is
121 ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
122 ///See \ref DfsDefaultTraits for the documentation of
123 ///a Dfs traits class.
125 ///\author Jacint Szabo and Alpar Juttner
126 ///\todo A compare object would be nice.
129 template <typename GR,
132 template <typename GR=ListGraph,
133 typename TR=DfsDefaultTraits<GR> >
138 * \brief \ref Exception for uninitialized parameters.
140 * This error represents problems in the initialization
141 * of the parameters of the algorithms.
143 class UninitializedParameter : public lemon::UninitializedParameter {
145 virtual const char* exceptionName() const {
146 return "lemon::Dfs::UninitializedParameter";
151 ///The type of the underlying graph.
152 typedef typename TR::Graph Graph;
154 typedef typename Graph::Node Node;
156 typedef typename Graph::NodeIt NodeIt;
158 typedef typename Graph::Edge Edge;
160 typedef typename Graph::OutEdgeIt OutEdgeIt;
162 ///\brief The type of the map that stores the last
163 ///edges of the %DFS paths.
164 typedef typename TR::PredMap PredMap;
165 ///The type of the map indicating which nodes are reached.
166 typedef typename TR::ReachedMap ReachedMap;
167 ///The type of the map indicating which nodes are processed.
168 typedef typename TR::ProcessedMap ProcessedMap;
169 ///The type of the map that stores the dists of the nodes.
170 typedef typename TR::DistMap DistMap;
172 /// Pointer to the underlying graph.
174 ///Pointer to the map of predecessors edges.
176 ///Indicates if \ref _pred is locally allocated (\c true) or not.
178 ///Pointer to the map of distances.
180 ///Indicates if \ref _dist is locally allocated (\c true) or not.
182 ///Pointer to the map of reached status of the nodes.
183 ReachedMap *_reached;
184 ///Indicates if \ref _reached is locally allocated (\c true) or not.
186 ///Pointer to the map of processed status of the nodes.
187 ProcessedMap *_processed;
188 ///Indicates if \ref _processed is locally allocated (\c true) or not.
189 bool local_processed;
191 std::vector<typename Graph::OutEdgeIt> _stack;
194 ///Creates the maps if necessary.
196 ///\todo Error if \c G are \c NULL.
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);
222 ///\name Named template parameters
227 struct DefPredMapTraits : public Traits {
229 static PredMap *createPredMap(const Graph &G)
231 throw UninitializedParameter();
234 ///\ref named-templ-param "Named parameter" for setting PredMap type
236 ///\ref named-templ-param "Named parameter" for setting PredMap type
239 struct DefPredMap : public Dfs<Graph, DefPredMapTraits<T> > {
240 typedef Dfs<Graph, DefPredMapTraits<T> > Create;
245 struct DefDistMapTraits : public Traits {
247 static DistMap *createDistMap(const Graph &G)
249 throw UninitializedParameter();
252 ///\ref named-templ-param "Named parameter" for setting DistMap type
254 ///\ref named-templ-param "Named parameter" for setting DistMap type
258 typedef Dfs<Graph, DefDistMapTraits<T> > Create;
262 struct DefReachedMapTraits : public Traits {
263 typedef T ReachedMap;
264 static ReachedMap *createReachedMap(const Graph &G)
266 throw UninitializedParameter();
269 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
271 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
274 struct DefReachedMap {
275 typedef Dfs< Graph, DefReachedMapTraits<T> > Create;
279 struct DefProcessedMapTraits : public Traits {
280 typedef T ProcessedMap;
281 static ProcessedMap *createProcessedMap(const Graph &G)
283 throw UninitializedParameter();
286 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
288 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
291 struct DefProcessedMap : public Dfs< Graph, DefProcessedMapTraits<T> > {
292 typedef Dfs< Graph, DefProcessedMapTraits<T> > Create;
295 struct DefGraphProcessedMapTraits : public Traits {
296 typedef typename Graph::template NodeMap<bool> ProcessedMap;
297 static ProcessedMap *createProcessedMap(const Graph &G)
299 return new ProcessedMap(G);
302 ///\brief \ref named-templ-param "Named parameter"
303 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
305 ///\ref named-templ-param "Named parameter"
306 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
307 ///If you don't set it explicitely, it will be automatically allocated.
309 class DefProcessedMapToBeDefaultMap :
310 public Dfs< Graph, DefGraphProcessedMapTraits> {
311 typedef Dfs< Graph, DefGraphProcessedMapTraits> Create;
320 ///\param _G the graph the algorithm will run on.
322 Dfs(const Graph& _G) :
324 _pred(NULL), local_pred(false),
325 // _predNode(NULL), local_predNode(false),
326 _dist(NULL), local_dist(false),
327 _reached(NULL), local_reached(false),
328 _processed(NULL), local_processed(false)
334 if(local_pred) delete _pred;
335 // if(local_predNode) delete _predNode;
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 predecessor nodes.
360 // ///Sets the map storing the predecessor nodes.
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 &predNodeMap(PredNodeMap &m)
367 // if(local_predNode) {
369 // local_predNode=false;
375 ///Sets the map storing the distances calculated by the algorithm.
377 ///Sets the map storing the distances calculated by the algorithm.
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 &distMap(DistMap &m)
392 ///Sets the map indicating if a node is reached.
394 ///Sets the map indicating if a node is reached.
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 &reachedMap(ReachedMap &m)
409 ///Sets the map indicating if a node is processed.
411 ///Sets the map indicating if a node is processed.
412 ///If you don't use this function before calling \ref run(),
413 ///it will allocate one. The destuctor deallocates this
414 ///automatically allocated map, of course.
415 ///\return <tt> (*this) </tt>
416 Dfs &processedMap(ProcessedMap &m)
418 if(local_processed) {
420 local_processed=false;
427 ///\name Execution control
428 ///The simplest way to execute the algorithm is to use
429 ///one of the member functions called \c run(...).
431 ///If you need more control on the execution,
432 ///first you must call \ref init(), then you can add several source nodes
433 ///with \ref addSource().
434 ///Finally \ref start() will perform the actual path
439 ///Initializes the internal data structures.
441 ///Initializes the internal data structures.
446 _stack.resize(countNodes(*G));
448 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
449 _pred->set(u,INVALID);
450 // _predNode->set(u,INVALID);
451 _reached->set(u,false);
452 _processed->set(u,false);
456 ///Adds a new source node.
458 ///Adds a new source node to the set of nodes to be processed.
460 ///\bug dists are wrong (or at least strange) in case of multiple sources.
461 void addSource(Node s)
465 _reached->set(s,true);
466 _pred->set(s,INVALID);
467 // _predNode->set(u,INVALID);
470 _stack[++_stack_head]=e;
471 _dist->set(s,_stack_head);
474 _processed->set(s,true);
480 ///Processes the next edge.
482 ///Processes the next edge.
484 ///\return The processed edge.
486 ///\pre The stack must not be empty!
487 Edge processNextEdge()
490 Edge e=_stack[_stack_head];
491 if(!(*_reached)[m=G->target(e)]) {
493 _reached->set(m,true);
494 // _pred_node->set(m,G->source(e));
496 _stack[_stack_head] = OutEdgeIt(*G, m);
497 _dist->set(m,_stack_head);
501 ++_stack[_stack_head];
503 //'m' is now the (original) source of the _stack[_stack_head]
504 while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
505 _processed->set(m,true);
508 m=G->source(_stack[_stack_head]);
509 ++_stack[_stack_head];
514 ///Next edge to be processed.
516 ///Next edge to be processed.
518 ///\return The next edge to be processed or INVALID if the stack is
522 return _stack_head>=0?_stack[_stack_head]:INVALID;
525 ///\brief Returns \c false if there are nodes
526 ///to be processed in the queue
528 ///Returns \c false if there are nodes
529 ///to be processed in the queue
531 ///\todo This should be called emptyStack() or some "neutral" name.
532 bool emptyQueue() { return _stack_head<0; }
533 ///Returns the number of the nodes to be processed.
535 ///Returns the number of the nodes to be processed in the queue.
537 ///\todo This should be called stackSize() or some "neutral" name.
538 int queueSize() { return _stack_head+1; }
540 ///Executes the algorithm.
542 ///Executes the algorithm.
544 ///\pre init() must be called and at least one node should be added
545 ///with addSource() before using this function.
547 ///This method runs the %DFS algorithm from the root node(s)
550 ///%DFS path to each node. The algorithm computes
552 ///- The distance of each node from the root(s) in the %DFS tree.
556 while ( !emptyQueue() ) processNextEdge();
559 ///Executes the algorithm until \c dest is reached.
561 ///Executes the algorithm until \c dest is reached.
563 ///\pre init() must be called and at least one node should be added
564 ///with addSource() before using this function.
566 ///This method runs the %DFS algorithm from the root node(s)
569 ///%DFS path to \c dest. The algorithm computes
570 ///- The %DFS path to \c dest.
571 ///- The distance of \c dest from the root(s) in the %DFS tree.
573 void start(Node dest)
575 while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
579 ///Executes the algorithm until a condition is met.
581 ///Executes the algorithm until a condition is met.
583 ///\pre init() must be called and at least one node should be added
584 ///with addSource() before using this function.
586 ///\param nm must be a bool (or convertible) edge map. The algorithm
587 ///will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>.
589 ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c nm is an edge map,
592 void start(const NM &nm)
594 while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge();
597 ///Runs %DFS algorithm from node \c s.
599 ///This method runs the %DFS algorithm from a root node \c s
602 ///%DFS path to each node. The algorithm computes
604 ///- The distance of each node from the root in the %DFS tree.
606 ///\note d.run(s) is just a shortcut of the following code.
618 ///Finds the %DFS path between \c s and \c t.
620 ///Finds the %DFS path between \c s and \c t.
622 ///\return The length of the %DFS s---t path if there exists one,
624 ///\note Apart from the return value, d.run(s,t) is
625 ///just a shortcut of the following code.
631 int run(Node s,Node t) {
635 return reached(t)?_stack_head+1:0;
640 ///\name Query Functions
641 ///The result of the %DFS algorithm can be obtained using these
643 ///Before the use of these functions,
644 ///either run() or start() must be called.
648 ///Copies the path to \c t on the DFS tree into \c p
650 ///This function copies the path to \c t on the DFS tree into \c p.
651 ///If \c t is a source itself or unreachable, then it does not
653 ///\todo Is this the right way to handle unreachable nodes?
655 ///\return Returns \c true if a path to \c t was actually copied to \c p,
656 ///\c false otherwise.
659 bool getPath(P &p,Node t)
663 typename P::Builder b(p);
664 for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
665 b.pushFront(pred(t));
672 ///The distance of a node from the root(s).
674 ///Returns the distance of a node from the root(s).
675 ///\pre \ref run() must be called before using this function.
676 ///\warning If node \c v is unreachable from the root(s) then the return value
677 ///of this funcion is undefined.
678 int dist(Node v) const { return (*_dist)[v]; }
680 ///Returns the 'previous edge' of the %DFS tree.
682 ///For a node \c v it returns the 'previous edge'
684 ///i.e. it returns the last edge of a %DFS path from the root(s) to \c
685 ///v. It is \ref INVALID
686 ///if \c v is unreachable from the root(s) or \c v is a root. The
687 ///%DFS tree used here is equal to the %DFS tree used in
689 ///\pre Either \ref run() or \ref start() must be called before using
691 ///\todo predEdge could be a better name.
692 Edge pred(Node v) const { return (*_pred)[v];}
694 ///Returns the 'previous node' of the %DFS tree.
696 ///For a node \c v it returns the 'previous node'
698 ///i.e. it returns the last but one node from a %DFS path from the
700 ///It is INVALID if \c v is unreachable from the root(s) or
701 ///if \c v itself a root.
702 ///The %DFS tree used here is equal to the %DFS
703 ///tree used in \ref pred().
704 ///\pre Either \ref run() or \ref start() must be called before
705 ///using this function.
706 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
707 G->source((*_pred)[v]); }
709 ///Returns a reference to the NodeMap of distances.
711 ///Returns a reference to the NodeMap of distances.
712 ///\pre Either \ref run() or \ref init() must
713 ///be called before using this function.
714 const DistMap &distMap() const { return *_dist;}
716 ///Returns a reference to the %DFS edge-tree map.
718 ///Returns a reference to the NodeMap of the edges of the
720 ///\pre Either \ref run() or \ref init()
721 ///must be called before using this function.
722 const PredMap &predMap() const { return *_pred;}
724 // ///Returns a reference to the map of nodes of %DFS paths.
726 // ///Returns a reference to the NodeMap of the last but one nodes of the
728 // ///\pre \ref run() must be called before using this function.
729 // const PredNodeMap &predNodeMap() const { return *_predNode;}
731 ///Checks if a node is reachable from the root.
733 ///Returns \c true if \c v is reachable from the root(s).
734 ///\warning The source nodes are inditated as unreachable.
735 ///\pre Either \ref run() or \ref start()
736 ///must be called before using this function.
738 bool reached(Node v) { return (*_reached)[v]; }
743 ///Default traits class of Dfs function.
745 ///Default traits class of Dfs function.
746 ///\param GR Graph type.
748 struct DfsWizardDefaultTraits
750 ///The graph type the algorithm runs on.
752 ///\brief The type of the map that stores the last
753 ///edges of the %DFS paths.
755 ///The type of the map that stores the last
756 ///edges of the %DFS paths.
757 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
759 typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
760 ///Instantiates a PredMap.
762 ///This function instantiates a \ref PredMap.
763 ///\param g is the graph, to which we would like to define the PredMap.
764 ///\todo The graph alone may be insufficient to initialize
766 static PredMap *createPredMap(const GR &g)
768 static PredMap *createPredMap(const GR &)
771 return new PredMap();
773 // ///\brief The type of the map that stores the last but one
774 // ///nodes of the %DFS paths.
776 // ///The type of the map that stores the last but one
777 // ///nodes of the %DFS paths.
778 // ///It must meet the \ref concept::WriteMap "WriteMap" concept.
780 // typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
781 // ///Instantiates a PredNodeMap.
783 // ///This function instantiates a \ref PredNodeMap.
784 // ///\param G is the graph, to which
785 // ///we would like to define the \ref PredNodeMap
786 // static PredNodeMap *createPredNodeMap(const GR &G)
788 // return new PredNodeMap();
791 ///The type of the map that indicates which nodes are processed.
793 ///The type of the map that indicates which nodes are processed.
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 NullMap<typename Graph::Node,bool> ProcessedMap;
797 ///Instantiates a ProcessedMap.
799 ///This function instantiates a \ref ProcessedMap.
800 ///\param g is the graph, to which
801 ///we would like to define the \ref ProcessedMap
803 static ProcessedMap *createProcessedMap(const GR &g)
805 static ProcessedMap *createProcessedMap(const GR &)
808 return new ProcessedMap();
810 ///The type of the map that indicates which nodes are reached.
812 ///The type of the map that indicates which nodes are reached.
813 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
814 ///\todo named parameter to set this type, function to read and write.
815 typedef typename Graph::template NodeMap<bool> ReachedMap;
816 ///Instantiates a ReachedMap.
818 ///This function instantiates a \ref ReachedMap.
819 ///\param G is the graph, to which
820 ///we would like to define the \ref ReachedMap.
821 static ReachedMap *createReachedMap(const GR &G)
823 return new ReachedMap(G);
825 ///The type of the map that stores the dists of the nodes.
827 ///The type of the map that stores the dists of the nodes.
828 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
830 typedef NullMap<typename Graph::Node,int> DistMap;
831 ///Instantiates a DistMap.
833 ///This function instantiates a \ref DistMap.
834 ///\param g is the graph, to which we would like to define the \ref DistMap
836 static DistMap *createDistMap(const GR &g)
838 static DistMap *createDistMap(const GR &)
841 return new DistMap();
845 /// Default traits used by \ref DfsWizard
847 /// To make it easier to use Dfs algorithm
848 ///we have created a wizard class.
849 /// This \ref DfsWizard class needs default traits,
850 ///as well as the \ref Dfs class.
851 /// The \ref DfsWizardBase is a class to be the default traits of the
852 /// \ref DfsWizard class.
854 class DfsWizardBase : public DfsWizardDefaultTraits<GR>
857 typedef DfsWizardDefaultTraits<GR> Base;
859 /// Type of the nodes in the graph.
860 typedef typename Base::Graph::Node Node;
862 /// Pointer to the underlying graph.
864 ///Pointer to the map of reached nodes.
866 ///Pointer to the map of processed nodes.
868 ///Pointer to the map of predecessors edges.
870 // ///Pointer to the map of predecessors nodes.
872 ///Pointer to the map of distances.
874 ///Pointer to the source node.
880 /// This constructor does not require parameters, therefore it initiates
881 /// all of the attributes to default values (0, INVALID).
882 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
884 _dist(0), _source(INVALID) {}
888 /// This constructor requires some parameters,
889 /// listed in the parameters list.
890 /// Others are initiated to 0.
891 /// \param g is the initial value of \ref _g
892 /// \param s is the initial value of \ref _source
893 DfsWizardBase(const GR &g, Node s=INVALID) :
894 _g((void *)&g), _reached(0), _processed(0), _pred(0),
896 _dist(0), _source(s) {}
900 /// A class to make the usage of the Dfs algorithm easier
902 /// This class is created to make it easier to use the Dfs algorithm.
903 /// It uses the functions and features of the plain \ref Dfs,
904 /// but it is much simpler to use it.
906 /// Simplicity means that the way to change the types defined
907 /// in the traits class is based on functions that returns the new class
908 /// and not on templatable built-in classes.
909 /// When using the plain \ref Dfs
910 /// the new class with the modified type comes from
911 /// the original class by using the ::
912 /// operator. In the case of \ref DfsWizard only
913 /// a function have to be called and it will
914 /// return the needed class.
916 /// It does not have own \ref run method. When its \ref run method is called
917 /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run
920 class DfsWizard : public TR
924 ///The type of the underlying graph.
925 typedef typename TR::Graph Graph;
927 typedef typename Graph::Node Node;
929 typedef typename Graph::NodeIt NodeIt;
931 typedef typename Graph::Edge Edge;
933 typedef typename Graph::OutEdgeIt OutEdgeIt;
935 ///\brief The type of the map that stores
937 typedef typename TR::ReachedMap ReachedMap;
938 ///\brief The type of the map that stores
939 ///the processed nodes
940 typedef typename TR::ProcessedMap ProcessedMap;
941 ///\brief The type of the map that stores the last
942 ///edges of the %DFS paths.
943 typedef typename TR::PredMap PredMap;
944 // ///\brief The type of the map that stores the last but one
945 // ///nodes of the %DFS paths.
946 // typedef typename TR::PredNodeMap PredNodeMap;
947 ///The type of the map that stores the distances of the nodes.
948 typedef typename TR::DistMap DistMap;
952 DfsWizard() : TR() {}
954 /// Constructor that requires parameters.
956 /// Constructor that requires parameters.
957 /// These parameters will be the default values for the traits class.
958 DfsWizard(const Graph &g, Node s=INVALID) :
962 DfsWizard(const TR &b) : TR(b) {}
966 ///Runs Dfs algorithm from a given node.
968 ///Runs Dfs algorithm from a given node.
969 ///The node can be given by the \ref source function.
972 if(Base::_source==INVALID) throw UninitializedParameter();
973 Dfs<Graph,TR> alg(*(Graph*)Base::_g);
974 if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached);
975 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
976 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
977 // if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
978 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
979 alg.run(Base::_source);
982 ///Runs Dfs algorithm from the given node.
984 ///Runs Dfs algorithm from the given node.
985 ///\param s is the given source.
993 struct DefPredMapBase : public Base {
995 static PredMap *createPredMap(const Graph &) { return 0; };
996 DefPredMapBase(const TR &b) : TR(b) {}
999 ///\brief \ref named-templ-param "Named parameter"
1000 ///function for setting PredMap type
1002 /// \ref named-templ-param "Named parameter"
1003 ///function for setting PredMap type
1006 DfsWizard<DefPredMapBase<T> > predMap(const T &t)
1008 Base::_pred=(void *)&t;
1009 return DfsWizard<DefPredMapBase<T> >(*this);
1014 struct DefReachedMapBase : public Base {
1015 typedef T ReachedMap;
1016 static ReachedMap *createReachedMap(const Graph &) { return 0; };
1017 DefReachedMapBase(const TR &b) : TR(b) {}
1020 ///\brief \ref named-templ-param "Named parameter"
1021 ///function for setting ReachedMap
1023 /// \ref named-templ-param "Named parameter"
1024 ///function for setting ReachedMap
1027 DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1029 Base::_pred=(void *)&t;
1030 return DfsWizard<DefReachedMapBase<T> >(*this);
1035 struct DefProcessedMapBase : public Base {
1036 typedef T ProcessedMap;
1037 static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
1038 DefProcessedMapBase(const TR &b) : TR(b) {}
1041 ///\brief \ref named-templ-param "Named parameter"
1042 ///function for setting ProcessedMap
1044 /// \ref named-templ-param "Named parameter"
1045 ///function for setting ProcessedMap
1048 DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1050 Base::_pred=(void *)&t;
1051 return DfsWizard<DefProcessedMapBase<T> >(*this);
1055 // template<class T>
1056 // struct DefPredNodeMapBase : public Base {
1057 // typedef T PredNodeMap;
1058 // static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
1059 // DefPredNodeMapBase(const TR &b) : TR(b) {}
1062 // ///\brief \ref named-templ-param "Named parameter"
1063 // ///function for setting PredNodeMap type
1065 // /// \ref named-templ-param "Named parameter"
1066 // ///function for setting PredNodeMap type
1068 // template<class T>
1069 // DfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1071 // Base::_predNode=(void *)&t;
1072 // return DfsWizard<DefPredNodeMapBase<T> >(*this);
1076 struct DefDistMapBase : public Base {
1078 static DistMap *createDistMap(const Graph &) { return 0; };
1079 DefDistMapBase(const TR &b) : TR(b) {}
1082 ///\brief \ref named-templ-param "Named parameter"
1083 ///function for setting DistMap type
1085 /// \ref named-templ-param "Named parameter"
1086 ///function for setting DistMap type
1089 DfsWizard<DefDistMapBase<T> > distMap(const T &t)
1091 Base::_dist=(void *)&t;
1092 return DfsWizard<DefDistMapBase<T> >(*this);
1095 /// Sets the source node, from which the Dfs algorithm runs.
1097 /// Sets the source node, from which the Dfs algorithm runs.
1098 /// \param s is the source node.
1099 DfsWizard<TR> &source(Node s)
1107 ///Function type interface for Dfs algorithm.
1109 /// \ingroup flowalgs
1110 ///Function type interface for Dfs algorithm.
1112 ///This function also has several
1113 ///\ref named-templ-func-param "named parameters",
1114 ///they are declared as the members of class \ref DfsWizard.
1116 ///example shows how to use these parameters.
1118 /// dfs(g,source).predMap(preds).run();
1120 ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
1121 ///to the end of the parameter list.
1125 DfsWizard<DfsWizardBase<GR> >
1126 dfs(const GR &g,typename GR::Node s=INVALID)
1128 return DfsWizard<DfsWizardBase<GR> >(g,s);
1131 } //END OF NAMESPACE LEMON