1.1 --- a/lemon/gomory_hu.h Fri Aug 09 11:07:27 2013 +0200
1.2 +++ b/lemon/gomory_hu.h Sun Aug 11 15:28:12 2013 +0200
1.3 @@ -1,8 +1,8 @@
1.4 -/* -*- C++ -*-
1.5 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.6 *
1.7 - * This file is a part of LEMON, a generic C++ optimization library
1.8 + * This file is a part of LEMON, a generic C++ optimization library.
1.9 *
1.10 - * Copyright (C) 2003-2008
1.11 + * Copyright (C) 2003-2010
1.12 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.13 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.14 *
1.15 @@ -27,7 +27,7 @@
1.16 #include <lemon/concepts/maps.h>
1.17
1.18 /// \ingroup min_cut
1.19 -/// \file
1.20 +/// \file
1.21 /// \brief Gomory-Hu cut tree in graphs.
1.22
1.23 namespace lemon {
1.24 @@ -38,13 +38,13 @@
1.25 ///
1.26 /// The Gomory-Hu tree is a tree on the node set of a given graph, but it
1.27 /// may contain edges which are not in the original graph. It has the
1.28 - /// property that the minimum capacity edge of the path between two nodes
1.29 + /// property that the minimum capacity edge of the path between two nodes
1.30 /// in this tree has the same weight as the minimum cut in the graph
1.31 /// between these nodes. Moreover the components obtained by removing
1.32 /// this edge from the tree determine the corresponding minimum cut.
1.33 /// Therefore once this tree is computed, the minimum cut between any pair
1.34 /// of nodes can easily be obtained.
1.35 - ///
1.36 + ///
1.37 /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
1.38 /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall
1.39 /// time complexity. It calculates a rooted Gomory-Hu tree.
1.40 @@ -60,10 +60,10 @@
1.41 /// The default map type is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
1.42 #ifdef DOXYGEN
1.43 template <typename GR,
1.44 - typename CAP>
1.45 + typename CAP>
1.46 #else
1.47 template <typename GR,
1.48 - typename CAP = typename GR::template EdgeMap<int> >
1.49 + typename CAP = typename GR::template EdgeMap<int> >
1.50 #endif
1.51 class GomoryHu {
1.52 public:
1.53 @@ -74,7 +74,7 @@
1.54 typedef CAP Capacity;
1.55 /// The value type of capacities
1.56 typedef typename Capacity::Value Value;
1.57 -
1.58 +
1.59 private:
1.60
1.61 TEMPLATE_GRAPH_TYPEDEFS(Graph);
1.62 @@ -89,28 +89,28 @@
1.63
1.64 void createStructures() {
1.65 if (!_pred) {
1.66 - _pred = new typename Graph::template NodeMap<Node>(_graph);
1.67 + _pred = new typename Graph::template NodeMap<Node>(_graph);
1.68 }
1.69 if (!_weight) {
1.70 - _weight = new typename Graph::template NodeMap<Value>(_graph);
1.71 + _weight = new typename Graph::template NodeMap<Value>(_graph);
1.72 }
1.73 if (!_order) {
1.74 - _order = new typename Graph::template NodeMap<int>(_graph);
1.75 + _order = new typename Graph::template NodeMap<int>(_graph);
1.76 }
1.77 }
1.78
1.79 void destroyStructures() {
1.80 if (_pred) {
1.81 - delete _pred;
1.82 + delete _pred;
1.83 }
1.84 if (_weight) {
1.85 - delete _weight;
1.86 + delete _weight;
1.87 }
1.88 if (_order) {
1.89 - delete _order;
1.90 + delete _order;
1.91 }
1.92 }
1.93 -
1.94 +
1.95 public:
1.96
1.97 /// \brief Constructor
1.98 @@ -118,9 +118,9 @@
1.99 /// Constructor.
1.100 /// \param graph The undirected graph the algorithm runs on.
1.101 /// \param capacity The edge capacity map.
1.102 - GomoryHu(const Graph& graph, const Capacity& capacity)
1.103 + GomoryHu(const Graph& graph, const Capacity& capacity)
1.104 : _graph(graph), _capacity(capacity),
1.105 - _pred(0), _weight(0), _order(0)
1.106 + _pred(0), _weight(0), _order(0)
1.107 {
1.108 checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();
1.109 }
1.110 @@ -134,7 +134,7 @@
1.111 }
1.112
1.113 private:
1.114 -
1.115 +
1.116 // Initialize the internal data structures
1.117 void init() {
1.118 createStructures();
1.119 @@ -145,7 +145,7 @@
1.120 (*_order)[n] = -1;
1.121 }
1.122 (*_pred)[_root] = INVALID;
1.123 - (*_weight)[_root] = std::numeric_limits<Value>::max();
1.124 + (*_weight)[_root] = std::numeric_limits<Value>::max();
1.125 }
1.126
1.127
1.128 @@ -154,50 +154,50 @@
1.129 Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
1.130
1.131 for (NodeIt n(_graph); n != INVALID; ++n) {
1.132 - if (n == _root) continue;
1.133 + if (n == _root) continue;
1.134
1.135 - Node pn = (*_pred)[n];
1.136 - fa.source(n);
1.137 - fa.target(pn);
1.138 + Node pn = (*_pred)[n];
1.139 + fa.source(n);
1.140 + fa.target(pn);
1.141
1.142 - fa.runMinCut();
1.143 + fa.runMinCut();
1.144
1.145 - (*_weight)[n] = fa.flowValue();
1.146 + (*_weight)[n] = fa.flowValue();
1.147
1.148 - for (NodeIt nn(_graph); nn != INVALID; ++nn) {
1.149 - if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
1.150 - (*_pred)[nn] = n;
1.151 - }
1.152 - }
1.153 - if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
1.154 - (*_pred)[n] = (*_pred)[pn];
1.155 - (*_pred)[pn] = n;
1.156 - (*_weight)[n] = (*_weight)[pn];
1.157 - (*_weight)[pn] = fa.flowValue();
1.158 - }
1.159 + for (NodeIt nn(_graph); nn != INVALID; ++nn) {
1.160 + if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
1.161 + (*_pred)[nn] = n;
1.162 + }
1.163 + }
1.164 + if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
1.165 + (*_pred)[n] = (*_pred)[pn];
1.166 + (*_pred)[pn] = n;
1.167 + (*_weight)[n] = (*_weight)[pn];
1.168 + (*_weight)[pn] = fa.flowValue();
1.169 + }
1.170 }
1.171
1.172 (*_order)[_root] = 0;
1.173 int index = 1;
1.174
1.175 for (NodeIt n(_graph); n != INVALID; ++n) {
1.176 - std::vector<Node> st;
1.177 - Node nn = n;
1.178 - while ((*_order)[nn] == -1) {
1.179 - st.push_back(nn);
1.180 - nn = (*_pred)[nn];
1.181 - }
1.182 - while (!st.empty()) {
1.183 - (*_order)[st.back()] = index++;
1.184 - st.pop_back();
1.185 - }
1.186 + std::vector<Node> st;
1.187 + Node nn = n;
1.188 + while ((*_order)[nn] == -1) {
1.189 + st.push_back(nn);
1.190 + nn = (*_pred)[nn];
1.191 + }
1.192 + while (!st.empty()) {
1.193 + (*_order)[st.back()] = index++;
1.194 + st.pop_back();
1.195 + }
1.196 }
1.197 }
1.198
1.199 public:
1.200
1.201 ///\name Execution Control
1.202 -
1.203 +
1.204 ///@{
1.205
1.206 /// \brief Run the Gomory-Hu algorithm.
1.207 @@ -207,7 +207,7 @@
1.208 init();
1.209 start();
1.210 }
1.211 -
1.212 +
1.213 /// @}
1.214
1.215 ///\name Query Functions
1.216 @@ -232,7 +232,7 @@
1.217 /// \brief Return the weight of the predecessor edge in the
1.218 /// Gomory-Hu tree.
1.219 ///
1.220 - /// This function returns the weight of the predecessor edge of the
1.221 + /// This function returns the weight of the predecessor edge of the
1.222 /// given node in the Gomory-Hu tree.
1.223 /// If \c node is the root of the tree, the result is undefined.
1.224 ///
1.225 @@ -254,7 +254,7 @@
1.226 /// \brief Return the minimum cut value between two nodes
1.227 ///
1.228 /// This function returns the minimum cut value between the nodes
1.229 - /// \c s and \c t.
1.230 + /// \c s and \c t.
1.231 /// It finds the nearest common ancestor of the given nodes in the
1.232 /// Gomory-Hu tree and calculates the minimum weight edge on the
1.233 /// paths to the ancestor.
1.234 @@ -263,15 +263,15 @@
1.235 Value minCutValue(const Node& s, const Node& t) const {
1.236 Node sn = s, tn = t;
1.237 Value value = std::numeric_limits<Value>::max();
1.238 -
1.239 +
1.240 while (sn != tn) {
1.241 - if ((*_order)[sn] < (*_order)[tn]) {
1.242 - if ((*_weight)[tn] <= value) value = (*_weight)[tn];
1.243 - tn = (*_pred)[tn];
1.244 - } else {
1.245 - if ((*_weight)[sn] <= value) value = (*_weight)[sn];
1.246 - sn = (*_pred)[sn];
1.247 - }
1.248 + if ((*_order)[sn] < (*_order)[tn]) {
1.249 + if ((*_weight)[tn] <= value) value = (*_weight)[tn];
1.250 + tn = (*_pred)[tn];
1.251 + } else {
1.252 + if ((*_weight)[sn] <= value) value = (*_weight)[sn];
1.253 + sn = (*_pred)[sn];
1.254 + }
1.255 }
1.256 return value;
1.257 }
1.258 @@ -294,33 +294,31 @@
1.259 ///
1.260 /// \pre \ref run() must be called before using this function.
1.261 template <typename CutMap>
1.262 - Value minCutMap(const Node& s, ///<
1.263 + Value minCutMap(const Node& s,
1.264 const Node& t,
1.265 - ///<
1.266 CutMap& cutMap
1.267 - ///<
1.268 ) const {
1.269 Node sn = s, tn = t;
1.270 bool s_root=false;
1.271 Node rn = INVALID;
1.272 Value value = std::numeric_limits<Value>::max();
1.273 -
1.274 +
1.275 while (sn != tn) {
1.276 - if ((*_order)[sn] < (*_order)[tn]) {
1.277 - if ((*_weight)[tn] <= value) {
1.278 - rn = tn;
1.279 + if ((*_order)[sn] < (*_order)[tn]) {
1.280 + if ((*_weight)[tn] <= value) {
1.281 + rn = tn;
1.282 s_root = false;
1.283 - value = (*_weight)[tn];
1.284 - }
1.285 - tn = (*_pred)[tn];
1.286 - } else {
1.287 - if ((*_weight)[sn] <= value) {
1.288 - rn = sn;
1.289 + value = (*_weight)[tn];
1.290 + }
1.291 + tn = (*_pred)[tn];
1.292 + } else {
1.293 + if ((*_weight)[sn] <= value) {
1.294 + rn = sn;
1.295 s_root = true;
1.296 - value = (*_weight)[sn];
1.297 - }
1.298 - sn = (*_pred)[sn];
1.299 - }
1.300 + value = (*_weight)[sn];
1.301 + }
1.302 + sn = (*_pred)[sn];
1.303 + }
1.304 }
1.305
1.306 typename Graph::template NodeMap<bool> reached(_graph, false);
1.307 @@ -331,18 +329,18 @@
1.308
1.309 std::vector<Node> st;
1.310 for (NodeIt n(_graph); n != INVALID; ++n) {
1.311 - st.clear();
1.312 + st.clear();
1.313 Node nn = n;
1.314 - while (!reached[nn]) {
1.315 - st.push_back(nn);
1.316 - nn = (*_pred)[nn];
1.317 - }
1.318 - while (!st.empty()) {
1.319 - cutMap.set(st.back(), cutMap[nn]);
1.320 - st.pop_back();
1.321 - }
1.322 + while (!reached[nn]) {
1.323 + st.push_back(nn);
1.324 + nn = (*_pred)[nn];
1.325 + }
1.326 + while (!st.empty()) {
1.327 + cutMap.set(st.back(), cutMap[nn]);
1.328 + st.pop_back();
1.329 + }
1.330 }
1.331 -
1.332 +
1.333 return value;
1.334 }
1.335
1.336 @@ -351,7 +349,7 @@
1.337 friend class MinCutNodeIt;
1.338
1.339 /// Iterate on the nodes of a minimum cut
1.340 -
1.341 +
1.342 /// This iterator class lists the nodes of a minimum cut found by
1.343 /// GomoryHu. Before using it, you must allocate a GomoryHu class
1.344 /// and call its \ref GomoryHu::run() "run()" method.
1.345 @@ -359,10 +357,10 @@
1.346 /// This example counts the nodes in the minimum cut separating \c s from
1.347 /// \c t.
1.348 /// \code
1.349 - /// GomoruHu<Graph> gom(g, capacities);
1.350 + /// GomoryHu<Graph> gom(g, capacities);
1.351 /// gom.run();
1.352 /// int cnt=0;
1.353 - /// for(GomoruHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
1.354 + /// for(GomoryHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
1.355 /// \endcode
1.356 class MinCutNodeIt
1.357 {
1.358 @@ -394,7 +392,7 @@
1.359 /// MinCutNodeIt(gomory, t, s, false);
1.360 /// \endcode
1.361 /// does not necessarily give the same set of nodes.
1.362 - /// However it is ensured that
1.363 + /// However, it is ensured that
1.364 /// \code
1.365 /// MinCutNodeIt(gomory, s, t, true);
1.366 /// \endcode
1.367 @@ -444,11 +442,11 @@
1.368 return n;
1.369 }
1.370 };
1.371 -
1.372 +
1.373 friend class MinCutEdgeIt;
1.374 -
1.375 +
1.376 /// Iterate on the edges of a minimum cut
1.377 -
1.378 +
1.379 /// This iterator class lists the edges of a minimum cut found by
1.380 /// GomoryHu. Before using it, you must allocate a GomoryHu class
1.381 /// and call its \ref GomoryHu::run() "run()" method.
1.382 @@ -456,10 +454,10 @@
1.383 /// This example computes the value of the minimum cut separating \c s from
1.384 /// \c t.
1.385 /// \code
1.386 - /// GomoruHu<Graph> gom(g, capacities);
1.387 + /// GomoryHu<Graph> gom(g, capacities);
1.388 /// gom.run();
1.389 /// int value=0;
1.390 - /// for(GomoruHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
1.391 + /// for(GomoryHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
1.392 /// value+=capacities[e];
1.393 /// \endcode
1.394 /// The result will be the same as the value returned by
1.395 @@ -481,7 +479,7 @@
1.396 _arc_it=typename Graph::OutArcIt(_graph,_node_it);
1.397 }
1.398 }
1.399 -
1.400 +
1.401 public:
1.402 /// Constructor
1.403
1.404 @@ -550,7 +548,7 @@
1.405 return *this;
1.406 }
1.407 /// Postfix incrementation
1.408 -
1.409 +
1.410 /// Postfix incrementation.
1.411 ///
1.412 /// \warning This incrementation