- lp_test is made working.
- some more 'const' for those who like them..
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
89 static ProcessedMap *createProcessedMap(const GR &)
91 return new ProcessedMap();
93 ///The type of the map that indicates which nodes are reached.
95 ///The type of the map that indicates which nodes are reached.
96 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
97 ///\todo named parameter to set this type, function to read and write.
98 typedef typename Graph::template NodeMap<bool> ReachedMap;
99 ///Instantiates a ReachedMap.
101 ///This function instantiates a \ref ReachedMap.
102 ///\param G is the graph, to which
103 ///we would like to define the \ref ReachedMap.
104 static ReachedMap *createReachedMap(const GR &G)
106 return new ReachedMap(G);
108 ///The type of the map that stores the dists of the nodes.
110 ///The type of the map that stores the dists of the nodes.
111 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
113 typedef typename Graph::template NodeMap<int> DistMap;
114 ///Instantiates a DistMap.
116 ///This function instantiates a \ref DistMap.
117 ///\param G is the graph, to which we would like to define the \ref DistMap
118 static DistMap *createDistMap(const GR &G)
120 return new DistMap(G);
124 ///%DFS algorithm class.
127 ///This class provides an efficient implementation of the %DFS algorithm.
129 ///\param GR The graph type the algorithm runs on. The default value is
130 ///\ref ListGraph. The value of GR is not used directly by Dfs, it
131 ///is only passed to \ref DfsDefaultTraits.
132 ///\param TR Traits class to set various data types used by the algorithm.
133 ///The default traits class is
134 ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
135 ///See \ref DfsDefaultTraits for the documentation of
136 ///a Dfs traits class.
138 ///\author Jacint Szabo and Alpar Juttner
139 ///\todo A compare object would be nice.
142 template <typename GR,
145 template <typename GR=ListGraph,
146 typename TR=DfsDefaultTraits<GR> >
151 * \brief \ref Exception for uninitialized parameters.
153 * This error represents problems in the initialization
154 * of the parameters of the algorithms.
156 class UninitializedParameter : public lemon::UninitializedParameter {
158 virtual const char* exceptionName() const {
159 return "lemon::Dfs::UninitializedParameter";
164 ///The type of the underlying graph.
165 typedef typename TR::Graph Graph;
167 typedef typename Graph::Node Node;
169 typedef typename Graph::NodeIt NodeIt;
171 typedef typename Graph::Edge Edge;
173 typedef typename Graph::OutEdgeIt OutEdgeIt;
175 ///\brief The type of the map that stores the last
176 ///edges of the %DFS paths.
177 typedef typename TR::PredMap PredMap;
178 // ///\brief The type of the map that stores the last but one
179 // ///nodes of the %DFS paths.
180 // typedef typename TR::PredNodeMap PredNodeMap;
181 ///The type of the map indicating which nodes are reached.
182 typedef typename TR::ReachedMap ReachedMap;
183 ///The type of the map indicating which nodes are processed.
184 typedef typename TR::ProcessedMap ProcessedMap;
185 ///The type of the map that stores the dists of the nodes.
186 typedef typename TR::DistMap DistMap;
188 /// Pointer to the underlying graph.
190 ///Pointer to the map of predecessors edges.
192 ///Indicates if \ref _pred is locally allocated (\c true) or not.
194 // ///Pointer to the map of predecessors nodes.
195 // PredNodeMap *_predNode;
196 // ///Indicates if \ref _predNode is locally allocated (\c true) or not.
197 // bool local_predNode;
198 ///Pointer to the map of distances.
200 ///Indicates if \ref _dist is locally allocated (\c true) or not.
202 ///Pointer to the map of reached status of the nodes.
203 ReachedMap *_reached;
204 ///Indicates if \ref _reached is locally allocated (\c true) or not.
206 ///Pointer to the map of processed status of the nodes.
207 ProcessedMap *_processed;
208 ///Indicates if \ref _processed is locally allocated (\c true) or not.
209 bool local_processed;
211 std::vector<typename Graph::OutEdgeIt> _stack;
213 // ///The source node of the last execution.
216 ///Creates the maps if necessary.
218 ///\todo Error if \c G are \c NULL.
219 ///\todo Better memory allocation (instead of new).
224 _pred = Traits::createPredMap(*G);
227 // local_predNode = true;
228 // _predNode = Traits::createPredNodeMap(*G);
232 _dist = Traits::createDistMap(*G);
235 local_reached = true;
236 _reached = Traits::createReachedMap(*G);
239 local_processed = true;
240 _processed = Traits::createProcessedMap(*G);
246 ///\name Named template parameters
251 struct DefPredMapTraits : public Traits {
253 static PredMap *createPredMap(const Graph &G)
255 throw UninitializedParameter();
258 ///\ref named-templ-param "Named parameter" for setting PredMap type
260 ///\ref named-templ-param "Named parameter" for setting PredMap type
263 class DefPredMap : public Dfs< Graph,
264 DefPredMapTraits<T> > { };
266 // template <class T>
267 // struct DefPredNodeMapTraits : public Traits {
268 // typedef T PredNodeMap;
269 // static PredNodeMap *createPredNodeMap(const Graph &G)
271 // throw UninitializedParameter();
274 // ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
276 // ///\ref named-templ-param "Named parameter" for setting PredNodeMap type
278 // template <class T>
279 // class DefPredNodeMap : public Dfs< Graph,
281 // DefPredNodeMapTraits<T> > { };
284 struct DefDistMapTraits : public Traits {
286 static DistMap *createDistMap(const Graph &G)
288 throw UninitializedParameter();
291 ///\ref named-templ-param "Named parameter" for setting DistMap type
293 ///\ref named-templ-param "Named parameter" for setting DistMap type
296 class DefDistMap : public Dfs< Graph,
297 DefDistMapTraits<T> > { };
300 struct DefReachedMapTraits : public Traits {
301 typedef T ReachedMap;
302 static ReachedMap *createReachedMap(const Graph &G)
304 throw UninitializedParameter();
307 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
309 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
312 class DefReachedMap : public Dfs< Graph,
313 DefReachedMapTraits<T> > { };
315 struct DefGraphReachedMapTraits : public Traits {
316 typedef typename Graph::template NodeMap<bool> ReachedMap;
317 static ReachedMap *createReachedMap(const Graph &G)
319 return new ReachedMap(G);
323 struct DefProcessedMapTraits : public Traits {
324 typedef T ProcessedMap;
325 static ProcessedMap *createProcessedMap(const Graph &G)
327 throw UninitializedParameter();
330 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
332 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
335 class DefProcessedMap : public Dfs< Graph,
336 DefProcessedMapTraits<T> > { };
338 struct DefGraphProcessedMapTraits : public Traits {
339 typedef typename Graph::template NodeMap<bool> ProcessedMap;
340 static ProcessedMap *createProcessedMap(const Graph &G)
342 return new ProcessedMap(G);
345 ///\brief \ref named-templ-param "Named parameter"
346 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
348 ///\ref named-templ-param "Named parameter"
349 ///for setting the ProcessedMap type to be Graph::NodeMap<bool>.
350 ///If you don't set it explicitely, it will be automatically allocated.
352 class DefProcessedMapToBeDefaultMap :
354 DefGraphProcessedMapTraits> { };
362 ///\param _G the graph the algorithm will run on.
364 Dfs(const Graph& _G) :
366 _pred(NULL), local_pred(false),
367 // _predNode(NULL), local_predNode(false),
368 _dist(NULL), local_dist(false),
369 _reached(NULL), local_reached(false),
370 _processed(NULL), local_processed(false)
376 if(local_pred) delete _pred;
377 // if(local_predNode) delete _predNode;
378 if(local_dist) delete _dist;
379 if(local_reached) delete _reached;
380 if(local_processed) delete _processed;
383 ///Sets the map storing the predecessor edges.
385 ///Sets the map storing the predecessor edges.
386 ///If you don't use this function before calling \ref run(),
387 ///it will allocate one. The destuctor deallocates this
388 ///automatically allocated map, of course.
389 ///\return <tt> (*this) </tt>
390 Dfs &predMap(PredMap &m)
400 // ///Sets the map storing the predecessor nodes.
402 // ///Sets the map storing the predecessor nodes.
403 // ///If you don't use this function before calling \ref run(),
404 // ///it will allocate one. The destuctor deallocates this
405 // ///automatically allocated map, of course.
406 // ///\return <tt> (*this) </tt>
407 // Dfs &predNodeMap(PredNodeMap &m)
409 // if(local_predNode) {
411 // local_predNode=false;
417 ///Sets the map storing the distances calculated by the algorithm.
419 ///Sets the map storing the distances calculated by the algorithm.
420 ///If you don't use this function before calling \ref run(),
421 ///it will allocate one. The destuctor deallocates this
422 ///automatically allocated map, of course.
423 ///\return <tt> (*this) </tt>
424 Dfs &distMap(DistMap &m)
434 ///Sets the map indicating if a node is reached.
436 ///Sets the map indicating if a node is reached.
437 ///If you don't use this function before calling \ref run(),
438 ///it will allocate one. The destuctor deallocates this
439 ///automatically allocated map, of course.
440 ///\return <tt> (*this) </tt>
441 Dfs &reachedMap(ReachedMap &m)
451 ///Sets the map indicating if a node is processed.
453 ///Sets the map indicating if a node is processed.
454 ///If you don't use this function before calling \ref run(),
455 ///it will allocate one. The destuctor deallocates this
456 ///automatically allocated map, of course.
457 ///\return <tt> (*this) </tt>
458 Dfs &processedMap(ProcessedMap &m)
460 if(local_processed) {
462 local_processed=false;
469 ///\name Execution control
470 ///The simplest way to execute the algorithm is to use
471 ///one of the member functions called \c run(...).
473 ///If you need more control on the execution,
474 ///first you must call \ref init(), then you can add several source nodes
475 ///with \ref addSource().
476 ///Finally \ref start() will perform the actual path
481 ///Initializes the internal data structures.
483 ///Initializes the internal data structures.
488 _stack.resize(countNodes(*G));
490 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
491 _pred->set(u,INVALID);
492 // _predNode->set(u,INVALID);
493 _reached->set(u,false);
494 _processed->set(u,false);
498 ///Adds a new source node.
500 ///Adds a new source node to the set of nodes to be processed.
502 ///\bug dists are wrong (or at least strange) in case of multiple sources.
503 void addSource(Node s)
507 _reached->set(s,true);
508 _pred->set(s,INVALID);
509 // _predNode->set(u,INVALID);
510 _stack[++_stack_head]=OutEdgeIt(*G,s);
511 _dist->set(s,_stack_head);
515 ///Processes the next node.
517 ///Processes the next node.
519 ///\pre The stack must not be empty!
520 void processNextEdge()
523 Edge e=_stack[_stack_head];
524 if(!(*_reached)[m=G->target(e)]) {
526 _reached->set(m,true);
527 // _pred_node->set(m,G->source(e));
529 _stack[_stack_head] = OutEdgeIt(*G, m);
530 _dist->set(m,_stack_head);
534 while(_stack_head>=0 &&
535 (n=G->source(_stack[_stack_head]),
536 ++_stack[_stack_head]==INVALID))
538 _processed->set(n,true);
544 ///\brief Returns \c false if there are nodes
545 ///to be processed in the queue
547 ///Returns \c false if there are nodes
548 ///to be processed in the queue
549 bool emptyQueue() { return _stack_head<0; }
550 ///Returns the number of the nodes to be processed.
552 ///Returns the number of the nodes to be processed in the queue.
554 int queueSize() { return _stack_head+1; }
556 ///Executes the algorithm.
558 ///Executes the algorithm.
560 ///\pre init() must be called and at least one node should be added
561 ///with addSource() before using this function.
563 ///This method runs the %DFS algorithm from the root node(s)
566 ///%DFS path to each node. The algorithm computes
568 ///- The distance of each node from the root(s) in the %DFS tree.
572 while ( !emptyQueue() ) processNextEdge();
575 ///Executes the algorithm until \c dest is reached.
577 ///Executes the algorithm until \c dest is reached.
579 ///\pre init() must be called and at least one node should be added
580 ///with addSource() before using this function.
582 ///This method runs the %DFS algorithm from the root node(s)
585 ///%DFS path to \c dest. The algorithm computes
586 ///- The %DFS path to \c dest.
587 ///- The distance of \c dest from the root(s) in the %DFS tree.
589 void start(Node dest)
591 while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
595 ///Executes the algorithm until a condition is met.
597 ///Executes the algorithm until a condition is met.
599 ///\pre init() must be called and at least one node should be added
600 ///with addSource() before using this function.
602 ///\param nm must be a bool (or convertible) edge map. The algorithm
603 ///will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>.
605 ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c nm is an edge map,
608 void start(const NM &nm)
610 while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge();
613 ///Runs %DFS algorithm from node \c s.
615 ///This method runs the %DFS algorithm from a root node \c s
618 ///%DFS path to each node. The algorithm computes
620 ///- The distance of each node from the root in the %DFS tree.
622 ///\note d.run(s) is just a shortcut of the following code.
634 ///Finds the %DFS path between \c s and \c t.
636 ///Finds the %DFS path between \c s and \c t.
638 ///\return The length of the %DFS s---t path if there exists one,
640 ///\note Apart from the return value, d.run(s) is
641 ///just a shortcut of the following code.
647 int run(Node s,Node t) {
651 return reached(t)?_stack_head+1:0;
656 ///\name Query Functions
657 ///The result of the %DFS algorithm can be obtained using these
659 ///Before the use of these functions,
660 ///either run() or start() must be called.
664 ///Copies the path to \c t on the DFS tree into \c p
666 ///This function copies the path to \c t on the DFS tree into \c p.
667 ///If \c t is a source itself or unreachable, then it does not
669 ///\todo Is this the right way to handle unreachable nodes?
671 ///\return Returns \c true if a path to \c t was actually copied to \c p,
672 ///\c false otherwise.
675 bool getPath(P &p,Node t)
679 typename P::Builder b(p);
680 for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
681 b.pushFront(pred(t));
688 ///The distance of a node from the root(s).
690 ///Returns the distance of a node from the root(s).
691 ///\pre \ref run() must be called before using this function.
692 ///\warning If node \c v is unreachable from the root(s) then the return value
693 ///of this funcion is undefined.
694 int dist(Node v) const { return (*_dist)[v]; }
696 ///Returns the 'previous edge' of the %DFS tree.
698 ///For a node \c v it returns the 'previous edge'
700 ///i.e. it returns the last edge of a %DFS path from the root(s) to \c
701 ///v. It is \ref INVALID
702 ///if \c v is unreachable from the root(s) or \c v is a root. The
703 ///%DFS tree used here is equal to the %DFS tree used in
704 ///\ref predNode(Node v).
705 ///\pre Either \ref run() or \ref start() must be called before using
707 ///\todo predEdge could be a better name.
708 Edge pred(Node v) const { return (*_pred)[v];}
710 ///Returns the 'previous node' of the %DFS tree.
712 ///For a node \c v it returns the 'previous node'
714 ///i.e. it returns the last but one node from a %DFS path from the
716 ///It is INVALID if \c v is unreachable from the root(s) or
717 ///if \c v itself a root.
718 ///The %DFS tree used here is equal to the %DFS
719 ///tree used in \ref pred(Node v).
720 ///\pre Either \ref run() or \ref start() must be called before
721 ///using this function.
722 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
723 G->source((*_pred)[v]); }
725 ///Returns a reference to the NodeMap of distances.
727 ///Returns a reference to the NodeMap of distances.
728 ///\pre Either \ref run() or \ref init() must
729 ///be called before using this function.
730 const DistMap &distMap() const { return *_dist;}
732 ///Returns a reference to the %DFS edge-tree map.
734 ///Returns a reference to the NodeMap of the edges of the
736 ///\pre Either \ref run() or \ref init()
737 ///must be called before using this function.
738 const PredMap &predMap() const { return *_pred;}
740 // ///Returns a reference to the map of nodes of %DFS paths.
742 // ///Returns a reference to the NodeMap of the last but one nodes of the
744 // ///\pre \ref run() must be called before using this function.
745 // const PredNodeMap &predNodeMap() const { return *_predNode;}
747 ///Checks if a node is reachable from the root.
749 ///Returns \c true if \c v is reachable from the root(s).
750 ///\warning The source nodes are inditated as unreachable.
751 ///\pre Either \ref run() or \ref start()
752 ///must be called before using this function.
754 bool reached(Node v) { return (*_reached)[v]; }
759 ///Default traits class of Dfs function.
761 ///Default traits class of Dfs function.
762 ///\param GR Graph type.
764 struct DfsWizardDefaultTraits
766 ///The graph type the algorithm runs on.
768 ///\brief The type of the map that stores the last
769 ///edges of the %DFS paths.
771 ///The type of the map that stores the last
772 ///edges of the %DFS paths.
773 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
775 typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
776 ///Instantiates a PredMap.
778 ///This function instantiates a \ref PredMap.
779 ///\param G is the graph, to which we would like to define the PredMap.
780 ///\todo The graph alone may be insufficient to initialize
781 static PredMap *createPredMap(const GR &)
783 return new PredMap();
785 // ///\brief The type of the map that stores the last but one
786 // ///nodes of the %DFS paths.
788 // ///The type of the map that stores the last but one
789 // ///nodes of the %DFS paths.
790 // ///It must meet the \ref concept::WriteMap "WriteMap" concept.
792 // typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
793 // ///Instantiates a PredNodeMap.
795 // ///This function instantiates a \ref PredNodeMap.
796 // ///\param G is the graph, to which
797 // ///we would like to define the \ref PredNodeMap
798 // static PredNodeMap *createPredNodeMap(const GR &G)
800 // return new PredNodeMap();
803 ///The type of the map that indicates which nodes are processed.
805 ///The type of the map that indicates which nodes are processed.
806 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
807 ///\todo named parameter to set this type, function to read and write.
808 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
809 ///Instantiates a ProcessedMap.
811 ///This function instantiates a \ref ProcessedMap.
812 ///\param G is the graph, to which
813 ///we would like to define the \ref ProcessedMap
814 static ProcessedMap *createProcessedMap(const GR &)
816 return new ProcessedMap();
818 ///The type of the map that indicates which nodes are reached.
820 ///The type of the map that indicates which nodes are reached.
821 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
822 ///\todo named parameter to set this type, function to read and write.
823 typedef typename Graph::template NodeMap<bool> ReachedMap;
824 ///Instantiates a ReachedMap.
826 ///This function instantiates a \ref ReachedMap.
827 ///\param G is the graph, to which
828 ///we would like to define the \ref ReachedMap.
829 static ReachedMap *createReachedMap(const GR &G)
831 return new ReachedMap(G);
833 ///The type of the map that stores the dists of the nodes.
835 ///The type of the map that stores the dists of the nodes.
836 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
838 typedef NullMap<typename Graph::Node,int> DistMap;
839 ///Instantiates a DistMap.
841 ///This function instantiates a \ref DistMap.
842 ///\param G is the graph, to which we would like to define the \ref DistMap
843 static DistMap *createDistMap(const GR &)
845 return new DistMap();
849 /// Default traits used by \ref DfsWizard
851 /// To make it easier to use Dfs algorithm
852 ///we have created a wizard class.
853 /// This \ref DfsWizard class needs default traits,
854 ///as well as the \ref Dfs class.
855 /// The \ref DfsWizardBase is a class to be the default traits of the
856 /// \ref DfsWizard class.
858 class DfsWizardBase : public DfsWizardDefaultTraits<GR>
861 typedef DfsWizardDefaultTraits<GR> Base;
863 /// Type of the nodes in the graph.
864 typedef typename Base::Graph::Node Node;
866 /// Pointer to the underlying graph.
868 ///Pointer to the map of reached nodes.
870 ///Pointer to the map of processed nodes.
872 ///Pointer to the map of predecessors edges.
874 // ///Pointer to the map of predecessors nodes.
876 ///Pointer to the map of distances.
878 ///Pointer to the source node.
884 /// This constructor does not require parameters, therefore it initiates
885 /// all of the attributes to default values (0, INVALID).
886 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
888 _dist(0), _source(INVALID) {}
892 /// This constructor requires some parameters,
893 /// listed in the parameters list.
894 /// Others are initiated to 0.
895 /// \param g is the initial value of \ref _g
896 /// \param s is the initial value of \ref _source
897 DfsWizardBase(const GR &g, Node s=INVALID) :
898 _g((void *)&g), _reached(0), _processed(0), _pred(0),
900 _dist(0), _source(s) {}
904 /// A class to make the usage of the Dfs algorithm easier
906 /// This class is created to make it easier to use the Dfs algorithm.
907 /// It uses the functions and features of the plain \ref Dfs,
908 /// but it is much simpler to use it.
910 /// Simplicity means that the way to change the types defined
911 /// in the traits class is based on functions that returns the new class
912 /// and not on templatable built-in classes.
913 /// When using the plain \ref Dfs
914 /// the new class with the modified type comes from
915 /// the original class by using the ::
916 /// operator. In the case of \ref DfsWizard only
917 /// a function have to be called and it will
918 /// return the needed class.
920 /// It does not have own \ref run method. When its \ref run method is called
921 /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run
924 class DfsWizard : public TR
928 ///The type of the underlying graph.
929 typedef typename TR::Graph Graph;
931 typedef typename Graph::Node Node;
933 typedef typename Graph::NodeIt NodeIt;
935 typedef typename Graph::Edge Edge;
937 typedef typename Graph::OutEdgeIt OutEdgeIt;
939 ///\brief The type of the map that stores
941 typedef typename TR::ReachedMap ReachedMap;
942 ///\brief The type of the map that stores
943 ///the processed nodes
944 typedef typename TR::ProcessedMap ProcessedMap;
945 ///\brief The type of the map that stores the last
946 ///edges of the %DFS paths.
947 typedef typename TR::PredMap PredMap;
948 // ///\brief The type of the map that stores the last but one
949 // ///nodes of the %DFS paths.
950 // typedef typename TR::PredNodeMap PredNodeMap;
951 ///The type of the map that stores the distances of the nodes.
952 typedef typename TR::DistMap DistMap;
956 DfsWizard() : TR() {}
958 /// Constructor that requires parameters.
960 /// Constructor that requires parameters.
961 /// These parameters will be the default values for the traits class.
962 DfsWizard(const Graph &g, Node s=INVALID) :
966 DfsWizard(const TR &b) : TR(b) {}
970 ///Runs Dfs algorithm from a given node.
972 ///Runs Dfs algorithm from a given node.
973 ///The node can be given by the \ref source function.
976 if(Base::_source==INVALID) throw UninitializedParameter();
977 Dfs<Graph,TR> alg(*(Graph*)Base::_g);
978 if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached);
979 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
980 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
981 // if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
982 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
983 alg.run(Base::_source);
986 ///Runs Dfs algorithm from the given node.
988 ///Runs Dfs algorithm from the given node.
989 ///\param s is the given source.
997 struct DefPredMapBase : public Base {
999 static PredMap *createPredMap(const Graph &) { return 0; };
1000 DefPredMapBase(const TR &b) : TR(b) {}
1003 ///\brief \ref named-templ-param "Named parameter"
1004 ///function for setting PredMap type
1006 /// \ref named-templ-param "Named parameter"
1007 ///function for setting PredMap type
1010 DfsWizard<DefPredMapBase<T> > predMap(const T &t)
1012 Base::_pred=(void *)&t;
1013 return DfsWizard<DefPredMapBase<T> >(*this);
1018 struct DefReachedMapBase : public Base {
1019 typedef T ReachedMap;
1020 static ReachedMap *createReachedMap(const Graph &) { return 0; };
1021 DefReachedMapBase(const TR &b) : TR(b) {}
1024 ///\brief \ref named-templ-param "Named parameter"
1025 ///function for setting ReachedMap
1027 /// \ref named-templ-param "Named parameter"
1028 ///function for setting ReachedMap
1031 DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1033 Base::_pred=(void *)&t;
1034 return DfsWizard<DefReachedMapBase<T> >(*this);
1039 struct DefProcessedMapBase : public Base {
1040 typedef T ProcessedMap;
1041 static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
1042 DefProcessedMapBase(const TR &b) : TR(b) {}
1045 ///\brief \ref named-templ-param "Named parameter"
1046 ///function for setting ProcessedMap
1048 /// \ref named-templ-param "Named parameter"
1049 ///function for setting ProcessedMap
1052 DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1054 Base::_pred=(void *)&t;
1055 return DfsWizard<DefProcessedMapBase<T> >(*this);
1059 // template<class T>
1060 // struct DefPredNodeMapBase : public Base {
1061 // typedef T PredNodeMap;
1062 // static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
1063 // DefPredNodeMapBase(const TR &b) : TR(b) {}
1066 // ///\brief \ref named-templ-param "Named parameter"
1067 // ///function for setting PredNodeMap type
1069 // /// \ref named-templ-param "Named parameter"
1070 // ///function for setting PredNodeMap type
1072 // template<class T>
1073 // DfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1075 // Base::_predNode=(void *)&t;
1076 // return DfsWizard<DefPredNodeMapBase<T> >(*this);
1080 struct DefDistMapBase : public Base {
1082 static DistMap *createDistMap(const Graph &) { return 0; };
1083 DefDistMapBase(const TR &b) : TR(b) {}
1086 ///\brief \ref named-templ-param "Named parameter"
1087 ///function for setting DistMap type
1089 /// \ref named-templ-param "Named parameter"
1090 ///function for setting DistMap type
1093 DfsWizard<DefDistMapBase<T> > distMap(const T &t)
1095 Base::_dist=(void *)&t;
1096 return DfsWizard<DefDistMapBase<T> >(*this);
1099 /// Sets the source node, from which the Dfs algorithm runs.
1101 /// Sets the source node, from which the Dfs algorithm runs.
1102 /// \param s is the source node.
1103 DfsWizard<TR> &source(Node s)
1111 ///Function type interface for Dfs algorithm.
1113 /// \ingroup flowalgs
1114 ///Function type interface for Dfs algorithm.
1116 ///This function also has several
1117 ///\ref named-templ-func-param "named parameters",
1118 ///they are declared as the members of class \ref DfsWizard.
1120 ///example shows how to use these parameters.
1122 /// dfs(g,source).predMap(preds).run();
1124 ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
1125 ///to the end of the parameter list.
1129 DfsWizard<DfsWizardBase<GR> >
1130 dfs(const GR &g,typename GR::Node s=INVALID)
1132 return DfsWizard<DfsWizardBase<GR> >(g,s);
1135 } //END OF NAMESPACE LEMON