1.1 --- a/lemon/gomory_hu.h Sat Apr 18 21:54:30 2009 +0200
1.2 +++ b/lemon/gomory_hu.h Tue Apr 21 10:34:49 2009 +0100
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 @@ -143,11 +141,11 @@
1.66
1.67 _root = NodeIt(_graph);
1.68 for (NodeIt n(_graph); n != INVALID; ++n) {
1.69 - _pred->set(n, _root);
1.70 - _order->set(n, -1);
1.71 + (*_pred)[n] = _root;
1.72 + (*_order)[n] = -1;
1.73 }
1.74 - _pred->set(_root, INVALID);
1.75 - _weight->set(_root, std::numeric_limits<Value>::max());
1.76 + (*_pred)[_root] = INVALID;
1.77 + (*_weight)[_root] = std::numeric_limits<Value>::max();
1.78 }
1.79
1.80
1.81 @@ -164,22 +162,22 @@
1.82
1.83 fa.runMinCut();
1.84
1.85 - _weight->set(n, fa.flowValue());
1.86 + (*_weight)[n] = fa.flowValue();
1.87
1.88 for (NodeIt nn(_graph); nn != INVALID; ++nn) {
1.89 if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
1.90 - _pred->set(nn, n);
1.91 + (*_pred)[nn] = n;
1.92 }
1.93 }
1.94 if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
1.95 - _pred->set(n, (*_pred)[pn]);
1.96 - _pred->set(pn, n);
1.97 - _weight->set(n, (*_weight)[pn]);
1.98 - _weight->set(pn, fa.flowValue());
1.99 + (*_pred)[n] = (*_pred)[pn];
1.100 + (*_pred)[pn] = n;
1.101 + (*_weight)[n] = (*_weight)[pn];
1.102 + (*_weight)[pn] = fa.flowValue();
1.103 }
1.104 }
1.105
1.106 - _order->set(_root, 0);
1.107 + (*_order)[_root] = 0;
1.108 int index = 1;
1.109
1.110 for (NodeIt n(_graph); n != INVALID; ++n) {
1.111 @@ -190,7 +188,7 @@
1.112 nn = (*_pred)[nn];
1.113 }
1.114 while (!st.empty()) {
1.115 - _order->set(st.back(), index++);
1.116 + (*_order)[st.back()] = index++;
1.117 st.pop_back();
1.118 }
1.119 }
1.120 @@ -215,43 +213,53 @@
1.121 ///\name Query Functions
1.122 ///The results of the algorithm can be obtained using these
1.123 ///functions.\n
1.124 - ///\ref run() "run()" should be called before using them.\n
1.125 + ///\ref run() should be called before using them.\n
1.126 ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt.
1.127
1.128 ///@{
1.129
1.130 /// \brief Return the predecessor node in the Gomory-Hu tree.
1.131 ///
1.132 - /// This function returns the predecessor node in the Gomory-Hu tree.
1.133 - /// If the node is
1.134 - /// the root of the Gomory-Hu tree, then it returns \c INVALID.
1.135 - Node predNode(const Node& node) {
1.136 + /// This function returns the predecessor node of the given node
1.137 + /// in the Gomory-Hu tree.
1.138 + /// If \c node is the root of the tree, then it returns \c INVALID.
1.139 + ///
1.140 + /// \pre \ref run() must be called before using this function.
1.141 + Node predNode(const Node& node) const {
1.142 return (*_pred)[node];
1.143 }
1.144
1.145 - /// \brief Return the distance from the root node in the Gomory-Hu tree.
1.146 - ///
1.147 - /// This function returns the distance of \c node from the root node
1.148 - /// in the Gomory-Hu tree.
1.149 - int rootDist(const Node& node) {
1.150 - return (*_order)[node];
1.151 - }
1.152 -
1.153 /// \brief Return the weight of the predecessor edge in the
1.154 /// Gomory-Hu tree.
1.155 ///
1.156 - /// This function returns the weight of the predecessor edge in the
1.157 - /// Gomory-Hu tree. If the node is the root, the result is undefined.
1.158 - Value predValue(const Node& node) {
1.159 + /// This function returns the weight of the predecessor edge of the
1.160 + /// given node in the Gomory-Hu tree.
1.161 + /// If \c node is the root of the tree, the result is undefined.
1.162 + ///
1.163 + /// \pre \ref run() must be called before using this function.
1.164 + Value predValue(const Node& node) const {
1.165 return (*_weight)[node];
1.166 }
1.167
1.168 + /// \brief Return the distance from the root node in the Gomory-Hu tree.
1.169 + ///
1.170 + /// This function returns the distance of the given node from the root
1.171 + /// node in the Gomory-Hu tree.
1.172 + ///
1.173 + /// \pre \ref run() must be called before using this function.
1.174 + int rootDist(const Node& node) const {
1.175 + return (*_order)[node];
1.176 + }
1.177 +
1.178 /// \brief Return the minimum cut value between two nodes
1.179 ///
1.180 - /// This function returns the minimum cut value between two nodes. The
1.181 - /// algorithm finds the nearest common ancestor in the Gomory-Hu
1.182 - /// tree and calculates the minimum weight edge on the paths to
1.183 - /// the ancestor.
1.184 + /// This function returns the minimum cut value between the nodes
1.185 + /// \c s and \c t.
1.186 + /// It finds the nearest common ancestor of the given nodes in the
1.187 + /// Gomory-Hu tree and calculates the minimum weight edge on the
1.188 + /// paths to the ancestor.
1.189 + ///
1.190 + /// \pre \ref run() must be called before using this function.
1.191 Value minCutValue(const Node& s, const Node& t) const {
1.192 Node sn = s, tn = t;
1.193 Value value = std::numeric_limits<Value>::max();
1.194 @@ -274,16 +282,23 @@
1.195 /// in the \c cutMap parameter by setting the nodes in the component of
1.196 /// \c s to \c true and the other nodes to \c false.
1.197 ///
1.198 - /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt.
1.199 + /// For higher level interfaces see MinCutNodeIt and MinCutEdgeIt.
1.200 + ///
1.201 + /// \param s The base node.
1.202 + /// \param t The node you want to separate from node \c s.
1.203 + /// \param cutMap The cut will be returned in this map.
1.204 + /// It must be a \c bool (or convertible) \ref concepts::ReadWriteMap
1.205 + /// "ReadWriteMap" on the graph nodes.
1.206 + ///
1.207 + /// \return The value of the minimum cut between \c s and \c t.
1.208 + ///
1.209 + /// \pre \ref run() must be called before using this function.
1.210 template <typename CutMap>
1.211 - Value minCutMap(const Node& s, ///< The base node.
1.212 + Value minCutMap(const Node& s, ///<
1.213 const Node& t,
1.214 - ///< The node you want to separate from node \c s.
1.215 + ///<
1.216 CutMap& cutMap
1.217 - ///< The cut will be returned in this map.
1.218 - /// It must be a \c bool (or convertible)
1.219 - /// \ref concepts::ReadWriteMap "ReadWriteMap"
1.220 - /// on the graph nodes.
1.221 + ///<
1.222 ) const {
1.223 Node sn = s, tn = t;
1.224 bool s_root=false;
1.225 @@ -309,9 +324,9 @@
1.226 }
1.227
1.228 typename Graph::template NodeMap<bool> reached(_graph, false);
1.229 - reached.set(_root, true);
1.230 + reached[_root] = true;
1.231 cutMap.set(_root, !s_root);
1.232 - reached.set(rn, true);
1.233 + reached[rn] = true;
1.234 cutMap.set(rn, s_root);
1.235
1.236 std::vector<Node> st;
1.237 @@ -338,7 +353,7 @@
1.238 /// Iterate on the nodes of a minimum cut
1.239
1.240 /// This iterator class lists the nodes of a minimum cut found by
1.241 - /// GomoryHu. Before using it, you must allocate a GomoryHu class,
1.242 + /// GomoryHu. Before using it, you must allocate a GomoryHu class
1.243 /// and call its \ref GomoryHu::run() "run()" method.
1.244 ///
1.245 /// This example counts the nodes in the minimum cut separating \c s from
1.246 @@ -435,7 +450,7 @@
1.247 /// Iterate on the edges of a minimum cut
1.248
1.249 /// This iterator class lists the edges of a minimum cut found by
1.250 - /// GomoryHu. Before using it, you must allocate a GomoryHu class,
1.251 + /// GomoryHu. Before using it, you must allocate a GomoryHu class
1.252 /// and call its \ref GomoryHu::run() "run()" method.
1.253 ///
1.254 /// This example computes the value of the minimum cut separating \c s from
1.255 @@ -447,8 +462,8 @@
1.256 /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
1.257 /// value+=capacities[e];
1.258 /// \endcode
1.259 - /// the result will be the same as it is returned by
1.260 - /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)"
1.261 + /// The result will be the same as the value returned by
1.262 + /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)".
1.263 class MinCutEdgeIt
1.264 {
1.265 bool _side;
1.266 @@ -468,6 +483,10 @@
1.267 }
1.268
1.269 public:
1.270 + /// Constructor
1.271 +
1.272 + /// Constructor.
1.273 + ///
1.274 MinCutEdgeIt(GomoryHu const &gomory,
1.275 ///< The GomoryHu class. You must call its
1.276 /// run() method
1.277 @@ -478,7 +497,7 @@
1.278 bool side=true
1.279 ///< If it is \c true (default) then the listed arcs
1.280 /// will be oriented from the
1.281 - /// the nodes of the component containing \c s,
1.282 + /// nodes of the component containing \c s,
1.283 /// otherwise they will be oriented in the opposite
1.284 /// direction.
1.285 )