Functions to query the next node/edge to be processed.
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);
515 if(e!=INVALID) _stack[++_stack_head]=e;
516 else _processed->set(s,true);
517 _dist->set(s,_stack_head);
521 ///Processes the next edge.
523 ///Processes the next edge.
525 ///\return The processed edge.
527 ///\pre The stack must not be empty!
528 Edge processNextEdge()
531 Edge e=_stack[_stack_head];
532 if(!(*_reached)[m=G->target(e)]) {
534 _reached->set(m,true);
535 // _pred_node->set(m,G->source(e));
537 _stack[_stack_head] = OutEdgeIt(*G, m);
538 _dist->set(m,_stack_head);
542 ++_stack[_stack_head];
544 //'m' is now the (original) source of the _stack[_stack_head]
545 while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
546 _processed->set(m,true);
549 m=G->source(_stack[_stack_head]);
550 ++_stack[_stack_head];
555 ///Next edge to be processed.
557 ///Next edge to be processed.
559 ///\return The next edge to be processed or INVALID if the stack is
563 return _stack_head>=0?_stack[_stack_head]:INVALID;
566 ///\brief Returns \c false if there are nodes
567 ///to be processed in the queue
569 ///Returns \c false if there are nodes
570 ///to be processed in the queue
572 ///\todo This should be called emptyStack() or some "neutral" name.
573 bool emptyQueue() { return _stack_head<0; }
574 ///Returns the number of the nodes to be processed.
576 ///Returns the number of the nodes to be processed in the queue.
578 ///\todo This should be called stackSize() or some "neutral" name.
579 int queueSize() { return _stack_head+1; }
581 ///Executes the algorithm.
583 ///Executes the algorithm.
585 ///\pre init() must be called and at least one node should be added
586 ///with addSource() before using this function.
588 ///This method runs the %DFS algorithm from the root node(s)
591 ///%DFS path to each node. The algorithm computes
593 ///- The distance of each node from the root(s) in the %DFS tree.
597 while ( !emptyQueue() ) processNextEdge();
600 ///Executes the algorithm until \c dest is reached.
602 ///Executes the algorithm until \c dest is reached.
604 ///\pre init() must be called and at least one node should be added
605 ///with addSource() before using this function.
607 ///This method runs the %DFS algorithm from the root node(s)
610 ///%DFS path to \c dest. The algorithm computes
611 ///- The %DFS path to \c dest.
612 ///- The distance of \c dest from the root(s) in the %DFS tree.
614 void start(Node dest)
616 while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
620 ///Executes the algorithm until a condition is met.
622 ///Executes the algorithm until a condition is met.
624 ///\pre init() must be called and at least one node should be added
625 ///with addSource() before using this function.
627 ///\param nm must be a bool (or convertible) edge map. The algorithm
628 ///will stop when it reaches an edge \c e with <tt>nm[e]==true</tt>.
630 ///\warning Contrary to \ref Dfs and \ref Dijkstra, \c nm is an edge map,
633 void start(const NM &nm)
635 while ( !emptyQueue() && !nm[_stack[_stack_head]] ) processNextEdge();
638 ///Runs %DFS algorithm from node \c s.
640 ///This method runs the %DFS algorithm from a root node \c s
643 ///%DFS path to each node. The algorithm computes
645 ///- The distance of each node from the root in the %DFS tree.
647 ///\note d.run(s) is just a shortcut of the following code.
659 ///Finds the %DFS path between \c s and \c t.
661 ///Finds the %DFS path between \c s and \c t.
663 ///\return The length of the %DFS s---t path if there exists one,
665 ///\note Apart from the return value, d.run(s,t) is
666 ///just a shortcut of the following code.
672 int run(Node s,Node t) {
676 return reached(t)?_stack_head+1:0;
681 ///\name Query Functions
682 ///The result of the %DFS algorithm can be obtained using these
684 ///Before the use of these functions,
685 ///either run() or start() must be called.
689 ///Copies the path to \c t on the DFS tree into \c p
691 ///This function copies the path to \c t on the DFS tree into \c p.
692 ///If \c t is a source itself or unreachable, then it does not
694 ///\todo Is this the right way to handle unreachable nodes?
696 ///\return Returns \c true if a path to \c t was actually copied to \c p,
697 ///\c false otherwise.
700 bool getPath(P &p,Node t)
704 typename P::Builder b(p);
705 for(b.setStartNode(t);pred(t)!=INVALID;t=predNode(t))
706 b.pushFront(pred(t));
713 ///The distance of a node from the root(s).
715 ///Returns the distance of a node from the root(s).
716 ///\pre \ref run() must be called before using this function.
717 ///\warning If node \c v is unreachable from the root(s) then the return value
718 ///of this funcion is undefined.
719 int dist(Node v) const { return (*_dist)[v]; }
721 ///Returns the 'previous edge' of the %DFS tree.
723 ///For a node \c v it returns the 'previous edge'
725 ///i.e. it returns the last edge of a %DFS path from the root(s) to \c
726 ///v. It is \ref INVALID
727 ///if \c v is unreachable from the root(s) or \c v is a root. The
728 ///%DFS tree used here is equal to the %DFS tree used in
730 ///\pre Either \ref run() or \ref start() must be called before using
732 ///\todo predEdge could be a better name.
733 Edge pred(Node v) const { return (*_pred)[v];}
735 ///Returns the 'previous node' of the %DFS tree.
737 ///For a node \c v it returns the 'previous node'
739 ///i.e. it returns the last but one node from a %DFS path from the
741 ///It is INVALID if \c v is unreachable from the root(s) or
742 ///if \c v itself a root.
743 ///The %DFS tree used here is equal to the %DFS
744 ///tree used in \ref pred().
745 ///\pre Either \ref run() or \ref start() must be called before
746 ///using this function.
747 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
748 G->source((*_pred)[v]); }
750 ///Returns a reference to the NodeMap of distances.
752 ///Returns a reference to the NodeMap of distances.
753 ///\pre Either \ref run() or \ref init() must
754 ///be called before using this function.
755 const DistMap &distMap() const { return *_dist;}
757 ///Returns a reference to the %DFS edge-tree map.
759 ///Returns a reference to the NodeMap of the edges of the
761 ///\pre Either \ref run() or \ref init()
762 ///must be called before using this function.
763 const PredMap &predMap() const { return *_pred;}
765 // ///Returns a reference to the map of nodes of %DFS paths.
767 // ///Returns a reference to the NodeMap of the last but one nodes of the
769 // ///\pre \ref run() must be called before using this function.
770 // const PredNodeMap &predNodeMap() const { return *_predNode;}
772 ///Checks if a node is reachable from the root.
774 ///Returns \c true if \c v is reachable from the root(s).
775 ///\warning The source nodes are inditated as unreachable.
776 ///\pre Either \ref run() or \ref start()
777 ///must be called before using this function.
779 bool reached(Node v) { return (*_reached)[v]; }
784 ///Default traits class of Dfs function.
786 ///Default traits class of Dfs function.
787 ///\param GR Graph type.
789 struct DfsWizardDefaultTraits
791 ///The graph type the algorithm runs on.
793 ///\brief The type of the map that stores the last
794 ///edges of the %DFS paths.
796 ///The type of the map that stores the last
797 ///edges of the %DFS paths.
798 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
800 typedef NullMap<typename Graph::Node,typename GR::Edge> PredMap;
801 ///Instantiates a PredMap.
803 ///This function instantiates a \ref PredMap.
804 ///\param g is the graph, to which we would like to define the PredMap.
805 ///\todo The graph alone may be insufficient to initialize
807 static PredMap *createPredMap(const GR &g)
809 static PredMap *createPredMap(const GR &)
812 return new PredMap();
814 // ///\brief The type of the map that stores the last but one
815 // ///nodes of the %DFS paths.
817 // ///The type of the map that stores the last but one
818 // ///nodes of the %DFS paths.
819 // ///It must meet the \ref concept::WriteMap "WriteMap" concept.
821 // typedef NullMap<typename Graph::Node,typename Graph::Node> PredNodeMap;
822 // ///Instantiates a PredNodeMap.
824 // ///This function instantiates a \ref PredNodeMap.
825 // ///\param G is the graph, to which
826 // ///we would like to define the \ref PredNodeMap
827 // static PredNodeMap *createPredNodeMap(const GR &G)
829 // return new PredNodeMap();
832 ///The type of the map that indicates which nodes are processed.
834 ///The type of the map that indicates which nodes are processed.
835 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
836 ///\todo named parameter to set this type, function to read and write.
837 typedef NullMap<typename Graph::Node,bool> ProcessedMap;
838 ///Instantiates a ProcessedMap.
840 ///This function instantiates a \ref ProcessedMap.
841 ///\param g is the graph, to which
842 ///we would like to define the \ref ProcessedMap
844 static ProcessedMap *createProcessedMap(const GR &g)
846 static ProcessedMap *createProcessedMap(const GR &)
849 return new ProcessedMap();
851 ///The type of the map that indicates which nodes are reached.
853 ///The type of the map that indicates which nodes are reached.
854 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
855 ///\todo named parameter to set this type, function to read and write.
856 typedef typename Graph::template NodeMap<bool> ReachedMap;
857 ///Instantiates a ReachedMap.
859 ///This function instantiates a \ref ReachedMap.
860 ///\param G is the graph, to which
861 ///we would like to define the \ref ReachedMap.
862 static ReachedMap *createReachedMap(const GR &G)
864 return new ReachedMap(G);
866 ///The type of the map that stores the dists of the nodes.
868 ///The type of the map that stores the dists of the nodes.
869 ///It must meet the \ref concept::WriteMap "WriteMap" concept.
871 typedef NullMap<typename Graph::Node,int> DistMap;
872 ///Instantiates a DistMap.
874 ///This function instantiates a \ref DistMap.
875 ///\param g is the graph, to which we would like to define the \ref DistMap
877 static DistMap *createDistMap(const GR &g)
879 static DistMap *createDistMap(const GR &)
882 return new DistMap();
886 /// Default traits used by \ref DfsWizard
888 /// To make it easier to use Dfs algorithm
889 ///we have created a wizard class.
890 /// This \ref DfsWizard class needs default traits,
891 ///as well as the \ref Dfs class.
892 /// The \ref DfsWizardBase is a class to be the default traits of the
893 /// \ref DfsWizard class.
895 class DfsWizardBase : public DfsWizardDefaultTraits<GR>
898 typedef DfsWizardDefaultTraits<GR> Base;
900 /// Type of the nodes in the graph.
901 typedef typename Base::Graph::Node Node;
903 /// Pointer to the underlying graph.
905 ///Pointer to the map of reached nodes.
907 ///Pointer to the map of processed nodes.
909 ///Pointer to the map of predecessors edges.
911 // ///Pointer to the map of predecessors nodes.
913 ///Pointer to the map of distances.
915 ///Pointer to the source node.
921 /// This constructor does not require parameters, therefore it initiates
922 /// all of the attributes to default values (0, INVALID).
923 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
925 _dist(0), _source(INVALID) {}
929 /// This constructor requires some parameters,
930 /// listed in the parameters list.
931 /// Others are initiated to 0.
932 /// \param g is the initial value of \ref _g
933 /// \param s is the initial value of \ref _source
934 DfsWizardBase(const GR &g, Node s=INVALID) :
935 _g((void *)&g), _reached(0), _processed(0), _pred(0),
937 _dist(0), _source(s) {}
941 /// A class to make the usage of the Dfs algorithm easier
943 /// This class is created to make it easier to use the Dfs algorithm.
944 /// It uses the functions and features of the plain \ref Dfs,
945 /// but it is much simpler to use it.
947 /// Simplicity means that the way to change the types defined
948 /// in the traits class is based on functions that returns the new class
949 /// and not on templatable built-in classes.
950 /// When using the plain \ref Dfs
951 /// the new class with the modified type comes from
952 /// the original class by using the ::
953 /// operator. In the case of \ref DfsWizard only
954 /// a function have to be called and it will
955 /// return the needed class.
957 /// It does not have own \ref run method. When its \ref run method is called
958 /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run
961 class DfsWizard : public TR
965 ///The type of the underlying graph.
966 typedef typename TR::Graph Graph;
968 typedef typename Graph::Node Node;
970 typedef typename Graph::NodeIt NodeIt;
972 typedef typename Graph::Edge Edge;
974 typedef typename Graph::OutEdgeIt OutEdgeIt;
976 ///\brief The type of the map that stores
978 typedef typename TR::ReachedMap ReachedMap;
979 ///\brief The type of the map that stores
980 ///the processed nodes
981 typedef typename TR::ProcessedMap ProcessedMap;
982 ///\brief The type of the map that stores the last
983 ///edges of the %DFS paths.
984 typedef typename TR::PredMap PredMap;
985 // ///\brief The type of the map that stores the last but one
986 // ///nodes of the %DFS paths.
987 // typedef typename TR::PredNodeMap PredNodeMap;
988 ///The type of the map that stores the distances of the nodes.
989 typedef typename TR::DistMap DistMap;
993 DfsWizard() : TR() {}
995 /// Constructor that requires parameters.
997 /// Constructor that requires parameters.
998 /// These parameters will be the default values for the traits class.
999 DfsWizard(const Graph &g, Node s=INVALID) :
1003 DfsWizard(const TR &b) : TR(b) {}
1007 ///Runs Dfs algorithm from a given node.
1009 ///Runs Dfs algorithm from a given node.
1010 ///The node can be given by the \ref source function.
1013 if(Base::_source==INVALID) throw UninitializedParameter();
1014 Dfs<Graph,TR> alg(*(Graph*)Base::_g);
1015 if(Base::_reached) alg.reachedMap(*(ReachedMap*)Base::_reached);
1016 if(Base::_processed) alg.processedMap(*(ProcessedMap*)Base::_processed);
1017 if(Base::_pred) alg.predMap(*(PredMap*)Base::_pred);
1018 // if(Base::_predNode) alg.predNodeMap(*(PredNodeMap*)Base::_predNode);
1019 if(Base::_dist) alg.distMap(*(DistMap*)Base::_dist);
1020 alg.run(Base::_source);
1023 ///Runs Dfs algorithm from the given node.
1025 ///Runs Dfs algorithm from the given node.
1026 ///\param s is the given source.
1034 struct DefPredMapBase : public Base {
1036 static PredMap *createPredMap(const Graph &) { return 0; };
1037 DefPredMapBase(const TR &b) : TR(b) {}
1040 ///\brief \ref named-templ-param "Named parameter"
1041 ///function for setting PredMap type
1043 /// \ref named-templ-param "Named parameter"
1044 ///function for setting PredMap type
1047 DfsWizard<DefPredMapBase<T> > predMap(const T &t)
1049 Base::_pred=(void *)&t;
1050 return DfsWizard<DefPredMapBase<T> >(*this);
1055 struct DefReachedMapBase : public Base {
1056 typedef T ReachedMap;
1057 static ReachedMap *createReachedMap(const Graph &) { return 0; };
1058 DefReachedMapBase(const TR &b) : TR(b) {}
1061 ///\brief \ref named-templ-param "Named parameter"
1062 ///function for setting ReachedMap
1064 /// \ref named-templ-param "Named parameter"
1065 ///function for setting ReachedMap
1068 DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1070 Base::_pred=(void *)&t;
1071 return DfsWizard<DefReachedMapBase<T> >(*this);
1076 struct DefProcessedMapBase : public Base {
1077 typedef T ProcessedMap;
1078 static ProcessedMap *createProcessedMap(const Graph &) { return 0; };
1079 DefProcessedMapBase(const TR &b) : TR(b) {}
1082 ///\brief \ref named-templ-param "Named parameter"
1083 ///function for setting ProcessedMap
1085 /// \ref named-templ-param "Named parameter"
1086 ///function for setting ProcessedMap
1089 DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1091 Base::_pred=(void *)&t;
1092 return DfsWizard<DefProcessedMapBase<T> >(*this);
1096 // template<class T>
1097 // struct DefPredNodeMapBase : public Base {
1098 // typedef T PredNodeMap;
1099 // static PredNodeMap *createPredNodeMap(const Graph &G) { return 0; };
1100 // DefPredNodeMapBase(const TR &b) : TR(b) {}
1103 // ///\brief \ref named-templ-param "Named parameter"
1104 // ///function for setting PredNodeMap type
1106 // /// \ref named-templ-param "Named parameter"
1107 // ///function for setting PredNodeMap type
1109 // template<class T>
1110 // DfsWizard<DefPredNodeMapBase<T> > predNodeMap(const T &t)
1112 // Base::_predNode=(void *)&t;
1113 // return DfsWizard<DefPredNodeMapBase<T> >(*this);
1117 struct DefDistMapBase : public Base {
1119 static DistMap *createDistMap(const Graph &) { return 0; };
1120 DefDistMapBase(const TR &b) : TR(b) {}
1123 ///\brief \ref named-templ-param "Named parameter"
1124 ///function for setting DistMap type
1126 /// \ref named-templ-param "Named parameter"
1127 ///function for setting DistMap type
1130 DfsWizard<DefDistMapBase<T> > distMap(const T &t)
1132 Base::_dist=(void *)&t;
1133 return DfsWizard<DefDistMapBase<T> >(*this);
1136 /// Sets the source node, from which the Dfs algorithm runs.
1138 /// Sets the source node, from which the Dfs algorithm runs.
1139 /// \param s is the source node.
1140 DfsWizard<TR> &source(Node s)
1148 ///Function type interface for Dfs algorithm.
1150 /// \ingroup flowalgs
1151 ///Function type interface for Dfs algorithm.
1153 ///This function also has several
1154 ///\ref named-templ-func-param "named parameters",
1155 ///they are declared as the members of class \ref DfsWizard.
1157 ///example shows how to use these parameters.
1159 /// dfs(g,source).predMap(preds).run();
1161 ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
1162 ///to the end of the parameter list.
1166 DfsWizard<DfsWizardBase<GR> >
1167 dfs(const GR &g,typename GR::Node s=INVALID)
1169 return DfsWizard<DfsWizardBase<GR> >(g,s);
1172 } //END OF NAMESPACE LEMON