Changeset 761:f1398882a928 in lemon-1.1 for lemon/gomory_hu.h
- Timestamp:
- 08/08/11 12:36:16 (13 years ago)
- Branch:
- 1.1
- Phase:
- public
- Tags:
- r1.1.4
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/gomory_hu.h
r588 r761 1 /* -*- C++-*-1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 085 * Copyright (C) 2003-2011 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 28 28 29 29 /// \ingroup min_cut 30 /// \file 30 /// \file 31 31 /// \brief Gomory-Hu cut tree in graphs. 32 32 … … 39 39 /// The Gomory-Hu tree is a tree on the node set of a given graph, but it 40 40 /// may contain edges which are not in the original graph. It has the 41 /// property that the minimum capacity edge of the path between two nodes 41 /// property that the minimum capacity edge of the path between two nodes 42 42 /// in this tree has the same weight as the minimum cut in the graph 43 43 /// between these nodes. Moreover the components obtained by removing … … 45 45 /// Therefore once this tree is computed, the minimum cut between any pair 46 46 /// of nodes can easily be obtained. 47 /// 47 /// 48 48 /// The algorithm calculates \e n-1 distinct minimum cuts (currently with 49 49 /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall … … 61 61 #ifdef DOXYGEN 62 62 template <typename GR, 63 63 typename CAP> 64 64 #else 65 65 template <typename GR, 66 66 typename CAP = typename GR::template EdgeMap<int> > 67 67 #endif 68 68 class GomoryHu { … … 75 75 /// The value type of capacities 76 76 typedef typename Capacity::Value Value; 77 77 78 78 private: 79 79 … … 90 90 void createStructures() { 91 91 if (!_pred) { 92 92 _pred = new typename Graph::template NodeMap<Node>(_graph); 93 93 } 94 94 if (!_weight) { 95 95 _weight = new typename Graph::template NodeMap<Value>(_graph); 96 96 } 97 97 if (!_order) { 98 98 _order = new typename Graph::template NodeMap<int>(_graph); 99 99 } 100 100 } … … 102 102 void destroyStructures() { 103 103 if (_pred) { 104 104 delete _pred; 105 105 } 106 106 if (_weight) { 107 107 delete _weight; 108 108 } 109 109 if (_order) { 110 111 } 112 } 113 110 delete _order; 111 } 112 } 113 114 114 public: 115 115 … … 119 119 /// \param graph The undirected graph the algorithm runs on. 120 120 /// \param capacity The edge capacity map. 121 GomoryHu(const Graph& graph, const Capacity& capacity) 121 GomoryHu(const Graph& graph, const Capacity& capacity) 122 122 : _graph(graph), _capacity(capacity), 123 _pred(0), _weight(0), _order(0) 123 _pred(0), _weight(0), _order(0) 124 124 { 125 125 checkConcept<concepts::ReadMap<Edge, Value>, Capacity>(); … … 135 135 136 136 private: 137 137 138 138 // Initialize the internal data structures 139 139 void init() { … … 146 146 } 147 147 (*_pred)[_root] = INVALID; 148 (*_weight)[_root] = std::numeric_limits<Value>::max(); 148 (*_weight)[_root] = std::numeric_limits<Value>::max(); 149 149 } 150 150 … … 155 155 156 156 for (NodeIt n(_graph); n != INVALID; ++n) { 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 157 if (n == _root) continue; 158 159 Node pn = (*_pred)[n]; 160 fa.source(n); 161 fa.target(pn); 162 163 fa.runMinCut(); 164 165 (*_weight)[n] = fa.flowValue(); 166 167 for (NodeIt nn(_graph); nn != INVALID; ++nn) { 168 if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) { 169 (*_pred)[nn] = n; 170 } 171 } 172 if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) { 173 (*_pred)[n] = (*_pred)[pn]; 174 (*_pred)[pn] = n; 175 (*_weight)[n] = (*_weight)[pn]; 176 (*_weight)[pn] = fa.flowValue(); 177 } 178 178 } 179 179 … … 182 182 183 183 for (NodeIt n(_graph); n != INVALID; ++n) { 184 185 186 187 188 189 190 191 192 193 184 std::vector<Node> st; 185 Node nn = n; 186 while ((*_order)[nn] == -1) { 187 st.push_back(nn); 188 nn = (*_pred)[nn]; 189 } 190 while (!st.empty()) { 191 (*_order)[st.back()] = index++; 192 st.pop_back(); 193 } 194 194 } 195 195 } … … 198 198 199 199 ///\name Execution Control 200 200 201 201 ///@{ 202 202 … … 208 208 start(); 209 209 } 210 210 211 211 /// @} 212 212 … … 233 233 /// Gomory-Hu tree. 234 234 /// 235 /// This function returns the weight of the predecessor edge of the 235 /// This function returns the weight of the predecessor edge of the 236 236 /// given node in the Gomory-Hu tree. 237 237 /// If \c node is the root of the tree, the result is undefined. … … 255 255 /// 256 256 /// This function returns the minimum cut value between the nodes 257 /// \c s and \c t. 257 /// \c s and \c t. 258 258 /// It finds the nearest common ancestor of the given nodes in the 259 259 /// Gomory-Hu tree and calculates the minimum weight edge on the … … 264 264 Node sn = s, tn = t; 265 265 Value value = std::numeric_limits<Value>::max(); 266 266 267 267 while (sn != tn) { 268 269 270 271 272 273 274 268 if ((*_order)[sn] < (*_order)[tn]) { 269 if ((*_weight)[tn] <= value) value = (*_weight)[tn]; 270 tn = (*_pred)[tn]; 271 } else { 272 if ((*_weight)[sn] <= value) value = (*_weight)[sn]; 273 sn = (*_pred)[sn]; 274 } 275 275 } 276 276 return value; … … 295 295 /// \pre \ref run() must be called before using this function. 296 296 template <typename CutMap> 297 Value minCutMap(const Node& s, ///< 297 Value minCutMap(const Node& s, ///< 298 298 const Node& t, 299 ///< 299 ///< 300 300 CutMap& cutMap 301 ///< 301 ///< 302 302 ) const { 303 303 Node sn = s, tn = t; … … 305 305 Node rn = INVALID; 306 306 Value value = std::numeric_limits<Value>::max(); 307 307 308 308 while (sn != tn) { 309 310 311 309 if ((*_order)[sn] < (*_order)[tn]) { 310 if ((*_weight)[tn] <= value) { 311 rn = tn; 312 312 s_root = false; 313 314 315 316 317 318 313 value = (*_weight)[tn]; 314 } 315 tn = (*_pred)[tn]; 316 } else { 317 if ((*_weight)[sn] <= value) { 318 rn = sn; 319 319 s_root = true; 320 321 322 323 320 value = (*_weight)[sn]; 321 } 322 sn = (*_pred)[sn]; 323 } 324 324 } 325 325 … … 332 332 std::vector<Node> st; 333 333 for (NodeIt n(_graph); n != INVALID; ++n) { 334 334 st.clear(); 335 335 Node nn = n; 336 337 338 339 340 341 342 343 344 } 345 336 while (!reached[nn]) { 337 st.push_back(nn); 338 nn = (*_pred)[nn]; 339 } 340 while (!st.empty()) { 341 cutMap.set(st.back(), cutMap[nn]); 342 st.pop_back(); 343 } 344 } 345 346 346 return value; 347 347 } … … 352 352 353 353 /// Iterate on the nodes of a minimum cut 354 354 355 355 /// This iterator class lists the nodes of a minimum cut found by 356 356 /// GomoryHu. Before using it, you must allocate a GomoryHu class … … 445 445 } 446 446 }; 447 447 448 448 friend class MinCutEdgeIt; 449 449 450 450 /// Iterate on the edges of a minimum cut 451 451 452 452 /// This iterator class lists the edges of a minimum cut found by 453 453 /// GomoryHu. Before using it, you must allocate a GomoryHu class … … 482 482 } 483 483 } 484 484 485 485 public: 486 486 /// Constructor … … 551 551 } 552 552 /// Postfix incrementation 553 553 554 554 /// Postfix incrementation. 555 555 ///
Note: See TracChangeset
for help on using the changeset viewer.