1.1 --- a/lemon/gomory_hu.h Wed Apr 15 07:13:30 2009 +0100
1.2 +++ b/lemon/gomory_hu.h Wed Apr 15 09:37:51 2009 +0200
1.3 @@ -42,24 +42,22 @@
1.4 /// in this tree has the same weight as the minimum cut in the graph
1.5 /// between these nodes. Moreover the components obtained by removing
1.6 /// this edge from the tree determine the corresponding minimum cut.
1.7 - ///
1.8 /// Therefore once this tree is computed, the minimum cut between any pair
1.9 /// of nodes can easily be obtained.
1.10 ///
1.11 /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
1.12 - /// the \ref Preflow algorithm), therefore the algorithm has
1.13 - /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
1.14 - /// rooted Gomory-Hu tree, its structure and the weights can be obtained
1.15 - /// by \c predNode(), \c predValue() and \c rootDist().
1.16 - ///
1.17 - /// The members \c minCutMap() and \c minCutValue() calculate
1.18 + /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall
1.19 + /// time complexity. It calculates a rooted Gomory-Hu tree.
1.20 + /// The structure of the tree and the edge weights can be
1.21 + /// obtained using \c predNode(), \c predValue() and \c rootDist().
1.22 + /// The functions \c minCutMap() and \c minCutValue() calculate
1.23 /// the minimum cut and the minimum cut value between any two nodes
1.24 /// in the graph. You can also list (iterate on) the nodes and the
1.25 /// edges of the cuts using \c MinCutNodeIt and \c MinCutEdgeIt.
1.26 ///
1.27 /// \tparam GR The type of the undirected graph the algorithm runs on.
1.28 - /// \tparam CAP The type of the edge map describing the edge capacities.
1.29 - /// It is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>" by default.
1.30 + /// \tparam CAP The type of the edge map containing the capacities.
1.31 + /// The default map type is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
1.32 #ifdef DOXYGEN
1.33 template <typename GR,
1.34 typename CAP>
1.35 @@ -70,9 +68,9 @@
1.36 class GomoryHu {
1.37 public:
1.38
1.39 - /// The graph type
1.40 + /// The graph type of the algorithm
1.41 typedef GR Graph;
1.42 - /// The type of the edge capacity map
1.43 + /// The capacity map type of the algorithm
1.44 typedef CAP Capacity;
1.45 /// The value type of capacities
1.46 typedef typename Capacity::Value Value;
1.47 @@ -117,7 +115,7 @@
1.48
1.49 /// \brief Constructor
1.50 ///
1.51 - /// Constructor
1.52 + /// Constructor.
1.53 /// \param graph The undirected graph the algorithm runs on.
1.54 /// \param capacity The edge capacity map.
1.55 GomoryHu(const Graph& graph, const Capacity& capacity)
1.56 @@ -130,7 +128,7 @@
1.57
1.58 /// \brief Destructor
1.59 ///
1.60 - /// Destructor
1.61 + /// Destructor.
1.62 ~GomoryHu() {
1.63 destroyStructures();
1.64 }
1.65 @@ -215,43 +213,53 @@
1.66 ///\name Query Functions
1.67 ///The results of the algorithm can be obtained using these
1.68 ///functions.\n
1.69 - ///\ref run() "run()" should be called before using them.\n
1.70 + ///\ref run() should be called before using them.\n
1.71 ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt.
1.72
1.73 ///@{
1.74
1.75 /// \brief Return the predecessor node in the Gomory-Hu tree.
1.76 ///
1.77 - /// This function returns the predecessor node in the Gomory-Hu tree.
1.78 - /// If the node is
1.79 - /// the root of the Gomory-Hu tree, then it returns \c INVALID.
1.80 - Node predNode(const Node& node) {
1.81 + /// This function returns the predecessor node of the given node
1.82 + /// in the Gomory-Hu tree.
1.83 + /// If \c node is the root of the tree, then it returns \c INVALID.
1.84 + ///
1.85 + /// \pre \ref run() must be called before using this function.
1.86 + Node predNode(const Node& node) const {
1.87 return (*_pred)[node];
1.88 }
1.89
1.90 - /// \brief Return the distance from the root node in the Gomory-Hu tree.
1.91 - ///
1.92 - /// This function returns the distance of \c node from the root node
1.93 - /// in the Gomory-Hu tree.
1.94 - int rootDist(const Node& node) {
1.95 - return (*_order)[node];
1.96 - }
1.97 -
1.98 /// \brief Return the weight of the predecessor edge in the
1.99 /// Gomory-Hu tree.
1.100 ///
1.101 - /// This function returns the weight of the predecessor edge in the
1.102 - /// Gomory-Hu tree. If the node is the root, the result is undefined.
1.103 - Value predValue(const Node& node) {
1.104 + /// This function returns the weight of the predecessor edge of the
1.105 + /// given node in the Gomory-Hu tree.
1.106 + /// If \c node is the root of the tree, the result is undefined.
1.107 + ///
1.108 + /// \pre \ref run() must be called before using this function.
1.109 + Value predValue(const Node& node) const {
1.110 return (*_weight)[node];
1.111 }
1.112
1.113 + /// \brief Return the distance from the root node in the Gomory-Hu tree.
1.114 + ///
1.115 + /// This function returns the distance of the given node from the root
1.116 + /// node in the Gomory-Hu tree.
1.117 + ///
1.118 + /// \pre \ref run() must be called before using this function.
1.119 + int rootDist(const Node& node) const {
1.120 + return (*_order)[node];
1.121 + }
1.122 +
1.123 /// \brief Return the minimum cut value between two nodes
1.124 ///
1.125 - /// This function returns the minimum cut value between two nodes. The
1.126 - /// algorithm finds the nearest common ancestor in the Gomory-Hu
1.127 - /// tree and calculates the minimum weight edge on the paths to
1.128 - /// the ancestor.
1.129 + /// This function returns the minimum cut value between the nodes
1.130 + /// \c s and \c t.
1.131 + /// It finds the nearest common ancestor of the given nodes in the
1.132 + /// Gomory-Hu tree and calculates the minimum weight edge on the
1.133 + /// paths to the ancestor.
1.134 + ///
1.135 + /// \pre \ref run() must be called before using this function.
1.136 Value minCutValue(const Node& s, const Node& t) const {
1.137 Node sn = s, tn = t;
1.138 Value value = std::numeric_limits<Value>::max();
1.139 @@ -274,16 +282,23 @@
1.140 /// in the \c cutMap parameter by setting the nodes in the component of
1.141 /// \c s to \c true and the other nodes to \c false.
1.142 ///
1.143 - /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt.
1.144 + /// For higher level interfaces see MinCutNodeIt and MinCutEdgeIt.
1.145 + ///
1.146 + /// \param s The base node.
1.147 + /// \param t The node you want to separate from node \c s.
1.148 + /// \param cutMap The cut will be returned in this map.
1.149 + /// It must be a \c bool (or convertible) \ref concepts::ReadWriteMap
1.150 + /// "ReadWriteMap" on the graph nodes.
1.151 + ///
1.152 + /// \return The value of the minimum cut between \c s and \c t.
1.153 + ///
1.154 + /// \pre \ref run() must be called before using this function.
1.155 template <typename CutMap>
1.156 - Value minCutMap(const Node& s, ///< The base node.
1.157 + Value minCutMap(const Node& s, ///<
1.158 const Node& t,
1.159 - ///< The node you want to separate from node \c s.
1.160 + ///<
1.161 CutMap& cutMap
1.162 - ///< The cut will be returned in this map.
1.163 - /// It must be a \c bool (or convertible)
1.164 - /// \ref concepts::ReadWriteMap "ReadWriteMap"
1.165 - /// on the graph nodes.
1.166 + ///<
1.167 ) const {
1.168 Node sn = s, tn = t;
1.169 bool s_root=false;
1.170 @@ -338,7 +353,7 @@
1.171 /// Iterate on the nodes of a minimum cut
1.172
1.173 /// This iterator class lists the nodes of a minimum cut found by
1.174 - /// GomoryHu. Before using it, you must allocate a GomoryHu class,
1.175 + /// GomoryHu. Before using it, you must allocate a GomoryHu class
1.176 /// and call its \ref GomoryHu::run() "run()" method.
1.177 ///
1.178 /// This example counts the nodes in the minimum cut separating \c s from
1.179 @@ -435,7 +450,7 @@
1.180 /// Iterate on the edges of a minimum cut
1.181
1.182 /// This iterator class lists the edges of a minimum cut found by
1.183 - /// GomoryHu. Before using it, you must allocate a GomoryHu class,
1.184 + /// GomoryHu. Before using it, you must allocate a GomoryHu class
1.185 /// and call its \ref GomoryHu::run() "run()" method.
1.186 ///
1.187 /// This example computes the value of the minimum cut separating \c s from
1.188 @@ -447,8 +462,8 @@
1.189 /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
1.190 /// value+=capacities[e];
1.191 /// \endcode
1.192 - /// the result will be the same as it is returned by
1.193 - /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)"
1.194 + /// The result will be the same as the value returned by
1.195 + /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)".
1.196 class MinCutEdgeIt
1.197 {
1.198 bool _side;
1.199 @@ -468,6 +483,10 @@
1.200 }
1.201
1.202 public:
1.203 + /// Constructor
1.204 +
1.205 + /// Constructor.
1.206 + ///
1.207 MinCutEdgeIt(GomoryHu const &gomory,
1.208 ///< The GomoryHu class. You must call its
1.209 /// run() method
1.210 @@ -478,7 +497,7 @@
1.211 bool side=true
1.212 ///< If it is \c true (default) then the listed arcs
1.213 /// will be oriented from the
1.214 - /// the nodes of the component containing \c s,
1.215 + /// nodes of the component containing \c s,
1.216 /// otherwise they will be oriented in the opposite
1.217 /// direction.
1.218 )