diff --git a/lemon/gomory_hu.h b/lemon/gomory_hu.h --- a/lemon/gomory_hu.h +++ b/lemon/gomory_hu.h @@ -42,24 +42,22 @@ /// in this tree has the same weight as the minimum cut in the graph /// between these nodes. Moreover the components obtained by removing /// this edge from the tree determine the corresponding minimum cut. - /// /// Therefore once this tree is computed, the minimum cut between any pair /// of nodes can easily be obtained. /// /// The algorithm calculates \e n-1 distinct minimum cuts (currently with - /// the \ref Preflow algorithm), therefore the algorithm has - /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a - /// rooted Gomory-Hu tree, its structure and the weights can be obtained - /// by \c predNode(), \c predValue() and \c rootDist(). - /// - /// The members \c minCutMap() and \c minCutValue() calculate + /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall + /// time complexity. It calculates a rooted Gomory-Hu tree. + /// The structure of the tree and the edge weights can be + /// obtained using \c predNode(), \c predValue() and \c rootDist(). + /// The functions \c minCutMap() and \c minCutValue() calculate /// the minimum cut and the minimum cut value between any two nodes /// in the graph. You can also list (iterate on) the nodes and the /// edges of the cuts using \c MinCutNodeIt and \c MinCutEdgeIt. /// /// \tparam GR The type of the undirected graph the algorithm runs on. - /// \tparam CAP The type of the edge map describing the edge capacities. - /// It is \ref concepts::Graph::EdgeMap "GR::EdgeMap" by default. + /// \tparam CAP The type of the edge map containing the capacities. + /// The default map type is \ref concepts::Graph::EdgeMap "GR::EdgeMap". #ifdef DOXYGEN template @@ -70,9 +68,9 @@ class GomoryHu { public: - /// The graph type + /// The graph type of the algorithm typedef GR Graph; - /// The type of the edge capacity map + /// The capacity map type of the algorithm typedef CAP Capacity; /// The value type of capacities typedef typename Capacity::Value Value; @@ -117,7 +115,7 @@ /// \brief Constructor /// - /// Constructor + /// Constructor. /// \param graph The undirected graph the algorithm runs on. /// \param capacity The edge capacity map. GomoryHu(const Graph& graph, const Capacity& capacity) @@ -130,7 +128,7 @@ /// \brief Destructor /// - /// Destructor + /// Destructor. ~GomoryHu() { destroyStructures(); } @@ -215,43 +213,53 @@ ///\name Query Functions ///The results of the algorithm can be obtained using these ///functions.\n - ///\ref run() "run()" should be called before using them.\n + ///\ref run() should be called before using them.\n ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt. ///@{ /// \brief Return the predecessor node in the Gomory-Hu tree. /// - /// This function returns the predecessor node in the Gomory-Hu tree. - /// If the node is - /// the root of the Gomory-Hu tree, then it returns \c INVALID. - Node predNode(const Node& node) { + /// This function returns the predecessor node of the given node + /// in the Gomory-Hu tree. + /// If \c node is the root of the tree, then it returns \c INVALID. + /// + /// \pre \ref run() must be called before using this function. + Node predNode(const Node& node) const { return (*_pred)[node]; } - /// \brief Return the distance from the root node in the Gomory-Hu tree. - /// - /// This function returns the distance of \c node from the root node - /// in the Gomory-Hu tree. - int rootDist(const Node& node) { - return (*_order)[node]; - } - /// \brief Return the weight of the predecessor edge in the /// Gomory-Hu tree. /// - /// This function returns the weight of the predecessor edge in the - /// Gomory-Hu tree. If the node is the root, the result is undefined. - Value predValue(const Node& node) { + /// This function returns the weight of the predecessor edge of the + /// given node in the Gomory-Hu tree. + /// If \c node is the root of the tree, the result is undefined. + /// + /// \pre \ref run() must be called before using this function. + Value predValue(const Node& node) const { return (*_weight)[node]; } + /// \brief Return the distance from the root node in the Gomory-Hu tree. + /// + /// This function returns the distance of the given node from the root + /// node in the Gomory-Hu tree. + /// + /// \pre \ref run() must be called before using this function. + int rootDist(const Node& node) const { + return (*_order)[node]; + } + /// \brief Return the minimum cut value between two nodes /// - /// This function returns the minimum cut value between two nodes. The - /// algorithm finds the nearest common ancestor in the Gomory-Hu - /// tree and calculates the minimum weight edge on the paths to - /// the ancestor. + /// This function returns the minimum cut value between the nodes + /// \c s and \c t. + /// It finds the nearest common ancestor of the given nodes in the + /// Gomory-Hu tree and calculates the minimum weight edge on the + /// paths to the ancestor. + /// + /// \pre \ref run() must be called before using this function. Value minCutValue(const Node& s, const Node& t) const { Node sn = s, tn = t; Value value = std::numeric_limits::max(); @@ -274,16 +282,23 @@ /// in the \c cutMap parameter by setting the nodes in the component of /// \c s to \c true and the other nodes to \c false. /// - /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt. + /// For higher level interfaces see MinCutNodeIt and MinCutEdgeIt. + /// + /// \param s The base node. + /// \param t The node you want to separate from node \c s. + /// \param cutMap The cut will be returned in this map. + /// It must be a \c bool (or convertible) \ref concepts::ReadWriteMap + /// "ReadWriteMap" on the graph nodes. + /// + /// \return The value of the minimum cut between \c s and \c t. + /// + /// \pre \ref run() must be called before using this function. template - Value minCutMap(const Node& s, ///< The base node. + Value minCutMap(const Node& s, ///< const Node& t, - ///< The node you want to separate from node \c s. + ///< CutMap& cutMap - ///< The cut will be returned in this map. - /// It must be a \c bool (or convertible) - /// \ref concepts::ReadWriteMap "ReadWriteMap" - /// on the graph nodes. + ///< ) const { Node sn = s, tn = t; bool s_root=false; @@ -338,7 +353,7 @@ /// Iterate on the nodes of a minimum cut /// This iterator class lists the nodes of a minimum cut found by - /// GomoryHu. Before using it, you must allocate a GomoryHu class, + /// GomoryHu. Before using it, you must allocate a GomoryHu class /// and call its \ref GomoryHu::run() "run()" method. /// /// This example counts the nodes in the minimum cut separating \c s from @@ -435,7 +450,7 @@ /// Iterate on the edges of a minimum cut /// This iterator class lists the edges of a minimum cut found by - /// GomoryHu. Before using it, you must allocate a GomoryHu class, + /// GomoryHu. Before using it, you must allocate a GomoryHu class /// and call its \ref GomoryHu::run() "run()" method. /// /// This example computes the value of the minimum cut separating \c s from @@ -447,8 +462,8 @@ /// for(GomoruHu::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e) /// value+=capacities[e]; /// \endcode - /// the result will be the same as it is returned by - /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)" + /// The result will be the same as the value returned by + /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)". class MinCutEdgeIt { bool _side; @@ -468,6 +483,10 @@ } public: + /// Constructor + + /// Constructor. + /// MinCutEdgeIt(GomoryHu const &gomory, ///< The GomoryHu class. You must call its /// run() method @@ -478,7 +497,7 @@ bool side=true ///< If it is \c true (default) then the listed arcs /// will be oriented from the - /// the nodes of the component containing \c s, + /// nodes of the component containing \c s, /// otherwise they will be oriented in the opposite /// direction. )