File demoprograms.dox thrown away: demos module used instead.
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 while(_stack_head>=0 &&
541 (n=G->source(_stack[_stack_head]),
542 ++_stack[_stack_head]==INVALID))
544 _processed->set(n,true);
551 ///\brief Returns \c false if there are nodes
552 ///to be processed in the queue
554 ///Returns \c false if there are nodes
555 ///to be processed in the queue
556 bool emptyQueue() { return _stack_head<0; }
557 ///Returns the number of the nodes to be processed.
559 ///Returns the number of the nodes to be processed in the queue.
561 int queueSize() { return _stack_head+1; }
563 ///Executes the algorithm.
565 ///Executes the algorithm.
567 ///\pre init() must be called and at least one node should be added
568 ///with addSource() before using this function.
570 ///This method runs the %DFS algorithm from the root node(s)
573 ///%DFS path to each node. The algorithm computes
575 ///- The distance of each node from the root(s) in the %DFS tree.
579 while ( !emptyQueue() ) processNextEdge();
582 ///Executes the algorithm until \c dest is reached.
584 ///Executes the algorithm until \c dest is reached.
586 ///\pre init() must be called and at least one node should be added
587 ///with addSource() before using this function.
589 ///This method runs the %DFS algorithm from the root node(s)
592 ///%DFS path to \c dest. The algorithm computes
593 ///- The %DFS path to \c dest.
594 ///- The distance of \c dest from the root(s) in the %DFS tree.
596 void start(Node dest)
598 while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
602 ///Executes the algorithm until a condition is met.
604 ///Executes the algorithm until a condition is met.
606 ///\pre init() must be called and at least one node should be added
607 ///with addSource() before using this function.
609 ///\param nm must be a bool (or convertible) edge map. The algorithm
610 ///will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>.
612 ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c nm is an edge map,
615 void start(const NM &nm)
617 while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge();
620 ///Runs %DFS algorithm from node \c s.
622 ///This method runs the %DFS algorithm from a root node \c s
625 ///%DFS path to each node. The algorithm computes
627 ///- The distance of each node from the root in the %DFS tree.
629 ///\note d.run(s) is just a shortcut of the following code.
641 ///Finds the %DFS path between \c s and \c t.
643 ///Finds the %DFS path between \c s and \c t.
645 ///\return The length of the %DFS s---t path if there exists one,
647 ///\note Apart from the return value, d.run(s,t) is
648 ///just a shortcut of the following code.
654 int run(Node s,Node t) {
658 return reached(t)?_stack_head+1:0;
663 ///\name Query Functions
664 ///The result of the %DFS algorithm can be obtained using these
666 ///Before the use of these functions,
667 ///either run() or start() must be called.
671 ///Copies the path to \c t on the DFS tree into \c p
673 ///This function copies the path to \c t on the DFS tree into \c p.
674 ///If \c t is a source itself or unreachable, then it does not
676 ///\todo Is this the right way to handle unreachable nodes?
678 ///\return Returns \c true if a path to \c t was actually copied to \c p,
679 ///\c false otherwise.
682 bool getPath(P &p,Node t)
686 typename P::Builder b(p);
687 for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
688 b.pushFront(pred(t));
695 ///The distance of a node from the root(s).
697 ///Returns the distance of a node from the root(s).
698 ///\pre \ref run() must be called before using this function.
699 ///\warning If node \c v is unreachable from the root(s) then the return value
700 ///of this funcion is undefined.
701 int dist(Node v) const { return (*_dist)[v]; }
703 ///Returns the 'previous edge' of the %DFS tree.
705 ///For a node \c v it returns the 'previous edge'
707 ///i.e. it returns the last edge of a %DFS path from the root(s) to \c
708 ///v. It is \ref INVALID
709 ///if \c v is unreachable from the root(s) or \c v is a root. The
710 ///%DFS tree used here is equal to the %DFS tree used in
711 ///\ref predNode(Node v).
712 ///\pre Either \ref run() or \ref start() must be called before using
714 ///\todo predEdge could be a better name.
715 Edge pred(Node v) const { return (*_pred)[v];}
717 ///Returns the 'previous node' of the %DFS tree.
719 ///For a node \c v it returns the 'previous node'
721 ///i.e. it returns the last but one node from a %DFS path from the
723 ///It is INVALID if \c v is unreachable from the root(s) or
724 ///if \c v itself a root.
725 ///The %DFS tree used here is equal to the %DFS
726 ///tree used in \ref pred(Node v).
727 ///\pre Either \ref run() or \ref start() must be called before
728 ///using this function.
729 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
730 G->source((*_pred)[v]); }
732 ///Returns a reference to the NodeMap of distances.
734 ///Returns a reference to the NodeMap of distances.
735 ///\pre Either \ref run() or \ref init() must
736 ///be called before using this function.
737 const DistMap &distMap() const { return *_dist;}
739 ///Returns a reference to the %DFS edge-tree map.
741 ///Returns a reference to the NodeMap of the edges of the
743 ///\pre Either \ref run() or \ref init()
744 ///must be called before using this function.
745 const PredMap &predMap() const { return *_pred;}
747 // ///Returns a reference to the map of nodes of %DFS paths.
749 // ///Returns a reference to the NodeMap of the last but one nodes of the
751 // ///\pre \ref run() must be called before using this function.
752 // const PredNodeMap &predNodeMap() const { return *_predNode;}
754 ///Checks if a node is reachable from the root.
756 ///Returns \c true if \c v is reachable from the root(s).
757 ///\warning The source nodes are inditated as unreachable.
758 ///\pre Either \ref run() or \ref start()
759 ///must be called before using this function.
761 bool reached(Node v) { return (*_reached)[v]; }
766 ///Default traits class of Dfs function.
768 ///Default traits class of Dfs function.
769 ///\param GR Graph type.
771 struct DfsWizardDefaultTraits
773 ///The graph type the algorithm runs on.
775 ///\brief The type of the map that stores the last
776 ///edges of the %DFS paths.
778 ///The type of the map that stores the last
779 ///edges of the %DFS paths.
780 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
782 typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
783 ///Instantiates a PredMap.
785 ///This function instantiates a \ref PredMap.
786 ///\param g is the graph, to which we would like to define the PredMap.
787 ///\todo The graph alone may be insufficient to initialize
789 static PredMap *createPredMap(const GR &g)
791 static PredMap *createPredMap(const GR &)
794 return new PredMap();
796 // ///\brief The type of the map that stores the last but one
797 // ///nodes of the %DFS paths.
799 // ///The type of the map that stores the last but one
800 // ///nodes of the %DFS paths.
801 // ///It must meet the \ref concept::WriteMap "WriteMap" concept.
803 // typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
804 // ///Instantiates a PredNodeMap.
806 // ///This function instantiates a \ref PredNodeMap.
807 // ///\param G is the graph, to which
808 // ///we would like to define the \ref PredNodeMap
809 // static PredNodeMap *createPredNodeMap(const GR &G)
811 // return new PredNodeMap();
814 ///The type of the map that indicates which nodes are processed.
816 ///The type of the map that indicates which nodes are processed.
817 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
818 ///\todo named parameter to set this type, function to read and write.
819 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
820 ///Instantiates a ProcessedMap.
822 ///This function instantiates a \ref ProcessedMap.
823 ///\param g is the graph, to which
824 ///we would like to define the \ref ProcessedMap
826 static ProcessedMap *createProcessedMap(const GR &g)
828 static ProcessedMap *createProcessedMap(const GR &)
831 return new ProcessedMap();
833 ///The type of the map that indicates which nodes are reached.
835 ///The type of the map that indicates which nodes are reached.
836 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
837 ///\todo named parameter to set this type, function to read and write.
838 typedef typename Graph::template NodeMap<bool> ReachedMap;
839 ///Instantiates a ReachedMap.
841 ///This function instantiates a \ref ReachedMap.
842 ///\param G is the graph, to which
843 ///we would like to define the \ref ReachedMap.
844 static ReachedMap *createReachedMap(const GR &G)
846 return new ReachedMap(G);
848 ///The type of the map that stores the dists of the nodes.
850 ///The type of the map that stores the dists of the nodes.
851 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
853 typedef NullMap<typename Graph::Node,int> DistMap;
854 ///Instantiates a DistMap.
856 ///This function instantiates a \ref DistMap.
857 ///\param g is the graph, to which we would like to define the \ref DistMap
859 static DistMap *createDistMap(const GR &g)
861 static DistMap *createDistMap(const GR &)
864 return new DistMap();
868 /// Default traits used by \ref DfsWizard
870 /// To make it easier to use Dfs algorithm
871 ///we have created a wizard class.
872 /// This \ref DfsWizard class needs default traits,
873 ///as well as the \ref Dfs class.
874 /// The \ref DfsWizardBase is a class to be the default traits of the
875 /// \ref DfsWizard class.
877 class DfsWizardBase : public DfsWizardDefaultTraits<GR>
880 typedef DfsWizardDefaultTraits<GR> Base;
882 /// Type of the nodes in the graph.
883 typedef typename Base::Graph::Node Node;
885 /// Pointer to the underlying graph.
887 ///Pointer to the map of reached nodes.
889 ///Pointer to the map of processed nodes.
891 ///Pointer to the map of predecessors edges.
893 // ///Pointer to the map of predecessors nodes.
895 ///Pointer to the map of distances.
897 ///Pointer to the source node.
903 /// This constructor does not require parameters, therefore it initiates
904 /// all of the attributes to default values (0, INVALID).
905 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
907 _dist(0), _source(INVALID) {}
911 /// This constructor requires some parameters,
912 /// listed in the parameters list.
913 /// Others are initiated to 0.
914 /// \param g is the initial value of \ref _g
915 /// \param s is the initial value of \ref _source
916 DfsWizardBase(const GR &g, Node s=INVALID) :
917 _g((void *)&g), _reached(0), _processed(0), _pred(0),
919 _dist(0), _source(s) {}
923 /// A class to make the usage of the Dfs algorithm easier
925 /// This class is created to make it easier to use the Dfs algorithm.
926 /// It uses the functions and features of the plain \ref Dfs,
927 /// but it is much simpler to use it.
929 /// Simplicity means that the way to change the types defined
930 /// in the traits class is based on functions that returns the new class
931 /// and not on templatable built-in classes.
932 /// When using the plain \ref Dfs
933 /// the new class with the modified type comes from
934 /// the original class by using the ::
935 /// operator. In the case of \ref DfsWizard only
936 /// a function have to be called and it will
937 /// return the needed class.
939 /// It does not have own \ref run method. When its \ref run method is called
940 /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run
943 class DfsWizard : public TR
947 ///The type of the underlying graph.
948 typedef typename TR::Graph Graph;
950 typedef typename Graph::Node Node;
952 typedef typename Graph::NodeIt NodeIt;
954 typedef typename Graph::Edge Edge;
956 typedef typename Graph::OutEdgeIt OutEdgeIt;
958 ///\brief The type of the map that stores
960 typedef typename TR::ReachedMap ReachedMap;
961 ///\brief The type of the map that stores
962 ///the processed nodes
963 typedef typename TR::ProcessedMap ProcessedMap;
964 ///\brief The type of the map that stores the last
965 ///edges of the %DFS paths.
966 typedef typename TR::PredMap PredMap;
967 // ///\brief The type of the map that stores the last but one
968 // ///nodes of the %DFS paths.
969 // typedef typename TR::PredNodeMap PredNodeMap;
970 ///The type of the map that stores the distances of the nodes.
971 typedef typename TR::DistMap DistMap;
975 DfsWizard() : TR() {}
977 /// Constructor that requires parameters.
979 /// Constructor that requires parameters.
980 /// These parameters will be the default values for the traits class.
981 DfsWizard(const Graph &g, Node s=INVALID) :
985 DfsWizard(const TR &b) : TR(b) {}
989 ///Runs Dfs algorithm from a given node.
991 ///Runs Dfs algorithm from a given node.
992 ///The node can be given by the \ref source function.
995 if(Base::_source==INVALID) throw UninitializedParameter();
996 Dfs<Graph,TR> alg(*(Graph*)Base::_g);
997 if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached);
998 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
999 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
1000 // if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
1001 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
1002 alg.run(Base::_source);
1005 ///Runs Dfs algorithm from the given node.
1007 ///Runs Dfs algorithm from the given node.
1008 ///\param s is the given source.
1016 struct DefPredMapBase : public Base {
1018 static PredMap *createPredMap(const Graph &) { return 0; };
1019 DefPredMapBase(const TR &b) : TR(b) {}
1022 ///\brief \ref named-templ-param "Named parameter"
1023 ///function for setting PredMap type
1025 /// \ref named-templ-param "Named parameter"
1026 ///function for setting PredMap type
1029 DfsWizard<DefPredMapBase<T> > predMap(const T &t)
1031 Base::_pred=(void *)&t;
1032 return DfsWizard<DefPredMapBase<T> >(*this);
1037 struct DefReachedMapBase : public Base {
1038 typedef T ReachedMap;
1039 static ReachedMap *createReachedMap(const Graph &) { return 0; };
1040 DefReachedMapBase(const TR &b) : TR(b) {}
1043 ///\brief \ref named-templ-param "Named parameter"
1044 ///function for setting ReachedMap
1046 /// \ref named-templ-param "Named parameter"
1047 ///function for setting ReachedMap
1050 DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1052 Base::_pred=(void *)&t;
1053 return DfsWizard<DefReachedMapBase<T> >(*this);
1058 struct DefProcessedMapBase : public Base {
1059 typedef T ProcessedMap;
1060 static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
1061 DefProcessedMapBase(const TR &b) : TR(b) {}
1064 ///\brief \ref named-templ-param "Named parameter"
1065 ///function for setting ProcessedMap
1067 /// \ref named-templ-param "Named parameter"
1068 ///function for setting ProcessedMap
1071 DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1073 Base::_pred=(void *)&t;
1074 return DfsWizard<DefProcessedMapBase<T> >(*this);
1078 // template<class T>
1079 // struct DefPredNodeMapBase : public Base {
1080 // typedef T PredNodeMap;
1081 // static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
1082 // DefPredNodeMapBase(const TR &b) : TR(b) {}
1085 // ///\brief \ref named-templ-param "Named parameter"
1086 // ///function for setting PredNodeMap type
1088 // /// \ref named-templ-param "Named parameter"
1089 // ///function for setting PredNodeMap type
1091 // template<class T>
1092 // DfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1094 // Base::_predNode=(void *)&t;
1095 // return DfsWizard<DefPredNodeMapBase<T> >(*this);
1099 struct DefDistMapBase : public Base {
1101 static DistMap *createDistMap(const Graph &) { return 0; };
1102 DefDistMapBase(const TR &b) : TR(b) {}
1105 ///\brief \ref named-templ-param "Named parameter"
1106 ///function for setting DistMap type
1108 /// \ref named-templ-param "Named parameter"
1109 ///function for setting DistMap type
1112 DfsWizard<DefDistMapBase<T> > distMap(const T &t)
1114 Base::_dist=(void *)&t;
1115 return DfsWizard<DefDistMapBase<T> >(*this);
1118 /// Sets the source node, from which the Dfs algorithm runs.
1120 /// Sets the source node, from which the Dfs algorithm runs.
1121 /// \param s is the source node.
1122 DfsWizard<TR> &source(Node s)
1130 ///Function type interface for Dfs algorithm.
1132 /// \ingroup flowalgs
1133 ///Function type interface for Dfs algorithm.
1135 ///This function also has several
1136 ///\ref named-templ-func-param "named parameters",
1137 ///they are declared as the members of class \ref DfsWizard.
1139 ///example shows how to use these parameters.
1141 /// dfs(g,source).predMap(preds).run();
1143 ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
1144 ///to the end of the parameter list.
1148 DfsWizard<DfsWizardBase<GR> >
1149 dfs(const GR &g,typename GR::Node s=INVALID)
1151 return DfsWizard<DfsWizardBase<GR> >(g,s);
1154 } //END OF NAMESPACE LEMON