lemon: comparison lemon/dfs.h

equal deleted inserted replaced

-:9cb5df99ef3d
+:3cea1518b40e
 /* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
-* Copyright (C) 2003-2009
+* Copyright (C) 2003-2010
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 ///\brief The type of the map that stores the predecessor
 ///arcs of the %DFS paths.
 ///
 ///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<typename Digraph::Arc> PredMap;
 ///Instantiates a \c PredMap.
 ///This function instantiates a \ref PredMap.
 ///\param g is the digraph, to which we would like to define the
 }
 ///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<typename Digraph::Node,bool> ProcessedMap;
 ///Instantiates a \c ProcessedMap.
 ///This function instantiates a \ref ProcessedMap.
 ///\param g is the digraph, to which
 }
 ///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<bool> ReachedMap;
 ///Instantiates a \c ReachedMap.
 ///This function instantiates a \ref ReachedMap.
 ///\param g is the digraph, to which
 }
 ///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<int> DistMap;
 ///Instantiates a \c DistMap.
 ///This function instantiates a \ref DistMap.
 ///\param g is the digraph, to which we would like to define the
 ///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 type is \ref ListDigraph.
+///\tparam TR The traits class that defines various types used by the
+///algorithm. By default, it is \ref DfsDefaultTraits
+///"DfsDefaultTraits<GR>".
+///In most cases, this parameter should not be set directly,
+///consider to use the named template parameters instead.
 #ifdef DOXYGEN
 template <typename GR,
 typename TR>
 #else
 template <typename GR=ListDigraph,
 ///\brief \ref named-templ-param "Named parameter" for setting
 ///\c PredMap type.
 ///
 ///\ref named-templ-param "Named parameter" for setting
 ///\c PredMap type.
-///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+///It must conform to 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
 ///\c DistMap type.
 ///
 ///\ref named-templ-param "Named parameter" for setting
 ///\c DistMap type.
-///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+///It must conform to 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
 ///\c ReachedMap type.
 ///
 ///\ref named-templ-param "Named parameter" for setting
 ///\c ReachedMap type.
-///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
+///It must conform to
+///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
 ///\c ProcessedMap type.
 ///
 ///\ref named-templ-param "Named parameter" for setting
 ///\c ProcessedMap type.
-///It must meet the \ref concepts::WriteMap "WriteMap" concept.
+///It must conform to the \ref concepts::WriteMap "WriteMap" concept.
 template <class T>
 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > {
 typedef Dfs< Digraph, SetProcessedMapTraits<T> > Create;
 };
 public:
 ///\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 more control on the execution, first you have to call
+///If you need better control on the execution, you have to call
-///\ref init(), then you can add a source node with \ref addSource()
+///\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.
 ///@{
 return reached(t);
 }
 ///Runs the algorithm to visit all nodes in the digraph.
-///This method runs the %DFS algorithm in order to compute the
+///This method runs the %DFS algorithm in order to visit all nodes
-///%DFS path to each node.
+///in the digraph.
-///
-///The algorithm computes
-///- the %DFS tree (forest),
-///- 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) {
 ///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 reached from the root(s).
 ///
 ///\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(s).
+///The distance of the given node from the root(s).
-///Returns the distance of a node from the root(s).
+///Returns the distance of the given node from the root(s).
 ///
 ///\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(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 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(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 a root to \c v. It is \c INVALID
+///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(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]); }
 ///\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.
+///arcs, which form the DFS tree (forest).
 ///
 ///\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 reached from the root(s).
+///Checks if the given node. node is reached from the root(s).
 ///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.
 ///\brief The type of the map that stores the predecessor
 ///arcs of the %DFS paths.
 ///
 ///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<typename Digraph::Arc> PredMap;
 ///Instantiates a PredMap.
 ///This function instantiates a PredMap.
 ///\param g is the digraph, to which we would like to define the
 }
 ///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.
+///By default, it is a NullMap.
 typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
 ///Instantiates a ProcessedMap.
 ///This function instantiates a ProcessedMap.
 ///\param g is the digraph, to which
 }
 ///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<bool> ReachedMap;
 ///Instantiates a ReachedMap.
 ///This function instantiates a ReachedMap.
 ///\param g is the digraph, to which
 }
 ///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<int> DistMap;
 ///Instantiates a DistMap.
 ///This function instantiates a DistMap.
 ///\param g is the digraph, to which we would like to define
 }
 ///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<Digraph> Path;
 };
 /// Default traits class used by DfsWizard
-/// To make it easier to use Dfs algorithm
+/// Default traits class used by DfsWizard.
-/// we have created a wizard class.
+/// \tparam GR The type of the digraph.
-/// 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.
 template<class GR>
 class DfsWizardBase : public DfsWizardDefaultTraits<GR>
 {
 typedef DfsWizardDefaultTraits<GR> Base;
 int *_di;
 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) {}
 /// Constructor.
 /// 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.
+///
+/// \tparam TR The traits class that defines various types used by the
+/// algorithm.
 template<class TR>
 class DfsWizard : public TR
 {
 typedef TR Base;
-///The type of the digraph the algorithm runs on.
 typedef typename TR::Digraph Digraph;
 typedef typename Digraph::Node Node;
 typedef typename Digraph::NodeIt NodeIt;
 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:
 /// Constructor.
 return alg.reached(t);
 }
 ///Runs DFS algorithm to visit all nodes in the digraph.
-///This method runs DFS algorithm in order to compute
+///This method runs DFS algorithm in order to visit all nodes
-///the DFS path to each node.
+///in the digraph.
 void run()
 {
 run(INVALID);
 }
 struct SetPredMapBase : public Base {
 typedef T PredMap;
 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<class T>
 DfsWizard<SetPredMapBase<T> > predMap(const T &t)
 {
 Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
 return DfsWizard<SetPredMapBase<T> >(*this);
 struct SetReachedMapBase : public Base {
 typedef T ReachedMap;
 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<class T>
 DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t)
 {
 Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
 return DfsWizard<SetReachedMapBase<T> >(*this);
 struct SetDistMapBase : public Base {
 typedef T DistMap;
 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<class T>
 DfsWizard<SetDistMapBase<T> > distMap(const T &t)
 {
 Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
 return DfsWizard<SetDistMapBase<T> >(*this);
 struct SetProcessedMapBase : public Base {
 typedef T ProcessedMap;
 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<class T>
 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t)
 {
 Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
 return DfsWizard<SetProcessedMapBase<T> >(*this);
 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<bool> ReachedMap;
 /// \brief Instantiates a ReachedMap.
 ///
 /// This function instantiates a ReachedMap.
 /// it is only passed to \ref DfsVisitDefaultTraits.
 /// \tparam VS The Visitor type that is used by the algorithm.
 /// \ref DfsVisitor "DfsVisitor<GR>" 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 TR Traits class to set various data types used by the
+/// \tparam TR The traits class that defines various types used by the
-/// algorithm. The default traits class is
+/// algorithm. By default, it is \ref DfsVisitDefaultTraits
-/// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>".
+/// "DfsVisitDefaultTraits<GR>".
-/// See \ref DfsVisitDefaultTraits for the documentation of
+/// In most cases, this parameter should not be set directly,
-/// a DFS visit traits class.
+/// consider to use the named template parameters instead.
 #ifdef DOXYGEN
 template <typename GR, typename VS, typename TR>
 #else
 template <typename GR = ListDigraph,
 typename VS = DfsVisitor<GR>,
 public:
 /// \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 more control on the execution, first you have to call
+/// If you need better control on the execution, you have to call
-/// \ref init(), then you can add a source node with \ref addSource()
+/// \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.
 /// @{
 return reached(t);
 }
 /// \brief Runs the algorithm to visit all nodes in the digraph.
-/// This method runs the %DFS algorithm in order to
+/// This method runs the %DFS algorithm in order to visit all nodes
-/// compute the %DFS path to each node.
+/// in the digraph.
-///
-/// The algorithm computes
-/// - the %DFS tree (forest),
-/// - 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) {
 /// Either \ref run(Node) "run()" or \ref start() should be called
 /// before using them.
 ///@{
-/// \brief Checks if a node is reached from the root(s).
+/// \brief Checks if the given node is reached from the root(s).
 ///
 /// 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.

changeset 1107	2b6bffe0e7e8
parent 1009	c85f53572941
parent 956	141f9c0db4a3
child 1110	02c93d1f00d7
child 1159	7fdaa05a69a1