1.1 --- a/lemon/gomory_hu.h Wed Mar 17 12:35:52 2010 +0100
1.2 +++ b/lemon/gomory_hu.h Sat Mar 06 14:35:12 2010 +0000
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 @@ -302,23 +302,23 @@
1.259 bool s_root=false;
1.260 Node rn = INVALID;
1.261 Value value = std::numeric_limits<Value>::max();
1.262 -
1.263 +
1.264 while (sn != tn) {
1.265 - if ((*_order)[sn] < (*_order)[tn]) {
1.266 - if ((*_weight)[tn] <= value) {
1.267 - rn = tn;
1.268 + if ((*_order)[sn] < (*_order)[tn]) {
1.269 + if ((*_weight)[tn] <= value) {
1.270 + rn = tn;
1.271 s_root = false;
1.272 - value = (*_weight)[tn];
1.273 - }
1.274 - tn = (*_pred)[tn];
1.275 - } else {
1.276 - if ((*_weight)[sn] <= value) {
1.277 - rn = sn;
1.278 + value = (*_weight)[tn];
1.279 + }
1.280 + tn = (*_pred)[tn];
1.281 + } else {
1.282 + if ((*_weight)[sn] <= value) {
1.283 + rn = sn;
1.284 s_root = true;
1.285 - value = (*_weight)[sn];
1.286 - }
1.287 - sn = (*_pred)[sn];
1.288 - }
1.289 + value = (*_weight)[sn];
1.290 + }
1.291 + sn = (*_pred)[sn];
1.292 + }
1.293 }
1.294
1.295 typename Graph::template NodeMap<bool> reached(_graph, false);
1.296 @@ -329,18 +329,18 @@
1.297
1.298 std::vector<Node> st;
1.299 for (NodeIt n(_graph); n != INVALID; ++n) {
1.300 - st.clear();
1.301 + st.clear();
1.302 Node nn = n;
1.303 - while (!reached[nn]) {
1.304 - st.push_back(nn);
1.305 - nn = (*_pred)[nn];
1.306 - }
1.307 - while (!st.empty()) {
1.308 - cutMap.set(st.back(), cutMap[nn]);
1.309 - st.pop_back();
1.310 - }
1.311 + while (!reached[nn]) {
1.312 + st.push_back(nn);
1.313 + nn = (*_pred)[nn];
1.314 + }
1.315 + while (!st.empty()) {
1.316 + cutMap.set(st.back(), cutMap[nn]);
1.317 + st.pop_back();
1.318 + }
1.319 }
1.320 -
1.321 +
1.322 return value;
1.323 }
1.324
1.325 @@ -349,7 +349,7 @@
1.326 friend class MinCutNodeIt;
1.327
1.328 /// Iterate on the nodes of a minimum cut
1.329 -
1.330 +
1.331 /// This iterator class lists the nodes of a minimum cut found by
1.332 /// GomoryHu. Before using it, you must allocate a GomoryHu class
1.333 /// and call its \ref GomoryHu::run() "run()" method.
1.334 @@ -442,11 +442,11 @@
1.335 return n;
1.336 }
1.337 };
1.338 -
1.339 +
1.340 friend class MinCutEdgeIt;
1.341 -
1.342 +
1.343 /// Iterate on the edges of a minimum cut
1.344 -
1.345 +
1.346 /// This iterator class lists the edges of a minimum cut found by
1.347 /// GomoryHu. Before using it, you must allocate a GomoryHu class
1.348 /// and call its \ref GomoryHu::run() "run()" method.
1.349 @@ -479,7 +479,7 @@
1.350 _arc_it=typename Graph::OutArcIt(_graph,_node_it);
1.351 }
1.352 }
1.353 -
1.354 +
1.355 public:
1.356 /// Constructor
1.357
1.358 @@ -548,7 +548,7 @@
1.359 return *this;
1.360 }
1.361 /// Postfix incrementation
1.362 -
1.363 +
1.364 /// Postfix incrementation.
1.365 ///
1.366 /// \warning This incrementation