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/bits/path_dump.h>
28 #include <lemon/core.h>
29 #include <lemon/error.h>
30 #include <lemon/assert.h>
31 #include <lemon/maps.h>
35 ///Default traits class of Dfs class.
37 ///Default traits class of Dfs class.
38 ///\tparam GR Digraph type.
40 struct DfsDefaultTraits
42 ///The type of the digraph the algorithm runs on.
45 ///\brief The type of the map that stores the predecessor
46 ///arcs of the %DFS paths.
48 ///The type of the map that stores the predecessor
49 ///arcs of the %DFS paths.
50 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap;
52 ///Instantiates a \ref PredMap.
54 ///This function instantiates a \ref PredMap.
55 ///\param g is the digraph, to which we would like to define the
57 ///\todo The digraph alone may be insufficient to initialize
58 static PredMap *createPredMap(const Digraph &g)
60 return new PredMap(g);
63 ///The type of the map that indicates which nodes are processed.
65 ///The type of the map that indicates which nodes are processed.
66 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
67 ///By default it is a NullMap.
68 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
69 ///Instantiates a \ref ProcessedMap.
71 ///This function instantiates a \ref ProcessedMap.
72 ///\param g is the digraph, to which
73 ///we would like to define the \ref ProcessedMap
75 static ProcessedMap *createProcessedMap(const Digraph &g)
77 static ProcessedMap *createProcessedMap(const Digraph &)
80 return new ProcessedMap();
83 ///The type of the map that indicates which nodes are reached.
85 ///The type of the map that indicates which nodes are reached.
86 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
87 typedef typename Digraph::template NodeMap<bool> ReachedMap;
88 ///Instantiates a \ref ReachedMap.
90 ///This function instantiates a \ref ReachedMap.
91 ///\param g is the digraph, to which
92 ///we would like to define the \ref ReachedMap.
93 static ReachedMap *createReachedMap(const Digraph &g)
95 return new ReachedMap(g);
98 ///The type of the map that stores the distances of the nodes.
100 ///The type of the map that stores the distances of the nodes.
101 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
102 typedef typename Digraph::template NodeMap<int> DistMap;
103 ///Instantiates a \ref DistMap.
105 ///This function instantiates a \ref DistMap.
106 ///\param g is the digraph, to which we would like to define the
108 static DistMap *createDistMap(const Digraph &g)
110 return new DistMap(g);
114 ///%DFS algorithm class.
117 ///This class provides an efficient implementation of the %DFS algorithm.
119 ///There is also a \ref dfs() "function type interface" for the DFS
120 ///algorithm, which is convenient in the simplier cases and it can be
123 ///\tparam GR The type of the digraph the algorithm runs on.
124 ///The default value is \ref ListDigraph. The value of GR is not used
125 ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
126 ///\tparam TR Traits class to set various data types used by the algorithm.
127 ///The default traits class is
128 ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
129 ///See \ref DfsDefaultTraits for the documentation of
130 ///a Dfs traits class.
132 template <typename GR,
135 template <typename GR=ListDigraph,
136 typename TR=DfsDefaultTraits<GR> >
140 ///\ref Exception for uninitialized parameters.
142 ///This error represents problems in the initialization of the
143 ///parameters of the algorithm.
144 class UninitializedParameter : public lemon::UninitializedParameter {
146 virtual const char* what() const throw() {
147 return "lemon::Dfs::UninitializedParameter";
151 ///The type of the digraph the algorithm runs on.
152 typedef typename TR::Digraph Digraph;
154 ///\brief The type of the map that stores the predecessor arcs of the
156 typedef typename TR::PredMap PredMap;
157 ///The type of the map that stores the distances of the nodes.
158 typedef typename TR::DistMap DistMap;
159 ///The type of the map that indicates which nodes are reached.
160 typedef typename TR::ReachedMap ReachedMap;
161 ///The type of the map that indicates which nodes are processed.
162 typedef typename TR::ProcessedMap ProcessedMap;
163 ///The type of the paths.
164 typedef PredMapPath<Digraph, PredMap> Path;
171 typedef typename Digraph::Node Node;
172 typedef typename Digraph::NodeIt NodeIt;
173 typedef typename Digraph::Arc Arc;
174 typedef typename Digraph::OutArcIt OutArcIt;
176 //Pointer to the underlying digraph.
178 //Pointer to the map of predecessor arcs.
180 //Indicates if _pred is locally allocated (true) or not.
182 //Pointer to the map of distances.
184 //Indicates if _dist is locally allocated (true) or not.
186 //Pointer to the map of reached status of the nodes.
187 ReachedMap *_reached;
188 //Indicates if _reached is locally allocated (true) or not.
190 //Pointer to the map of processed status of the nodes.
191 ProcessedMap *_processed;
192 //Indicates if _processed is locally allocated (true) or not.
193 bool local_processed;
195 std::vector<typename Digraph::OutArcIt> _stack;
198 ///Creates the maps if necessary.
199 ///\todo Better memory allocation (instead of new).
204 _pred = Traits::createPredMap(*G);
208 _dist = Traits::createDistMap(*G);
211 local_reached = true;
212 _reached = Traits::createReachedMap(*G);
215 local_processed = true;
216 _processed = Traits::createProcessedMap(*G);
228 ///\name Named template parameters
233 struct SetPredMapTraits : public Traits {
235 static PredMap *createPredMap(const Digraph &)
237 throw UninitializedParameter();
240 ///\brief \ref named-templ-param "Named parameter" for setting
241 ///\ref PredMap type.
243 ///\ref named-templ-param "Named parameter" for setting
244 ///\ref PredMap type.
246 struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
247 typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
251 struct SetDistMapTraits : public Traits {
253 static DistMap *createDistMap(const Digraph &)
255 throw UninitializedParameter();
258 ///\brief \ref named-templ-param "Named parameter" for setting
259 ///\ref DistMap type.
261 ///\ref named-templ-param "Named parameter" for setting
262 ///\ref DistMap type.
264 struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
265 typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
269 struct SetReachedMapTraits : public Traits {
270 typedef T ReachedMap;
271 static ReachedMap *createReachedMap(const Digraph &)
273 throw UninitializedParameter();
276 ///\brief \ref named-templ-param "Named parameter" for setting
277 ///\ref ReachedMap type.
279 ///\ref named-templ-param "Named parameter" for setting
280 ///\ref ReachedMap type.
282 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
283 typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
287 struct SetProcessedMapTraits : public Traits {
288 typedef T ProcessedMap;
289 static ProcessedMap *createProcessedMap(const Digraph &)
291 throw UninitializedParameter();
294 ///\brief \ref named-templ-param "Named parameter" for setting
295 ///\ref ProcessedMap type.
297 ///\ref named-templ-param "Named parameter" for setting
298 ///\ref ProcessedMap type.
300 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
301 typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
304 struct SetStandardProcessedMapTraits : public Traits {
305 typedef typename Digraph::template NodeMap<bool> ProcessedMap;
306 static ProcessedMap *createProcessedMap(const Digraph &g)
308 return new ProcessedMap(g);
311 ///\brief \ref named-templ-param "Named parameter" for setting
312 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
314 ///\ref named-templ-param "Named parameter" for setting
315 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
316 ///If you don't set it explicitly, it will be automatically allocated.
317 struct SetStandardProcessedMap :
318 public Dfs< Digraph, SetStandardProcessedMapTraits > {
319 typedef Dfs< Digraph, SetStandardProcessedMapTraits > Create;
329 ///\param g The digraph the algorithm runs on.
330 Dfs(const Digraph &g) :
332 _pred(NULL), local_pred(false),
333 _dist(NULL), local_dist(false),
334 _reached(NULL), local_reached(false),
335 _processed(NULL), local_processed(false)
341 if(local_pred) delete _pred;
342 if(local_dist) delete _dist;
343 if(local_reached) delete _reached;
344 if(local_processed) delete _processed;
347 ///Sets the map that stores the predecessor arcs.
349 ///Sets the map that stores the predecessor arcs.
350 ///If you don't use this function before calling \ref run(),
351 ///it will allocate one. The destructor deallocates this
352 ///automatically allocated map, of course.
353 ///\return <tt> (*this) </tt>
354 Dfs &predMap(PredMap &m)
364 ///Sets the map that indicates which nodes are reached.
366 ///Sets the map that indicates which nodes are reached.
367 ///If you don't use this function before calling \ref run(),
368 ///it will allocate one. The destructor deallocates this
369 ///automatically allocated map, of course.
370 ///\return <tt> (*this) </tt>
371 Dfs &reachedMap(ReachedMap &m)
381 ///Sets the map that indicates which nodes are processed.
383 ///Sets the map that indicates which nodes are processed.
384 ///If you don't use this function before calling \ref run(),
385 ///it will allocate one. The destructor deallocates this
386 ///automatically allocated map, of course.
387 ///\return <tt> (*this) </tt>
388 Dfs &processedMap(ProcessedMap &m)
390 if(local_processed) {
392 local_processed=false;
398 ///Sets the map that stores the distances of the nodes.
400 ///Sets the map that stores the distances of the nodes calculated by
402 ///If you don't use this function before calling \ref run(),
403 ///it will allocate one. The destructor deallocates this
404 ///automatically allocated map, of course.
405 ///\return <tt> (*this) </tt>
406 Dfs &distMap(DistMap &m)
418 ///\name Execution control
419 ///The simplest way to execute the algorithm is to use
420 ///one of the member functions called \ref lemon::Dfs::run() "run()".
422 ///If you need more control on the execution, first you must call
423 ///\ref lemon::Dfs::init() "init()", then you can add a source node
424 ///with \ref lemon::Dfs::addSource() "addSource()".
425 ///Finally \ref lemon::Dfs::start() "start()" will perform the
426 ///actual path computation.
430 ///Initializes the internal data structures.
432 ///Initializes the internal data structures.
437 _stack.resize(countNodes(*G));
439 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
440 _pred->set(u,INVALID);
441 _reached->set(u,false);
442 _processed->set(u,false);
446 ///Adds a new source node.
448 ///Adds a new source node to the set of nodes to be processed.
450 ///\pre The stack must be empty. (Otherwise the algorithm gives
453 ///\warning Distances will be wrong (or at least strange) in case of
455 void addSource(Node s)
457 LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
460 _reached->set(s,true);
461 _pred->set(s,INVALID);
464 _stack[++_stack_head]=e;
465 _dist->set(s,_stack_head);
468 _processed->set(s,true);
474 ///Processes the next arc.
476 ///Processes the next arc.
478 ///\return The processed arc.
480 ///\pre The stack must not be empty.
484 Arc e=_stack[_stack_head];
485 if(!(*_reached)[m=G->target(e)]) {
487 _reached->set(m,true);
489 _stack[_stack_head] = OutArcIt(*G, m);
490 _dist->set(m,_stack_head);
494 ++_stack[_stack_head];
496 while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
497 _processed->set(m,true);
500 m=G->source(_stack[_stack_head]);
501 ++_stack[_stack_head];
507 ///Next arc to be processed.
509 ///Next arc to be processed.
511 ///\return The next arc to be processed or \c INVALID if the stack
513 OutArcIt nextArc() const
515 return _stack_head>=0?_stack[_stack_head]:INVALID;
518 ///\brief Returns \c false if there are nodes
521 ///Returns \c false if there are nodes
522 ///to be processed in the queue (stack).
523 bool emptyQueue() const { return _stack_head<0; }
525 ///Returns the number of the nodes to be processed.
527 ///Returns the number of the nodes to be processed in the queue (stack).
528 int queueSize() const { return _stack_head+1; }
530 ///Executes the algorithm.
532 ///Executes the algorithm.
534 ///This method runs the %DFS algorithm from the root node
535 ///in order to compute the DFS path to each node.
537 /// The algorithm computes
539 ///- the distance of each node from the root in the %DFS tree.
541 ///\pre init() must be called and a root node should be
542 ///added with addSource() before using this function.
544 ///\note <tt>d.start()</tt> is just a shortcut of the following code.
546 /// while ( !d.emptyQueue() ) {
547 /// d.processNextArc();
552 while ( !emptyQueue() ) processNextArc();
555 ///Executes the algorithm until the given target node is reached.
557 ///Executes the algorithm until the given target node is reached.
559 ///This method runs the %DFS algorithm from the root node
560 ///in order to compute the DFS path to \c dest.
562 ///The algorithm computes
563 ///- the %DFS path to \c dest,
564 ///- the distance of \c dest from the root in the %DFS tree.
566 ///\pre init() must be called and a root node should be
567 ///added with addSource() before using this function.
568 void start(Node dest)
570 while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
574 ///Executes the algorithm until a condition is met.
576 ///Executes the algorithm until a condition is met.
578 ///This method runs the %DFS algorithm from the root node
579 ///until an arc \c a with <tt>am[a]</tt> true is found.
581 ///\param am A \c bool (or convertible) arc map. The algorithm
582 ///will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
584 ///\return The reached arc \c a with <tt>am[a]</tt> true or
585 ///\c INVALID if no such arc was found.
587 ///\pre init() must be called and a root node should be
588 ///added with addSource() before using this function.
590 ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
592 template<class ArcBoolMap>
593 Arc start(const ArcBoolMap &am)
595 while ( !emptyQueue() && !am[_stack[_stack_head]] )
597 return emptyQueue() ? INVALID : _stack[_stack_head];
600 ///Runs the algorithm from the given node.
602 ///This method runs the %DFS algorithm from node \c s
603 ///in order to compute the DFS path to each node.
605 ///The algorithm computes
607 ///- the distance of each node from the root in the %DFS tree.
609 ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
621 ///Finds the %DFS path between \c s and \c t.
623 ///This method runs the %DFS algorithm from node \c s
624 ///in order to compute the DFS path to \c t.
626 ///\return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
627 ///if \c t is reachable form \c s, \c 0 otherwise.
629 ///\note Apart from the return value, <tt>d.run(s,t)</tt> is
630 ///just a shortcut of the following code.
636 int run(Node s,Node t) {
640 return reached(t)?_stack_head+1:0;
643 ///Runs the algorithm to visit all nodes in the digraph.
645 ///This method runs the %DFS algorithm in order to compute the
646 ///%DFS path to each node.
648 ///The algorithm computes
650 ///- the distance of each node from the root in the %DFS tree.
652 ///\note <tt>d.run()</tt> is just a shortcut of the following code.
655 /// for (NodeIt n(digraph); n != INVALID; ++n) {
656 /// if (!d.reached(n)) {
664 for (NodeIt it(*G); it != INVALID; ++it) {
674 ///\name Query Functions
675 ///The result of the %DFS algorithm can be obtained using these
677 ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
678 ///"start()" must be called before using them.
682 ///The DFS path to a node.
684 ///Returns the DFS path to a node.
686 ///\warning \c t should be reachable from the root.
688 ///\pre Either \ref run() or \ref start() must be called before
689 ///using this function.
690 Path path(Node t) const { return Path(*G, *_pred, t); }
692 ///The distance of a node from the root.
694 ///Returns the distance of a node from the root.
696 ///\warning If node \c v is not reachable from the root, then
697 ///the return value of this function is undefined.
699 ///\pre Either \ref run() or \ref start() must be called before
700 ///using this function.
701 int dist(Node v) const { return (*_dist)[v]; }
703 ///Returns the 'previous arc' of the %DFS tree for a node.
705 ///This function returns the 'previous arc' of the %DFS tree for the
706 ///node \c v, i.e. it returns the last arc of a %DFS path from the
707 ///root to \c v. It is \c INVALID
708 ///if \c v is not reachable from the root(s) or if \c v is a root.
710 ///The %DFS tree used here is equal to the %DFS tree used in
713 ///\pre Either \ref run() or \ref start() must be called before using
715 Arc predArc(Node v) const { return (*_pred)[v];}
717 ///Returns the 'previous node' of the %DFS tree.
719 ///This function returns the 'previous node' of the %DFS
720 ///tree for the node \c v, i.e. it returns the last but one node
721 ///from a %DFS path from the root to \c v. It is \c INVALID
722 ///if \c v is not reachable from the root(s) or if \c v is a root.
724 ///The %DFS tree used here is equal to the %DFS tree used in
727 ///\pre Either \ref run() or \ref start() must be called before
728 ///using this function.
729 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
730 G->source((*_pred)[v]); }
732 ///\brief Returns a const reference to the node map that stores the
733 ///distances of the nodes.
735 ///Returns a const reference to the node map that stores the
736 ///distances of the nodes calculated by the algorithm.
738 ///\pre Either \ref run() or \ref init()
739 ///must be called before using this function.
740 const DistMap &distMap() const { return *_dist;}
742 ///\brief Returns a const reference to the node map that stores the
745 ///Returns a const reference to the node map that stores the predecessor
746 ///arcs, which form the DFS tree.
748 ///\pre Either \ref run() or \ref init()
749 ///must be called before using this function.
750 const PredMap &predMap() const { return *_pred;}
752 ///Checks if a node is reachable from the root(s).
754 ///Returns \c true if \c v is reachable from the root(s).
755 ///\pre Either \ref run() or \ref start()
756 ///must be called before using this function.
757 bool reached(Node v) const { return (*_reached)[v]; }
762 ///Default traits class of dfs() function.
764 ///Default traits class of dfs() function.
765 ///\tparam GR Digraph type.
767 struct DfsWizardDefaultTraits
769 ///The type of the digraph the algorithm runs on.
772 ///\brief The type of the map that stores the predecessor
773 ///arcs of the %DFS paths.
775 ///The type of the map that stores the predecessor
776 ///arcs of the %DFS paths.
777 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
779 typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
780 ///Instantiates a \ref PredMap.
782 ///This function instantiates a \ref PredMap.
783 ///\param g is the digraph, to which we would like to define the
785 ///\todo The digraph alone may be insufficient to initialize
787 static PredMap *createPredMap(const Digraph &g)
789 static PredMap *createPredMap(const Digraph &)
792 return new PredMap();
795 ///The type of the map that indicates which nodes are processed.
797 ///The type of the map that indicates which nodes are processed.
798 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
799 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
800 ///Instantiates a \ref ProcessedMap.
802 ///This function instantiates a \ref ProcessedMap.
803 ///\param g is the digraph, to which
804 ///we would like to define the \ref ProcessedMap.
806 static ProcessedMap *createProcessedMap(const Digraph &g)
808 static ProcessedMap *createProcessedMap(const Digraph &)
811 return new ProcessedMap();
814 ///The type of the map that indicates which nodes are reached.
816 ///The type of the map that indicates which nodes are reached.
817 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
818 typedef typename Digraph::template NodeMap<bool> ReachedMap;
819 ///Instantiates a \ref ReachedMap.
821 ///This function instantiates a \ref ReachedMap.
822 ///\param g is the digraph, to which
823 ///we would like to define the \ref ReachedMap.
824 static ReachedMap *createReachedMap(const Digraph &g)
826 return new ReachedMap(g);
829 ///The type of the map that stores the distances of the nodes.
831 ///The type of the map that stores the distances of the nodes.
832 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
834 typedef NullMap<typename Digraph::Node,int> DistMap;
835 ///Instantiates a \ref DistMap.
837 ///This function instantiates a \ref DistMap.
838 ///\param g is the digraph, to which we would like to define
841 static DistMap *createDistMap(const Digraph &g)
843 static DistMap *createDistMap(const Digraph &)
846 return new DistMap();
850 /// Default traits class used by \ref DfsWizard
852 /// To make it easier to use Dfs algorithm
853 /// we have created a wizard class.
854 /// This \ref DfsWizard class needs default traits,
855 /// as well as the \ref Dfs class.
856 /// The \ref DfsWizardBase is a class to be the default traits of the
857 /// \ref DfsWizard class.
859 class DfsWizardBase : public DfsWizardDefaultTraits<GR>
862 typedef DfsWizardDefaultTraits<GR> Base;
864 //The type of the nodes in the digraph.
865 typedef typename Base::Digraph::Node Node;
867 //Pointer to the digraph the algorithm runs on.
869 //Pointer to the map of reached nodes.
871 //Pointer to the map of processed nodes.
873 //Pointer to the map of predecessors arcs.
875 //Pointer to the map of distances.
877 //Pointer to the source node.
883 /// This constructor does not require parameters, therefore it initiates
884 /// all of the attributes to default values (0, INVALID).
885 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
886 _dist(0), _source(INVALID) {}
890 /// This constructor requires some parameters,
891 /// listed in the parameters list.
892 /// Others are initiated to 0.
893 /// \param g The digraph the algorithm runs on.
894 /// \param s The source node.
895 DfsWizardBase(const GR &g, Node s=INVALID) :
896 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
897 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
901 /// Auxiliary class for the function type interface of DFS algorithm.
903 /// This auxiliary class is created to implement the function type
904 /// interface of \ref Dfs algorithm. It uses the functions and features
905 /// of the plain \ref Dfs, but it is much simpler to use it.
906 /// It should only be used through the \ref dfs() function, which makes
907 /// it easier to use the algorithm.
909 /// Simplicity means that the way to change the types defined
910 /// in the traits class is based on functions that returns the new class
911 /// and not on templatable built-in classes.
912 /// When using the plain \ref Dfs
913 /// the new class with the modified type comes from
914 /// the original class by using the ::
915 /// operator. In the case of \ref DfsWizard only
916 /// a function have to be called, and it will
917 /// return the needed class.
919 /// It does not have own \ref run() method. When its \ref run() method
920 /// is called, it initiates a plain \ref Dfs object, and calls the
921 /// \ref Dfs::run() method of it.
923 class DfsWizard : public TR
927 ///The type of the digraph the algorithm runs on.
928 typedef typename TR::Digraph Digraph;
930 typedef typename Digraph::Node Node;
931 typedef typename Digraph::NodeIt NodeIt;
932 typedef typename Digraph::Arc Arc;
933 typedef typename Digraph::OutArcIt OutArcIt;
935 ///\brief The type of the map that stores the predecessor
936 ///arcs of the shortest paths.
937 typedef typename TR::PredMap PredMap;
938 ///\brief The type of the map that stores the distances of the nodes.
939 typedef typename TR::DistMap DistMap;
940 ///\brief The type of the map that indicates which nodes are reached.
941 typedef typename TR::ReachedMap ReachedMap;
942 ///\brief The type of the map that indicates which nodes are processed.
943 typedef typename TR::ProcessedMap ProcessedMap;
948 DfsWizard() : TR() {}
950 /// Constructor that requires parameters.
952 /// Constructor that requires parameters.
953 /// These parameters will be the default values for the traits class.
954 DfsWizard(const Digraph &g, Node s=INVALID) :
958 DfsWizard(const TR &b) : TR(b) {}
962 ///Runs DFS algorithm from a source node.
964 ///Runs DFS algorithm from a source node.
965 ///The node can be given with the \ref source() function.
968 if(Base::_source==INVALID) throw UninitializedParameter();
969 Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
971 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
973 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
975 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
977 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
978 alg.run(Base::_source);
981 ///Runs DFS algorithm from the given node.
983 ///Runs DFS algorithm from the given node.
984 ///\param s is the given source.
991 /// Sets the source node, from which the Dfs algorithm runs.
993 /// Sets the source node, from which the Dfs algorithm runs.
994 /// \param s is the source node.
995 DfsWizard<TR> &source(Node s)
1002 struct SetPredMapBase : public Base {
1004 static PredMap *createPredMap(const Digraph &) { return 0; };
1005 SetPredMapBase(const TR &b) : TR(b) {}
1007 ///\brief \ref named-templ-param "Named parameter"
1008 ///for setting \ref PredMap object.
1010 ///\ref named-templ-param "Named parameter"
1011 ///for setting \ref PredMap object.
1013 DfsWizard<SetPredMapBase<T> > predMap(const T &t)
1015 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1016 return DfsWizard<SetPredMapBase<T> >(*this);
1020 struct SetReachedMapBase : public Base {
1021 typedef T ReachedMap;
1022 static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1023 SetReachedMapBase(const TR &b) : TR(b) {}
1025 ///\brief \ref named-templ-param "Named parameter"
1026 ///for setting \ref ReachedMap object.
1028 /// \ref named-templ-param "Named parameter"
1029 ///for setting \ref ReachedMap object.
1031 DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
1033 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
1034 return DfsWizard<SetReachedMapBase<T> >(*this);
1038 struct SetProcessedMapBase : public Base {
1039 typedef T ProcessedMap;
1040 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1041 SetProcessedMapBase(const TR &b) : TR(b) {}
1043 ///\brief \ref named-templ-param "Named parameter"
1044 ///for setting \ref ProcessedMap object.
1046 /// \ref named-templ-param "Named parameter"
1047 ///for setting \ref ProcessedMap object.
1049 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1051 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
1052 return DfsWizard<SetProcessedMapBase<T> >(*this);
1056 struct SetDistMapBase : public Base {
1058 static DistMap *createDistMap(const Digraph &) { return 0; };
1059 SetDistMapBase(const TR &b) : TR(b) {}
1061 ///\brief \ref named-templ-param "Named parameter"
1062 ///for setting \ref DistMap object.
1064 ///\ref named-templ-param "Named parameter"
1065 ///for setting \ref DistMap object.
1067 DfsWizard<SetDistMapBase<T> > distMap(const T &t)
1069 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1070 return DfsWizard<SetDistMapBase<T> >(*this);
1075 ///Function type interface for Dfs algorithm.
1078 ///Function type interface for Dfs algorithm.
1080 ///This function also has several
1081 ///\ref named-templ-func-param "named parameters",
1082 ///they are declared as the members of class \ref DfsWizard.
1084 ///example shows how to use these parameters.
1086 /// dfs(g,source).predMap(preds).run();
1088 ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
1089 ///to the end of the parameter list.
1093 DfsWizard<DfsWizardBase<GR> >
1094 dfs(const GR &g,typename GR::Node s=INVALID)
1096 return DfsWizard<DfsWizardBase<GR> >(g,s);
1100 /// \brief Visitor class for DFS.
1102 /// This class defines the interface of the DfsVisit events, and
1103 /// it could be the base of a real visitor class.
1104 template <typename _Digraph>
1106 typedef _Digraph Digraph;
1107 typedef typename Digraph::Arc Arc;
1108 typedef typename Digraph::Node Node;
1109 /// \brief Called for the source node of the DFS.
1111 /// This function is called for the source node of the DFS.
1112 void start(const Node& node) {}
1113 /// \brief Called when the source node is leaved.
1115 /// This function is called when the source node is leaved.
1116 void stop(const Node& node) {}
1117 /// \brief Called when a node is reached first time.
1119 /// This function is called when a node is reached first time.
1120 void reach(const Node& node) {}
1121 /// \brief Called when an arc reaches a new node.
1123 /// This function is called when the DFS finds an arc whose target node
1124 /// is not reached yet.
1125 void discover(const Arc& arc) {}
1126 /// \brief Called when an arc is examined but its target node is
1127 /// already discovered.
1129 /// This function is called when an arc is examined but its target node is
1130 /// already discovered.
1131 void examine(const Arc& arc) {}
1132 /// \brief Called when the DFS steps back from a node.
1134 /// This function is called when the DFS steps back from a node.
1135 void leave(const Node& node) {}
1136 /// \brief Called when the DFS steps back on an arc.
1138 /// This function is called when the DFS steps back on an arc.
1139 void backtrack(const Arc& arc) {}
1142 template <typename _Digraph>
1144 typedef _Digraph Digraph;
1145 typedef typename Digraph::Arc Arc;
1146 typedef typename Digraph::Node Node;
1147 void start(const Node&) {}
1148 void stop(const Node&) {}
1149 void reach(const Node&) {}
1150 void discover(const Arc&) {}
1151 void examine(const Arc&) {}
1152 void leave(const Node&) {}
1153 void backtrack(const Arc&) {}
1155 template <typename _Visitor>
1156 struct Constraints {
1157 void constraints() {
1160 visitor.start(node);
1162 visitor.reach(node);
1163 visitor.discover(arc);
1164 visitor.examine(arc);
1165 visitor.leave(node);
1166 visitor.backtrack(arc);
1173 /// \brief Default traits class of DfsVisit class.
1175 /// Default traits class of DfsVisit class.
1176 /// \tparam _Digraph The type of the digraph the algorithm runs on.
1177 template<class _Digraph>
1178 struct DfsVisitDefaultTraits {
1180 /// \brief The type of the digraph the algorithm runs on.
1181 typedef _Digraph Digraph;
1183 /// \brief The type of the map that indicates which nodes are reached.
1185 /// The type of the map that indicates which nodes are reached.
1186 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1187 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1189 /// \brief Instantiates a \ref ReachedMap.
1191 /// This function instantiates a \ref ReachedMap.
1192 /// \param digraph is the digraph, to which
1193 /// we would like to define the \ref ReachedMap.
1194 static ReachedMap *createReachedMap(const Digraph &digraph) {
1195 return new ReachedMap(digraph);
1202 /// \brief %DFS algorithm class with visitor interface.
1204 /// This class provides an efficient implementation of the %DFS algorithm
1205 /// with visitor interface.
1207 /// The %DfsVisit class provides an alternative interface to the Dfs
1208 /// class. It works with callback mechanism, the DfsVisit object calls
1209 /// the member functions of the \c Visitor class on every DFS event.
1211 /// \tparam _Digraph The type of the digraph the algorithm runs on.
1212 /// The default value is
1213 /// \ref ListDigraph. The value of _Digraph is not used directly by
1214 /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
1215 /// \tparam _Visitor The Visitor type that is used by the algorithm.
1216 /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
1217 /// does not observe the DFS events. If you want to observe the DFS
1218 /// events, you should implement your own visitor class.
1219 /// \tparam _Traits Traits class to set various data types used by the
1220 /// algorithm. The default traits class is
1221 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
1222 /// See \ref DfsVisitDefaultTraits for the documentation of
1223 /// a DFS visit traits class.
1225 template <typename _Digraph, typename _Visitor, typename _Traits>
1227 template <typename _Digraph = ListDigraph,
1228 typename _Visitor = DfsVisitor<_Digraph>,
1229 typename _Traits = DfsDefaultTraits<_Digraph> >
1234 /// \brief \ref Exception for uninitialized parameters.
1236 /// This error represents problems in the initialization
1237 /// of the parameters of the algorithm.
1238 class UninitializedParameter : public lemon::UninitializedParameter {
1240 virtual const char* what() const throw()
1242 return "lemon::DfsVisit::UninitializedParameter";
1246 ///The traits class.
1247 typedef _Traits Traits;
1249 ///The type of the digraph the algorithm runs on.
1250 typedef typename Traits::Digraph Digraph;
1252 ///The visitor type used by the algorithm.
1253 typedef _Visitor Visitor;
1255 ///The type of the map that indicates which nodes are reached.
1256 typedef typename Traits::ReachedMap ReachedMap;
1260 typedef typename Digraph::Node Node;
1261 typedef typename Digraph::NodeIt NodeIt;
1262 typedef typename Digraph::Arc Arc;
1263 typedef typename Digraph::OutArcIt OutArcIt;
1265 //Pointer to the underlying digraph.
1266 const Digraph *_digraph;
1267 //Pointer to the visitor object.
1269 //Pointer to the map of reached status of the nodes.
1270 ReachedMap *_reached;
1271 //Indicates if _reached is locally allocated (true) or not.
1274 std::vector<typename Digraph::Arc> _stack;
1277 ///Creates the maps if necessary.
1278 ///\todo Better memory allocation (instead of new).
1279 void create_maps() {
1281 local_reached = true;
1282 _reached = Traits::createReachedMap(*_digraph);
1292 typedef DfsVisit Create;
1294 /// \name Named template parameters
1298 struct SetReachedMapTraits : public Traits {
1299 typedef T ReachedMap;
1300 static ReachedMap *createReachedMap(const Digraph &digraph) {
1301 throw UninitializedParameter();
1304 /// \brief \ref named-templ-param "Named parameter" for setting
1305 /// ReachedMap type.
1307 /// \ref named-templ-param "Named parameter" for setting ReachedMap type.
1309 struct SetReachedMap : public DfsVisit< Digraph, Visitor,
1310 SetReachedMapTraits<T> > {
1311 typedef DfsVisit< Digraph, Visitor, SetReachedMapTraits<T> > Create;
1317 /// \brief Constructor.
1321 /// \param digraph The digraph the algorithm runs on.
1322 /// \param visitor The visitor object of the algorithm.
1323 DfsVisit(const Digraph& digraph, Visitor& visitor)
1324 : _digraph(&digraph), _visitor(&visitor),
1325 _reached(0), local_reached(false) {}
1327 /// \brief Destructor.
1329 if(local_reached) delete _reached;
1332 /// \brief Sets the map that indicates which nodes are reached.
1334 /// Sets the map that indicates which nodes are reached.
1335 /// If you don't use this function before calling \ref run(),
1336 /// it will allocate one. The destructor deallocates this
1337 /// automatically allocated map, of course.
1338 /// \return <tt> (*this) </tt>
1339 DfsVisit &reachedMap(ReachedMap &m) {
1342 local_reached=false;
1350 /// \name Execution control
1351 /// The simplest way to execute the algorithm is to use
1352 /// one of the member functions called \ref lemon::DfsVisit::run()
1355 /// If you need more control on the execution, first you must call
1356 /// \ref lemon::DfsVisit::init() "init()", then you can add several
1357 /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
1358 /// Finally \ref lemon::DfsVisit::start() "start()" will perform the
1359 /// actual path computation.
1363 /// \brief Initializes the internal data structures.
1365 /// Initializes the internal data structures.
1368 _stack.resize(countNodes(*_digraph));
1370 for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
1371 _reached->set(u, false);
1375 ///Adds a new source node.
1377 ///Adds a new source node to the set of nodes to be processed.
1379 ///\pre The stack must be empty. (Otherwise the algorithm gives
1382 ///\warning Distances will be wrong (or at least strange) in case of
1383 ///multiple sources.
1384 void addSource(Node s)
1386 LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
1387 if(!(*_reached)[s]) {
1388 _reached->set(s,true);
1392 _digraph->firstOut(e, s);
1394 _stack[++_stack_head] = e;
1401 /// \brief Processes the next arc.
1403 /// Processes the next arc.
1405 /// \return The processed arc.
1407 /// \pre The stack must not be empty.
1408 Arc processNextArc() {
1409 Arc e = _stack[_stack_head];
1410 Node m = _digraph->target(e);
1411 if(!(*_reached)[m]) {
1412 _visitor->discover(e);
1414 _reached->set(m, true);
1415 _digraph->firstOut(_stack[++_stack_head], m);
1417 _visitor->examine(e);
1418 m = _digraph->source(e);
1419 _digraph->nextOut(_stack[_stack_head]);
1421 while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
1424 if (_stack_head >= 0) {
1425 _visitor->backtrack(_stack[_stack_head]);
1426 m = _digraph->source(_stack[_stack_head]);
1427 _digraph->nextOut(_stack[_stack_head]);
1435 /// \brief Next arc to be processed.
1437 /// Next arc to be processed.
1439 /// \return The next arc to be processed or INVALID if the stack is
1441 Arc nextArc() const {
1442 return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
1445 /// \brief Returns \c false if there are nodes
1446 /// to be processed.
1448 /// Returns \c false if there are nodes
1449 /// to be processed in the queue (stack).
1450 bool emptyQueue() const { return _stack_head < 0; }
1452 /// \brief Returns the number of the nodes to be processed.
1454 /// Returns the number of the nodes to be processed in the queue (stack).
1455 int queueSize() const { return _stack_head + 1; }
1457 /// \brief Executes the algorithm.
1459 /// Executes the algorithm.
1461 /// This method runs the %DFS algorithm from the root node
1462 /// in order to compute the %DFS path to each node.
1464 /// The algorithm computes
1465 /// - the %DFS tree,
1466 /// - the distance of each node from the root in the %DFS tree.
1468 /// \pre init() must be called and a root node should be
1469 /// added with addSource() before using this function.
1471 /// \note <tt>d.start()</tt> is just a shortcut of the following code.
1473 /// while ( !d.emptyQueue() ) {
1474 /// d.processNextArc();
1478 while ( !emptyQueue() ) processNextArc();
1481 /// \brief Executes the algorithm until the given target node is reached.
1483 /// Executes the algorithm until the given target node is reached.
1485 /// This method runs the %DFS algorithm from the root node
1486 /// in order to compute the DFS path to \c dest.
1488 /// The algorithm computes
1489 /// - the %DFS path to \c dest,
1490 /// - the distance of \c dest from the root in the %DFS tree.
1492 /// \pre init() must be called and a root node should be added
1493 /// with addSource() before using this function.
1494 void start(Node dest) {
1495 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest )
1499 /// \brief Executes the algorithm until a condition is met.
1501 /// Executes the algorithm until a condition is met.
1503 /// This method runs the %DFS algorithm from the root node
1504 /// until an arc \c a with <tt>am[a]</tt> true is found.
1506 /// \param am A \c bool (or convertible) arc map. The algorithm
1507 /// will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
1509 /// \return The reached arc \c a with <tt>am[a]</tt> true or
1510 /// \c INVALID if no such arc was found.
1512 /// \pre init() must be called and a root node should be added
1513 /// with addSource() before using this function.
1515 /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
1517 template <typename AM>
1518 Arc start(const AM &am) {
1519 while ( !emptyQueue() && !am[_stack[_stack_head]] )
1521 return emptyQueue() ? INVALID : _stack[_stack_head];
1524 /// \brief Runs the algorithm from the given node.
1526 /// This method runs the %DFS algorithm from node \c s.
1527 /// in order to compute the DFS path to each node.
1529 /// The algorithm computes
1530 /// - the %DFS tree,
1531 /// - the distance of each node from the root in the %DFS tree.
1533 /// \note <tt>d.run(s)</tt> is just a shortcut of the following code.
1545 /// \brief Finds the %DFS path between \c s and \c t.
1547 /// This method runs the %DFS algorithm from node \c s
1548 /// in order to compute the DFS path to \c t.
1550 /// \return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
1551 /// if \c t is reachable form \c s, \c 0 otherwise.
1553 /// \note Apart from the return value, <tt>d.run(s,t)</tt> is
1554 /// just a shortcut of the following code.
1560 int run(Node s,Node t) {
1564 return reached(t)?_stack_head+1:0;
1567 /// \brief Runs the algorithm to visit all nodes in the digraph.
1569 /// This method runs the %DFS algorithm in order to
1570 /// compute the %DFS path to each node.
1572 /// The algorithm computes
1573 /// - the %DFS tree,
1574 /// - the distance of each node from the root in the %DFS tree.
1576 /// \note <tt>d.run()</tt> is just a shortcut of the following code.
1579 /// for (NodeIt n(digraph); n != INVALID; ++n) {
1580 /// if (!d.reached(n)) {
1588 for (NodeIt it(*_digraph); it != INVALID; ++it) {
1598 /// \name Query Functions
1599 /// The result of the %DFS algorithm can be obtained using these
1601 /// Either \ref lemon::DfsVisit::run() "run()" or
1602 /// \ref lemon::DfsVisit::start() "start()" must be called before
1606 /// \brief Checks if a node is reachable from the root(s).
1608 /// Returns \c true if \c v is reachable from the root(s).
1609 /// \pre Either \ref run() or \ref start()
1610 /// must be called before using this function.
1611 bool reached(Node v) { return (*_reached)[v]; }
1617 } //END OF NAMESPACE LEMON