Update README file.
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/maps.h>
32 #include <lemon/concept_check.h>
37 ///Default traits class of Dfs class.
39 ///Default traits class of Dfs class.
40 ///\tparam GR Digraph type.
42 struct DfsDefaultTraits
44 ///The digraph type the algorithm runs on.
46 ///\brief The type of the map that stores the last
47 ///arcs of the %DFS paths.
49 ///The type of the map that stores the last
50 ///arcs of the %DFS paths.
51 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
53 typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
54 ///Instantiates a PredMap.
56 ///This function instantiates a \ref PredMap.
57 ///\param G is the digraph, to which we would like to define the PredMap.
58 ///\todo The digraph alone may be insufficient to initialize
59 static PredMap *createPredMap(const GR &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 ///\todo named parameter to set this type, function to read and write.
69 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
70 ///Instantiates a 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 GR &g)
78 static ProcessedMap *createProcessedMap(const GR &)
81 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::WriteMap "WriteMap" concept.
87 ///\todo named parameter to set this type, function to read and write.
88 typedef typename Digraph::template NodeMap<bool> ReachedMap;
89 ///Instantiates a 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 GR &G)
96 return new ReachedMap(G);
98 ///The type of the map that stores the dists of the nodes.
100 ///The type of the map that stores the dists of the nodes.
101 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
103 typedef typename Digraph::template NodeMap<int> DistMap;
104 ///Instantiates a DistMap.
106 ///This function instantiates a \ref DistMap.
107 ///\param G is the digraph, to which we would like to define
109 static DistMap *createDistMap(const GR &G)
111 return new DistMap(G);
115 ///%DFS algorithm class.
118 ///This class provides an efficient implementation of the %DFS algorithm.
120 ///\tparam GR The digraph type the algorithm runs on. The default value is
121 ///\ref ListDigraph. The value of GR is not used directly by Dfs, it
122 ///is only passed to \ref DfsDefaultTraits.
123 ///\tparam TR Traits class to set various data types used by the algorithm.
124 ///The default traits class is
125 ///\ref DfsDefaultTraits "DfsDefaultTraits<GR>".
126 ///See \ref DfsDefaultTraits for the documentation of
127 ///a Dfs traits class.
129 template <typename GR,
132 template <typename GR=ListDigraph,
133 typename TR=DfsDefaultTraits<GR> >
138 * \brief \ref Exception for uninitialized parameters.
140 * This error represents problems in the initialization
141 * of the parameters of the algorithms.
143 class UninitializedParameter : public lemon::UninitializedParameter {
145 virtual const char* what() const throw() {
146 return "lemon::Dfs::UninitializedParameter";
151 ///The type of the underlying digraph.
152 typedef typename TR::Digraph Digraph;
154 typedef typename Digraph::Node Node;
156 typedef typename Digraph::NodeIt NodeIt;
158 typedef typename Digraph::Arc Arc;
160 typedef typename Digraph::OutArcIt OutArcIt;
162 ///\brief The type of the map that stores the last
163 ///arcs of the %DFS paths.
164 typedef typename TR::PredMap PredMap;
165 ///The type of the map indicating which nodes are reached.
166 typedef typename TR::ReachedMap ReachedMap;
167 ///The type of the map indicating which nodes are processed.
168 typedef typename TR::ProcessedMap ProcessedMap;
169 ///The type of the map that stores the dists of the nodes.
170 typedef typename TR::DistMap DistMap;
172 /// Pointer to the underlying digraph.
174 ///Pointer to the map of predecessors arcs.
176 ///Indicates if \ref _pred is locally allocated (\c true) or not.
178 ///Pointer to the map of distances.
180 ///Indicates if \ref _dist is locally allocated (\c true) or not.
182 ///Pointer to the map of reached status of the nodes.
183 ReachedMap *_reached;
184 ///Indicates if \ref _reached is locally allocated (\c true) or not.
186 ///Pointer to the map of processed status of the nodes.
187 ProcessedMap *_processed;
188 ///Indicates if \ref _processed is locally allocated (\c true) or not.
189 bool local_processed;
191 std::vector<typename Digraph::OutArcIt> _stack;
194 ///Creates the maps if necessary.
196 ///\todo Better memory allocation (instead of new).
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 DefPredMapTraits : public Traits {
232 static PredMap *createPredMap(const Digraph &G)
234 throw UninitializedParameter();
237 ///\brief \ref named-templ-param "Named parameter" for setting
240 ///\ref named-templ-param "Named parameter" for setting PredMap type
243 struct DefPredMap : public Dfs<Digraph, DefPredMapTraits<T> > {
244 typedef Dfs<Digraph, DefPredMapTraits<T> > Create;
249 struct DefDistMapTraits : public Traits {
251 static DistMap *createDistMap(const Digraph &)
253 throw UninitializedParameter();
256 ///\brief \ref named-templ-param "Named parameter" for setting
259 ///\ref named-templ-param "Named parameter" for setting DistMap
263 typedef Dfs<Digraph, DefDistMapTraits<T> > Create;
267 struct DefReachedMapTraits : public Traits {
268 typedef T ReachedMap;
269 static ReachedMap *createReachedMap(const Digraph &)
271 throw UninitializedParameter();
274 ///\brief \ref named-templ-param "Named parameter" for setting
277 ///\ref named-templ-param "Named parameter" for setting ReachedMap type
280 struct DefReachedMap : public Dfs< Digraph, DefReachedMapTraits<T> > {
281 typedef Dfs< Digraph, DefReachedMapTraits<T> > Create;
285 struct DefProcessedMapTraits : public Traits {
286 typedef T ProcessedMap;
287 static ProcessedMap *createProcessedMap(const Digraph &)
289 throw UninitializedParameter();
292 ///\brief \ref named-templ-param "Named parameter" for setting
295 ///\ref named-templ-param "Named parameter" for setting ProcessedMap type
298 struct DefProcessedMap : public Dfs< Digraph, DefProcessedMapTraits<T> > {
299 typedef Dfs< Digraph, DefProcessedMapTraits<T> > Create;
302 struct DefDigraphProcessedMapTraits : public Traits {
303 typedef typename Digraph::template NodeMap<bool> ProcessedMap;
304 static ProcessedMap *createProcessedMap(const Digraph &G)
306 return new ProcessedMap(G);
309 ///\brief \ref named-templ-param "Named parameter"
310 ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
312 ///\ref named-templ-param "Named parameter"
313 ///for setting the ProcessedMap type to be Digraph::NodeMap<bool>.
314 ///If you don't set it explicitely, it will be automatically allocated.
316 class DefProcessedMapToBeDefaultMap :
317 public Dfs< Digraph, DefDigraphProcessedMapTraits> {
318 typedef Dfs< Digraph, DefDigraphProcessedMapTraits> Create;
327 ///\param _G the digraph the algorithm will run on.
329 Dfs(const Digraph& _G) :
331 _pred(NULL), local_pred(false),
332 _dist(NULL), local_dist(false),
333 _reached(NULL), local_reached(false),
334 _processed(NULL), local_processed(false)
340 if(local_pred) delete _pred;
341 if(local_dist) delete _dist;
342 if(local_reached) delete _reached;
343 if(local_processed) delete _processed;
346 ///Sets the map storing the predecessor arcs.
348 ///Sets the map storing the predecessor arcs.
349 ///If you don't use this function before calling \ref run(),
350 ///it will allocate one. The destuctor deallocates this
351 ///automatically allocated map, of course.
352 ///\return <tt> (*this) </tt>
353 Dfs &predMap(PredMap &m)
363 ///Sets the map storing the distances calculated by the algorithm.
365 ///Sets the map storing the distances calculated by the algorithm.
366 ///If you don't use this function before calling \ref run(),
367 ///it will allocate one. The destuctor deallocates this
368 ///automatically allocated map, of course.
369 ///\return <tt> (*this) </tt>
370 Dfs &distMap(DistMap &m)
380 ///Sets the map indicating if a node is reached.
382 ///Sets the map indicating if a node is reached.
383 ///If you don't use this function before calling \ref run(),
384 ///it will allocate one. The destuctor deallocates this
385 ///automatically allocated map, of course.
386 ///\return <tt> (*this) </tt>
387 Dfs &reachedMap(ReachedMap &m)
397 ///Sets the map indicating if a node is processed.
399 ///Sets the map indicating if a node is processed.
400 ///If you don't use this function before calling \ref run(),
401 ///it will allocate one. The destuctor deallocates this
402 ///automatically allocated map, of course.
403 ///\return <tt> (*this) </tt>
404 Dfs &processedMap(ProcessedMap &m)
406 if(local_processed) {
408 local_processed=false;
415 ///\name Execution control
416 ///The simplest way to execute the algorithm is to use
417 ///one of the member functions called \c run(...).
419 ///If you need more control on the execution,
420 ///first you must call \ref init(), then you can add a source node
421 ///with \ref addSource().
422 ///Finally \ref start() will perform the actual path
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 // _predNode->set(u,INVALID);
439 _reached->set(u,false);
440 _processed->set(u,false);
444 ///Adds a new source node.
446 ///Adds a new source node to the set of nodes to be processed.
448 ///\warning dists are wrong (or at least strange)
449 ///in case of multiple sources.
450 void addSource(Node s)
454 _reached->set(s,true);
455 _pred->set(s,INVALID);
458 _stack[++_stack_head]=e;
459 _dist->set(s,_stack_head);
462 _processed->set(s,true);
468 ///Processes the next arc.
470 ///Processes the next arc.
472 ///\return The processed arc.
474 ///\pre The stack must not be empty!
478 Arc e=_stack[_stack_head];
479 if(!(*_reached)[m=G->target(e)]) {
481 _reached->set(m,true);
483 _stack[_stack_head] = OutArcIt(*G, m);
484 _dist->set(m,_stack_head);
488 ++_stack[_stack_head];
490 while(_stack_head>=0 && _stack[_stack_head]==INVALID) {
491 _processed->set(m,true);
494 m=G->source(_stack[_stack_head]);
495 ++_stack[_stack_head];
500 ///Next arc to be processed.
502 ///Next arc to be processed.
504 ///\return The next arc to be processed or INVALID if the stack is
508 return _stack_head>=0?_stack[_stack_head]:INVALID;
511 ///\brief Returns \c false if there are nodes
512 ///to be processed in the queue
514 ///Returns \c false if there are nodes
515 ///to be processed in the queue
516 bool emptyQueue() { return _stack_head<0; }
517 ///Returns the number of the nodes to be processed.
519 ///Returns the number of the nodes to be processed in the queue.
520 int queueSize() { return _stack_head+1; }
522 ///Executes the algorithm.
524 ///Executes the algorithm.
526 ///\pre init() must be called and at least one node should be added
527 ///with addSource() before using this function.
529 ///This method runs the %DFS algorithm from the root node(s)
532 ///%DFS path to each node. The algorithm computes
534 ///- The distance of each node from the root(s) in the %DFS tree.
538 while ( !emptyQueue() ) processNextArc();
541 ///Executes the algorithm until \c dest is reached.
543 ///Executes the algorithm until \c dest is reached.
545 ///\pre init() must be called and at least one node should be added
546 ///with addSource() before using this function.
548 ///This method runs the %DFS algorithm from the root node(s)
551 ///%DFS path to \c dest. The algorithm computes
552 ///- The %DFS path to \c dest.
553 ///- The distance of \c dest from the root(s) in the %DFS tree.
555 void start(Node dest)
557 while ( !emptyQueue() && G->target(_stack[_stack_head])!=dest )
561 ///Executes the algorithm until a condition is met.
563 ///Executes the algorithm until a condition is met.
565 ///\pre init() must be called and at least one node should be added
566 ///with addSource() before using this function.
568 ///\param em must be a bool (or convertible) arc map. The algorithm
569 ///will stop when it reaches an arc \c e with <tt>em[e]</tt> true.
571 ///\return The reached arc \c e with <tt>em[e]</tt> true or
572 ///\c INVALID if no such arc was found.
574 ///\warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map,
577 Arc start(const EM &em)
579 while ( !emptyQueue() && !em[_stack[_stack_head]] )
581 return emptyQueue() ? INVALID : _stack[_stack_head];
584 ///Runs %DFS algorithm to visit all nodes in the digraph.
586 ///This method runs the %DFS algorithm in order to
588 ///%DFS path to each node. The algorithm computes
590 ///- The distance of each node from the root in the %DFS tree.
592 ///\note d.run() is just a shortcut of the following code.
595 /// for (NodeIt it(digraph); it != INVALID; ++it) {
596 /// if (!d.reached(it)) {
604 for (NodeIt it(*G); it != INVALID; ++it) {
612 ///Runs %DFS algorithm from node \c s.
614 ///This method runs the %DFS algorithm from a root node \c s
617 ///%DFS path to each node. The algorithm computes
619 ///- The distance of each node from the root in the %DFS tree.
621 ///\note d.run(s) is just a shortcut of the following code.
633 ///Finds the %DFS path between \c s and \c t.
635 ///Finds the %DFS path between \c s and \c t.
637 ///\return The length of the %DFS s---t path if there exists one,
639 ///\note Apart from the return value, d.run(s,t) is
640 ///just a shortcut of the following code.
646 int run(Node s,Node t) {
650 return reached(t)?_stack_head+1:0;
655 ///\name Query Functions
656 ///The result of the %DFS algorithm can be obtained using these
658 ///Before the use of these functions,
659 ///either run() or start() must be called.
663 typedef PredMapPath<Digraph, PredMap> Path;
665 ///Gives back the shortest path.
667 ///Gives back the shortest path.
668 ///\pre The \c t should be reachable from the source.
671 return Path(*G, *_pred, t);
674 ///The distance of a node from the root(s).
676 ///Returns the distance of a node from the root(s).
677 ///\pre \ref run() must be called before using this function.
678 ///\warning If node \c v is unreachable from the root(s) then the return
679 ///value of this funcion is undefined.
680 int dist(Node v) const { return (*_dist)[v]; }
682 ///Returns the 'previous arc' of the %DFS tree.
684 ///For a node \c v it returns the 'previous arc'
686 ///i.e. it returns the last arc of a %DFS path from the root(s) to \c
687 ///v. It is \ref INVALID
688 ///if \c v is unreachable from the root(s) or \c v is a root. The
689 ///%DFS tree used here is equal to the %DFS tree used in
691 ///\pre Either \ref run() or \ref start() must be called before using
693 Arc predArc(Node v) const { return (*_pred)[v];}
695 ///Returns the 'previous node' of the %DFS tree.
697 ///For a node \c v it returns the 'previous node'
699 ///i.e. it returns the last but one node from a %DFS path from the
701 ///It is INVALID if \c v is unreachable from the root(s) or
702 ///if \c v itself a root.
703 ///The %DFS tree used here is equal to the %DFS
704 ///tree used in \ref predArc().
705 ///\pre Either \ref run() or \ref start() must be called before
706 ///using this function.
707 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
708 G->source((*_pred)[v]); }
710 ///Returns a reference to the NodeMap of distances.
712 ///Returns a reference to the NodeMap of distances.
713 ///\pre Either \ref run() or \ref init() must
714 ///be called before using this function.
715 const DistMap &distMap() const { return *_dist;}
717 ///Returns a reference to the %DFS arc-tree map.
719 ///Returns a reference to the NodeMap of the arcs of the
721 ///\pre Either \ref run() or \ref init()
722 ///must be called before using this function.
723 const PredMap &predMap() const { return *_pred;}
725 ///Checks if a node is reachable from the root.
727 ///Returns \c true if \c v is reachable from the root(s).
728 ///\warning The source nodes are inditated as unreachable.
729 ///\pre Either \ref run() or \ref start()
730 ///must be called before using this function.
732 bool reached(Node v) { return (*_reached)[v]; }
737 ///Default traits class of Dfs function.
739 ///Default traits class of Dfs function.
740 ///\tparam GR Digraph type.
742 struct DfsWizardDefaultTraits
744 ///The digraph type the algorithm runs on.
746 ///\brief The type of the map that stores the last
747 ///arcs of the %DFS paths.
749 ///The type of the map that stores the last
750 ///arcs of the %DFS paths.
751 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
753 typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
754 ///Instantiates a PredMap.
756 ///This function instantiates a \ref PredMap.
757 ///\param g is the digraph, to which we would like to define the PredMap.
758 ///\todo The digraph alone may be insufficient to initialize
760 static PredMap *createPredMap(const GR &g)
762 static PredMap *createPredMap(const GR &)
765 return new PredMap();
768 ///The type of the map that indicates which nodes are processed.
770 ///The type of the map that indicates which nodes are processed.
771 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
772 ///\todo named parameter to set this type, function to read and write.
773 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
774 ///Instantiates a ProcessedMap.
776 ///This function instantiates a \ref ProcessedMap.
777 ///\param g is the digraph, to which
778 ///we would like to define the \ref ProcessedMap
780 static ProcessedMap *createProcessedMap(const GR &g)
782 static ProcessedMap *createProcessedMap(const GR &)
785 return new ProcessedMap();
787 ///The type of the map that indicates which nodes are reached.
789 ///The type of the map that indicates which nodes are reached.
790 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
791 ///\todo named parameter to set this type, function to read and write.
792 typedef typename Digraph::template NodeMap<bool> ReachedMap;
793 ///Instantiates a ReachedMap.
795 ///This function instantiates a \ref ReachedMap.
796 ///\param G is the digraph, to which
797 ///we would like to define the \ref ReachedMap.
798 static ReachedMap *createReachedMap(const GR &G)
800 return new ReachedMap(G);
802 ///The type of the map that stores the dists of the nodes.
804 ///The type of the map that stores the dists of the nodes.
805 ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
807 typedef NullMap<typename Digraph::Node,int> DistMap;
808 ///Instantiates a DistMap.
810 ///This function instantiates a \ref DistMap.
811 ///\param g is the digraph, to which we would like to define
814 static DistMap *createDistMap(const GR &g)
816 static DistMap *createDistMap(const GR &)
819 return new DistMap();
823 /// Default traits used by \ref DfsWizard
825 /// To make it easier to use Dfs algorithm
826 ///we have created a wizard class.
827 /// This \ref DfsWizard class needs default traits,
828 ///as well as the \ref Dfs class.
829 /// The \ref DfsWizardBase is a class to be the default traits of the
830 /// \ref DfsWizard class.
832 class DfsWizardBase : public DfsWizardDefaultTraits<GR>
835 typedef DfsWizardDefaultTraits<GR> Base;
837 /// Type of the nodes in the digraph.
838 typedef typename Base::Digraph::Node Node;
840 /// Pointer to the underlying digraph.
842 ///Pointer to the map of reached nodes.
844 ///Pointer to the map of processed nodes.
846 ///Pointer to the map of predecessors arcs.
848 ///Pointer to the map of distances.
850 ///Pointer to the source node.
856 /// This constructor does not require parameters, therefore it initiates
857 /// all of the attributes to default values (0, INVALID).
858 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
859 _dist(0), _source(INVALID) {}
863 /// This constructor requires some parameters,
864 /// listed in the parameters list.
865 /// Others are initiated to 0.
866 /// \param g is the initial value of \ref _g
867 /// \param s is the initial value of \ref _source
868 DfsWizardBase(const GR &g, Node s=INVALID) :
869 _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
870 _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
874 /// A class to make the usage of the Dfs algorithm easier
876 /// This class is created to make it easier to use the Dfs algorithm.
877 /// It uses the functions and features of the plain \ref Dfs,
878 /// but it is much simpler to use it.
880 /// Simplicity means that the way to change the types defined
881 /// in the traits class is based on functions that returns the new class
882 /// and not on templatable built-in classes.
883 /// When using the plain \ref Dfs
884 /// the new class with the modified type comes from
885 /// the original class by using the ::
886 /// operator. In the case of \ref DfsWizard only
887 /// a function have to be called and it will
888 /// return the needed class.
890 /// It does not have own \ref run method. When its \ref run method is called
891 /// it initiates a plain \ref Dfs object, and calls the \ref Dfs::run
894 class DfsWizard : public TR
898 ///The type of the underlying digraph.
899 typedef typename TR::Digraph Digraph;
901 typedef typename Digraph::Node Node;
903 typedef typename Digraph::NodeIt NodeIt;
905 typedef typename Digraph::Arc Arc;
907 typedef typename Digraph::OutArcIt OutArcIt;
909 ///\brief The type of the map that stores
911 typedef typename TR::ReachedMap ReachedMap;
912 ///\brief The type of the map that stores
913 ///the processed nodes
914 typedef typename TR::ProcessedMap ProcessedMap;
915 ///\brief The type of the map that stores the last
916 ///arcs of the %DFS paths.
917 typedef typename TR::PredMap PredMap;
918 ///The type of the map that stores the distances of the nodes.
919 typedef typename TR::DistMap DistMap;
923 DfsWizard() : TR() {}
925 /// Constructor that requires parameters.
927 /// Constructor that requires parameters.
928 /// These parameters will be the default values for the traits class.
929 DfsWizard(const Digraph &g, Node s=INVALID) :
933 DfsWizard(const TR &b) : TR(b) {}
937 ///Runs Dfs algorithm from a given node.
939 ///Runs Dfs algorithm from a given node.
940 ///The node can be given by the \ref source function.
943 if(Base::_source==INVALID) throw UninitializedParameter();
944 Dfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
946 alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
948 alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
950 alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
952 alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
953 alg.run(Base::_source);
956 ///Runs Dfs algorithm from the given node.
958 ///Runs Dfs algorithm from the given node.
959 ///\param s is the given source.
967 struct DefPredMapBase : public Base {
969 static PredMap *createPredMap(const Digraph &) { return 0; };
970 DefPredMapBase(const TR &b) : TR(b) {}
973 ///\brief \ref named-templ-param "Named parameter"
974 ///function for setting PredMap type
976 /// \ref named-templ-param "Named parameter"
977 ///function for setting PredMap type
980 DfsWizard<DefPredMapBase<T> > predMap(const T &t)
982 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
983 return DfsWizard<DefPredMapBase<T> >(*this);
988 struct DefReachedMapBase : public Base {
989 typedef T ReachedMap;
990 static ReachedMap *createReachedMap(const Digraph &) { return 0; };
991 DefReachedMapBase(const TR &b) : TR(b) {}
994 ///\brief \ref named-templ-param "Named parameter"
995 ///function for setting ReachedMap
997 /// \ref named-templ-param "Named parameter"
998 ///function for setting ReachedMap
1001 DfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
1003 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
1004 return DfsWizard<DefReachedMapBase<T> >(*this);
1009 struct DefProcessedMapBase : public Base {
1010 typedef T ProcessedMap;
1011 static ProcessedMap *createProcessedMap(const Digraph &) { return 0; };
1012 DefProcessedMapBase(const TR &b) : TR(b) {}
1015 ///\brief \ref named-templ-param "Named parameter"
1016 ///function for setting ProcessedMap
1018 /// \ref named-templ-param "Named parameter"
1019 ///function for setting ProcessedMap
1022 DfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
1024 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
1025 return DfsWizard<DefProcessedMapBase<T> >(*this);
1029 struct DefDistMapBase : public Base {
1031 static DistMap *createDistMap(const Digraph &) { return 0; };
1032 DefDistMapBase(const TR &b) : TR(b) {}
1035 ///\brief \ref named-templ-param "Named parameter"
1036 ///function for setting DistMap type
1038 /// \ref named-templ-param "Named parameter"
1039 ///function for setting DistMap type
1042 DfsWizard<DefDistMapBase<T> > distMap(const T &t)
1044 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
1045 return DfsWizard<DefDistMapBase<T> >(*this);
1048 /// Sets the source node, from which the Dfs algorithm runs.
1050 /// Sets the source node, from which the Dfs algorithm runs.
1051 /// \param s is the source node.
1052 DfsWizard<TR> &source(Node s)
1060 ///Function type interface for Dfs algorithm.
1063 ///Function type interface for Dfs algorithm.
1065 ///This function also has several
1066 ///\ref named-templ-func-param "named parameters",
1067 ///they are declared as the members of class \ref DfsWizard.
1069 ///example shows how to use these parameters.
1071 /// dfs(g,source).predMap(preds).run();
1073 ///\warning Don't forget to put the \ref DfsWizard::run() "run()"
1074 ///to the end of the parameter list.
1078 DfsWizard<DfsWizardBase<GR> >
1079 dfs(const GR &g,typename GR::Node s=INVALID)
1081 return DfsWizard<DfsWizardBase<GR> >(g,s);
1085 /// \brief Visitor class for dfs.
1087 /// It gives a simple interface for a functional interface for dfs
1088 /// traversal. The traversal on a linear data structure.
1089 template <typename _Digraph>
1091 typedef _Digraph Digraph;
1092 typedef typename Digraph::Arc Arc;
1093 typedef typename Digraph::Node Node;
1094 /// \brief Called when the arc reach a node.
1096 /// It is called when the dfs find an arc which target is not
1098 void discover(const Arc& arc) {}
1099 /// \brief Called when the node reached first time.
1101 /// It is Called when the node reached first time.
1102 void reach(const Node& node) {}
1103 /// \brief Called when we step back on an arc.
1105 /// It is called when the dfs should step back on the arc.
1106 void backtrack(const Arc& arc) {}
1107 /// \brief Called when we step back from the node.
1109 /// It is called when we step back from the node.
1110 void leave(const Node& node) {}
1111 /// \brief Called when the arc examined but target of the arc
1112 /// already discovered.
1114 /// It called when the arc examined but the target of the arc
1115 /// already discovered.
1116 void examine(const Arc& arc) {}
1117 /// \brief Called for the source node of the dfs.
1119 /// It is called for the source node of the dfs.
1120 void start(const Node& node) {}
1121 /// \brief Called when we leave the source node of the dfs.
1123 /// It is called when we leave the source node of the dfs.
1124 void stop(const Node& node) {}
1128 template <typename _Digraph>
1130 typedef _Digraph Digraph;
1131 typedef typename Digraph::Arc Arc;
1132 typedef typename Digraph::Node Node;
1133 void discover(const Arc&) {}
1134 void reach(const Node&) {}
1135 void backtrack(const Arc&) {}
1136 void leave(const Node&) {}
1137 void examine(const Arc&) {}
1138 void start(const Node&) {}
1139 void stop(const Node&) {}
1141 template <typename _Visitor>
1142 struct Constraints {
1143 void constraints() {
1146 visitor.discover(arc);
1147 visitor.reach(node);
1148 visitor.backtrack(arc);
1149 visitor.leave(node);
1150 visitor.examine(arc);
1151 visitor.start(node);
1159 /// \brief Default traits class of DfsVisit class.
1161 /// Default traits class of DfsVisit class.
1162 /// \tparam _Digraph Digraph type.
1163 template<class _Digraph>
1164 struct DfsVisitDefaultTraits {
1166 /// \brief The digraph type the algorithm runs on.
1167 typedef _Digraph Digraph;
1169 /// \brief The type of the map that indicates which nodes are reached.
1171 /// The type of the map that indicates which nodes are reached.
1172 /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
1173 /// \todo named parameter to set this type, function to read and write.
1174 typedef typename Digraph::template NodeMap<bool> ReachedMap;
1176 /// \brief Instantiates a ReachedMap.
1178 /// This function instantiates a \ref ReachedMap.
1179 /// \param digraph is the digraph, to which
1180 /// we would like to define the \ref ReachedMap.
1181 static ReachedMap *createReachedMap(const Digraph &digraph) {
1182 return new ReachedMap(digraph);
1187 /// %DFS Visit algorithm class.
1190 /// This class provides an efficient implementation of the %DFS algorithm
1191 /// with visitor interface.
1193 /// The %DfsVisit class provides an alternative interface to the Dfs
1194 /// class. It works with callback mechanism, the DfsVisit object calls
1195 /// on every dfs event the \c Visitor class member functions.
1197 /// \tparam _Digraph The digraph type the algorithm runs on.
1198 /// The default value is
1199 /// \ref ListDigraph. The value of _Digraph is not used directly by Dfs, it
1200 /// is only passed to \ref DfsDefaultTraits.
1201 /// \tparam _Visitor The Visitor object for the algorithm. The
1202 /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty Visitor which
1203 /// does not observe the Dfs events. If you want to observe the dfs
1204 /// events you should implement your own Visitor class.
1205 /// \tparam _Traits Traits class to set various data types used by the
1206 /// algorithm. The default traits class is
1207 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>".
1208 /// See \ref DfsVisitDefaultTraits for the documentation of
1209 /// a Dfs visit traits class.
1211 /// \author Jacint Szabo, Alpar Juttner and Balazs Dezso
1213 template <typename _Digraph, typename _Visitor, typename _Traits>
1215 template <typename _Digraph = ListDigraph,
1216 typename _Visitor = DfsVisitor<_Digraph>,
1217 typename _Traits = DfsDefaultTraits<_Digraph> >
1222 /// \brief \ref Exception for uninitialized parameters.
1224 /// This error represents problems in the initialization
1225 /// of the parameters of the algorithms.
1226 class UninitializedParameter : public lemon::UninitializedParameter {
1228 virtual const char* what() const throw()
1230 return "lemon::DfsVisit::UninitializedParameter";
1234 typedef _Traits Traits;
1236 typedef typename Traits::Digraph Digraph;
1238 typedef _Visitor Visitor;
1240 ///The type of the map indicating which nodes are reached.
1241 typedef typename Traits::ReachedMap ReachedMap;
1245 typedef typename Digraph::Node Node;
1246 typedef typename Digraph::NodeIt NodeIt;
1247 typedef typename Digraph::Arc Arc;
1248 typedef typename Digraph::OutArcIt OutArcIt;
1250 /// Pointer to the underlying digraph.
1251 const Digraph *_digraph;
1252 /// Pointer to the visitor object.
1254 ///Pointer to the map of reached status of the nodes.
1255 ReachedMap *_reached;
1256 ///Indicates if \ref _reached is locally allocated (\c true) or not.
1259 std::vector<typename Digraph::Arc> _stack;
1262 /// \brief Creates the maps if necessary.
1264 /// Creates the maps if necessary.
1265 void create_maps() {
1267 local_reached = true;
1268 _reached = Traits::createReachedMap(*_digraph);
1278 typedef DfsVisit Create;
1280 /// \name Named template parameters
1284 struct DefReachedMapTraits : public Traits {
1285 typedef T ReachedMap;
1286 static ReachedMap *createReachedMap(const Digraph &digraph) {
1287 throw UninitializedParameter();
1290 /// \brief \ref named-templ-param "Named parameter" for setting
1293 /// \ref named-templ-param "Named parameter" for setting ReachedMap type
1295 struct DefReachedMap : public DfsVisit< Digraph, Visitor,
1296 DefReachedMapTraits<T> > {
1297 typedef DfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
1303 /// \brief Constructor.
1307 /// \param digraph the digraph the algorithm will run on.
1308 /// \param visitor The visitor of the algorithm.
1310 DfsVisit(const Digraph& digraph, Visitor& visitor)
1311 : _digraph(&digraph), _visitor(&visitor),
1312 _reached(0), local_reached(false) {}
1314 /// \brief Destructor.
1318 if(local_reached) delete _reached;
1321 /// \brief Sets the map indicating if a node is reached.
1323 /// Sets the map indicating if a node is reached.
1324 /// If you don't use this function before calling \ref run(),
1325 /// it will allocate one. The destuctor deallocates this
1326 /// automatically allocated map, of course.
1327 /// \return <tt> (*this) </tt>
1328 DfsVisit &reachedMap(ReachedMap &m) {
1331 local_reached=false;
1338 /// \name Execution control
1339 /// The simplest way to execute the algorithm is to use
1340 /// one of the member functions called \c run(...).
1342 /// If you need more control on the execution,
1343 /// first you must call \ref init(), then you can adda source node
1344 /// with \ref addSource().
1345 /// Finally \ref start() will perform the actual path
1349 /// \brief Initializes the internal data structures.
1351 /// Initializes the internal data structures.
1355 _stack.resize(countNodes(*_digraph));
1357 for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
1358 _reached->set(u, false);
1362 /// \brief Adds a new source node.
1364 /// Adds a new source node to the set of nodes to be processed.
1365 void addSource(Node s) {
1366 if(!(*_reached)[s]) {
1367 _reached->set(s,true);
1371 _digraph->firstOut(e, s);
1373 _stack[++_stack_head] = e;
1380 /// \brief Processes the next arc.
1382 /// Processes the next arc.
1384 /// \return The processed arc.
1386 /// \pre The stack must not be empty!
1387 Arc processNextArc() {
1388 Arc e = _stack[_stack_head];
1389 Node m = _digraph->target(e);
1390 if(!(*_reached)[m]) {
1391 _visitor->discover(e);
1393 _reached->set(m, true);
1394 _digraph->firstOut(_stack[++_stack_head], m);
1396 _visitor->examine(e);
1397 m = _digraph->source(e);
1398 _digraph->nextOut(_stack[_stack_head]);
1400 while (_stack_head>=0 && _stack[_stack_head] == INVALID) {
1403 if (_stack_head >= 0) {
1404 _visitor->backtrack(_stack[_stack_head]);
1405 m = _digraph->source(_stack[_stack_head]);
1406 _digraph->nextOut(_stack[_stack_head]);
1414 /// \brief Next arc to be processed.
1416 /// Next arc to be processed.
1418 /// \return The next arc to be processed or INVALID if the stack is
1421 return _stack_head >= 0 ? _stack[_stack_head] : INVALID;
1424 /// \brief Returns \c false if there are nodes
1425 /// to be processed in the queue
1427 /// Returns \c false if there are nodes
1428 /// to be processed in the queue
1429 bool emptyQueue() { return _stack_head < 0; }
1431 /// \brief Returns the number of the nodes to be processed.
1433 /// Returns the number of the nodes to be processed in the queue.
1434 int queueSize() { return _stack_head + 1; }
1436 /// \brief Executes the algorithm.
1438 /// Executes the algorithm.
1440 /// \pre init() must be called and at least one node should be added
1441 /// with addSource() before using this function.
1443 while ( !emptyQueue() ) processNextArc();
1446 /// \brief Executes the algorithm until \c dest is reached.
1448 /// Executes the algorithm until \c dest is reached.
1450 /// \pre init() must be called and at least one node should be added
1451 /// with addSource() before using this function.
1452 void start(Node dest) {
1453 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != dest )
1457 /// \brief Executes the algorithm until a condition is met.
1459 /// Executes the algorithm until a condition is met.
1461 /// \pre init() must be called and at least one node should be added
1462 /// with addSource() before using this function.
1464 /// \param em must be a bool (or convertible) arc map. The algorithm
1465 /// will stop when it reaches an arc \c e with <tt>em[e]</tt> true.
1467 ///\return The reached arc \c e with <tt>em[e]</tt> true or
1468 ///\c INVALID if no such arc was found.
1470 /// \warning Contrary to \ref Bfs and \ref Dijkstra, \c em is an arc map,
1472 template <typename EM>
1473 Arc start(const EM &em) {
1474 while ( !emptyQueue() && !em[_stack[_stack_head]] )
1476 return emptyQueue() ? INVALID : _stack[_stack_head];
1479 /// \brief Runs %DFSVisit algorithm from node \c s.
1481 /// This method runs the %DFS algorithm from a root node \c s.
1482 /// \note d.run(s) is just a shortcut of the following code.
1494 /// \brief Runs %DFSVisit algorithm to visit all nodes in the digraph.
1496 /// This method runs the %DFS algorithm in order to
1497 /// compute the %DFS path to each node. The algorithm computes
1498 /// - The %DFS tree.
1499 /// - The distance of each node from the root in the %DFS tree.
1501 ///\note d.run() is just a shortcut of the following code.
1504 /// for (NodeIt it(digraph); it != INVALID; ++it) {
1505 /// if (!d.reached(it)) {
1506 /// d.addSource(it);
1513 for (NodeIt it(*_digraph); it != INVALID; ++it) {
1522 /// \name Query Functions
1523 /// The result of the %DFS algorithm can be obtained using these
1525 /// Before the use of these functions,
1526 /// either run() or start() must be called.
1528 /// \brief Checks if a node is reachable from the root.
1530 /// Returns \c true if \c v is reachable from the root(s).
1531 /// \warning The source nodes are inditated as unreachable.
1532 /// \pre Either \ref run() or \ref start()
1533 /// must be called before using this function.
1535 bool reached(Node v) { return (*_reached)[v]; }
1540 } //END OF NAMESPACE LEMON