lemon-main: comparison lemon/dfs.h

equal deleted inserted replaced

-:e43c2bec5a78
+:df6a2babf106
 ///There is also a \ref dfs() "function-type interface" for the DFS
 ///algorithm, which is convenient in the simplier cases and it can be
 ///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
+///The default type is \ref ListDigraph.
-///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<GR>".
-///See \ref DfsDefaultTraits for the documentation of
-///a Dfs traits class.
 #ifdef DOXYGEN
 template <typename GR,
 typename TR>
 #else
 template <typename GR=ListDigraph,
 ///The type of the map that indicates which nodes are processed.
 typedef typename TR::ProcessedMap ProcessedMap;
 ///The type of the paths.
 typedef PredMapPath<Digraph, PredMap> Path;
-///The traits class.
+///The \ref DfsDefaultTraits "traits class" of the algorithm.
 typedef TR Traits;
 private:
 typedef typename Digraph::Node Node;
 ///\brief \ref named-templ-param "Named parameter" for setting
 ///PredMap type.
 ///
 ///\ref named-templ-param "Named parameter" for setting
 ///PredMap type.
+///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 template <class T>
 struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > {
 typedef Dfs<Digraph, SetPredMapTraits<T> > Create;
 };
 ///\brief \ref named-templ-param "Named parameter" for setting
 ///DistMap type.
 ///
 ///\ref named-templ-param "Named parameter" for setting
 ///DistMap type.
+///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 template <class T>
 struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > {
 typedef Dfs<Digraph, SetDistMapTraits<T> > Create;
 };
 ///\brief \ref named-templ-param "Named parameter" for setting
 ///ReachedMap type.
 ///
 ///\ref named-templ-param "Named parameter" for setting
 ///ReachedMap type.
+///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 template <class T>
 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > {
 typedef Dfs< Digraph, SetReachedMapTraits<T> > Create;
 };
 ///\brief \ref named-templ-param "Named parameter" for setting
 ///ProcessedMap type.
 ///
 ///\ref named-templ-param "Named parameter" for setting
 ///ProcessedMap type.
+///It must meet the \ref concepts::WriteMap "WriteMap" concept.
 template <class T>
 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
 typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
 };
 }
 ///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(),
+///If you don't use this function before calling \ref run(Node) "run()"
-///it will allocate one. The destructor deallocates this
+///or \ref init(), an instance will be allocated automatically.
-///automatically allocated map, of course.
+///The destructor deallocates this automatically allocated map,
+///of course.
 ///\return <tt> (*this) </tt>
 Dfs &predMap(PredMap &m)
 {
 if(local_pred) {
 delete _pred;
 }
 ///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(),
+///If you don't use this function before calling \ref run(Node) "run()"
-///it will allocate one. The destructor deallocates this
+///or \ref init(), an instance will be allocated automatically.
-///automatically allocated map, of course.
+///The destructor deallocates this automatically allocated map,
+///of course.
 ///\return <tt> (*this) </tt>
 Dfs &reachedMap(ReachedMap &m)
 {
 if(local_reached) {
 delete _reached;
 }
 ///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(),
+///If you don't use this function before calling \ref run(Node) "run()"
-///it will allocate one. The destructor deallocates this
+///or \ref init(), an instance will be allocated automatically.
-///automatically allocated map, of course.
+///The destructor deallocates this automatically allocated map,
+///of course.
 ///\return <tt> (*this) </tt>
 Dfs &processedMap(ProcessedMap &m)
 {
 if(local_processed) {
 delete _processed;
 ///Sets the map that stores the distances of the nodes.
 ///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(),
+///If you don't use this function before calling \ref run(Node) "run()"
-///it will allocate one. The destructor deallocates this
+///or \ref init(), an instance will be allocated automatically.
-///automatically allocated map, of course.
+///The destructor deallocates this automatically allocated map,
+///of course.
 ///\return <tt> (*this) </tt>
 Dfs &distMap(DistMap &m)
 {
 if(local_dist) {
 delete _dist;
 return *this;
 }
 public:
-///\name Execution control
+///\name Execution Control
-///The simplest way to execute the algorithm is to use
+///The simplest way to execute the DFS algorithm is to use one of the
-///one of the member functions called \ref lemon::Dfs::run() "run()".
+///member functions called \ref run(Node) "run()".\n
-///\n
+///If you need more control on the execution, first you have to call
-///If you need more control on the execution, first you must call
+///\ref init(), then you can add a source node with \ref addSource()
-///\ref lemon::Dfs::init() "init()", then you can add a source node
+///and perform the actual computation with \ref start().
-///with \ref lemon::Dfs::addSource() "addSource()".
+///This procedure can be repeated if there are nodes that have not
-///Finally \ref lemon::Dfs::start() "start()" will perform the
+///been reached.
-///actual path computation.
 ///@{
+///\brief Initializes the internal data structures.
+///
 ///Initializes the internal data structures.
-///Initializes the internal data structures.
-///
 void init()
 {
 create_maps();
 _stack.resize(countNodes(*G));
 _stack_head=-1;
 ///Adds a new source node.
 ///Adds a new source node to the set of nodes to be processed.
 ///
-///\pre The stack must be empty. (Otherwise the algorithm gives
+///\pre The stack must be empty. Otherwise the algorithm gives
-///false results.)
+///wrong results. (One of the outgoing arcs of all the source nodes
-///
+///except for the last one will not be visited and distances will
-///\warning Distances will be wrong (or at least strange) in case of
+///also be wrong.)
-///multiple sources.
 void addSource(Node s)
 {
 LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
 if(!(*_reached)[s])
 {
 OutArcIt nextArc() const
 {
 return _stack_head>=0?_stack[_stack_head]:INVALID;
 }
-///\brief Returns \c false if there are nodes
+///Returns \c false if there are nodes to be processed.
-///to be processed.
-///
+///Returns \c false if there are nodes to be processed
-///Returns \c false if there are nodes
+///in the queue (stack).
-///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.
 ///Executes the algorithm.
 ///This method runs the %DFS algorithm in order to compute the
 ///%DFS path to each node.
 ///
 ///The algorithm computes
-///- the %DFS tree,
+///- the %DFS tree (forest),
-///- the distance of each node from the root in the %DFS tree.
+///- the distance of each node from the root(s) in the %DFS tree.
 ///
 ///\note <tt>d.run()</tt> is just a shortcut of the following code.
 ///\code
 ///  d.init();
 ///  for (NodeIt n(digraph); n != INVALID; ++n) {
 }
 ///@}
 ///\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()
+///Either \ref run(Node) "run()" or \ref start() should be called
-///"start()" must be called before using them.
+///before using them.
 ///@{
 ///The DFS path to a node.
 ///Returns the DFS path to a node.
 ///
-///\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
+///\pre Either \ref run(Node) "run()" or \ref init()
-///using this function.
+///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 a node from the root(s).
-///Returns the distance of a node from the root.
+///Returns the distance of a 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
+///\pre Either \ref run(Node) "run()" or \ref init()
-///using this function.
+///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.
 ///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
+///node \c v, i.e. it returns the last arc of a %DFS path from a
-///root to \c v. It is \c INVALID
+///root to \c v. It is \c INVALID if \c v is not reached from the
-///if \c v is not reachable from the root(s) or if \c v is a root.
+///root(s) or if \c v is a root.
 ///
 ///The %DFS tree used here is equal to the %DFS tree used in
 ///\ref predNode().
 ///
-///\pre Either \ref run() or \ref start() must be called before using
+///\pre Either \ref run(Node) "run()" or \ref init()
-///this function.
+///must be called before using this function.
 Arc predArc(Node v) const { return (*_pred)[v];}
 ///Returns the 'previous node' of the %DFS tree.
 ///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
+///from a %DFS path from a 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.
+///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().
 ///
-///\pre Either \ref run() or \ref start() must be called before
+///\pre Either \ref run(Node) "run()" or \ref init()
-///using this function.
+///must be called before using this function.
 Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
 G->source((*_pred)[v]); }
 ///\brief Returns a const reference to the node map that stores the
 ///distances of the nodes.
 ///
 ///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;}
 ///\brief Returns a const reference to the node map that stores the
 ///predecessor arcs.
 ///
 ///Returns a const reference to the node map that stores the predecessor
 ///arcs, which form the DFS tree.
 ///
-///\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 a node is reached from the root(s).
-///Returns \c true if \c v is reachable from the root(s).
+///Returns \c true if \c v is reached from the root(s).
-///\pre Either \ref run() or \ref start()
+///
+///\pre Either \ref run(Node) "run()" or \ref init()
 ///must be called before using this function.
 bool reached(Node v) const { return (*_reached)[v]; }
 ///@}
 };
 /// Auxiliary class for the function-type interface of DFS algorithm.
 /// 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
+/// It does not have own \ref run(Node) "run()" method, it uses the
-/// and features of the plain \ref Dfs.
+/// 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.
 template<class TR>
 class DfsWizard : public TR
 ///  dfs(g).predMap(preds).distMap(dists).run(s);
 ///
 ///  // 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(Node) "run()"
-///\warning Don't forget to put the \ref DfsWizard::run() "run()"
 ///to the end of the parameter list.
 ///\sa DfsWizard
 ///\sa Dfs
 template<class GR>
 DfsWizard<DfsWizardBase<GR> >
 public:
 typedef DfsVisit Create;
-/// \name Named template parameters
+/// \name Named Template Parameters
 ///@{
 template <class T>
 struct SetReachedMapTraits : public Traits {
 typedef T ReachedMap;
 }
 /// \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(),
+/// If you don't use this function before calling \ref run(Node) "run()"
-/// it will allocate one. The destructor deallocates this
+/// or \ref init(), an instance will be allocated automatically.
-/// automatically allocated map, of course.
+/// The destructor deallocates this automatically allocated map,
+/// of course.
 /// \return <tt> (*this) </tt>
 DfsVisit &reachedMap(ReachedMap &m) {
 if(local_reached) {
 delete _reached;
 local_reached=false;
 return *this;
 }
 public:
-/// \name Execution control
+/// \name Execution Control
-/// The simplest way to execute the algorithm is to use
+/// The simplest way to execute the DFS algorithm is to use one of the
-/// one of the member functions called \ref lemon::DfsVisit::run()
+/// member functions called \ref run(Node) "run()".\n
-/// "run()".
+/// If you need more control on the execution, first you have to call
-/// \n
+/// \ref init(), then you can add a source node with \ref addSource()
-/// If you need more control on the execution, first you must call
+/// and perform the actual computation with \ref start().
-/// \ref lemon::DfsVisit::init() "init()", then you can add several
+/// This procedure can be repeated if there are nodes that have not
-/// source nodes with \ref lemon::DfsVisit::addSource() "addSource()".
+/// been reached.
-/// Finally \ref lemon::DfsVisit::start() "start()" will perform the
-/// actual path computation.
 /// @{
 /// \brief Initializes the internal data structures.
 ///
 for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
 _reached->set(u, false);
 }
 }
-///Adds a new source node.
+/// \brief Adds a new source node.
+///
-///Adds a new source node to the set of nodes to be processed.
+/// Adds a new source node to the set of nodes to be processed.
 ///
-///\pre The stack must be empty. (Otherwise the algorithm gives
+/// \pre The stack must be empty. Otherwise the algorithm gives
-///false results.)
+/// wrong results. (One of the outgoing arcs of all the source nodes
-///
+/// except for the last one will not be visited and distances will
-///\warning Distances will be wrong (or at least strange) in case of
+/// also be wrong.)
-///multiple sources.
 void addSource(Node s)
 {
 LEMON_DEBUG(emptyQueue(), "The stack is not empty.");
 if(!(*_reached)[s]) {
 _reached->set(s,true);
 /// This method runs the %DFS algorithm in order to
 /// compute the %DFS path to each node.
 ///
 /// The algorithm computes
-/// - the %DFS tree,
+/// - the %DFS tree (forest),
-/// - the distance of each node from the root in the %DFS tree.
+/// - the distance of each node from the root(s) in the %DFS tree.
 ///
 /// \note <tt>d.run()</tt> is just a shortcut of the following code.
 ///\code
 ///   d.init();
 ///   for (NodeIt n(digraph); n != INVALID; ++n) {
 }
 ///@}
 /// \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
+/// Either \ref run(Node) "run()" or \ref start() should be called
-/// \ref lemon::DfsVisit::start() "start()" must be called before
+/// before using them.
-/// using them.
 ///@{
-/// \brief Checks if a node is reachable from the root(s).
+/// \brief Checks if a node is reached from the root(s).
 ///
-/// Returns \c true if \c v is reachable from the root(s).
+/// Returns \c true if \c v is reached from the root(s).
-/// \pre Either \ref run() or \ref start()
+///
+/// \pre Either \ref run(Node) "run()" or \ref init()
 /// must be called before using this function.
 bool reached(Node v) { return (*_reached)[v]; }
 ///@}

changeset 451	fbd6e04acf44
parent 319	5e12d7734036
child 419	9afe81e4c543
child 420	6a2a33ad261b