1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
24 ///\brief DFS algorithm.
26 #include <lemon/list_graph.h>
27 #include <lemon/graph_utils.h>
28 #include <lemon/bits/path_dump.h>
29 #include <lemon/bits/invalid.h>
30 #include <lemon/error.h>
31 #include <lemon/assert.h>
32 #include <lemon/maps.h>
36 ///Default traits class of Dfs class.
38 ///Default traits class of Dfs class.
39 ///\tparam GR Digraph type.
41 struct DfsDefaultTraits
43 ///The type of the digraph the algorithm runs on.
46 ///\brief The type of the map that stores the predecessor
47 ///arcs of the %DFS paths.
49 ///The type of the map that stores the predecessor
50 ///arcs of the %DFS paths.
51 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
52 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
53 ///Instantiates a \ref PredMap.
55 ///This function instantiates a \ref PredMap.
56 ///\param g is the digraph, to which we would like to define the
58 ///\todo The digraph alone may be insufficient to initialize
59 static PredMap *createPredMap(const Digraph &g)
61 return new PredMap(g);
64 ///The type of the map that indicates which nodes are processed.
66 ///The type of the map that indicates which nodes are processed.
67 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
68 ///By default it is a NullMap.
69 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
70 ///Instantiates a \ref ProcessedMap.
72 ///This function instantiates a \ref ProcessedMap.
73 ///\param g is the digraph, to which
74 ///we would like to define the \ref ProcessedMap
76 static ProcessedMap *createProcessedMap(const Digraph &g)
78 static ProcessedMap *createProcessedMap(const Digraph &)
81 return new ProcessedMap();
84 ///The type of the map that indicates which nodes are reached.
86 ///The type of the map that indicates which nodes are reached.
87 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
88 typedef typename Digraph::template NodeMap<bool> ReachedMap;
89 ///Instantiates a \ref ReachedMap.
91 ///This function instantiates a \ref ReachedMap.
92 ///\param g is the digraph, to which
93 ///we would like to define the \ref ReachedMap.
94 static ReachedMap *createReachedMap(const Digraph &g)
96 return new ReachedMap(g);
99 ///The type of the map that stores the distances of the nodes.
101 ///The type of the map that stores the distances of the nodes.
102 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
103 typedef typename Digraph::template NodeMap<int> DistMap;
104 ///Instantiates a \ref DistMap.
106 ///This function instantiates a \ref DistMap.
107 ///\param g is the digraph, to which we would like to define the
109 static DistMap *createDistMap(const Digraph &g)
111 return new DistMap(g);
115 ///%DFS algorithm class.
118 ///This class provides an efficient implementation of the %DFS algorithm.
120 ///There is also a \ref dfs() "function type interface" for the DFS
121 ///algorithm, which is convenient in the simplier cases and it can be
124 ///\tparam GR The type of the digraph the algorithm runs on.
125 ///The default value is \ref ListDigraph. The value of GR is not used
126 ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
127 ///\tparam TR Traits class to set various data types used by the algorithm.
128 ///The default traits class is
129 ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
130 ///See \ref DfsDefaultTraits for the documentation of
131 ///a Dfs traits class.
133 template <typename GR,
136 template <typename GR=ListDigraph,
137 typename TR=DfsDefaultTraits<GR> >
141 ///\ref Exception for uninitialized parameters.
143 ///This error represents problems in the initialization of the
144 ///parameters of the algorithm.
145 class UninitializedParameter : public lemon::UninitializedParameter {
147 virtual const char* what() const throw() {
148 return "lemon::Dfs::UninitializedParameter";
152 ///The type of the digraph the algorithm runs on.
153 typedef typename TR::Digraph Digraph;
155 ///\brief The type of the map that stores the predecessor arcs of the
157 typedef typename TR::PredMap PredMap;
158 ///The type of the map that stores the distances of the nodes.
159 typedef typename TR::DistMap DistMap;
160 ///The type of the map that indicates which nodes are reached.
161 typedef typename TR::ReachedMap ReachedMap;
162 ///The type of the map that indicates which nodes are processed.
163 typedef typename TR::ProcessedMap ProcessedMap;
164 ///The type of the paths.
165 typedef PredMapPath<Digraph, PredMap> Path;
172 typedef typename Digraph::Node Node;
173 typedef typename Digraph::NodeIt NodeIt;
174 typedef typename Digraph::Arc Arc;
175 typedef typename Digraph::OutArcIt OutArcIt;
177 //Pointer to the underlying digraph.
179 //Pointer to the map of predecessor arcs.
181 //Indicates if _pred is locally allocated (true) or not.
183 //Pointer to the map of distances.
185 //Indicates if _dist is locally allocated (true) or not.
187 //Pointer to the map of reached status of the nodes.
188 ReachedMap *_reached;
189 //Indicates if _reached is locally allocated (true) or not.
191 //Pointer to the map of processed status of the nodes.
192 ProcessedMap *_processed;
193 //Indicates if _processed is locally allocated (true) or not.
194 bool local_processed;
196 std::vector<typename Digraph::OutArcIt> _stack;
199 ///Creates the maps if necessary.
200 ///\todo Better memory allocation (instead of new).
205 _pred = Traits::createPredMap(*G);
209 _dist = Traits::createDistMap(*G);
212 local_reached = true;
213 _reached = Traits::createReachedMap(*G);
216 local_processed = true;
217 _processed = Traits::createProcessedMap(*G);
229 ///\name Named template parameters
234 struct DefPredMapTraits : public Traits {
236 static PredMap *createPredMap(const Digraph &)
238 throw UninitializedParameter();
241 ///\brief \ref named-templ-param "Named parameter" for setting
242 ///\ref PredMap type.
244 ///\ref named-templ-param "Named parameter" for setting
245 ///\ref PredMap type.
247 struct DefPredMap : public Dfs<Digraph, DefPredMapTraits<T> > {
248 typedef Dfs<Digraph, DefPredMapTraits<T> > Create;
252 struct DefDistMapTraits : public Traits {
254 static DistMap *createDistMap(const Digraph &)
256 throw UninitializedParameter();
259 ///\brief \ref named-templ-param "Named parameter" for setting
260 ///\ref DistMap type.
262 ///\ref named-templ-param "Named parameter" for setting
263 ///\ref DistMap type.
265 struct DefDistMap : public Dfs< Digraph, DefDistMapTraits<T> > {
266 typedef Dfs<Digraph, DefDistMapTraits<T> > Create;
270 struct DefReachedMapTraits : public Traits {
271 typedef T ReachedMap;
272 static ReachedMap *createReachedMap(const Digraph &)
274 throw UninitializedParameter();
277 ///\brief \ref named-templ-param "Named parameter" for setting
278 ///\ref ReachedMap type.
280 ///\ref named-templ-param "Named parameter" for setting
281 ///\ref ReachedMap type.
283 struct DefReachedMap : public Dfs< Digraph, DefReachedMapTraits<T> > {
284 typedef Dfs< Digraph, DefReachedMapTraits<T> > Create;
288 struct DefProcessedMapTraits : public Traits {
289 typedef T ProcessedMap;
290 static ProcessedMap *createProcessedMap(const Digraph &)
292 throw UninitializedParameter();
295 ///\brief \ref named-templ-param "Named parameter" for setting
296 ///\ref ProcessedMap type.
298 ///\ref named-templ-param "Named parameter" for setting
299 ///\ref ProcessedMap type.
301 struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > {
302 typedef Dfs< Digraph, DefProcessedMapTraits<T> > Create;
305 struct DefDigraphProcessedMapTraits : public Traits {
306 typedef typename Digraph::template NodeMap<bool> ProcessedMap;
307 static ProcessedMap *createProcessedMap(const Digraph &g)
309 return new ProcessedMap(g);
312 ///\brief \ref named-templ-param "Named parameter" for setting
313 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
315 ///\ref named-templ-param "Named parameter" for setting
316 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
317 ///If you don't set it explicitly, it will be automatically allocated.
319 struct DefProcessedMapToBeDefaultMap :
320 public Dfs< Digraph, DefDigraphProcessedMapTraits> {
321 typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create;
331 ///\param g The digraph the algorithm runs on.
332 Dfs(const Digraph &g) :
334 _pred(NULL), local_pred(false),
335 _dist(NULL), local_dist(false),
336 _reached(NULL), local_reached(false),
337 _processed(NULL), local_processed(false)
343 if(local_pred) delete _pred;
344 if(local_dist) delete _dist;
345 if(local_reached) delete _reached;
346 if(local_processed) delete _processed;
349 ///Sets the map that stores the predecessor arcs.
351 ///Sets the map that stores the predecessor arcs.
352 ///If you don't use this function before calling \ref run(),
353 ///it will allocate one. The destructor deallocates this
354 ///automatically allocated map, of course.
355 ///\return <tt> (*this) </tt>
356 Dfs &predMap(PredMap &m)
366 ///Sets the map that indicates which nodes are reached.
368 ///Sets the map that indicates which nodes are reached.
369 ///If you don't use this function before calling \ref run(),
370 ///it will allocate one. The destructor deallocates this
371 ///automatically allocated map, of course.
372 ///\return <tt> (*this) </tt>
373 Dfs &reachedMap(ReachedMap &m)
383 ///Sets the map that indicates which nodes are processed.
385 ///Sets the map that indicates which nodes are processed.
386 ///If you don't use this function before calling \ref run(),
387 ///it will allocate one. The destructor deallocates this
388 ///automatically allocated map, of course.
389 ///\return <tt> (*this) </tt>
390 Dfs &processedMap(ProcessedMap &m)
392 if(local_processed) {
394 local_processed=false;
400 ///Sets the map that stores the distances of the nodes.
402 ///Sets the map that stores the distances of the nodes calculated by
404 ///If you don't use this function before calling \ref run(),
405 ///it will allocate one. The destructor deallocates this
406 ///automatically allocated map, of course.
407 ///\return <tt> (*this) </tt>
408 Dfs &distMap(DistMap &m)
420 ///\name Execution control
421 ///The simplest way to execute the algorithm is to use
422 ///one of the member functions called \ref lemon::Dfs::run() "run()".
424 ///If you need more control on the execution, first you must call
425 ///\ref lemon::Dfs::init() "init()", then you can add a source node
426 ///with \ref lemon::Dfs::addSource() "addSource()".
427 ///Finally \ref lemon::Dfs::start() "start()" will perform the
428 ///actual path computation.
432 ///Initializes the internal data structures.
434 ///Initializes the internal data structures.
439 _stack.resize(countNodes(*G));
441 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
442 _pred->set(u,INVALID);
443 _reached->set(u,false);
444 _processed->set(u,false);
448 ///Adds a new source node.
450 ///Adds a new source node to the set of nodes to be processed.
452 ///\pre The stack must be empty. (Otherwise the algorithm gives
455 ///\warning Distances will be wrong (or at least strange) in case of
457 void addSource(Node s)
459 LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
462 _reached->set(s,true);
463 _pred->set(s,INVALID);
466 _stack[++_stack_head]=e;
467 _dist->set(s,_stack_head);
470 _processed->set(s,true);
476 ///Processes the next arc.
478 ///Processes the next arc.
480 ///\return The processed arc.
482 ///\pre The stack must not be empty.
486 Arc e=_stack[_stack_head];
487 if(!(*_reached)[m=G->target(e)]) {
489 _reached->set(m,true);
491 _stack[_stack_head] = OutArcIt(*G, m);
492 _dist->set(m,_stack_head);
496 ++_stack[_stack_head];
498 while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
499 _processed->set(m,true);
502 m=G->source(_stack[_stack_head]);
503 ++_stack[_stack_head];
509 ///Next arc to be processed.
511 ///Next arc to be processed.
513 ///\return The next arc to be processed or \c INVALID if the stack
515 OutArcIt nextArc() const
517 return _stack_head>=0?_stack[_stack_head]:INVALID;
520 ///\brief Returns \c false if there are nodes
523 ///Returns \c false if there are nodes
524 ///to be processed in the queue (stack).
525 bool emptyQueue() const { return _stack_head<0; }
527 ///Returns the number of the nodes to be processed.
529 ///Returns the number of the nodes to be processed in the queue (stack).
530 int queueSize() const { return _stack_head+1; }
532 ///Executes the algorithm.
534 ///Executes the algorithm.
536 ///This method runs the %DFS algorithm from the root node
537 ///in order to compute the DFS path to each node.
539 /// The algorithm computes
541 ///- the distance of each node from the root in the %DFS tree.
543 ///\pre init() must be called and a root node should be
544 ///added with addSource() before using this function.
546 ///\note <tt>d.start()</tt> is just a shortcut of the following code.
548 /// while ( !d.emptyQueue() ) {
549 /// d.processNextArc();
554 while ( !emptyQueue() ) processNextArc();
557 ///Executes the algorithm until the given target node is reached.
559 ///Executes the algorithm until the given target node is reached.
561 ///This method runs the %DFS algorithm from the root node
562 ///in order to compute the DFS path to \c dest.
564 ///The algorithm computes
565 ///- the %DFS path to \c dest,
566 ///- the distance of \c dest from the root in the %DFS tree.
568 ///\pre init() must be called and a root node should be
569 ///added with addSource() before using this function.
570 void start(Node dest)
572 while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
576 ///Executes the algorithm until a condition is met.
578 ///Executes the algorithm until a condition is met.
580 ///This method runs the %DFS algorithm from the root node
581 ///until an arc \c a with <tt>am[a]</tt> true is found.
583 ///\param am A \c bool (or convertible) arc map. The algorithm
584 ///will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
586 ///\return The reached arc \c a with <tt>am[a]</tt> true or
587 ///\c INVALID if no such arc was found.
589 ///\pre init() must be called and a root node should be
590 ///added with addSource() before using this function.
592 ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
594 template<class ArcBoolMap>
595 Arc start(const ArcBoolMap &am)
597 while ( !emptyQueue() && !am[_stack[_stack_head]] )
599 return emptyQueue() ? INVALID : _stack[_stack_head];
602 ///Runs the algorithm from the given node.
604 ///This method runs the %DFS algorithm from node \c s
605 ///in order to compute the DFS path to each node.
607 ///The algorithm computes
609 ///- the distance of each node from the root in the %DFS tree.
611 ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
623 ///Finds the %DFS path between \c s and \c t.
625 ///This method runs the %DFS algorithm from node \c s
626 ///in order to compute the DFS path to \c t.
628 ///\return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
629 ///if \c t is reachable form \c s, \c 0 otherwise.
631 ///\note Apart from the return value, <tt>d.run(s,t)</tt> is
632 ///just a shortcut of the following code.
638 int run(Node s,Node t) {
642 return reached(t)?_stack_head+1:0;
645 ///Runs the algorithm to visit all nodes in the digraph.
647 ///This method runs the %DFS algorithm in order to compute the
648 ///%DFS path to each node.
650 ///The algorithm computes
652 ///- the distance of each node from the root in the %DFS tree.
654 ///\note <tt>d.run()</tt> is just a shortcut of the following code.
657 /// for (NodeIt n(digraph); n != INVALID; ++n) {
658 /// if (!d.reached(n)) {
666 for (NodeIt it(*G); it != INVALID; ++it) {
676 ///\name Query Functions
677 ///The result of the %DFS algorithm can be obtained using these
679 ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
680 ///"start()" must be called before using them.
684 ///The DFS path to a node.
686 ///Returns the DFS path to a node.
688 ///\warning \c t should be reachable from the root.
690 ///\pre Either \ref run() or \ref start() must be called before
691 ///using this function.
692 Path path(Node t) const { return Path(*G, *_pred, t); }
694 ///The distance of a node from the root.
696 ///Returns the distance of a node from the root.
698 ///\warning If node \c v is not reachable from the root, then
699 ///the return value of this function is undefined.
701 ///\pre Either \ref run() or \ref start() must be called before
702 ///using this function.
703 int dist(Node v) const { return (*_dist)[v]; }
705 ///Returns the 'previous arc' of the %DFS tree for a node.
707 ///This function returns the 'previous arc' of the %DFS tree for the
708 ///node \c v, i.e. it returns the last arc of a %DFS path from the
709 ///root to \c v. It is \c INVALID
710 ///if \c v is not reachable from the root(s) or if \c v is a root.
712 ///The %DFS tree used here is equal to the %DFS tree used in
715 ///\pre Either \ref run() or \ref start() must be called before using
717 Arc predArc(Node v) const { return (*_pred)[v];}
719 ///Returns the 'previous node' of the %DFS tree.
721 ///This function returns the 'previous node' of the %DFS
722 ///tree for the node \c v, i.e. it returns the last but one node
723 ///from a %DFS path from the root to \c v. It is \c INVALID
724 ///if \c v is not reachable from the root(s) or if \c v is a root.
726 ///The %DFS tree used here is equal to the %DFS tree used in
729 ///\pre Either \ref run() or \ref start() must be called before
730 ///using this function.
731 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
732 G->source((*_pred)[v]); }
734 ///\brief Returns a const reference to the node map that stores the
735 ///distances of the nodes.
737 ///Returns a const reference to the node map that stores the
738 ///distances of the nodes calculated by the algorithm.
740 ///\pre Either \ref run() or \ref init()
741 ///must be called before using this function.
742 const DistMap &distMap() const { return *_dist;}
744 ///\brief Returns a const reference to the node map that stores the
747 ///Returns a const reference to the node map that stores the predecessor
748 ///arcs, which form the DFS tree.
750 ///\pre Either \ref run() or \ref init()
751 ///must be called before using this function.
752 const PredMap &predMap() const { return *_pred;}
754 ///Checks if a node is reachable from the root(s).
756 ///Returns \c true if \c v is reachable from the root(s).
757 ///\pre Either \ref run() or \ref start()
758 ///must be called before using this function.
759 bool reached(Node v) const { return (*_reached)[v]; }
764 ///Default traits class of dfs() function.
766 ///Default traits class of dfs() function.
767 ///\tparam GR Digraph type.
769 struct DfsWizardDefaultTraits
771 ///The type of the digraph the algorithm runs on.
774 ///\brief The type of the map that stores the predecessor
775 ///arcs of the %DFS paths.
777 ///The type of the map that stores the predecessor
778 ///arcs of the %DFS paths.
779 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
781 typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
782 ///Instantiates a \ref PredMap.
784 ///This function instantiates a \ref PredMap.
785 ///\param g is the digraph, to which we would like to define the
787 ///\todo The digraph alone may be insufficient to initialize
789 static PredMap *createPredMap(const Digraph &g)
791 static PredMap *createPredMap(const Digraph &)
794 return new PredMap();
797 ///The type of the map that indicates which nodes are processed.
799 ///The type of the map that indicates which nodes are processed.
800 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
801 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
802 ///Instantiates a \ref ProcessedMap.
804 ///This function instantiates a \ref ProcessedMap.
805 ///\param g is the digraph, to which
806 ///we would like to define the \ref ProcessedMap.
808 static ProcessedMap *createProcessedMap(const Digraph &g)
810 static ProcessedMap *createProcessedMap(const Digraph &)
813 return new ProcessedMap();
816 ///The type of the map that indicates which nodes are reached.
818 ///The type of the map that indicates which nodes are reached.
819 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
820 typedef typename Digraph::template NodeMap<bool> ReachedMap;
821 ///Instantiates a \ref ReachedMap.
823 ///This function instantiates a \ref ReachedMap.
824 ///\param g is the digraph, to which
825 ///we would like to define the \ref ReachedMap.
826 static ReachedMap *createReachedMap(const Digraph &g)
828 return new ReachedMap(g);
831 ///The type of the map that stores the distances of the nodes.
833 ///The type of the map that stores the distances of the nodes.
834 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
836 typedef NullMap<typename Digraph::Node,int> DistMap;
837 ///Instantiates a \ref DistMap.
839 ///This function instantiates a \ref DistMap.
840 ///\param g is the digraph, to which we would like to define
843 static DistMap *createDistMap(const Digraph &g)
845 static DistMap *createDistMap(const Digraph &)
848 return new DistMap();
852 /// Default traits class used by \ref DfsWizard
854 /// To make it easier to use Dfs algorithm
855 /// we have created a wizard class.
856 /// This \ref DfsWizard class needs default traits,
857 /// as well as the \ref Dfs class.
858 /// The \ref DfsWizardBase is a class to be the default traits of the
859 /// \ref DfsWizard class.
861 class DfsWizardBase : public DfsWizardDefaultTraits<GR>
864 typedef DfsWizardDefaultTraits<GR> Base;
866 //The type of the nodes in the digraph.
867 typedef typename Base::Digraph::Node Node;
869 //Pointer to the digraph the algorithm runs on.
871 //Pointer to the map of reached nodes.
873 //Pointer to the map of processed nodes.
875 //Pointer to the map of predecessors arcs.
877 //Pointer to the map of distances.
879 //Pointer to the source node.
885 /// This constructor does not require parameters, therefore it initiates
886 /// all of the attributes to default values (0, INVALID).
887 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
888 _dist(0), _source(INVALID) {}
892 /// This constructor requires some parameters,
893 /// listed in the parameters list.
894 /// Others are initiated to 0.
895 /// \param g The digraph the algorithm runs on.
896 /// \param s The source node.
897 DfsWizardBase(const GR &g, Node s=INVALID) :
898 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
899 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
903 /// Auxiliary class for the function type interface of DFS algorithm.
905 /// This auxiliary class is created to implement the function type
906 /// interface of \ref Dfs algorithm. It uses the functions and features
907 /// of the plain \ref Dfs, but it is much simpler to use it.
908 /// It should only be used through the \ref dfs() function, which makes
909 /// it easier to use the algorithm.
911 /// Simplicity means that the way to change the types defined
912 /// in the traits class is based on functions that returns the new class
913 /// and not on templatable built-in classes.
914 /// When using the plain \ref Dfs
915 /// the new class with the modified type comes from
916 /// the original class by using the ::
917 /// operator. In the case of \ref DfsWizard only
918 /// a function have to be called, and it will
919 /// return the needed class.
921 /// It does not have own \ref run() method. When its \ref run() method
922 /// is called, it initiates a plain \ref Dfs object, and calls the
923 /// \ref Dfs::run() method of it.
925 class DfsWizard : public TR
929 ///The type of the digraph the algorithm runs on.
930 typedef typename TR::Digraph Digraph;
932 typedef typename Digraph::Node Node;
933 typedef typename Digraph::NodeIt NodeIt;
934 typedef typename Digraph::Arc Arc;
935 typedef typename Digraph::OutArcIt OutArcIt;
937 ///\brief The type of the map that stores the predecessor
938 ///arcs of the shortest paths.
939 typedef typename TR::PredMap PredMap;
940 ///\brief The type of the map that stores the distances of the nodes.
941 typedef typename TR::DistMap DistMap;
942 ///\brief The type of the map that indicates which nodes are reached.
943 typedef typename TR::ReachedMap ReachedMap;
944 ///\brief The type of the map that indicates which nodes are processed.
945 typedef typename TR::ProcessedMap ProcessedMap;
950 DfsWizard() : TR() {}
952 /// Constructor that requires parameters.
954 /// Constructor that requires parameters.
955 /// These parameters will be the default values for the traits class.
956 DfsWizard(const Digraph &g, Node s=INVALID) :
960 DfsWizard(const TR &b) : TR(b) {}
964 ///Runs DFS algorithm from a source node.
966 ///Runs DFS algorithm from a source node.
967 ///The node can be given with the \ref source() function.
970 if(Base::_source==INVALID) throw UninitializedParameter();
971 Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
973 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
975 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
977 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
979 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
980 alg.run(Base::_source);
983 ///Runs DFS algorithm from the given node.
985 ///Runs DFS algorithm from the given node.
986 ///\param s is the given source.
993 /// Sets the source node, from which the Dfs algorithm runs.
995 /// Sets the source node, from which the Dfs algorithm runs.
996 /// \param s is the source node.
997 DfsWizard<TR> &source(Node s)
1004 struct DefPredMapBase : public Base {
1006 static PredMap *createPredMap(const Digraph &) { return 0; };
1007 DefPredMapBase(const TR &b) : TR(b) {}
1009 ///\brief \ref named-templ-param "Named parameter"
1010 ///for setting \ref PredMap object.
1012 ///\ref named-templ-param "Named parameter"
1013 ///for setting \ref PredMap object.
1015 DfsWizard<DefPredMapBase<T> > predMap(const T &t)
1017 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1018 return DfsWizard<DefPredMapBase<T> >(*this);
1022 struct DefReachedMapBase : public Base {
1023 typedef T ReachedMap;
1024 static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1025 DefReachedMapBase(const TR &b) : TR(b) {}
1027 ///\brief \ref named-templ-param "Named parameter"
1028 ///for setting \ref ReachedMap object.
1030 /// \ref named-templ-param "Named parameter"
1031 ///for setting \ref ReachedMap object.
1033 DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1035 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
1036 return DfsWizard<DefReachedMapBase<T> >(*this);
1040 struct DefProcessedMapBase : public Base {
1041 typedef T ProcessedMap;
1042 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1043 DefProcessedMapBase(const TR &b) : TR(b) {}
1045 ///\brief \ref named-templ-param "Named parameter"
1046 ///for setting \ref ProcessedMap object.
1048 /// \ref named-templ-param "Named parameter"
1049 ///for setting \ref ProcessedMap object.
1051 DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1053 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
1054 return DfsWizard<DefProcessedMapBase<T> >(*this);
1058 struct DefDistMapBase : public Base {
1060 static DistMap *createDistMap(const Digraph &) { return 0; };
1061 DefDistMapBase(const TR &b) : TR(b) {}
1063 ///\brief \ref named-templ-param "Named parameter"
1064 ///for setting \ref DistMap object.
1066 ///\ref named-templ-param "Named parameter"
1067 ///for setting \ref DistMap object.
1069 DfsWizard<DefDistMapBase<T> > distMap(const T &t)
1071 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1072 return DfsWizard<DefDistMapBase<T> >(*this);
1077 ///Function type interface for Dfs algorithm.
1080 ///Function type interface for Dfs algorithm.
1082 ///This function also has several
1083 ///\ref named-templ-func-param "named parameters",
1084 ///they are declared as the members of class \ref DfsWizard.
1086 ///example shows how to use these parameters.
1088 /// dfs(g,source).predMap(preds).run();
1090 ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
1091 ///to the end of the parameter list.
1095 DfsWizard<DfsWizardBase<GR> >
1096 dfs(const GR &g,typename GR::Node s=INVALID)
1098 return DfsWizard<DfsWizardBase<GR> >(g,s);
1102 /// \brief Visitor class for DFS.
1104 /// This class defines the interface of the DfsVisit events, and
1105 /// it could be the base of a real visitor class.
1106 template <typename _Digraph>
1108 typedef _Digraph Digraph;
1109 typedef typename Digraph::Arc Arc;
1110 typedef typename Digraph::Node Node;
1111 /// \brief Called for the source node of the DFS.
1113 /// This function is called for the source node of the DFS.
1114 void start(const Node& node) {}
1115 /// \brief Called when the source node is leaved.
1117 /// This function is called when the source node is leaved.
1118 void stop(const Node& node) {}
1119 /// \brief Called when a node is reached first time.
1121 /// This function is called when a node is reached first time.
1122 void reach(const Node& node) {}
1123 /// \brief Called when an arc reaches a new node.
1125 /// This function is called when the DFS finds an arc whose target node
1126 /// is not reached yet.
1127 void discover(const Arc& arc) {}
1128 /// \brief Called when an arc is examined but its target node is
1129 /// already discovered.
1131 /// This function is called when an arc is examined but its target node is
1132 /// already discovered.
1133 void examine(const Arc& arc) {}
1134 /// \brief Called when the DFS steps back from a node.
1136 /// This function is called when the DFS steps back from a node.
1137 void leave(const Node& node) {}
1138 /// \brief Called when the DFS steps back on an arc.
1140 /// This function is called when the DFS steps back on an arc.
1141 void backtrack(const Arc& arc) {}
1144 template <typename _Digraph>
1146 typedef _Digraph Digraph;
1147 typedef typename Digraph::Arc Arc;
1148 typedef typename Digraph::Node Node;
1149 void start(const Node&) {}
1150 void stop(const Node&) {}
1151 void reach(const Node&) {}
1152 void discover(const Arc&) {}
1153 void examine(const Arc&) {}
1154 void leave(const Node&) {}
1155 void backtrack(const Arc&) {}
1157 template <typename _Visitor>
1158 struct Constraints {
1159 void constraints() {
1162 visitor.start(node);
1164 visitor.reach(node);
1165 visitor.discover(arc);
1166 visitor.examine(arc);
1167 visitor.leave(node);
1168 visitor.backtrack(arc);
1175 /// \brief Default traits class of DfsVisit class.
1177 /// Default traits class of DfsVisit class.
1178 /// \tparam _Digraph The type of the digraph the algorithm runs on.
1179 template<class _Digraph>
1180 struct DfsVisitDefaultTraits {
1182 /// \brief The type of the digraph the algorithm runs on.
1183 typedef _Digraph Digraph;
1185 /// \brief The type of the map that indicates which nodes are reached.
1187 /// The type of the map that indicates which nodes are reached.
1188 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1189 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1191 /// \brief Instantiates a \ref ReachedMap.
1193 /// This function instantiates a \ref ReachedMap.
1194 /// \param digraph is the digraph, to which
1195 /// we would like to define the \ref ReachedMap.
1196 static ReachedMap *createReachedMap(const Digraph &digraph) {
1197 return new ReachedMap(digraph);
1204 /// \brief %DFS algorithm class with visitor interface.
1206 /// This class provides an efficient implementation of the %DFS algorithm
1207 /// with visitor interface.
1209 /// The %DfsVisit class provides an alternative interface to the Dfs
1210 /// class. It works with callback mechanism, the DfsVisit object calls
1211 /// the member functions of the \c Visitor class on every DFS event.
1213 /// \tparam _Digraph The type of the digraph the algorithm runs on.
1214 /// The default value is
1215 /// \ref ListDigraph. The value of _Digraph is not used directly by
1216 /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
1217 /// \tparam _Visitor The Visitor type that is used by the algorithm.
1218 /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
1219 /// does not observe the DFS events. If you want to observe the DFS
1220 /// events, you should implement your own visitor class.
1221 /// \tparam _Traits Traits class to set various data types used by the
1222 /// algorithm. The default traits class is
1223 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
1224 /// See \ref DfsVisitDefaultTraits for the documentation of
1225 /// a DFS visit traits class.
1227 template <typename _Digraph, typename _Visitor, typename _Traits>
1229 template <typename _Digraph = ListDigraph,
1230 typename _Visitor = DfsVisitor<_Digraph>,
1231 typename _Traits = DfsDefaultTraits<_Digraph> >
1236 /// \brief \ref Exception for uninitialized parameters.
1238 /// This error represents problems in the initialization
1239 /// of the parameters of the algorithm.
1240 class UninitializedParameter : public lemon::UninitializedParameter {
1242 virtual const char* what() const throw()
1244 return "lemon::DfsVisit::UninitializedParameter";
1248 ///The traits class.
1249 typedef _Traits Traits;
1251 ///The type of the digraph the algorithm runs on.
1252 typedef typename Traits::Digraph Digraph;
1254 ///The visitor type used by the algorithm.
1255 typedef _Visitor Visitor;
1257 ///The type of the map that indicates which nodes are reached.
1258 typedef typename Traits::ReachedMap ReachedMap;
1262 typedef typename Digraph::Node Node;
1263 typedef typename Digraph::NodeIt NodeIt;
1264 typedef typename Digraph::Arc Arc;
1265 typedef typename Digraph::OutArcIt OutArcIt;
1267 //Pointer to the underlying digraph.
1268 const Digraph *_digraph;
1269 //Pointer to the visitor object.
1271 //Pointer to the map of reached status of the nodes.
1272 ReachedMap *_reached;
1273 //Indicates if _reached is locally allocated (true) or not.
1276 std::vector<typename Digraph::Arc> _stack;
1279 ///Creates the maps if necessary.
1280 ///\todo Better memory allocation (instead of new).
1281 void create_maps() {
1283 local_reached = true;
1284 _reached = Traits::createReachedMap(*_digraph);
1294 typedef DfsVisit Create;
1296 /// \name Named template parameters
1300 struct DefReachedMapTraits : public Traits {
1301 typedef T ReachedMap;
1302 static ReachedMap *createReachedMap(const Digraph &digraph) {
1303 throw UninitializedParameter();
1306 /// \brief \ref named-templ-param "Named parameter" for setting
1307 /// ReachedMap type.
1309 /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
1311 struct DefReachedMap : public DfsVisit< Digraph, Visitor,
1312 DefReachedMapTraits<T> > {
1313 typedef DfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
1319 /// \brief Constructor.
1323 /// \param digraph The digraph the algorithm runs on.
1324 /// \param visitor The visitor object of the algorithm.
1325 DfsVisit(const Digraph& digraph, Visitor& visitor)
1326 : _digraph(&digraph), _visitor(&visitor),
1327 _reached(0), local_reached(false) {}
1329 /// \brief Destructor.
1331 if(local_reached) delete _reached;
1334 /// \brief Sets the map that indicates which nodes are reached.
1336 /// Sets the map that indicates which nodes are reached.
1337 /// If you don't use this function before calling \ref run(),
1338 /// it will allocate one. The destructor deallocates this
1339 /// automatically allocated map, of course.
1340 /// \return <tt> (*this) </tt>
1341 DfsVisit &reachedMap(ReachedMap &m) {
1344 local_reached=false;
1352 /// \name Execution control
1353 /// The simplest way to execute the algorithm is to use
1354 /// one of the member functions called \ref lemon::DfsVisit::run()
1357 /// If you need more control on the execution, first you must call
1358 /// \ref lemon::DfsVisit::init() "init()", then you can add several
1359 /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
1360 /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
1361 /// actual path computation.
1365 /// \brief Initializes the internal data structures.
1367 /// Initializes the internal data structures.
1370 _stack.resize(countNodes(*_digraph));
1372 for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
1373 _reached->set(u, false);
1377 ///Adds a new source node.
1379 ///Adds a new source node to the set of nodes to be processed.
1381 ///\pre The stack must be empty. (Otherwise the algorithm gives
1384 ///\warning Distances will be wrong (or at least strange) in case of
1385 ///multiple sources.
1386 void addSource(Node s)
1388 LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
1389 if(!(*_reached)[s]) {
1390 _reached->set(s,true);
1394 _digraph->firstOut(e, s);
1396 _stack[++_stack_head] = e;
1403 /// \brief Processes the next arc.
1405 /// Processes the next arc.
1407 /// \return The processed arc.
1409 /// \pre The stack must not be empty.
1410 Arc processNextArc() {
1411 Arc e = _stack[_stack_head];
1412 Node m = _digraph->target(e);
1413 if(!(*_reached)[m]) {
1414 _visitor->discover(e);
1416 _reached->set(m, true);
1417 _digraph->firstOut(_stack[++_stack_head], m);
1419 _visitor->examine(e);
1420 m = _digraph->source(e);
1421 _digraph->nextOut(_stack[_stack_head]);
1423 while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
1426 if (_stack_head >= 0) {
1427 _visitor->backtrack(_stack[_stack_head]);
1428 m = _digraph->source(_stack[_stack_head]);
1429 _digraph->nextOut(_stack[_stack_head]);
1437 /// \brief Next arc to be processed.
1439 /// Next arc to be processed.
1441 /// \return The next arc to be processed or INVALID if the stack is
1443 Arc nextArc() const {
1444 return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
1447 /// \brief Returns \c false if there are nodes
1448 /// to be processed.
1450 /// Returns \c false if there are nodes
1451 /// to be processed in the queue (stack).
1452 bool emptyQueue() const { return _stack_head < 0; }
1454 /// \brief Returns the number of the nodes to be processed.
1456 /// Returns the number of the nodes to be processed in the queue (stack).
1457 int queueSize() const { return _stack_head + 1; }
1459 /// \brief Executes the algorithm.
1461 /// Executes the algorithm.
1463 /// This method runs the %DFS algorithm from the root node
1464 /// in order to compute the %DFS path to each node.
1466 /// The algorithm computes
1467 /// - the %DFS tree,
1468 /// - the distance of each node from the root in the %DFS tree.
1470 /// \pre init() must be called and a root node should be
1471 /// added with addSource() before using this function.
1473 /// \note <tt>d.start()</tt> is just a shortcut of the following code.
1475 /// while ( !d.emptyQueue() ) {
1476 /// d.processNextArc();
1480 while ( !emptyQueue() ) processNextArc();
1483 /// \brief Executes the algorithm until the given target node is reached.
1485 /// Executes the algorithm until the given target node is reached.
1487 /// This method runs the %DFS algorithm from the root node
1488 /// in order to compute the DFS path to \c dest.
1490 /// The algorithm computes
1491 /// - the %DFS path to \c dest,
1492 /// - the distance of \c dest from the root in the %DFS tree.
1494 /// \pre init() must be called and a root node should be added
1495 /// with addSource() before using this function.
1496 void start(Node dest) {
1497 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest )
1501 /// \brief Executes the algorithm until a condition is met.
1503 /// Executes the algorithm until a condition is met.
1505 /// This method runs the %DFS algorithm from the root node
1506 /// until an arc \c a with <tt>am[a]</tt> true is found.
1508 /// \param am A \c bool (or convertible) arc map. The algorithm
1509 /// will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
1511 /// \return The reached arc \c a with <tt>am[a]</tt> true or
1512 /// \c INVALID if no such arc was found.
1514 /// \pre init() must be called and a root node should be added
1515 /// with addSource() before using this function.
1517 /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
1519 template <typename AM>
1520 Arc start(const AM &am) {
1521 while ( !emptyQueue() && !am[_stack[_stack_head]] )
1523 return emptyQueue() ? INVALID : _stack[_stack_head];
1526 /// \brief Runs the algorithm from the given node.
1528 /// This method runs the %DFS algorithm from node \c s.
1529 /// in order to compute the DFS path to each node.
1531 /// The algorithm computes
1532 /// - the %DFS tree,
1533 /// - the distance of each node from the root in the %DFS tree.
1535 /// \note <tt>d.run(s)</tt> is just a shortcut of the following code.
1547 /// \brief Finds the %DFS path between \c s and \c t.
1549 /// This method runs the %DFS algorithm from node \c s
1550 /// in order to compute the DFS path to \c t.
1552 /// \return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
1553 /// if \c t is reachable form \c s, \c 0 otherwise.
1555 /// \note Apart from the return value, <tt>d.run(s,t)</tt> is
1556 /// just a shortcut of the following code.
1562 int run(Node s,Node t) {
1566 return reached(t)?_stack_head+1:0;
1569 /// \brief Runs the algorithm to visit all nodes in the digraph.
1571 /// This method runs the %DFS algorithm in order to
1572 /// compute the %DFS path to each node.
1574 /// The algorithm computes
1575 /// - the %DFS tree,
1576 /// - the distance of each node from the root in the %DFS tree.
1578 /// \note <tt>d.run()</tt> is just a shortcut of the following code.
1581 /// for (NodeIt n(digraph); n != INVALID; ++n) {
1582 /// if (!d.reached(n)) {
1590 for (NodeIt it(*_digraph); it != INVALID; ++it) {
1600 /// \name Query Functions
1601 /// The result of the %DFS algorithm can be obtained using these
1603 /// Either \ref lemon::DfsVisit::run() "run()" or
1604 /// \ref lemon::DfsVisit::start() "start()" must be called before
1608 /// \brief Checks if a node is reachable from the root(s).
1610 /// Returns \c true if \c v is reachable from the root(s).
1611 /// \pre Either \ref run() or \ref start()
1612 /// must be called before using this function.
1613 bool reached(Node v) { return (*_reached)[v]; }
1619 } //END OF NAMESPACE LEMON