Serious bugfix.
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);
60 // ///\brief The type of the map that stores the last but one
61 // ///nodes of the %DFS paths.
63 // ///The type of the map that stores the last but one
64 // ///nodes of the %DFS paths.
65 // ///It must meet the \ref concept::WriteMap "WriteMap" concept.
67 // typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
68 // ///Instantiates a PredNodeMap.
70 // ///This function instantiates a \ref PredNodeMap.
71 // ///\param G is the graph, to which
72 // ///we would like to define the \ref PredNodeMap
73 // static PredNodeMap *createPredNodeMap(const GR &G)
75 // return new PredNodeMap();
78 ///The type of the map that indicates which nodes are processed.
80 ///The type of the map that indicates which nodes are processed.
81 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
82 ///\todo named parameter to set this type, function to read and write.
83 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
84 ///Instantiates a ProcessedMap.
86 ///This function instantiates a \ref ProcessedMap.
87 ///\param g is the graph, to which
88 ///we would like to define the \ref ProcessedMap
90 static ProcessedMap *createProcessedMap(const GR &g)
92 static ProcessedMap *createProcessedMap(const GR &)
95 return new ProcessedMap();
97 ///The type of the map that indicates which nodes are reached.
99 ///The type of the map that indicates which nodes are reached.
100 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
101 ///\todo named parameter to set this type, function to read and write.
102 typedef typename Graph::template NodeMap<bool> ReachedMap;
103 ///Instantiates a ReachedMap.
105 ///This function instantiates a \ref ReachedMap.
106 ///\param G is the graph, to which
107 ///we would like to define the \ref ReachedMap.
108 static ReachedMap *createReachedMap(const GR &G)
110 return new ReachedMap(G);
112 ///The type of the map that stores the dists of the nodes.
114 ///The type of the map that stores the dists of the nodes.
115 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
117 typedef typename Graph::template NodeMap<int> DistMap;
118 ///Instantiates a DistMap.
120 ///This function instantiates a \ref DistMap.
121 ///\param G is the graph, to which we would like to define the \ref DistMap
122 static DistMap *createDistMap(const GR &G)
124 return new DistMap(G);
128 ///%DFS algorithm class.
131 ///This class provides an efficient implementation of the %DFS algorithm.
133 ///\param GR The graph type the algorithm runs on. The default value is
134 ///\ref ListGraph. The value of GR is not used directly by Dfs, it
135 ///is only passed to \ref DfsDefaultTraits.
136 ///\param TR Traits class to set various data types used by the algorithm.
137 ///The default traits class is
138 ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
139 ///See \ref DfsDefaultTraits for the documentation of
140 ///a Dfs traits class.
142 ///\author Jacint Szabo and Alpar Juttner
143 ///\todo A compare object would be nice.
146 template <typename GR,
149 template <typename GR=ListGraph,
150 typename TR=DfsDefaultTraits<GR> >
155 * \brief \ref Exception for uninitialized parameters.
157 * This error represents problems in the initialization
158 * of the parameters of the algorithms.
160 class UninitializedParameter : public lemon::UninitializedParameter {
162 virtual const char* exceptionName() const {
163 return "lemon::Dfs::UninitializedParameter";
168 ///The type of the underlying graph.
169 typedef typename TR::Graph Graph;
171 typedef typename Graph::Node Node;
173 typedef typename Graph::NodeIt NodeIt;
175 typedef typename Graph::Edge Edge;
177 typedef typename Graph::OutEdgeIt OutEdgeIt;
179 ///\brief The type of the map that stores the last
180 ///edges of the %DFS paths.
181 typedef typename TR::PredMap PredMap;
182 // ///\brief The type of the map that stores the last but one
183 // ///nodes of the %DFS paths.
184 // typedef typename TR::PredNodeMap PredNodeMap;
185 ///The type of the map indicating which nodes are reached.
186 typedef typename TR::ReachedMap ReachedMap;
187 ///The type of the map indicating which nodes are processed.
188 typedef typename TR::ProcessedMap ProcessedMap;
189 ///The type of the map that stores the dists of the nodes.
190 typedef typename TR::DistMap DistMap;
192 /// Pointer to the underlying graph.
194 ///Pointer to the map of predecessors edges.
196 ///Indicates if \ref _pred is locally allocated (\c true) or not.
198 // ///Pointer to the map of predecessors nodes.
199 // PredNodeMap *_predNode;
200 // ///Indicates if \ref _predNode is locally allocated (\c true) or not.
201 // bool local_predNode;
202 ///Pointer to the map of distances.
204 ///Indicates if \ref _dist is locally allocated (\c true) or not.
206 ///Pointer to the map of reached status of the nodes.
207 ReachedMap *_reached;
208 ///Indicates if \ref _reached is locally allocated (\c true) or not.
210 ///Pointer to the map of processed status of the nodes.
211 ProcessedMap *_processed;
212 ///Indicates if \ref _processed is locally allocated (\c true) or not.
213 bool local_processed;
215 std::vector<typename Graph::OutEdgeIt> _stack;
217 // ///The source node of the last execution.
220 ///Creates the maps if necessary.
222 ///\todo Error if \c G are \c NULL.
223 ///\todo Better memory allocation (instead of new).
228 _pred = Traits::createPredMap(*G);
231 // local_predNode = true;
232 // _predNode = Traits::createPredNodeMap(*G);
236 _dist = Traits::createDistMap(*G);
239 local_reached = true;
240 _reached = Traits::createReachedMap(*G);
243 local_processed = true;
244 _processed = Traits::createProcessedMap(*G);
250 ///\name Named template parameters
255 struct DefPredMapTraits : public Traits {
257 static PredMap *createPredMap(const Graph &G)
259 throw UninitializedParameter();
262 ///\ref named-templ-param "Named parameter" for setting PredMap type
264 ///\ref named-templ-param "Named parameter" for setting PredMap type
267 class DefPredMap : public Dfs< Graph,
268 DefPredMapTraits<T> > { };
270 // template <class T>
271 // struct DefPredNodeMapTraits : public Traits {
272 // typedef T PredNodeMap;
273 // static PredNodeMap *createPredNodeMap(const Graph &G)
275 // throw UninitializedParameter();
278 // ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
280 // ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
282 // template <class T>
283 // class DefPredNodeMap : public Dfs< Graph,
285 // DefPredNodeMapTraits<T> > { };
288 struct DefDistMapTraits : public Traits {
290 static DistMap *createDistMap(const Graph &G)
292 throw UninitializedParameter();
295 ///\ref named-templ-param "Named parameter" for setting DistMap type
297 ///\ref named-templ-param "Named parameter" for setting DistMap type
300 class DefDistMap : public Dfs< Graph,
301 DefDistMapTraits<T> > { };
304 struct DefReachedMapTraits : public Traits {
305 typedef T ReachedMap;
306 static ReachedMap *createReachedMap(const Graph &G)
308 throw UninitializedParameter();
311 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
313 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
316 class DefReachedMap : public Dfs< Graph,
317 DefReachedMapTraits<T> > { };
319 struct DefGraphReachedMapTraits : public Traits {
320 typedef typename Graph::template NodeMap<bool> ReachedMap;
321 static ReachedMap *createReachedMap(const Graph &G)
323 return new ReachedMap(G);
327 struct DefProcessedMapTraits : public Traits {
328 typedef T ProcessedMap;
329 static ProcessedMap *createProcessedMap(const Graph &G)
331 throw UninitializedParameter();
334 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
336 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
339 class DefProcessedMap : public Dfs< Graph,
340 DefProcessedMapTraits<T> > { };
342 struct DefGraphProcessedMapTraits : public Traits {
343 typedef typename Graph::template NodeMap<bool> ProcessedMap;
344 static ProcessedMap *createProcessedMap(const Graph &G)
346 return new ProcessedMap(G);
349 ///\brief \ref named-templ-param "Named parameter"
350 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
352 ///\ref named-templ-param "Named parameter"
353 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
354 ///If you don't set it explicitely, it will be automatically allocated.
356 class DefProcessedMapToBeDefaultMap :
358 DefGraphProcessedMapTraits> { };
366 ///\param _G the graph the algorithm will run on.
368 Dfs(const Graph& _G) :
370 _pred(NULL), local_pred(false),
371 // _predNode(NULL), local_predNode(false),
372 _dist(NULL), local_dist(false),
373 _reached(NULL), local_reached(false),
374 _processed(NULL), local_processed(false)
380 if(local_pred) delete _pred;
381 // if(local_predNode) delete _predNode;
382 if(local_dist) delete _dist;
383 if(local_reached) delete _reached;
384 if(local_processed) delete _processed;
387 ///Sets the map storing the predecessor edges.
389 ///Sets the map storing the predecessor edges.
390 ///If you don't use this function before calling \ref run(),
391 ///it will allocate one. The destuctor deallocates this
392 ///automatically allocated map, of course.
393 ///\return <tt> (*this) </tt>
394 Dfs &predMap(PredMap &m)
404 // ///Sets the map storing the predecessor nodes.
406 // ///Sets the map storing the predecessor nodes.
407 // ///If you don't use this function before calling \ref run(),
408 // ///it will allocate one. The destuctor deallocates this
409 // ///automatically allocated map, of course.
410 // ///\return <tt> (*this) </tt>
411 // Dfs &predNodeMap(PredNodeMap &m)
413 // if(local_predNode) {
415 // local_predNode=false;
421 ///Sets the map storing the distances calculated by the algorithm.
423 ///Sets the map storing the distances calculated by the algorithm.
424 ///If you don't use this function before calling \ref run(),
425 ///it will allocate one. The destuctor deallocates this
426 ///automatically allocated map, of course.
427 ///\return <tt> (*this) </tt>
428 Dfs &distMap(DistMap &m)
438 ///Sets the map indicating if a node is reached.
440 ///Sets the map indicating if a node is reached.
441 ///If you don't use this function before calling \ref run(),
442 ///it will allocate one. The destuctor deallocates this
443 ///automatically allocated map, of course.
444 ///\return <tt> (*this) </tt>
445 Dfs &reachedMap(ReachedMap &m)
455 ///Sets the map indicating if a node is processed.
457 ///Sets the map indicating if a node is processed.
458 ///If you don't use this function before calling \ref run(),
459 ///it will allocate one. The destuctor deallocates this
460 ///automatically allocated map, of course.
461 ///\return <tt> (*this) </tt>
462 Dfs &processedMap(ProcessedMap &m)
464 if(local_processed) {
466 local_processed=false;
473 ///\name Execution control
474 ///The simplest way to execute the algorithm is to use
475 ///one of the member functions called \c run(...).
477 ///If you need more control on the execution,
478 ///first you must call \ref init(), then you can add several source nodes
479 ///with \ref addSource().
480 ///Finally \ref start() will perform the actual path
485 ///Initializes the internal data structures.
487 ///Initializes the internal data structures.
492 _stack.resize(countNodes(*G));
494 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
495 _pred->set(u,INVALID);
496 // _predNode->set(u,INVALID);
497 _reached->set(u,false);
498 _processed->set(u,false);
502 ///Adds a new source node.
504 ///Adds a new source node to the set of nodes to be processed.
506 ///\bug dists are wrong (or at least strange) in case of multiple sources.
507 void addSource(Node s)
511 _reached->set(s,true);
512 _pred->set(s,INVALID);
513 // _predNode->set(u,INVALID);
514 _stack[++_stack_head]=OutEdgeIt(*G,s);
515 _dist->set(s,_stack_head);
519 ///Processes the next edge.
521 ///Processes the next edge.
523 ///\return The processed edge.
525 ///\pre The stack must not be empty!
526 Edge processNextEdge()
529 Edge e=_stack[_stack_head];
530 if(!(*_reached)[m=G->target(e)]) {
532 _reached->set(m,true);
533 // _pred_node->set(m,G->source(e));
535 _stack[_stack_head] = OutEdgeIt(*G, m);
536 _dist->set(m,_stack_head);
540 ++_stack[_stack_head];
542 //'m' is now the (original) source of the _stack[_stack_head]
543 while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
544 _processed->set(m,true);
547 m=G->source(_stack[_stack_head]);
548 ++_stack[_stack_head];
554 ///\brief Returns \c false if there are nodes
555 ///to be processed in the queue
557 ///Returns \c false if there are nodes
558 ///to be processed in the queue
559 bool emptyQueue() { return _stack_head<0; }
560 ///Returns the number of the nodes to be processed.
562 ///Returns the number of the nodes to be processed in the queue.
564 int queueSize() { return _stack_head+1; }
566 ///Executes the algorithm.
568 ///Executes the algorithm.
570 ///\pre init() must be called and at least one node should be added
571 ///with addSource() before using this function.
573 ///This method runs the %DFS algorithm from the root node(s)
576 ///%DFS path to each node. The algorithm computes
578 ///- The distance of each node from the root(s) in the %DFS tree.
582 while ( !emptyQueue() ) processNextEdge();
585 ///Executes the algorithm until \c dest is reached.
587 ///Executes the algorithm until \c dest is reached.
589 ///\pre init() must be called and at least one node should be added
590 ///with addSource() before using this function.
592 ///This method runs the %DFS algorithm from the root node(s)
595 ///%DFS path to \c dest. The algorithm computes
596 ///- The %DFS path to \c dest.
597 ///- The distance of \c dest from the root(s) in the %DFS tree.
599 void start(Node dest)
601 while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
605 ///Executes the algorithm until a condition is met.
607 ///Executes the algorithm until a condition is met.
609 ///\pre init() must be called and at least one node should be added
610 ///with addSource() before using this function.
612 ///\param nm must be a bool (or convertible) edge map. The algorithm
613 ///will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>.
615 ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c nm is an edge map,
618 void start(const NM &nm)
620 while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge();
623 ///Runs %DFS algorithm from node \c s.
625 ///This method runs the %DFS algorithm from a root node \c s
628 ///%DFS path to each node. The algorithm computes
630 ///- The distance of each node from the root in the %DFS tree.
632 ///\note d.run(s) is just a shortcut of the following code.
644 ///Finds the %DFS path between \c s and \c t.
646 ///Finds the %DFS path between \c s and \c t.
648 ///\return The length of the %DFS s---t path if there exists one,
650 ///\note Apart from the return value, d.run(s,t) is
651 ///just a shortcut of the following code.
657 int run(Node s,Node t) {
661 return reached(t)?_stack_head+1:0;
666 ///\name Query Functions
667 ///The result of the %DFS algorithm can be obtained using these
669 ///Before the use of these functions,
670 ///either run() or start() must be called.
674 ///Copies the path to \c t on the DFS tree into \c p
676 ///This function copies the path to \c t on the DFS tree into \c p.
677 ///If \c t is a source itself or unreachable, then it does not
679 ///\todo Is this the right way to handle unreachable nodes?
681 ///\return Returns \c true if a path to \c t was actually copied to \c p,
682 ///\c false otherwise.
685 bool getPath(P &p,Node t)
689 typename P::Builder b(p);
690 for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
691 b.pushFront(pred(t));
698 ///The distance of a node from the root(s).
700 ///Returns the distance of a node from the root(s).
701 ///\pre \ref run() must be called before using this function.
702 ///\warning If node \c v is unreachable from the root(s) then the return value
703 ///of this funcion is undefined.
704 int dist(Node v) const { return (*_dist)[v]; }
706 ///Returns the 'previous edge' of the %DFS tree.
708 ///For a node \c v it returns the 'previous edge'
710 ///i.e. it returns the last edge of a %DFS path from the root(s) to \c
711 ///v. It is \ref INVALID
712 ///if \c v is unreachable from the root(s) or \c v is a root. The
713 ///%DFS tree used here is equal to the %DFS tree used in
715 ///\pre Either \ref run() or \ref start() must be called before using
717 ///\todo predEdge could be a better name.
718 Edge pred(Node v) const { return (*_pred)[v];}
720 ///Returns the 'previous node' of the %DFS tree.
722 ///For a node \c v it returns the 'previous node'
724 ///i.e. it returns the last but one node from a %DFS path from the
726 ///It is INVALID if \c v is unreachable from the root(s) or
727 ///if \c v itself a root.
728 ///The %DFS tree used here is equal to the %DFS
729 ///tree used in \ref pred().
730 ///\pre Either \ref run() or \ref start() must be called before
731 ///using this function.
732 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
733 G->source((*_pred)[v]); }
735 ///Returns a reference to the NodeMap of distances.
737 ///Returns a reference to the NodeMap of distances.
738 ///\pre Either \ref run() or \ref init() must
739 ///be called before using this function.
740 const DistMap &distMap() const { return *_dist;}
742 ///Returns a reference to the %DFS edge-tree map.
744 ///Returns a reference to the NodeMap of the edges of the
746 ///\pre Either \ref run() or \ref init()
747 ///must be called before using this function.
748 const PredMap &predMap() const { return *_pred;}
750 // ///Returns a reference to the map of nodes of %DFS paths.
752 // ///Returns a reference to the NodeMap of the last but one nodes of the
754 // ///\pre \ref run() must be called before using this function.
755 // const PredNodeMap &predNodeMap() const { return *_predNode;}
757 ///Checks if a node is reachable from the root.
759 ///Returns \c true if \c v is reachable from the root(s).
760 ///\warning The source nodes are inditated as unreachable.
761 ///\pre Either \ref run() or \ref start()
762 ///must be called before using this function.
764 bool reached(Node v) { return (*_reached)[v]; }
769 ///Default traits class of Dfs function.
771 ///Default traits class of Dfs function.
772 ///\param GR Graph type.
774 struct DfsWizardDefaultTraits
776 ///The graph type the algorithm runs on.
778 ///\brief The type of the map that stores the last
779 ///edges of the %DFS paths.
781 ///The type of the map that stores the last
782 ///edges of the %DFS paths.
783 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
785 typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
786 ///Instantiates a PredMap.
788 ///This function instantiates a \ref PredMap.
789 ///\param g is the graph, to which we would like to define the PredMap.
790 ///\todo The graph alone may be insufficient to initialize
792 static PredMap *createPredMap(const GR &g)
794 static PredMap *createPredMap(const GR &)
797 return new PredMap();
799 // ///\brief The type of the map that stores the last but one
800 // ///nodes of the %DFS paths.
802 // ///The type of the map that stores the last but one
803 // ///nodes of the %DFS paths.
804 // ///It must meet the \ref concept::WriteMap "WriteMap" concept.
806 // typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
807 // ///Instantiates a PredNodeMap.
809 // ///This function instantiates a \ref PredNodeMap.
810 // ///\param G is the graph, to which
811 // ///we would like to define the \ref PredNodeMap
812 // static PredNodeMap *createPredNodeMap(const GR &G)
814 // return new PredNodeMap();
817 ///The type of the map that indicates which nodes are processed.
819 ///The type of the map that indicates which nodes are processed.
820 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
821 ///\todo named parameter to set this type, function to read and write.
822 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
823 ///Instantiates a ProcessedMap.
825 ///This function instantiates a \ref ProcessedMap.
826 ///\param g is the graph, to which
827 ///we would like to define the \ref ProcessedMap
829 static ProcessedMap *createProcessedMap(const GR &g)
831 static ProcessedMap *createProcessedMap(const GR &)
834 return new ProcessedMap();
836 ///The type of the map that indicates which nodes are reached.
838 ///The type of the map that indicates which nodes are reached.
839 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
840 ///\todo named parameter to set this type, function to read and write.
841 typedef typename Graph::template NodeMap<bool> ReachedMap;
842 ///Instantiates a ReachedMap.
844 ///This function instantiates a \ref ReachedMap.
845 ///\param G is the graph, to which
846 ///we would like to define the \ref ReachedMap.
847 static ReachedMap *createReachedMap(const GR &G)
849 return new ReachedMap(G);
851 ///The type of the map that stores the dists of the nodes.
853 ///The type of the map that stores the dists of the nodes.
854 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
856 typedef NullMap<typename Graph::Node,int> DistMap;
857 ///Instantiates a DistMap.
859 ///This function instantiates a \ref DistMap.
860 ///\param g is the graph, to which we would like to define the \ref DistMap
862 static DistMap *createDistMap(const GR &g)
864 static DistMap *createDistMap(const GR &)
867 return new DistMap();
871 /// Default traits used by \ref DfsWizard
873 /// To make it easier to use Dfs algorithm
874 ///we have created a wizard class.
875 /// This \ref DfsWizard class needs default traits,
876 ///as well as the \ref Dfs class.
877 /// The \ref DfsWizardBase is a class to be the default traits of the
878 /// \ref DfsWizard class.
880 class DfsWizardBase : public DfsWizardDefaultTraits<GR>
883 typedef DfsWizardDefaultTraits<GR> Base;
885 /// Type of the nodes in the graph.
886 typedef typename Base::Graph::Node Node;
888 /// Pointer to the underlying graph.
890 ///Pointer to the map of reached nodes.
892 ///Pointer to the map of processed nodes.
894 ///Pointer to the map of predecessors edges.
896 // ///Pointer to the map of predecessors nodes.
898 ///Pointer to the map of distances.
900 ///Pointer to the source node.
906 /// This constructor does not require parameters, therefore it initiates
907 /// all of the attributes to default values (0, INVALID).
908 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
910 _dist(0), _source(INVALID) {}
914 /// This constructor requires some parameters,
915 /// listed in the parameters list.
916 /// Others are initiated to 0.
917 /// \param g is the initial value of \ref _g
918 /// \param s is the initial value of \ref _source
919 DfsWizardBase(const GR &g, Node s=INVALID) :
920 _g((void *)&g), _reached(0), _processed(0), _pred(0),
922 _dist(0), _source(s) {}
926 /// A class to make the usage of the Dfs algorithm easier
928 /// This class is created to make it easier to use the Dfs algorithm.
929 /// It uses the functions and features of the plain \ref Dfs,
930 /// but it is much simpler to use it.
932 /// Simplicity means that the way to change the types defined
933 /// in the traits class is based on functions that returns the new class
934 /// and not on templatable built-in classes.
935 /// When using the plain \ref Dfs
936 /// the new class with the modified type comes from
937 /// the original class by using the ::
938 /// operator. In the case of \ref DfsWizard only
939 /// a function have to be called and it will
940 /// return the needed class.
942 /// It does not have own \ref run method. When its \ref run method is called
943 /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run
946 class DfsWizard : public TR
950 ///The type of the underlying graph.
951 typedef typename TR::Graph Graph;
953 typedef typename Graph::Node Node;
955 typedef typename Graph::NodeIt NodeIt;
957 typedef typename Graph::Edge Edge;
959 typedef typename Graph::OutEdgeIt OutEdgeIt;
961 ///\brief The type of the map that stores
963 typedef typename TR::ReachedMap ReachedMap;
964 ///\brief The type of the map that stores
965 ///the processed nodes
966 typedef typename TR::ProcessedMap ProcessedMap;
967 ///\brief The type of the map that stores the last
968 ///edges of the %DFS paths.
969 typedef typename TR::PredMap PredMap;
970 // ///\brief The type of the map that stores the last but one
971 // ///nodes of the %DFS paths.
972 // typedef typename TR::PredNodeMap PredNodeMap;
973 ///The type of the map that stores the distances of the nodes.
974 typedef typename TR::DistMap DistMap;
978 DfsWizard() : TR() {}
980 /// Constructor that requires parameters.
982 /// Constructor that requires parameters.
983 /// These parameters will be the default values for the traits class.
984 DfsWizard(const Graph &g, Node s=INVALID) :
988 DfsWizard(const TR &b) : TR(b) {}
992 ///Runs Dfs algorithm from a given node.
994 ///Runs Dfs algorithm from a given node.
995 ///The node can be given by the \ref source function.
998 if(Base::_source==INVALID) throw UninitializedParameter();
999 Dfs<Graph,TR> alg(*(Graph*)Base::_g);
1000 if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached);
1001 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
1002 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
1003 // if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
1004 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
1005 alg.run(Base::_source);
1008 ///Runs Dfs algorithm from the given node.
1010 ///Runs Dfs algorithm from the given node.
1011 ///\param s is the given source.
1019 struct DefPredMapBase : public Base {
1021 static PredMap *createPredMap(const Graph &) { return 0; };
1022 DefPredMapBase(const TR &b) : TR(b) {}
1025 ///\brief \ref named-templ-param "Named parameter"
1026 ///function for setting PredMap type
1028 /// \ref named-templ-param "Named parameter"
1029 ///function for setting PredMap type
1032 DfsWizard<DefPredMapBase<T> > predMap(const T &t)
1034 Base::_pred=(void *)&t;
1035 return DfsWizard<DefPredMapBase<T> >(*this);
1040 struct DefReachedMapBase : public Base {
1041 typedef T ReachedMap;
1042 static ReachedMap *createReachedMap(const Graph &) { return 0; };
1043 DefReachedMapBase(const TR &b) : TR(b) {}
1046 ///\brief \ref named-templ-param "Named parameter"
1047 ///function for setting ReachedMap
1049 /// \ref named-templ-param "Named parameter"
1050 ///function for setting ReachedMap
1053 DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1055 Base::_pred=(void *)&t;
1056 return DfsWizard<DefReachedMapBase<T> >(*this);
1061 struct DefProcessedMapBase : public Base {
1062 typedef T ProcessedMap;
1063 static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
1064 DefProcessedMapBase(const TR &b) : TR(b) {}
1067 ///\brief \ref named-templ-param "Named parameter"
1068 ///function for setting ProcessedMap
1070 /// \ref named-templ-param "Named parameter"
1071 ///function for setting ProcessedMap
1074 DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1076 Base::_pred=(void *)&t;
1077 return DfsWizard<DefProcessedMapBase<T> >(*this);
1081 // template<class T>
1082 // struct DefPredNodeMapBase : public Base {
1083 // typedef T PredNodeMap;
1084 // static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
1085 // DefPredNodeMapBase(const TR &b) : TR(b) {}
1088 // ///\brief \ref named-templ-param "Named parameter"
1089 // ///function for setting PredNodeMap type
1091 // /// \ref named-templ-param "Named parameter"
1092 // ///function for setting PredNodeMap type
1094 // template<class T>
1095 // DfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1097 // Base::_predNode=(void *)&t;
1098 // return DfsWizard<DefPredNodeMapBase<T> >(*this);
1102 struct DefDistMapBase : public Base {
1104 static DistMap *createDistMap(const Graph &) { return 0; };
1105 DefDistMapBase(const TR &b) : TR(b) {}
1108 ///\brief \ref named-templ-param "Named parameter"
1109 ///function for setting DistMap type
1111 /// \ref named-templ-param "Named parameter"
1112 ///function for setting DistMap type
1115 DfsWizard<DefDistMapBase<T> > distMap(const T &t)
1117 Base::_dist=(void *)&t;
1118 return DfsWizard<DefDistMapBase<T> >(*this);
1121 /// Sets the source node, from which the Dfs algorithm runs.
1123 /// Sets the source node, from which the Dfs algorithm runs.
1124 /// \param s is the source node.
1125 DfsWizard<TR> &source(Node s)
1133 ///Function type interface for Dfs algorithm.
1135 /// \ingroup flowalgs
1136 ///Function type interface for Dfs algorithm.
1138 ///This function also has several
1139 ///\ref named-templ-func-param "named parameters",
1140 ///they are declared as the members of class \ref DfsWizard.
1142 ///example shows how to use these parameters.
1144 /// dfs(g,source).predMap(preds).run();
1146 ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
1147 ///to the end of the parameter list.
1151 DfsWizard<DfsWizardBase<GR> >
1152 dfs(const GR &g,typename GR::Node s=INVALID)
1154 return DfsWizard<DfsWizardBase<GR> >(g,s);
1157 } //END OF NAMESPACE LEMON