diff -r c6acc34f98dc -r 1a7fe3bef514 lemon/dfs.h --- a/lemon/dfs.h Fri Oct 16 10:21:37 2009 +0200 +++ b/lemon/dfs.h Thu Nov 05 15:50:01 2009 +0100 @@ -2,7 +2,7 @@ * * This file is a part of LEMON, a generic C++ optimization library. * - * Copyright (C) 2003-2008 + * Copyright (C) 2003-2009 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * @@ -47,13 +47,13 @@ /// ///The type of the map that stores the predecessor ///arcs of the %DFS paths. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap PredMap; - ///Instantiates a PredMap. + ///Instantiates a \c PredMap. - ///This function instantiates a PredMap. + ///This function instantiates a \ref PredMap. ///\param g is the digraph, to which we would like to define the - ///PredMap. + ///\ref PredMap. static PredMap *createPredMap(const Digraph &g) { return new PredMap(g); @@ -62,13 +62,14 @@ ///The type of the map that indicates which nodes are processed. ///The type of the map that indicates which nodes are processed. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. + ///By default it is a NullMap. typedef NullMap ProcessedMap; - ///Instantiates a ProcessedMap. + ///Instantiates a \c ProcessedMap. - ///This function instantiates a ProcessedMap. + ///This function instantiates a \ref ProcessedMap. ///\param g is the digraph, to which - ///we would like to define the ProcessedMap + ///we would like to define the \ref ProcessedMap. #ifdef DOXYGEN static ProcessedMap *createProcessedMap(const Digraph &g) #else @@ -81,13 +82,13 @@ ///The type of the map that indicates which nodes are reached. ///The type of the map that indicates which nodes are reached. - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; - ///Instantiates a ReachedMap. + ///Instantiates a \c ReachedMap. - ///This function instantiates a ReachedMap. + ///This function instantiates a \ref ReachedMap. ///\param g is the digraph, to which - ///we would like to define the ReachedMap. + ///we would like to define the \ref ReachedMap. static ReachedMap *createReachedMap(const Digraph &g) { return new ReachedMap(g); @@ -96,13 +97,13 @@ ///The type of the map that stores the distances of the nodes. ///The type of the map that stores the distances of the nodes. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap DistMap; - ///Instantiates a DistMap. + ///Instantiates a \c DistMap. - ///This function instantiates a DistMap. + ///This function instantiates a \ref DistMap. ///\param g is the digraph, to which we would like to define the - ///DistMap. + ///\ref DistMap. static DistMap *createDistMap(const Digraph &g) { return new DistMap(g); @@ -119,13 +120,7 @@ ///used easier. /// ///\tparam GR The type of the digraph the algorithm runs on. - ///The default value is \ref ListDigraph. The value of GR is not used - ///directly by \ref Dfs, it is only passed to \ref DfsDefaultTraits. - ///\tparam TR Traits class to set various data types used by the algorithm. - ///The default traits class is - ///\ref DfsDefaultTraits "DfsDefaultTraits". - ///See \ref DfsDefaultTraits for the documentation of - ///a Dfs traits class. + ///The default type is \ref ListDigraph. #ifdef DOXYGEN template @@ -151,7 +146,7 @@ ///The type of the paths. typedef PredMapPath Path; - ///The traits class. + ///The \ref DfsDefaultTraits "traits class" of the algorithm. typedef TR Traits; private: @@ -212,7 +207,7 @@ typedef Dfs Create; - ///\name Named template parameters + ///\name Named Template Parameters ///@{ @@ -226,10 +221,11 @@ } }; ///\brief \ref named-templ-param "Named parameter" for setting - ///PredMap type. + ///\c PredMap type. /// ///\ref named-templ-param "Named parameter" for setting - ///PredMap type. + ///\c PredMap type. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetPredMap : public Dfs > { typedef Dfs > Create; @@ -245,10 +241,11 @@ } }; ///\brief \ref named-templ-param "Named parameter" for setting - ///DistMap type. + ///\c DistMap type. /// ///\ref named-templ-param "Named parameter" for setting - ///DistMap type. + ///\c DistMap type. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetDistMap : public Dfs< Digraph, SetDistMapTraits > { typedef Dfs > Create; @@ -264,10 +261,11 @@ } }; ///\brief \ref named-templ-param "Named parameter" for setting - ///ReachedMap type. + ///\c ReachedMap type. /// ///\ref named-templ-param "Named parameter" for setting - ///ReachedMap type. + ///\c ReachedMap type. + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. template struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits > { typedef Dfs< Digraph, SetReachedMapTraits > Create; @@ -283,10 +281,11 @@ } }; ///\brief \ref named-templ-param "Named parameter" for setting - ///ProcessedMap type. + ///\c ProcessedMap type. /// ///\ref named-templ-param "Named parameter" for setting - ///ProcessedMap type. + ///\c ProcessedMap type. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. template struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits > { typedef Dfs< Digraph, SetProcessedMapTraits > Create; @@ -300,10 +299,10 @@ } }; ///\brief \ref named-templ-param "Named parameter" for setting - ///ProcessedMap type to be Digraph::NodeMap. + ///\c ProcessedMap type to be Digraph::NodeMap. /// ///\ref named-templ-param "Named parameter" for setting - ///ProcessedMap type to be Digraph::NodeMap. + ///\c ProcessedMap type to be Digraph::NodeMap. ///If you don't set it explicitly, it will be automatically allocated. struct SetStandardProcessedMap : public Dfs< Digraph, SetStandardProcessedMapTraits > { @@ -338,9 +337,10 @@ ///Sets the map that stores the predecessor arcs. ///Sets the map that stores the predecessor arcs. - ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destructor deallocates this - ///automatically allocated map, of course. + ///If you don't use this function before calling \ref run(Node) "run()" + ///or \ref init(), an instance will be allocated automatically. + ///The destructor deallocates this automatically allocated map, + ///of course. ///\return (*this) Dfs &predMap(PredMap &m) { @@ -355,9 +355,10 @@ ///Sets the map that indicates which nodes are reached. ///Sets the map that indicates which nodes are reached. - ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destructor deallocates this - ///automatically allocated map, of course. + ///If you don't use this function before calling \ref run(Node) "run()" + ///or \ref init(), an instance will be allocated automatically. + ///The destructor deallocates this automatically allocated map, + ///of course. ///\return (*this) Dfs &reachedMap(ReachedMap &m) { @@ -372,9 +373,10 @@ ///Sets the map that indicates which nodes are processed. ///Sets the map that indicates which nodes are processed. - ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destructor deallocates this - ///automatically allocated map, of course. + ///If you don't use this function before calling \ref run(Node) "run()" + ///or \ref init(), an instance will be allocated automatically. + ///The destructor deallocates this automatically allocated map, + ///of course. ///\return (*this) Dfs &processedMap(ProcessedMap &m) { @@ -390,9 +392,10 @@ ///Sets the map that stores the distances of the nodes calculated by ///the algorithm. - ///If you don't use this function before calling \ref run(), - ///it will allocate one. The destructor deallocates this - ///automatically allocated map, of course. + ///If you don't use this function before calling \ref run(Node) "run()" + ///or \ref init(), an instance will be allocated automatically. + ///The destructor deallocates this automatically allocated map, + ///of course. ///\return (*this) Dfs &distMap(DistMap &m) { @@ -406,22 +409,20 @@ public: - ///\name Execution control - ///The simplest way to execute the algorithm is to use - ///one of the member functions called \ref lemon::Dfs::run() "run()". - ///\n - ///If you need more control on the execution, first you must call - ///\ref lemon::Dfs::init() "init()", then you can add a source node - ///with \ref lemon::Dfs::addSource() "addSource()". - ///Finally \ref lemon::Dfs::start() "start()" will perform the - ///actual path computation. + ///\name Execution Control + ///The simplest way to execute the DFS algorithm is to use one of the + ///member functions called \ref run(Node) "run()".\n + ///If you need better control on the execution, you have to call + ///\ref init() first, then you can add a source node with \ref addSource() + ///and perform the actual computation with \ref start(). + ///This procedure can be repeated if there are nodes that have not + ///been reached. ///@{ + ///\brief Initializes the internal data structures. + /// ///Initializes the internal data structures. - - ///Initializes the internal data structures. - /// void init() { create_maps(); @@ -438,11 +439,10 @@ ///Adds a new source node to the set of nodes to be processed. /// - ///\pre The stack must be empty. (Otherwise the algorithm gives - ///false results.) - /// - ///\warning Distances will be wrong (or at least strange) in case of - ///multiple sources. + ///\pre The stack must be empty. Otherwise the algorithm gives + ///wrong results. (One of the outgoing arcs of all the source nodes + ///except for the last one will not be visited and distances will + ///also be wrong.) void addSource(Node s) { LEMON_DEBUG(emptyQueue(), "The stack is not empty."); @@ -506,16 +506,16 @@ return _stack_head>=0?_stack[_stack_head]:INVALID; } - ///\brief Returns \c false if there are nodes - ///to be processed. - /// - ///Returns \c false if there are nodes - ///to be processed in the queue (stack). + ///Returns \c false if there are nodes to be processed. + + ///Returns \c false if there are nodes to be processed + ///in the queue (stack). bool emptyQueue() const { return _stack_head<0; } ///Returns the number of the nodes to be processed. - ///Returns the number of the nodes to be processed in the queue (stack). + ///Returns the number of the nodes to be processed + ///in the queue (stack). int queueSize() const { return _stack_head+1; } ///Executes the algorithm. @@ -637,8 +637,8 @@ ///%DFS path to each node. /// ///The algorithm computes - ///- the %DFS tree, - ///- the distance of each node from the root in the %DFS tree. + ///- the %DFS tree (forest), + ///- the distance of each node from the root(s) in the %DFS tree. /// ///\note d.run() is just a shortcut of the following code. ///\code @@ -663,60 +663,60 @@ ///@} ///\name Query Functions - ///The result of the %DFS algorithm can be obtained using these + ///The results of the DFS algorithm can be obtained using these ///functions.\n - ///Either \ref lemon::Dfs::run() "run()" or \ref lemon::Dfs::start() - ///"start()" must be called before using them. + ///Either \ref run(Node) "run()" or \ref start() should be called + ///before using them. ///@{ - ///The DFS path to a node. + ///The DFS path to the given node. - ///Returns the DFS path to a node. + ///Returns the DFS path to the given node from the root(s). /// - ///\warning \c t should be reachable from the root. + ///\warning \c t should be reached from the root(s). /// - ///\pre Either \ref run() or \ref start() must be called before - ///using this function. + ///\pre Either \ref run(Node) "run()" or \ref init() + ///must be called before using this function. Path path(Node t) const { return Path(*G, *_pred, t); } - ///The distance of a node from the root. + ///The distance of the given node from the root(s). - ///Returns the distance of a node from the root. + ///Returns the distance of the given node from the root(s). /// - ///\warning If node \c v is not reachable from the root, then + ///\warning If node \c v is not reached from the root(s), then ///the return value of this function is undefined. /// - ///\pre Either \ref run() or \ref start() must be called before - ///using this function. + ///\pre Either \ref run(Node) "run()" or \ref init() + ///must be called before using this function. int dist(Node v) const { return (*_dist)[v]; } - ///Returns the 'previous arc' of the %DFS tree for a node. + ///Returns the 'previous arc' of the %DFS tree for the given node. ///This function returns the 'previous arc' of the %DFS tree for the - ///node \c v, i.e. it returns the last arc of a %DFS path from the - ///root to \c v. It is \c INVALID - ///if \c v is not reachable from the root(s) or if \c v is a root. + ///node \c v, i.e. it returns the last arc of a %DFS path from a + ///root to \c v. It is \c INVALID if \c v is not reached from the + ///root(s) or if \c v is a root. /// ///The %DFS tree used here is equal to the %DFS tree used in - ///\ref predNode(). + ///\ref predNode() and \ref predMap(). /// - ///\pre Either \ref run() or \ref start() must be called before using - ///this function. + ///\pre Either \ref run(Node) "run()" or \ref init() + ///must be called before using this function. Arc predArc(Node v) const { return (*_pred)[v];} - ///Returns the 'previous node' of the %DFS tree. + ///Returns the 'previous node' of the %DFS tree for the given node. ///This function returns the 'previous node' of the %DFS ///tree for the node \c v, i.e. it returns the last but one node - ///from a %DFS path from the root to \c v. It is \c INVALID - ///if \c v is not reachable from the root(s) or if \c v is a root. + ///of a %DFS path from a root to \c v. It is \c INVALID + ///if \c v is not reached from the root(s) or if \c v is a root. /// ///The %DFS tree used here is equal to the %DFS tree used in - ///\ref predArc(). + ///\ref predArc() and \ref predMap(). /// - ///\pre Either \ref run() or \ref start() must be called before - ///using this function. + ///\pre Either \ref run(Node) "run()" or \ref init() + ///must be called before using this function. Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID: G->source((*_pred)[v]); } @@ -726,7 +726,7 @@ ///Returns a const reference to the node map that stores the ///distances of the nodes calculated by the algorithm. /// - ///\pre Either \ref run() or \ref init() + ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. const DistMap &distMap() const { return *_dist;} @@ -734,16 +734,17 @@ ///predecessor arcs. /// ///Returns a const reference to the node map that stores the predecessor - ///arcs, which form the DFS tree. + ///arcs, which form the DFS tree (forest). /// - ///\pre Either \ref run() or \ref init() + ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. const PredMap &predMap() const { return *_pred;} - ///Checks if a node is reachable from the root(s). + ///Checks if the given node. node is reached from the root(s). - ///Returns \c true if \c v is reachable from the root(s). - ///\pre Either \ref run() or \ref start() + ///Returns \c true if \c v is reached from the root(s). + /// + ///\pre Either \ref run(Node) "run()" or \ref init() ///must be called before using this function. bool reached(Node v) const { return (*_reached)[v]; } @@ -765,7 +766,7 @@ /// ///The type of the map that stores the predecessor ///arcs of the %DFS paths. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap PredMap; ///Instantiates a PredMap. @@ -780,7 +781,7 @@ ///The type of the map that indicates which nodes are processed. ///The type of the map that indicates which nodes are processed. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. ///By default it is a NullMap. typedef NullMap ProcessedMap; ///Instantiates a ProcessedMap. @@ -800,7 +801,7 @@ ///The type of the map that indicates which nodes are reached. ///The type of the map that indicates which nodes are reached. - ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + ///It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; ///Instantiates a ReachedMap. @@ -815,7 +816,7 @@ ///The type of the map that stores the distances of the nodes. ///The type of the map that stores the distances of the nodes. - ///It must meet the \ref concepts::WriteMap "WriteMap" concept. + ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. typedef typename Digraph::template NodeMap DistMap; ///Instantiates a DistMap. @@ -830,18 +831,14 @@ ///The type of the DFS paths. ///The type of the DFS paths. - ///It must meet the \ref concepts::Path "Path" concept. + ///It must conform to the \ref concepts::Path "Path" concept. typedef lemon::Path Path; }; /// Default traits class used by DfsWizard - /// To make it easier to use Dfs algorithm - /// we have created a wizard class. - /// This \ref DfsWizard class needs default traits, - /// as well as the \ref Dfs class. - /// The \ref DfsWizardBase is a class to be the default traits of the - /// \ref DfsWizard class. + /// Default traits class used by DfsWizard. + /// \tparam GR The type of the digraph. template class DfsWizardBase : public DfsWizardDefaultTraits { @@ -869,7 +866,7 @@ public: /// Constructor. - /// This constructor does not require parameters, therefore it initiates + /// This constructor does not require parameters, it initiates /// all of the attributes to \c 0. DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), _dist(0), _path(0), _di(0) {} @@ -889,8 +886,8 @@ /// This auxiliary class is created to implement the /// \ref dfs() "function-type interface" of \ref Dfs algorithm. - /// It does not have own \ref run() method, it uses the functions - /// and features of the plain \ref Dfs. + /// It does not have own \ref run(Node) "run()" method, it uses the + /// functions and features of the plain \ref Dfs. /// /// This class should only be used through the \ref dfs() function, /// which makes it easier to use the algorithm. @@ -899,7 +896,6 @@ { typedef TR Base; - ///The type of the digraph the algorithm runs on. typedef typename TR::Digraph Digraph; typedef typename Digraph::Node Node; @@ -907,16 +903,10 @@ typedef typename Digraph::Arc Arc; typedef typename Digraph::OutArcIt OutArcIt; - ///\brief The type of the map that stores the predecessor - ///arcs of the DFS paths. typedef typename TR::PredMap PredMap; - ///\brief The type of the map that stores the distances of the nodes. typedef typename TR::DistMap DistMap; - ///\brief The type of the map that indicates which nodes are reached. typedef typename TR::ReachedMap ReachedMap; - ///\brief The type of the map that indicates which nodes are processed. typedef typename TR::ProcessedMap ProcessedMap; - ///The type of the DFS paths typedef typename TR::Path Path; public: @@ -999,11 +989,12 @@ static PredMap *createPredMap(const Digraph &) { return 0; }; SetPredMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting PredMap object. + + ///\brief \ref named-templ-param "Named parameter" for setting + ///the predecessor map. /// - ///\ref named-func-param "Named parameter" - ///for setting PredMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that stores the predecessor arcs of the nodes. template DfsWizard > predMap(const T &t) { @@ -1017,11 +1008,12 @@ static ReachedMap *createReachedMap(const Digraph &) { return 0; }; SetReachedMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting ReachedMap object. + + ///\brief \ref named-templ-param "Named parameter" for setting + ///the reached map. /// - /// \ref named-func-param "Named parameter" - ///for setting ReachedMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that indicates which nodes are reached. template DfsWizard > reachedMap(const T &t) { @@ -1035,11 +1027,13 @@ static DistMap *createDistMap(const Digraph &) { return 0; }; SetDistMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting DistMap object. + + ///\brief \ref named-templ-param "Named parameter" for setting + ///the distance map. /// - /// \ref named-func-param "Named parameter" - ///for setting DistMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that stores the distances of the nodes calculated + ///by the algorithm. template DfsWizard > distMap(const T &t) { @@ -1053,11 +1047,12 @@ static ProcessedMap *createProcessedMap(const Digraph &) { return 0; }; SetProcessedMapBase(const TR &b) : TR(b) {} }; - ///\brief \ref named-func-param "Named parameter" - ///for setting ProcessedMap object. + + ///\brief \ref named-func-param "Named parameter" for setting + ///the processed map. /// - /// \ref named-func-param "Named parameter" - ///for setting ProcessedMap object. + ///\ref named-templ-param "Named parameter" function for setting + ///the map that indicates which nodes are processed. template DfsWizard > processedMap(const T &t) { @@ -1110,8 +1105,7 @@ /// // Compute the DFS path from s to t /// bool reached = dfs(g).path(p).dist(d).run(s,t); ///\endcode - - ///\warning Don't forget to put the \ref DfsWizard::run() "run()" + ///\warning Don't forget to put the \ref DfsWizard::run(Node) "run()" ///to the end of the parameter list. ///\sa DfsWizard ///\sa Dfs @@ -1127,9 +1121,9 @@ /// /// This class defines the interface of the DfsVisit events, and /// it could be the base of a real visitor class. - template + template struct DfsVisitor { - typedef _Digraph Digraph; + typedef GR Digraph; typedef typename Digraph::Arc Arc; typedef typename Digraph::Node Node; /// \brief Called for the source node of the DFS. @@ -1165,9 +1159,9 @@ void backtrack(const Arc& arc) {} }; #else - template + template struct DfsVisitor { - typedef _Digraph Digraph; + typedef GR Digraph; typedef typename Digraph::Arc Arc; typedef typename Digraph::Node Node; void start(const Node&) {} @@ -1200,16 +1194,16 @@ /// /// Default traits class of DfsVisit class. /// \tparam _Digraph The type of the digraph the algorithm runs on. - template + template struct DfsVisitDefaultTraits { /// \brief The type of the digraph the algorithm runs on. - typedef _Digraph Digraph; + typedef GR Digraph; /// \brief The type of the map that indicates which nodes are reached. /// /// The type of the map that indicates which nodes are reached. - /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. + /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" concept. typedef typename Digraph::template NodeMap ReachedMap; /// \brief Instantiates a ReachedMap. @@ -1225,12 +1219,12 @@ /// \ingroup search /// - /// \brief %DFS algorithm class with visitor interface. + /// \brief DFS algorithm class with visitor interface. /// - /// This class provides an efficient implementation of the %DFS algorithm + /// This class provides an efficient implementation of the DFS algorithm /// with visitor interface. /// - /// The %DfsVisit class provides an alternative interface to the Dfs + /// The DfsVisit class provides an alternative interface to the Dfs /// class. It works with callback mechanism, the DfsVisit object calls /// the member functions of the \c Visitor class on every DFS event. /// @@ -1239,37 +1233,37 @@ /// events of the DFS algorithm. Otherwise consider to use Dfs or dfs() /// instead. /// - /// \tparam _Digraph The type of the digraph the algorithm runs on. - /// The default value is - /// \ref ListDigraph. The value of _Digraph is not used directly by - /// \ref DfsVisit, it is only passed to \ref DfsVisitDefaultTraits. - /// \tparam _Visitor The Visitor type that is used by the algorithm. - /// \ref DfsVisitor "DfsVisitor<_Digraph>" is an empty visitor, which + /// \tparam GR The type of the digraph the algorithm runs on. + /// The default type is \ref ListDigraph. + /// The value of GR is not used directly by \ref DfsVisit, + /// it is only passed to \ref DfsVisitDefaultTraits. + /// \tparam VS The Visitor type that is used by the algorithm. + /// \ref DfsVisitor "DfsVisitor" is an empty visitor, which /// does not observe the DFS events. If you want to observe the DFS /// events, you should implement your own visitor class. - /// \tparam _Traits Traits class to set various data types used by the + /// \tparam TR Traits class to set various data types used by the /// algorithm. The default traits class is - /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<_Digraph>". + /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits". /// See \ref DfsVisitDefaultTraits for the documentation of /// a DFS visit traits class. #ifdef DOXYGEN - template + template #else - template , - typename _Traits = DfsVisitDefaultTraits<_Digraph> > + template , + typename TR = DfsVisitDefaultTraits > #endif class DfsVisit { public: ///The traits class. - typedef _Traits Traits; + typedef TR Traits; ///The type of the digraph the algorithm runs on. typedef typename Traits::Digraph Digraph; ///The visitor type used by the algorithm. - typedef _Visitor Visitor; + typedef VS Visitor; ///The type of the map that indicates which nodes are reached. typedef typename Traits::ReachedMap ReachedMap; @@ -1309,7 +1303,7 @@ typedef DfsVisit Create; - /// \name Named template parameters + /// \name Named Template Parameters ///@{ template @@ -1351,9 +1345,10 @@ /// \brief Sets the map that indicates which nodes are reached. /// /// Sets the map that indicates which nodes are reached. - /// If you don't use this function before calling \ref run(), - /// it will allocate one. The destructor deallocates this - /// automatically allocated map, of course. + /// If you don't use this function before calling \ref run(Node) "run()" + /// or \ref init(), an instance will be allocated automatically. + /// The destructor deallocates this automatically allocated map, + /// of course. /// \return (*this) DfsVisit &reachedMap(ReachedMap &m) { if(local_reached) { @@ -1366,16 +1361,14 @@ public: - /// \name Execution control - /// The simplest way to execute the algorithm is to use - /// one of the member functions called \ref lemon::DfsVisit::run() - /// "run()". - /// \n - /// If you need more control on the execution, first you must call - /// \ref lemon::DfsVisit::init() "init()", then you can add several - /// source nodes with \ref lemon::DfsVisit::addSource() "addSource()". - /// Finally \ref lemon::DfsVisit::start() "start()" will perform the - /// actual path computation. + /// \name Execution Control + /// The simplest way to execute the DFS algorithm is to use one of the + /// member functions called \ref run(Node) "run()".\n + /// If you need better control on the execution, you have to call + /// \ref init() first, then you can add a source node with \ref addSource() + /// and perform the actual computation with \ref start(). + /// This procedure can be repeated if there are nodes that have not + /// been reached. /// @{ @@ -1391,15 +1384,14 @@ } } - ///Adds a new source node. - - ///Adds a new source node to the set of nodes to be processed. + /// \brief Adds a new source node. /// - ///\pre The stack must be empty. (Otherwise the algorithm gives - ///false results.) + /// Adds a new source node to the set of nodes to be processed. /// - ///\warning Distances will be wrong (or at least strange) in case of - ///multiple sources. + /// \pre The stack must be empty. Otherwise the algorithm gives + /// wrong results. (One of the outgoing arcs of all the source nodes + /// except for the last one will not be visited and distances will + /// also be wrong.) void addSource(Node s) { LEMON_DEBUG(emptyQueue(), "The stack is not empty."); @@ -1413,6 +1405,7 @@ _stack[++_stack_head] = e; } else { _visitor->leave(s); + _visitor->stop(s); } } } @@ -1589,8 +1582,8 @@ /// compute the %DFS path to each node. /// /// The algorithm computes - /// - the %DFS tree, - /// - the distance of each node from the root in the %DFS tree. + /// - the %DFS tree (forest), + /// - the distance of each node from the root(s) in the %DFS tree. /// /// \note d.run() is just a shortcut of the following code. ///\code @@ -1615,19 +1608,20 @@ ///@} /// \name Query Functions - /// The result of the %DFS algorithm can be obtained using these + /// The results of the DFS algorithm can be obtained using these /// functions.\n - /// Either \ref lemon::DfsVisit::run() "run()" or - /// \ref lemon::DfsVisit::start() "start()" must be called before - /// using them. + /// Either \ref run(Node) "run()" or \ref start() should be called + /// before using them. + ///@{ - /// \brief Checks if a node is reachable from the root(s). + /// \brief Checks if the given node is reached from the root(s). /// - /// Returns \c true if \c v is reachable from the root(s). - /// \pre Either \ref run() or \ref start() + /// Returns \c true if \c v is reached from the root(s). + /// + /// \pre Either \ref run(Node) "run()" or \ref init() /// must be called before using this function. - bool reached(Node v) { return (*_reached)[v]; } + bool reached(Node v) const { return (*_reached)[v]; } ///@}