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 static PredMap *createPredMap(const Digraph &g)
59 return new PredMap(g);
62 ///The type of the map that indicates which nodes are processed.
64 ///The type of the map that indicates which nodes are processed.
65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
66 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
67 ///Instantiates a \ref ProcessedMap.
69 ///This function instantiates a \ref ProcessedMap.
70 ///\param g is the digraph, to which
71 ///we would like to define the \ref ProcessedMap
73 static ProcessedMap *createProcessedMap(const Digraph &g)
75 static ProcessedMap *createProcessedMap(const Digraph &)
78 return new ProcessedMap();
81 ///The type of the map that indicates which nodes are reached.
83 ///The type of the map that indicates which nodes are reached.
84 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
85 typedef typename Digraph::template NodeMap<bool> ReachedMap;
86 ///Instantiates a \ref ReachedMap.
88 ///This function instantiates a \ref ReachedMap.
89 ///\param g is the digraph, to which
90 ///we would like to define the \ref ReachedMap.
91 static ReachedMap *createReachedMap(const Digraph &g)
93 return new ReachedMap(g);
96 ///The type of the map that stores the distances of the nodes.
98 ///The type of the map that stores the distances of the nodes.
99 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
100 typedef typename Digraph::template NodeMap<int> DistMap;
101 ///Instantiates a \ref DistMap.
103 ///This function instantiates a \ref DistMap.
104 ///\param g is the digraph, to which we would like to define the
106 static DistMap *createDistMap(const Digraph &g)
108 return new DistMap(g);
112 ///%DFS algorithm class.
115 ///This class provides an efficient implementation of the %DFS algorithm.
117 ///There is also a \ref dfs() "function type interface" for the DFS
118 ///algorithm, which is convenient in the simplier cases and it can be
121 ///\tparam GR The type of the digraph the algorithm runs on.
122 ///The default value is \ref ListDigraph. The value of GR is not used
123 ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits.
124 ///\tparam TR Traits class to set various data types used by the algorithm.
125 ///The default traits class is
126 ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
127 ///See \ref DfsDefaultTraits for the documentation of
128 ///a Dfs traits class.
130 template <typename GR,
133 template <typename GR=ListDigraph,
134 typename TR=DfsDefaultTraits<GR> >
138 ///\ref Exception for uninitialized parameters.
140 ///This error represents problems in the initialization of the
141 ///parameters of the algorithm.
142 class UninitializedParameter : public lemon::UninitializedParameter {
144 virtual const char* what() const throw() {
145 return "lemon::Dfs::UninitializedParameter";
149 ///The type of the digraph the algorithm runs on.
150 typedef typename TR::Digraph Digraph;
152 ///\brief The type of the map that stores the predecessor arcs of the
154 typedef typename TR::PredMap PredMap;
155 ///The type of the map that stores the distances of the nodes.
156 typedef typename TR::DistMap DistMap;
157 ///The type of the map that indicates which nodes are reached.
158 typedef typename TR::ReachedMap ReachedMap;
159 ///The type of the map that indicates which nodes are processed.
160 typedef typename TR::ProcessedMap ProcessedMap;
161 ///The type of the paths.
162 typedef PredMapPath<Digraph, PredMap> Path;
169 typedef typename Digraph::Node Node;
170 typedef typename Digraph::NodeIt NodeIt;
171 typedef typename Digraph::Arc Arc;
172 typedef typename Digraph::OutArcIt OutArcIt;
174 //Pointer to the underlying digraph.
176 //Pointer to the map of predecessor arcs.
178 //Indicates if _pred is locally allocated (true) or not.
180 //Pointer to the map of distances.
182 //Indicates if _dist is locally allocated (true) or not.
184 //Pointer to the map of reached status of the nodes.
185 ReachedMap *_reached;
186 //Indicates if _reached is locally allocated (true) or not.
188 //Pointer to the map of processed status of the nodes.
189 ProcessedMap *_processed;
190 //Indicates if _processed is locally allocated (true) or not.
191 bool local_processed;
193 std::vector<typename Digraph::OutArcIt> _stack;
196 //Creates the maps if necessary.
201 _pred = Traits::createPredMap(*G);
205 _dist = Traits::createDistMap(*G);
208 local_reached = true;
209 _reached = Traits::createReachedMap(*G);
212 local_processed = true;
213 _processed = Traits::createProcessedMap(*G);
225 ///\name Named template parameters
230 struct SetPredMapTraits : public Traits {
232 static PredMap *createPredMap(const Digraph &)
234 throw UninitializedParameter();
237 ///\brief \ref named-templ-param "Named parameter" for setting
238 ///\ref PredMap type.
240 ///\ref named-templ-param "Named parameter" for setting
241 ///\ref PredMap type.
243 struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
244 typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
248 struct SetDistMapTraits : public Traits {
250 static DistMap *createDistMap(const Digraph &)
252 throw UninitializedParameter();
255 ///\brief \ref named-templ-param "Named parameter" for setting
256 ///\ref DistMap type.
258 ///\ref named-templ-param "Named parameter" for setting
259 ///\ref DistMap type.
261 struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
262 typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
266 struct SetReachedMapTraits : public Traits {
267 typedef T ReachedMap;
268 static ReachedMap *createReachedMap(const Digraph &)
270 throw UninitializedParameter();
273 ///\brief \ref named-templ-param "Named parameter" for setting
274 ///\ref ReachedMap type.
276 ///\ref named-templ-param "Named parameter" for setting
277 ///\ref ReachedMap type.
279 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
280 typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
284 struct SetProcessedMapTraits : public Traits {
285 typedef T ProcessedMap;
286 static ProcessedMap *createProcessedMap(const Digraph &)
288 throw UninitializedParameter();
291 ///\brief \ref named-templ-param "Named parameter" for setting
292 ///\ref ProcessedMap type.
294 ///\ref named-templ-param "Named parameter" for setting
295 ///\ref ProcessedMap type.
297 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
298 typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
301 struct SetStandardProcessedMapTraits : public Traits {
302 typedef typename Digraph::template NodeMap<bool> ProcessedMap;
303 static ProcessedMap *createProcessedMap(const Digraph &g)
305 return new ProcessedMap(g);
308 ///\brief \ref named-templ-param "Named parameter" for setting
309 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
311 ///\ref named-templ-param "Named parameter" for setting
312 ///\ref ProcessedMap type to be <tt>Digraph::NodeMap<bool></tt>.
313 ///If you don't set it explicitly, it will be automatically allocated.
314 struct SetStandardProcessedMap :
315 public Dfs< Digraph, SetStandardProcessedMapTraits > {
316 typedef Dfs< Digraph, SetStandardProcessedMapTraits > Create;
326 ///\param g The digraph the algorithm runs on.
327 Dfs(const Digraph &g) :
329 _pred(NULL), local_pred(false),
330 _dist(NULL), local_dist(false),
331 _reached(NULL), local_reached(false),
332 _processed(NULL), local_processed(false)
338 if(local_pred) delete _pred;
339 if(local_dist) delete _dist;
340 if(local_reached) delete _reached;
341 if(local_processed) delete _processed;
344 ///Sets the map that stores the predecessor arcs.
346 ///Sets the map that stores the predecessor arcs.
347 ///If you don't use this function before calling \ref run(),
348 ///it will allocate one. The destructor deallocates this
349 ///automatically allocated map, of course.
350 ///\return <tt> (*this) </tt>
351 Dfs &predMap(PredMap &m)
361 ///Sets the map that indicates which nodes are reached.
363 ///Sets the map that indicates which nodes are reached.
364 ///If you don't use this function before calling \ref run(),
365 ///it will allocate one. The destructor deallocates this
366 ///automatically allocated map, of course.
367 ///\return <tt> (*this) </tt>
368 Dfs &reachedMap(ReachedMap &m)
378 ///Sets the map that indicates which nodes are processed.
380 ///Sets the map that indicates which nodes are processed.
381 ///If you don't use this function before calling \ref run(),
382 ///it will allocate one. The destructor deallocates this
383 ///automatically allocated map, of course.
384 ///\return <tt> (*this) </tt>
385 Dfs &processedMap(ProcessedMap &m)
387 if(local_processed) {
389 local_processed=false;
395 ///Sets the map that stores the distances of the nodes.
397 ///Sets the map that stores the distances of the nodes calculated by
399 ///If you don't use this function before calling \ref run(),
400 ///it will allocate one. The destructor deallocates this
401 ///automatically allocated map, of course.
402 ///\return <tt> (*this) </tt>
403 Dfs &distMap(DistMap &m)
415 ///\name Execution control
416 ///The simplest way to execute the algorithm is to use
417 ///one of the member functions called \ref lemon::Dfs::run() "run()".
419 ///If you need more control on the execution, first you must call
420 ///\ref lemon::Dfs::init() "init()", then you can add a source node
421 ///with \ref lemon::Dfs::addSource() "addSource()".
422 ///Finally \ref lemon::Dfs::start() "start()" will perform the
423 ///actual path computation.
427 ///Initializes the internal data structures.
429 ///Initializes the internal data structures.
434 _stack.resize(countNodes(*G));
436 for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
437 _pred->set(u,INVALID);
438 _reached->set(u,false);
439 _processed->set(u,false);
443 ///Adds a new source node.
445 ///Adds a new source node to the set of nodes to be processed.
447 ///\pre The stack must be empty. (Otherwise the algorithm gives
450 ///\warning Distances will be wrong (or at least strange) in case of
452 void addSource(Node s)
454 LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
457 _reached->set(s,true);
458 _pred->set(s,INVALID);
461 _stack[++_stack_head]=e;
462 _dist->set(s,_stack_head);
465 _processed->set(s,true);
471 ///Processes the next arc.
473 ///Processes the next arc.
475 ///\return The processed arc.
477 ///\pre The stack must not be empty.
481 Arc e=_stack[_stack_head];
482 if(!(*_reached)[m=G->target(e)]) {
484 _reached->set(m,true);
486 _stack[_stack_head] = OutArcIt(*G, m);
487 _dist->set(m,_stack_head);
491 ++_stack[_stack_head];
493 while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
494 _processed->set(m,true);
497 m=G->source(_stack[_stack_head]);
498 ++_stack[_stack_head];
504 ///Next arc to be processed.
506 ///Next arc to be processed.
508 ///\return The next arc to be processed or \c INVALID if the stack
510 OutArcIt nextArc() const
512 return _stack_head>=0?_stack[_stack_head]:INVALID;
515 ///\brief Returns \c false if there are nodes
518 ///Returns \c false if there are nodes
519 ///to be processed in the queue (stack).
520 bool emptyQueue() const { return _stack_head<0; }
522 ///Returns the number of the nodes to be processed.
524 ///Returns the number of the nodes to be processed in the queue (stack).
525 int queueSize() const { return _stack_head+1; }
527 ///Executes the algorithm.
529 ///Executes the algorithm.
531 ///This method runs the %DFS algorithm from the root node
532 ///in order to compute the DFS path to each node.
534 /// The algorithm computes
536 ///- the distance of each node from the root in the %DFS tree.
538 ///\pre init() must be called and a root node should be
539 ///added with addSource() before using this function.
541 ///\note <tt>d.start()</tt> is just a shortcut of the following code.
543 /// while ( !d.emptyQueue() ) {
544 /// d.processNextArc();
549 while ( !emptyQueue() ) processNextArc();
552 ///Executes the algorithm until the given target node is reached.
554 ///Executes the algorithm until the given target node is reached.
556 ///This method runs the %DFS algorithm from the root node
557 ///in order to compute the DFS path to \c dest.
559 ///The algorithm computes
560 ///- the %DFS path to \c dest,
561 ///- the distance of \c dest from the root in the %DFS tree.
563 ///\pre init() must be called and a root node should be
564 ///added with addSource() before using this function.
565 void start(Node dest)
567 while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
571 ///Executes the algorithm until a condition is met.
573 ///Executes the algorithm until a condition is met.
575 ///This method runs the %DFS algorithm from the root node
576 ///until an arc \c a with <tt>am[a]</tt> true is found.
578 ///\param am A \c bool (or convertible) arc map. The algorithm
579 ///will stop when it reaches an arc \c a with <tt>am[a]</tt> true.
581 ///\return The reached arc \c a with <tt>am[a]</tt> true or
582 ///\c INVALID if no such arc was found.
584 ///\pre init() must be called and a root node should be
585 ///added with addSource() before using this function.
587 ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c am is an arc map,
589 template<class ArcBoolMap>
590 Arc start(const ArcBoolMap &am)
592 while ( !emptyQueue() && !am[_stack[_stack_head]] )
594 return emptyQueue() ? INVALID : _stack[_stack_head];
597 ///Runs the algorithm from the given node.
599 ///This method runs the %DFS algorithm from node \c s
600 ///in order to compute the DFS path to each node.
602 ///The algorithm computes
604 ///- the distance of each node from the root in the %DFS tree.
606 ///\note <tt>d.run(s)</tt> is just a shortcut of the following code.
618 ///Finds the %DFS path between \c s and \c t.
620 ///This method runs the %DFS algorithm from node \c s
621 ///in order to compute the DFS path to \c t.
623 ///\return The length of the <tt>s</tt>--<tt>t</tt> DFS path,
624 ///if \c t is reachable form \c s, \c 0 otherwise.
626 ///\note Apart from the return value, <tt>d.run(s,t)</tt> is
627 ///just a shortcut of the following code.
633 int run(Node s,Node t) {
637 return reached(t)?_stack_head+1:0;
640 ///Runs the algorithm to visit all nodes in the digraph.
642 ///This method runs the %DFS algorithm in order to compute the
643 ///%DFS path to each node.
645 ///The algorithm computes
647 ///- the distance of each node from the root in the %DFS tree.
649 ///\note <tt>d.run()</tt> is just a shortcut of the following code.
652 /// for (NodeIt n(digraph); n != INVALID; ++n) {
653 /// if (!d.reached(n)) {
661 for (NodeIt it(*G); it != INVALID; ++it) {
671 ///\name Query Functions
672 ///The result of the %DFS algorithm can be obtained using these
674 ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start()
675 ///"start()" must be called before using them.
679 ///The DFS path to a node.
681 ///Returns the DFS path to a node.
683 ///\warning \c t should be reachable from the root.
685 ///\pre Either \ref run() or \ref start() must be called before
686 ///using this function.
687 Path path(Node t) const { return Path(*G, *_pred, t); }
689 ///The distance of a node from the root.
691 ///Returns the distance of a node from the root.
693 ///\warning If node \c v is not reachable from the root, then
694 ///the return value of this function is undefined.
696 ///\pre Either \ref run() or \ref start() must be called before
697 ///using this function.
698 int dist(Node v) const { return (*_dist)[v]; }
700 ///Returns the 'previous arc' of the %DFS tree for a node.
702 ///This function returns the 'previous arc' of the %DFS tree for the
703 ///node \c v, i.e. it returns the last arc of a %DFS path from the
704 ///root to \c v. It is \c INVALID
705 ///if \c v is not reachable from the root(s) or if \c v is a root.
707 ///The %DFS tree used here is equal to the %DFS tree used in
710 ///\pre Either \ref run() or \ref start() must be called before using
712 Arc predArc(Node v) const { return (*_pred)[v];}
714 ///Returns the 'previous node' of the %DFS tree.
716 ///This function returns the 'previous node' of the %DFS
717 ///tree for the node \c v, i.e. it returns the last but one node
718 ///from a %DFS path from the root to \c v. It is \c INVALID
719 ///if \c v is not reachable from the root(s) or if \c v is a root.
721 ///The %DFS tree used here is equal to the %DFS tree used in
724 ///\pre Either \ref run() or \ref start() must be called before
725 ///using this function.
726 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
727 G->source((*_pred)[v]); }
729 ///\brief Returns a const reference to the node map that stores the
730 ///distances of the nodes.
732 ///Returns a const reference to the node map that stores the
733 ///distances of the nodes calculated by the algorithm.
735 ///\pre Either \ref run() or \ref init()
736 ///must be called before using this function.
737 const DistMap &distMap() const { return *_dist;}
739 ///\brief Returns a const reference to the node map that stores the
742 ///Returns a const reference to the node map that stores the predecessor
743 ///arcs, which form the DFS tree.
745 ///\pre Either \ref run() or \ref init()
746 ///must be called before using this function.
747 const PredMap &predMap() const { return *_pred;}
749 ///Checks if a node is reachable from the root(s).
751 ///Returns \c true if \c v is reachable from the root(s).
752 ///\pre Either \ref run() or \ref start()
753 ///must be called before using this function.
754 bool reached(Node v) const { return (*_reached)[v]; }
759 ///Default traits class of dfs() function.
761 ///Default traits class of dfs() function.
762 ///\tparam GR Digraph type.
764 struct DfsWizardDefaultTraits
766 ///The type of the digraph the algorithm runs on.
769 ///\brief The type of the map that stores the predecessor
770 ///arcs of the %DFS paths.
772 ///The type of the map that stores the predecessor
773 ///arcs of the %DFS paths.
774 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
776 typedef NullMap<typename Digraph::Node,typename Digraph::Arc> PredMap;
777 ///Instantiates a \ref PredMap.
779 ///This function instantiates a \ref PredMap.
780 ///\param g is the digraph, to which we would like to define the
783 static PredMap *createPredMap(const Digraph &g)
785 static PredMap *createPredMap(const Digraph &)
788 return new PredMap();
791 ///The type of the map that indicates which nodes are processed.
793 ///The type of the map that indicates which nodes are processed.
794 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
795 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
796 ///Instantiates a \ref ProcessedMap.
798 ///This function instantiates a \ref ProcessedMap.
799 ///\param g is the digraph, to which
800 ///we would like to define the \ref ProcessedMap.
802 static ProcessedMap *createProcessedMap(const Digraph &g)
804 static ProcessedMap *createProcessedMap(const Digraph &)
807 return new ProcessedMap();
810 ///The type of the map that indicates which nodes are reached.
812 ///The type of the map that indicates which nodes are reached.
813 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
814 typedef typename Digraph::template NodeMap<bool> ReachedMap;
815 ///Instantiates a \ref ReachedMap.
817 ///This function instantiates a \ref ReachedMap.
818 ///\param g is the digraph, to which
819 ///we would like to define the \ref ReachedMap.
820 static ReachedMap *createReachedMap(const Digraph &g)
822 return new ReachedMap(g);
825 ///The type of the map that stores the distances of the nodes.
827 ///The type of the map that stores the distances of the nodes.
828 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
830 typedef NullMap<typename Digraph::Node,int> DistMap;
831 ///Instantiates a \ref DistMap.
833 ///This function instantiates a \ref DistMap.
834 ///\param g is the digraph, to which we would like to define
837 static DistMap *createDistMap(const Digraph &g)
839 static DistMap *createDistMap(const Digraph &)
842 return new DistMap();
846 /// Default traits class used by \ref DfsWizard
848 /// To make it easier to use Dfs algorithm
849 /// we have created a wizard class.
850 /// This \ref DfsWizard class needs default traits,
851 /// as well as the \ref Dfs class.
852 /// The \ref DfsWizardBase is a class to be the default traits of the
853 /// \ref DfsWizard class.
855 class DfsWizardBase : public DfsWizardDefaultTraits<GR>
858 typedef DfsWizardDefaultTraits<GR> Base;
860 //The type of the nodes in the digraph.
861 typedef typename Base::Digraph::Node Node;
863 //Pointer to the digraph the algorithm runs on.
865 //Pointer to the map of reached nodes.
867 //Pointer to the map of processed nodes.
869 //Pointer to the map of predecessors arcs.
871 //Pointer to the map of distances.
873 //Pointer to the source node.
879 /// This constructor does not require parameters, therefore it initiates
880 /// all of the attributes to default values (0, INVALID).
881 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
882 _dist(0), _source(INVALID) {}
886 /// This constructor requires some parameters,
887 /// listed in the parameters list.
888 /// Others are initiated to 0.
889 /// \param g The digraph the algorithm runs on.
890 /// \param s The source node.
891 DfsWizardBase(const GR &g, Node s=INVALID) :
892 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
893 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
897 /// Auxiliary class for the function type interface of DFS algorithm.
899 /// This auxiliary class is created to implement the function type
900 /// interface of \ref Dfs algorithm. It uses the functions and features
901 /// of the plain \ref Dfs, but it is much simpler to use it.
902 /// It should only be used through the \ref dfs() function, which makes
903 /// it easier to use the algorithm.
905 /// Simplicity means that the way to change the types defined
906 /// in the traits class is based on functions that returns the new class
907 /// and not on templatable built-in classes.
908 /// When using the plain \ref Dfs
909 /// the new class with the modified type comes from
910 /// the original class by using the ::
911 /// operator. In the case of \ref DfsWizard only
912 /// a function have to be called, and it will
913 /// return the needed class.
915 /// It does not have own \ref run() method. When its \ref run() method
916 /// is called, it initiates a plain \ref Dfs object, and calls the
917 /// \ref Dfs::run() method of it.
919 class DfsWizard : public TR
923 ///The type of the digraph the algorithm runs on.
924 typedef typename TR::Digraph Digraph;
926 typedef typename Digraph::Node Node;
927 typedef typename Digraph::NodeIt NodeIt;
928 typedef typename Digraph::Arc Arc;
929 typedef typename Digraph::OutArcIt OutArcIt;
931 ///\brief The type of the map that stores the predecessor
932 ///arcs of the shortest paths.
933 typedef typename TR::PredMap PredMap;
934 ///\brief The type of the map that stores the distances of the nodes.
935 typedef typename TR::DistMap DistMap;
936 ///\brief The type of the map that indicates which nodes are reached.
937 typedef typename TR::ReachedMap ReachedMap;
938 ///\brief The type of the map that indicates which nodes are processed.
939 typedef typename TR::ProcessedMap ProcessedMap;
944 DfsWizard() : TR() {}
946 /// Constructor that requires parameters.
948 /// Constructor that requires parameters.
949 /// These parameters will be the default values for the traits class.
950 DfsWizard(const Digraph &g, Node s=INVALID) :
954 DfsWizard(const TR &b) : TR(b) {}
958 ///Runs DFS algorithm from a source node.
960 ///Runs DFS algorithm from a source node.
961 ///The node can be given with the \ref source() function.
964 if(Base::_source==INVALID) throw UninitializedParameter();
965 Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
967 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
969 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
971 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
973 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
974 alg.run(Base::_source);
977 ///Runs DFS algorithm from the given node.
979 ///Runs DFS algorithm from the given node.
980 ///\param s is the given source.
987 /// Sets the source node, from which the Dfs algorithm runs.
989 /// Sets the source node, from which the Dfs algorithm runs.
990 /// \param s is the source node.
991 DfsWizard<TR> &source(Node s)
998 struct SetPredMapBase : public Base {
1000 static PredMap *createPredMap(const Digraph &) { return 0; };
1001 SetPredMapBase(const TR &b) : TR(b) {}
1003 ///\brief \ref named-templ-param "Named parameter"
1004 ///for setting \ref PredMap object.
1006 ///\ref named-templ-param "Named parameter"
1007 ///for setting \ref PredMap object.
1009 DfsWizard<SetPredMapBase<T> > predMap(const T &t)
1011 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
1012 return DfsWizard<SetPredMapBase<T> >(*this);
1016 struct SetReachedMapBase : public Base {
1017 typedef T ReachedMap;
1018 static ReachedMap *createReachedMap(const Digraph &) { return 0; };
1019 SetReachedMapBase(const TR &b) : TR(b) {}
1021 ///\brief \ref named-templ-param "Named parameter"
1022 ///for setting \ref ReachedMap object.
1024 /// \ref named-templ-param "Named parameter"
1025 ///for setting \ref ReachedMap object.
1027 DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
1029 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
1030 return DfsWizard<SetReachedMapBase<T> >(*this);
1034 struct SetProcessedMapBase : public Base {
1035 typedef T ProcessedMap;
1036 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1037 SetProcessedMapBase(const TR &b) : TR(b) {}
1039 ///\brief \ref named-templ-param "Named parameter"
1040 ///for setting \ref ProcessedMap object.
1042 /// \ref named-templ-param "Named parameter"
1043 ///for setting \ref ProcessedMap object.
1045 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
1047 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
1048 return DfsWizard<SetProcessedMapBase<T> >(*this);
1052 struct SetDistMapBase : public Base {
1054 static DistMap *createDistMap(const Digraph &) { return 0; };
1055 SetDistMapBase(const TR &b) : TR(b) {}
1057 ///\brief \ref named-templ-param "Named parameter"
1058 ///for setting \ref DistMap object.
1060 ///\ref named-templ-param "Named parameter"
1061 ///for setting \ref DistMap object.
1063 DfsWizard<SetDistMapBase<T> > distMap(const T &t)
1065 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1066 return DfsWizard<SetDistMapBase<T> >(*this);
1071 ///Function type interface for Dfs algorithm.
1074 ///Function type interface for Dfs algorithm.
1076 ///This function also has several
1077 ///\ref named-templ-func-param "named parameters",
1078 ///they are declared as the members of class \ref DfsWizard.
1080 ///example shows how to use these parameters.
1082 /// dfs(g,source).predMap(preds).run();
1084 ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
1085 ///to the end of the parameter list.
1089 DfsWizard<DfsWizardBase<GR> >
1090 dfs(const GR &g,typename GR::Node s=INVALID)
1092 return DfsWizard<DfsWizardBase<GR> >(g,s);
1096 /// \brief Visitor class for DFS.
1098 /// This class defines the interface of the DfsVisit events, and
1099 /// it could be the base of a real visitor class.
1100 template <typename _Digraph>
1102 typedef _Digraph Digraph;
1103 typedef typename Digraph::Arc Arc;
1104 typedef typename Digraph::Node Node;
1105 /// \brief Called for the source node of the DFS.
1107 /// This function is called for the source node of the DFS.
1108 void start(const Node& node) {}
1109 /// \brief Called when the source node is leaved.
1111 /// This function is called when the source node is leaved.
1112 void stop(const Node& node) {}
1113 /// \brief Called when a node is reached first time.
1115 /// This function is called when a node is reached first time.
1116 void reach(const Node& node) {}
1117 /// \brief Called when an arc reaches a new node.
1119 /// This function is called when the DFS finds an arc whose target node
1120 /// is not reached yet.
1121 void discover(const Arc& arc) {}
1122 /// \brief Called when an arc is examined but its target node is
1123 /// already discovered.
1125 /// This function is called when an arc is examined but its target node is
1126 /// already discovered.
1127 void examine(const Arc& arc) {}
1128 /// \brief Called when the DFS steps back from a node.
1130 /// This function is called when the DFS steps back from a node.
1131 void leave(const Node& node) {}
1132 /// \brief Called when the DFS steps back on an arc.
1134 /// This function is called when the DFS steps back on an arc.
1135 void backtrack(const Arc& arc) {}
1138 template <typename _Digraph>
1140 typedef _Digraph Digraph;
1141 typedef typename Digraph::Arc Arc;
1142 typedef typename Digraph::Node Node;
1143 void start(const Node&) {}
1144 void stop(const Node&) {}
1145 void reach(const Node&) {}
1146 void discover(const Arc&) {}
1147 void examine(const Arc&) {}
1148 void leave(const Node&) {}
1149 void backtrack(const Arc&) {}
1151 template <typename _Visitor>
1152 struct Constraints {
1153 void constraints() {
1156 visitor.start(node);
1158 visitor.reach(node);
1159 visitor.discover(arc);
1160 visitor.examine(arc);
1161 visitor.leave(node);
1162 visitor.backtrack(arc);
1169 /// \brief Default traits class of DfsVisit class.
1171 /// Default traits class of DfsVisit class.
1172 /// \tparam _Digraph The type of the digraph the algorithm runs on.
1173 template<class _Digraph>
1174 struct DfsVisitDefaultTraits {
1176 /// \brief The type of the digraph the algorithm runs on.
1177 typedef _Digraph Digraph;
1179 /// \brief The type of the map that indicates which nodes are reached.
1181 /// The type of the map that indicates which nodes are reached.
1182 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
1183 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1185 /// \brief Instantiates a \ref ReachedMap.
1187 /// This function instantiates a \ref ReachedMap.
1188 /// \param digraph is the digraph, to which
1189 /// we would like to define the \ref ReachedMap.
1190 static ReachedMap *createReachedMap(const Digraph &digraph) {
1191 return new ReachedMap(digraph);
1198 /// \brief %DFS algorithm class with visitor interface.
1200 /// This class provides an efficient implementation of the %DFS algorithm
1201 /// with visitor interface.
1203 /// The %DfsVisit class provides an alternative interface to the Dfs
1204 /// class. It works with callback mechanism, the DfsVisit object calls
1205 /// the member functions of the \c Visitor class on every DFS event.
1207 /// This interface of the DFS algorithm should be used in special cases
1208 /// when extra actions have to be performed in connection with certain
1209 /// events of the DFS algorithm. Otherwise consider to use Dfs or dfs()
1212 /// \tparam _Digraph The type of the digraph the algorithm runs on.
1213 /// The default value is
1214 /// \ref ListDigraph. The value of _Digraph is not used directly by
1215 /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits.
1216 /// \tparam _Visitor The Visitor type that is used by the algorithm.
1217 /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which
1218 /// does not observe the DFS events. If you want to observe the DFS
1219 /// events, you should implement your own visitor class.
1220 /// \tparam _Traits Traits class to set various data types used by the
1221 /// algorithm. The default traits class is
1222 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
1223 /// See \ref DfsVisitDefaultTraits for the documentation of
1224 /// a DFS visit traits class.
1226 template <typename _Digraph, typename _Visitor, typename _Traits>
1228 template <typename _Digraph = ListDigraph,
1229 typename _Visitor = DfsVisitor<_Digraph>,
1230 typename _Traits = DfsDefaultTraits<_Digraph> >
1235 /// \brief \ref Exception for uninitialized parameters.
1237 /// This error represents problems in the initialization
1238 /// of the parameters of the algorithm.
1239 class UninitializedParameter : public lemon::UninitializedParameter {
1241 virtual const char* what() const throw()
1243 return "lemon::DfsVisit::UninitializedParameter";
1247 ///The traits class.
1248 typedef _Traits Traits;
1250 ///The type of the digraph the algorithm runs on.
1251 typedef typename Traits::Digraph Digraph;
1253 ///The visitor type used by the algorithm.
1254 typedef _Visitor Visitor;
1256 ///The type of the map that indicates which nodes are reached.
1257 typedef typename Traits::ReachedMap ReachedMap;
1261 typedef typename Digraph::Node Node;
1262 typedef typename Digraph::NodeIt NodeIt;
1263 typedef typename Digraph::Arc Arc;
1264 typedef typename Digraph::OutArcIt OutArcIt;
1266 //Pointer to the underlying digraph.
1267 const Digraph *_digraph;
1268 //Pointer to the visitor object.
1270 //Pointer to the map of reached status of the nodes.
1271 ReachedMap *_reached;
1272 //Indicates if _reached is locally allocated (true) or not.
1275 std::vector<typename Digraph::Arc> _stack;
1278 //Creates the maps if necessary.
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