Changeset 596:293551ad254f in lemon-1.2 for lemon/gomory_hu.h

Ignore:
Timestamp:
04/15/09 09:37:51 (11 years ago)
Branch:
default
Phase:
public
Message:

Improvements and fixes for the minimum cut algorithms (#264)

File:
1 edited

Legend:

Unmodified
 r581 /// 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 /// /// \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 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; /// 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 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. /// ///   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 { public: /// Constructor /// Constructor. /// MinCutEdgeIt(GomoryHu const &gomory, ///< The GomoryHu class. You must call its ///< 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.