graph_orientation.cc: A thoroughly documented demo application.
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);
516 _stack[++_stack_head]=e;
517 _dist->set(s,_stack_head);
520 _processed->set(s,true);
526 ///Processes the next edge.
528 ///Processes the next edge.
530 ///\return The processed edge.
532 ///\pre The stack must not be empty!
533 Edge processNextEdge()
536 Edge e=_stack[_stack_head];
537 if(!(*_reached)[m=G->target(e)]) {
539 _reached->set(m,true);
540 // _pred_node->set(m,G->source(e));
542 _stack[_stack_head] = OutEdgeIt(*G, m);
543 _dist->set(m,_stack_head);
547 ++_stack[_stack_head];
549 //'m' is now the (original) source of the _stack[_stack_head]
550 while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
551 _processed->set(m,true);
554 m=G->source(_stack[_stack_head]);
555 ++_stack[_stack_head];
560 ///Next edge to be processed.
562 ///Next edge to be processed.
564 ///\return The next edge to be processed or INVALID if the stack is
568 return _stack_head>=0?_stack[_stack_head]:INVALID;
571 ///\brief Returns \c false if there are nodes
572 ///to be processed in the queue
574 ///Returns \c false if there are nodes
575 ///to be processed in the queue
577 ///\todo This should be called emptyStack() or some "neutral" name.
578 bool emptyQueue() { return _stack_head<0; }
579 ///Returns the number of the nodes to be processed.
581 ///Returns the number of the nodes to be processed in the queue.
583 ///\todo This should be called stackSize() or some "neutral" name.
584 int queueSize() { return _stack_head+1; }
586 ///Executes the algorithm.
588 ///Executes the algorithm.
590 ///\pre init() must be called and at least one node should be added
591 ///with addSource() before using this function.
593 ///This method runs the %DFS algorithm from the root node(s)
596 ///%DFS path to each node. The algorithm computes
598 ///- The distance of each node from the root(s) in the %DFS tree.
602 while ( !emptyQueue() ) processNextEdge();
605 ///Executes the algorithm until \c dest is reached.
607 ///Executes the algorithm until \c dest is reached.
609 ///\pre init() must be called and at least one node should be added
610 ///with addSource() before using this function.
612 ///This method runs the %DFS algorithm from the root node(s)
615 ///%DFS path to \c dest. The algorithm computes
616 ///- The %DFS path to \c dest.
617 ///- The distance of \c dest from the root(s) in the %DFS tree.
619 void start(Node dest)
621 while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
625 ///Executes the algorithm until a condition is met.
627 ///Executes the algorithm until a condition is met.
629 ///\pre init() must be called and at least one node should be added
630 ///with addSource() before using this function.
632 ///\param nm must be a bool (or convertible) edge map. The algorithm
633 ///will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>.
635 ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c nm is an edge map,
638 void start(const NM &nm)
640 while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge();
643 ///Runs %DFS algorithm from node \c s.
645 ///This method runs the %DFS algorithm from a root node \c s
648 ///%DFS path to each node. The algorithm computes
650 ///- The distance of each node from the root in the %DFS tree.
652 ///\note d.run(s) is just a shortcut of the following code.
664 ///Finds the %DFS path between \c s and \c t.
666 ///Finds the %DFS path between \c s and \c t.
668 ///\return The length of the %DFS s---t path if there exists one,
670 ///\note Apart from the return value, d.run(s,t) is
671 ///just a shortcut of the following code.
677 int run(Node s,Node t) {
681 return reached(t)?_stack_head+1:0;
686 ///\name Query Functions
687 ///The result of the %DFS algorithm can be obtained using these
689 ///Before the use of these functions,
690 ///either run() or start() must be called.
694 ///Copies the path to \c t on the DFS tree into \c p
696 ///This function copies the path to \c t on the DFS tree into \c p.
697 ///If \c t is a source itself or unreachable, then it does not
699 ///\todo Is this the right way to handle unreachable nodes?
701 ///\return Returns \c true if a path to \c t was actually copied to \c p,
702 ///\c false otherwise.
705 bool getPath(P &p,Node t)
709 typename P::Builder b(p);
710 for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
711 b.pushFront(pred(t));
718 ///The distance of a node from the root(s).
720 ///Returns the distance of a node from the root(s).
721 ///\pre \ref run() must be called before using this function.
722 ///\warning If node \c v is unreachable from the root(s) then the return value
723 ///of this funcion is undefined.
724 int dist(Node v) const { return (*_dist)[v]; }
726 ///Returns the 'previous edge' of the %DFS tree.
728 ///For a node \c v it returns the 'previous edge'
730 ///i.e. it returns the last edge of a %DFS path from the root(s) to \c
731 ///v. It is \ref INVALID
732 ///if \c v is unreachable from the root(s) or \c v is a root. The
733 ///%DFS tree used here is equal to the %DFS tree used in
735 ///\pre Either \ref run() or \ref start() must be called before using
737 ///\todo predEdge could be a better name.
738 Edge pred(Node v) const { return (*_pred)[v];}
740 ///Returns the 'previous node' of the %DFS tree.
742 ///For a node \c v it returns the 'previous node'
744 ///i.e. it returns the last but one node from a %DFS path from the
746 ///It is INVALID if \c v is unreachable from the root(s) or
747 ///if \c v itself a root.
748 ///The %DFS tree used here is equal to the %DFS
749 ///tree used in \ref pred().
750 ///\pre Either \ref run() or \ref start() must be called before
751 ///using this function.
752 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
753 G->source((*_pred)[v]); }
755 ///Returns a reference to the NodeMap of distances.
757 ///Returns a reference to the NodeMap of distances.
758 ///\pre Either \ref run() or \ref init() must
759 ///be called before using this function.
760 const DistMap &distMap() const { return *_dist;}
762 ///Returns a reference to the %DFS edge-tree map.
764 ///Returns a reference to the NodeMap of the edges of the
766 ///\pre Either \ref run() or \ref init()
767 ///must be called before using this function.
768 const PredMap &predMap() const { return *_pred;}
770 // ///Returns a reference to the map of nodes of %DFS paths.
772 // ///Returns a reference to the NodeMap of the last but one nodes of the
774 // ///\pre \ref run() must be called before using this function.
775 // const PredNodeMap &predNodeMap() const { return *_predNode;}
777 ///Checks if a node is reachable from the root.
779 ///Returns \c true if \c v is reachable from the root(s).
780 ///\warning The source nodes are inditated as unreachable.
781 ///\pre Either \ref run() or \ref start()
782 ///must be called before using this function.
784 bool reached(Node v) { return (*_reached)[v]; }
789 ///Default traits class of Dfs function.
791 ///Default traits class of Dfs function.
792 ///\param GR Graph type.
794 struct DfsWizardDefaultTraits
796 ///The graph type the algorithm runs on.
798 ///\brief The type of the map that stores the last
799 ///edges of the %DFS paths.
801 ///The type of the map that stores the last
802 ///edges of the %DFS paths.
803 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
805 typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
806 ///Instantiates a PredMap.
808 ///This function instantiates a \ref PredMap.
809 ///\param g is the graph, to which we would like to define the PredMap.
810 ///\todo The graph alone may be insufficient to initialize
812 static PredMap *createPredMap(const GR &g)
814 static PredMap *createPredMap(const GR &)
817 return new PredMap();
819 // ///\brief The type of the map that stores the last but one
820 // ///nodes of the %DFS paths.
822 // ///The type of the map that stores the last but one
823 // ///nodes of the %DFS paths.
824 // ///It must meet the \ref concept::WriteMap "WriteMap" concept.
826 // typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
827 // ///Instantiates a PredNodeMap.
829 // ///This function instantiates a \ref PredNodeMap.
830 // ///\param G is the graph, to which
831 // ///we would like to define the \ref PredNodeMap
832 // static PredNodeMap *createPredNodeMap(const GR &G)
834 // return new PredNodeMap();
837 ///The type of the map that indicates which nodes are processed.
839 ///The type of the map that indicates which nodes are processed.
840 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
841 ///\todo named parameter to set this type, function to read and write.
842 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
843 ///Instantiates a ProcessedMap.
845 ///This function instantiates a \ref ProcessedMap.
846 ///\param g is the graph, to which
847 ///we would like to define the \ref ProcessedMap
849 static ProcessedMap *createProcessedMap(const GR &g)
851 static ProcessedMap *createProcessedMap(const GR &)
854 return new ProcessedMap();
856 ///The type of the map that indicates which nodes are reached.
858 ///The type of the map that indicates which nodes are reached.
859 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
860 ///\todo named parameter to set this type, function to read and write.
861 typedef typename Graph::template NodeMap<bool> ReachedMap;
862 ///Instantiates a ReachedMap.
864 ///This function instantiates a \ref ReachedMap.
865 ///\param G is the graph, to which
866 ///we would like to define the \ref ReachedMap.
867 static ReachedMap *createReachedMap(const GR &G)
869 return new ReachedMap(G);
871 ///The type of the map that stores the dists of the nodes.
873 ///The type of the map that stores the dists of the nodes.
874 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
876 typedef NullMap<typename Graph::Node,int> DistMap;
877 ///Instantiates a DistMap.
879 ///This function instantiates a \ref DistMap.
880 ///\param g is the graph, to which we would like to define the \ref DistMap
882 static DistMap *createDistMap(const GR &g)
884 static DistMap *createDistMap(const GR &)
887 return new DistMap();
891 /// Default traits used by \ref DfsWizard
893 /// To make it easier to use Dfs algorithm
894 ///we have created a wizard class.
895 /// This \ref DfsWizard class needs default traits,
896 ///as well as the \ref Dfs class.
897 /// The \ref DfsWizardBase is a class to be the default traits of the
898 /// \ref DfsWizard class.
900 class DfsWizardBase : public DfsWizardDefaultTraits<GR>
903 typedef DfsWizardDefaultTraits<GR> Base;
905 /// Type of the nodes in the graph.
906 typedef typename Base::Graph::Node Node;
908 /// Pointer to the underlying graph.
910 ///Pointer to the map of reached nodes.
912 ///Pointer to the map of processed nodes.
914 ///Pointer to the map of predecessors edges.
916 // ///Pointer to the map of predecessors nodes.
918 ///Pointer to the map of distances.
920 ///Pointer to the source node.
926 /// This constructor does not require parameters, therefore it initiates
927 /// all of the attributes to default values (0, INVALID).
928 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
930 _dist(0), _source(INVALID) {}
934 /// This constructor requires some parameters,
935 /// listed in the parameters list.
936 /// Others are initiated to 0.
937 /// \param g is the initial value of \ref _g
938 /// \param s is the initial value of \ref _source
939 DfsWizardBase(const GR &g, Node s=INVALID) :
940 _g((void *)&g), _reached(0), _processed(0), _pred(0),
942 _dist(0), _source(s) {}
946 /// A class to make the usage of the Dfs algorithm easier
948 /// This class is created to make it easier to use the Dfs algorithm.
949 /// It uses the functions and features of the plain \ref Dfs,
950 /// but it is much simpler to use it.
952 /// Simplicity means that the way to change the types defined
953 /// in the traits class is based on functions that returns the new class
954 /// and not on templatable built-in classes.
955 /// When using the plain \ref Dfs
956 /// the new class with the modified type comes from
957 /// the original class by using the ::
958 /// operator. In the case of \ref DfsWizard only
959 /// a function have to be called and it will
960 /// return the needed class.
962 /// It does not have own \ref run method. When its \ref run method is called
963 /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run
966 class DfsWizard : public TR
970 ///The type of the underlying graph.
971 typedef typename TR::Graph Graph;
973 typedef typename Graph::Node Node;
975 typedef typename Graph::NodeIt NodeIt;
977 typedef typename Graph::Edge Edge;
979 typedef typename Graph::OutEdgeIt OutEdgeIt;
981 ///\brief The type of the map that stores
983 typedef typename TR::ReachedMap ReachedMap;
984 ///\brief The type of the map that stores
985 ///the processed nodes
986 typedef typename TR::ProcessedMap ProcessedMap;
987 ///\brief The type of the map that stores the last
988 ///edges of the %DFS paths.
989 typedef typename TR::PredMap PredMap;
990 // ///\brief The type of the map that stores the last but one
991 // ///nodes of the %DFS paths.
992 // typedef typename TR::PredNodeMap PredNodeMap;
993 ///The type of the map that stores the distances of the nodes.
994 typedef typename TR::DistMap DistMap;
998 DfsWizard() : TR() {}
1000 /// Constructor that requires parameters.
1002 /// Constructor that requires parameters.
1003 /// These parameters will be the default values for the traits class.
1004 DfsWizard(const Graph &g, Node s=INVALID) :
1008 DfsWizard(const TR &b) : TR(b) {}
1012 ///Runs Dfs algorithm from a given node.
1014 ///Runs Dfs algorithm from a given node.
1015 ///The node can be given by the \ref source function.
1018 if(Base::_source==INVALID) throw UninitializedParameter();
1019 Dfs<Graph,TR> alg(*(Graph*)Base::_g);
1020 if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached);
1021 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
1022 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
1023 // if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
1024 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
1025 alg.run(Base::_source);
1028 ///Runs Dfs algorithm from the given node.
1030 ///Runs Dfs algorithm from the given node.
1031 ///\param s is the given source.
1039 struct DefPredMapBase : public Base {
1041 static PredMap *createPredMap(const Graph &) { return 0; };
1042 DefPredMapBase(const TR &b) : TR(b) {}
1045 ///\brief \ref named-templ-param "Named parameter"
1046 ///function for setting PredMap type
1048 /// \ref named-templ-param "Named parameter"
1049 ///function for setting PredMap type
1052 DfsWizard<DefPredMapBase<T> > predMap(const T &t)
1054 Base::_pred=(void *)&t;
1055 return DfsWizard<DefPredMapBase<T> >(*this);
1060 struct DefReachedMapBase : public Base {
1061 typedef T ReachedMap;
1062 static ReachedMap *createReachedMap(const Graph &) { return 0; };
1063 DefReachedMapBase(const TR &b) : TR(b) {}
1066 ///\brief \ref named-templ-param "Named parameter"
1067 ///function for setting ReachedMap
1069 /// \ref named-templ-param "Named parameter"
1070 ///function for setting ReachedMap
1073 DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1075 Base::_pred=(void *)&t;
1076 return DfsWizard<DefReachedMapBase<T> >(*this);
1081 struct DefProcessedMapBase : public Base {
1082 typedef T ProcessedMap;
1083 static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
1084 DefProcessedMapBase(const TR &b) : TR(b) {}
1087 ///\brief \ref named-templ-param "Named parameter"
1088 ///function for setting ProcessedMap
1090 /// \ref named-templ-param "Named parameter"
1091 ///function for setting ProcessedMap
1094 DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1096 Base::_pred=(void *)&t;
1097 return DfsWizard<DefProcessedMapBase<T> >(*this);
1101 // template<class T>
1102 // struct DefPredNodeMapBase : public Base {
1103 // typedef T PredNodeMap;
1104 // static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
1105 // DefPredNodeMapBase(const TR &b) : TR(b) {}
1108 // ///\brief \ref named-templ-param "Named parameter"
1109 // ///function for setting PredNodeMap type
1111 // /// \ref named-templ-param "Named parameter"
1112 // ///function for setting PredNodeMap type
1114 // template<class T>
1115 // DfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1117 // Base::_predNode=(void *)&t;
1118 // return DfsWizard<DefPredNodeMapBase<T> >(*this);
1122 struct DefDistMapBase : public Base {
1124 static DistMap *createDistMap(const Graph &) { return 0; };
1125 DefDistMapBase(const TR &b) : TR(b) {}
1128 ///\brief \ref named-templ-param "Named parameter"
1129 ///function for setting DistMap type
1131 /// \ref named-templ-param "Named parameter"
1132 ///function for setting DistMap type
1135 DfsWizard<DefDistMapBase<T> > distMap(const T &t)
1137 Base::_dist=(void *)&t;
1138 return DfsWizard<DefDistMapBase<T> >(*this);
1141 /// Sets the source node, from which the Dfs algorithm runs.
1143 /// Sets the source node, from which the Dfs algorithm runs.
1144 /// \param s is the source node.
1145 DfsWizard<TR> &source(Node s)
1153 ///Function type interface for Dfs algorithm.
1155 /// \ingroup flowalgs
1156 ///Function type interface for Dfs algorithm.
1158 ///This function also has several
1159 ///\ref named-templ-func-param "named parameters",
1160 ///they are declared as the members of class \ref DfsWizard.
1162 ///example shows how to use these parameters.
1164 /// dfs(g,source).predMap(preds).run();
1166 ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
1167 ///to the end of the parameter list.
1171 DfsWizard<DfsWizardBase<GR> >
1172 dfs(const GR &g,typename GR::Node s=INVALID)
1174 return DfsWizard<DfsWizardBase<GR> >(g,s);
1177 } //END OF NAMESPACE LEMON