[409] | 1 | /* -*- mode: C++; indent-tabs-mode: nil; -*- |
---|
| 2 | * |
---|
| 3 | * This file is a part of LEMON, a generic C++ optimization library. |
---|
| 4 | * |
---|
[1092] | 5 | * Copyright (C) 2003-2013 |
---|
[409] | 6 | * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
---|
| 7 | * (Egervary Research Group on Combinatorial Optimization, EGRES). |
---|
| 8 | * |
---|
| 9 | * Permission to use, modify and distribute this software is granted |
---|
| 10 | * provided that this copyright notice appears in all copies. For |
---|
| 11 | * precise terms see the accompanying LICENSE file. |
---|
| 12 | * |
---|
| 13 | * This software is provided "AS IS" with no warranty of any kind, |
---|
| 14 | * express or implied, and with no claim as to its suitability for any |
---|
| 15 | * purpose. |
---|
| 16 | * |
---|
| 17 | */ |
---|
| 18 | |
---|
| 19 | #ifndef LEMON_HAO_ORLIN_H |
---|
| 20 | #define LEMON_HAO_ORLIN_H |
---|
| 21 | |
---|
| 22 | #include <vector> |
---|
| 23 | #include <list> |
---|
| 24 | #include <limits> |
---|
| 25 | |
---|
| 26 | #include <lemon/maps.h> |
---|
| 27 | #include <lemon/core.h> |
---|
| 28 | #include <lemon/tolerance.h> |
---|
| 29 | |
---|
| 30 | /// \file |
---|
| 31 | /// \ingroup min_cut |
---|
| 32 | /// \brief Implementation of the Hao-Orlin algorithm. |
---|
| 33 | /// |
---|
[877] | 34 | /// Implementation of the Hao-Orlin algorithm for finding a minimum cut |
---|
[596] | 35 | /// in a digraph. |
---|
[409] | 36 | |
---|
| 37 | namespace lemon { |
---|
| 38 | |
---|
| 39 | /// \ingroup min_cut |
---|
| 40 | /// |
---|
[596] | 41 | /// \brief Hao-Orlin algorithm for finding a minimum cut in a digraph. |
---|
[409] | 42 | /// |
---|
[596] | 43 | /// This class implements the Hao-Orlin algorithm for finding a minimum |
---|
[877] | 44 | /// value cut in a directed graph \f$D=(V,A)\f$. |
---|
[596] | 45 | /// It takes a fixed node \f$ source \in V \f$ and |
---|
[409] | 46 | /// consists of two phases: in the first phase it determines a |
---|
| 47 | /// minimum cut with \f$ source \f$ on the source-side (i.e. a set |
---|
[596] | 48 | /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal outgoing |
---|
| 49 | /// capacity) and in the second phase it determines a minimum cut |
---|
[409] | 50 | /// with \f$ source \f$ on the sink-side (i.e. a set |
---|
[596] | 51 | /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal outgoing |
---|
| 52 | /// capacity). Obviously, the smaller of these two cuts will be a |
---|
[409] | 53 | /// minimum cut of \f$ D \f$. The algorithm is a modified |
---|
[596] | 54 | /// preflow push-relabel algorithm. Our implementation calculates |
---|
[409] | 55 | /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the |
---|
[915] | 56 | /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. A notable |
---|
| 57 | /// use of this algorithm is testing network reliability. |
---|
[409] | 58 | /// |
---|
[596] | 59 | /// For an undirected graph you can run just the first phase of the |
---|
| 60 | /// algorithm or you can use the algorithm of Nagamochi and Ibaraki, |
---|
[877] | 61 | /// which solves the undirected problem in \f$ O(nm + n^2 \log n) \f$ |
---|
[596] | 62 | /// time. It is implemented in the NagamochiIbaraki algorithm class. |
---|
| 63 | /// |
---|
| 64 | /// \tparam GR The type of the digraph the algorithm runs on. |
---|
| 65 | /// \tparam CAP The type of the arc map containing the capacities, |
---|
| 66 | /// which can be any numreric type. The default map type is |
---|
| 67 | /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". |
---|
| 68 | /// \tparam TOL Tolerance class for handling inexact computations. The |
---|
[559] | 69 | /// default tolerance type is \ref Tolerance "Tolerance<CAP::Value>". |
---|
[409] | 70 | #ifdef DOXYGEN |
---|
[559] | 71 | template <typename GR, typename CAP, typename TOL> |
---|
[409] | 72 | #else |
---|
[559] | 73 | template <typename GR, |
---|
| 74 | typename CAP = typename GR::template ArcMap<int>, |
---|
| 75 | typename TOL = Tolerance<typename CAP::Value> > |
---|
[409] | 76 | #endif |
---|
| 77 | class HaoOrlin { |
---|
[596] | 78 | public: |
---|
[877] | 79 | |
---|
[596] | 80 | /// The digraph type of the algorithm |
---|
| 81 | typedef GR Digraph; |
---|
| 82 | /// The capacity map type of the algorithm |
---|
| 83 | typedef CAP CapacityMap; |
---|
| 84 | /// The tolerance type of the algorithm |
---|
| 85 | typedef TOL Tolerance; |
---|
| 86 | |
---|
[409] | 87 | private: |
---|
| 88 | |
---|
| 89 | typedef typename CapacityMap::Value Value; |
---|
| 90 | |
---|
[596] | 91 | TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
---|
[409] | 92 | |
---|
| 93 | const Digraph& _graph; |
---|
| 94 | const CapacityMap* _capacity; |
---|
| 95 | |
---|
| 96 | typedef typename Digraph::template ArcMap<Value> FlowMap; |
---|
| 97 | FlowMap* _flow; |
---|
| 98 | |
---|
| 99 | Node _source; |
---|
| 100 | |
---|
| 101 | int _node_num; |
---|
| 102 | |
---|
| 103 | // Bucketing structure |
---|
| 104 | std::vector<Node> _first, _last; |
---|
| 105 | typename Digraph::template NodeMap<Node>* _next; |
---|
| 106 | typename Digraph::template NodeMap<Node>* _prev; |
---|
| 107 | typename Digraph::template NodeMap<bool>* _active; |
---|
| 108 | typename Digraph::template NodeMap<int>* _bucket; |
---|
| 109 | |
---|
| 110 | std::vector<bool> _dormant; |
---|
| 111 | |
---|
| 112 | std::list<std::list<int> > _sets; |
---|
| 113 | std::list<int>::iterator _highest; |
---|
| 114 | |
---|
| 115 | typedef typename Digraph::template NodeMap<Value> ExcessMap; |
---|
| 116 | ExcessMap* _excess; |
---|
| 117 | |
---|
| 118 | typedef typename Digraph::template NodeMap<bool> SourceSetMap; |
---|
| 119 | SourceSetMap* _source_set; |
---|
| 120 | |
---|
| 121 | Value _min_cut; |
---|
| 122 | |
---|
| 123 | typedef typename Digraph::template NodeMap<bool> MinCutMap; |
---|
| 124 | MinCutMap* _min_cut_map; |
---|
| 125 | |
---|
| 126 | Tolerance _tolerance; |
---|
| 127 | |
---|
| 128 | public: |
---|
| 129 | |
---|
| 130 | /// \brief Constructor |
---|
| 131 | /// |
---|
| 132 | /// Constructor of the algorithm class. |
---|
| 133 | HaoOrlin(const Digraph& graph, const CapacityMap& capacity, |
---|
| 134 | const Tolerance& tolerance = Tolerance()) : |
---|
| 135 | _graph(graph), _capacity(&capacity), _flow(0), _source(), |
---|
| 136 | _node_num(), _first(), _last(), _next(0), _prev(0), |
---|
| 137 | _active(0), _bucket(0), _dormant(), _sets(), _highest(), |
---|
| 138 | _excess(0), _source_set(0), _min_cut(), _min_cut_map(0), |
---|
| 139 | _tolerance(tolerance) {} |
---|
| 140 | |
---|
| 141 | ~HaoOrlin() { |
---|
| 142 | if (_min_cut_map) { |
---|
| 143 | delete _min_cut_map; |
---|
| 144 | } |
---|
| 145 | if (_source_set) { |
---|
| 146 | delete _source_set; |
---|
| 147 | } |
---|
| 148 | if (_excess) { |
---|
| 149 | delete _excess; |
---|
| 150 | } |
---|
| 151 | if (_next) { |
---|
| 152 | delete _next; |
---|
| 153 | } |
---|
| 154 | if (_prev) { |
---|
| 155 | delete _prev; |
---|
| 156 | } |
---|
| 157 | if (_active) { |
---|
| 158 | delete _active; |
---|
| 159 | } |
---|
| 160 | if (_bucket) { |
---|
| 161 | delete _bucket; |
---|
| 162 | } |
---|
| 163 | if (_flow) { |
---|
| 164 | delete _flow; |
---|
| 165 | } |
---|
| 166 | } |
---|
| 167 | |
---|
[860] | 168 | /// \brief Set the tolerance used by the algorithm. |
---|
| 169 | /// |
---|
| 170 | /// This function sets the tolerance object used by the algorithm. |
---|
| 171 | /// \return <tt>(*this)</tt> |
---|
| 172 | HaoOrlin& tolerance(const Tolerance& tolerance) { |
---|
| 173 | _tolerance = tolerance; |
---|
| 174 | return *this; |
---|
| 175 | } |
---|
| 176 | |
---|
| 177 | /// \brief Returns a const reference to the tolerance. |
---|
| 178 | /// |
---|
| 179 | /// This function returns a const reference to the tolerance object |
---|
| 180 | /// used by the algorithm. |
---|
| 181 | const Tolerance& tolerance() const { |
---|
| 182 | return _tolerance; |
---|
| 183 | } |
---|
| 184 | |
---|
[409] | 185 | private: |
---|
| 186 | |
---|
| 187 | void activate(const Node& i) { |
---|
[581] | 188 | (*_active)[i] = true; |
---|
[409] | 189 | |
---|
| 190 | int bucket = (*_bucket)[i]; |
---|
| 191 | |
---|
| 192 | if ((*_prev)[i] == INVALID || (*_active)[(*_prev)[i]]) return; |
---|
| 193 | //unlace |
---|
[581] | 194 | (*_next)[(*_prev)[i]] = (*_next)[i]; |
---|
[409] | 195 | if ((*_next)[i] != INVALID) { |
---|
[581] | 196 | (*_prev)[(*_next)[i]] = (*_prev)[i]; |
---|
[409] | 197 | } else { |
---|
| 198 | _last[bucket] = (*_prev)[i]; |
---|
| 199 | } |
---|
| 200 | //lace |
---|
[581] | 201 | (*_next)[i] = _first[bucket]; |
---|
| 202 | (*_prev)[_first[bucket]] = i; |
---|
| 203 | (*_prev)[i] = INVALID; |
---|
[409] | 204 | _first[bucket] = i; |
---|
| 205 | } |
---|
| 206 | |
---|
| 207 | void deactivate(const Node& i) { |
---|
[581] | 208 | (*_active)[i] = false; |
---|
[409] | 209 | int bucket = (*_bucket)[i]; |
---|
| 210 | |
---|
| 211 | if ((*_next)[i] == INVALID || !(*_active)[(*_next)[i]]) return; |
---|
| 212 | |
---|
| 213 | //unlace |
---|
[581] | 214 | (*_prev)[(*_next)[i]] = (*_prev)[i]; |
---|
[409] | 215 | if ((*_prev)[i] != INVALID) { |
---|
[581] | 216 | (*_next)[(*_prev)[i]] = (*_next)[i]; |
---|
[409] | 217 | } else { |
---|
| 218 | _first[bucket] = (*_next)[i]; |
---|
| 219 | } |
---|
| 220 | //lace |
---|
[581] | 221 | (*_prev)[i] = _last[bucket]; |
---|
| 222 | (*_next)[_last[bucket]] = i; |
---|
| 223 | (*_next)[i] = INVALID; |
---|
[409] | 224 | _last[bucket] = i; |
---|
| 225 | } |
---|
| 226 | |
---|
| 227 | void addItem(const Node& i, int bucket) { |
---|
| 228 | (*_bucket)[i] = bucket; |
---|
| 229 | if (_last[bucket] != INVALID) { |
---|
[581] | 230 | (*_prev)[i] = _last[bucket]; |
---|
| 231 | (*_next)[_last[bucket]] = i; |
---|
| 232 | (*_next)[i] = INVALID; |
---|
[409] | 233 | _last[bucket] = i; |
---|
| 234 | } else { |
---|
[581] | 235 | (*_prev)[i] = INVALID; |
---|
[409] | 236 | _first[bucket] = i; |
---|
[581] | 237 | (*_next)[i] = INVALID; |
---|
[409] | 238 | _last[bucket] = i; |
---|
| 239 | } |
---|
| 240 | } |
---|
| 241 | |
---|
| 242 | void findMinCutOut() { |
---|
| 243 | |
---|
| 244 | for (NodeIt n(_graph); n != INVALID; ++n) { |
---|
[581] | 245 | (*_excess)[n] = 0; |
---|
[597] | 246 | (*_source_set)[n] = false; |
---|
[409] | 247 | } |
---|
| 248 | |
---|
| 249 | for (ArcIt a(_graph); a != INVALID; ++a) { |
---|
[581] | 250 | (*_flow)[a] = 0; |
---|
[409] | 251 | } |
---|
| 252 | |
---|
[411] | 253 | int bucket_num = 0; |
---|
| 254 | std::vector<Node> queue(_node_num); |
---|
| 255 | int qfirst = 0, qlast = 0, qsep = 0; |
---|
[409] | 256 | |
---|
| 257 | { |
---|
| 258 | typename Digraph::template NodeMap<bool> reached(_graph, false); |
---|
| 259 | |
---|
[581] | 260 | reached[_source] = true; |
---|
[409] | 261 | bool first_set = true; |
---|
| 262 | |
---|
| 263 | for (NodeIt t(_graph); t != INVALID; ++t) { |
---|
| 264 | if (reached[t]) continue; |
---|
| 265 | _sets.push_front(std::list<int>()); |
---|
[440] | 266 | |
---|
[411] | 267 | queue[qlast++] = t; |
---|
[581] | 268 | reached[t] = true; |
---|
[409] | 269 | |
---|
[411] | 270 | while (qfirst != qlast) { |
---|
| 271 | if (qsep == qfirst) { |
---|
| 272 | ++bucket_num; |
---|
| 273 | _sets.front().push_front(bucket_num); |
---|
| 274 | _dormant[bucket_num] = !first_set; |
---|
| 275 | _first[bucket_num] = _last[bucket_num] = INVALID; |
---|
| 276 | qsep = qlast; |
---|
| 277 | } |
---|
[409] | 278 | |
---|
[411] | 279 | Node n = queue[qfirst++]; |
---|
| 280 | addItem(n, bucket_num); |
---|
| 281 | |
---|
| 282 | for (InArcIt a(_graph, n); a != INVALID; ++a) { |
---|
| 283 | Node u = _graph.source(a); |
---|
| 284 | if (!reached[u] && _tolerance.positive((*_capacity)[a])) { |
---|
[581] | 285 | reached[u] = true; |
---|
[411] | 286 | queue[qlast++] = u; |
---|
[409] | 287 | } |
---|
| 288 | } |
---|
| 289 | } |
---|
| 290 | first_set = false; |
---|
| 291 | } |
---|
| 292 | |
---|
[411] | 293 | ++bucket_num; |
---|
[581] | 294 | (*_bucket)[_source] = 0; |
---|
[409] | 295 | _dormant[0] = true; |
---|
| 296 | } |
---|
[581] | 297 | (*_source_set)[_source] = true; |
---|
[409] | 298 | |
---|
| 299 | Node target = _last[_sets.back().back()]; |
---|
| 300 | { |
---|
| 301 | for (OutArcIt a(_graph, _source); a != INVALID; ++a) { |
---|
| 302 | if (_tolerance.positive((*_capacity)[a])) { |
---|
| 303 | Node u = _graph.target(a); |
---|
[581] | 304 | (*_flow)[a] = (*_capacity)[a]; |
---|
| 305 | (*_excess)[u] += (*_capacity)[a]; |
---|
[409] | 306 | if (!(*_active)[u] && u != _source) { |
---|
| 307 | activate(u); |
---|
| 308 | } |
---|
| 309 | } |
---|
| 310 | } |
---|
| 311 | |
---|
| 312 | if ((*_active)[target]) { |
---|
| 313 | deactivate(target); |
---|
| 314 | } |
---|
| 315 | |
---|
| 316 | _highest = _sets.back().begin(); |
---|
| 317 | while (_highest != _sets.back().end() && |
---|
| 318 | !(*_active)[_first[*_highest]]) { |
---|
| 319 | ++_highest; |
---|
| 320 | } |
---|
| 321 | } |
---|
| 322 | |
---|
| 323 | while (true) { |
---|
| 324 | while (_highest != _sets.back().end()) { |
---|
| 325 | Node n = _first[*_highest]; |
---|
| 326 | Value excess = (*_excess)[n]; |
---|
| 327 | int next_bucket = _node_num; |
---|
| 328 | |
---|
| 329 | int under_bucket; |
---|
| 330 | if (++std::list<int>::iterator(_highest) == _sets.back().end()) { |
---|
| 331 | under_bucket = -1; |
---|
| 332 | } else { |
---|
| 333 | under_bucket = *(++std::list<int>::iterator(_highest)); |
---|
| 334 | } |
---|
| 335 | |
---|
| 336 | for (OutArcIt a(_graph, n); a != INVALID; ++a) { |
---|
| 337 | Node v = _graph.target(a); |
---|
| 338 | if (_dormant[(*_bucket)[v]]) continue; |
---|
| 339 | Value rem = (*_capacity)[a] - (*_flow)[a]; |
---|
| 340 | if (!_tolerance.positive(rem)) continue; |
---|
| 341 | if ((*_bucket)[v] == under_bucket) { |
---|
| 342 | if (!(*_active)[v] && v != target) { |
---|
| 343 | activate(v); |
---|
| 344 | } |
---|
| 345 | if (!_tolerance.less(rem, excess)) { |
---|
[581] | 346 | (*_flow)[a] += excess; |
---|
| 347 | (*_excess)[v] += excess; |
---|
[409] | 348 | excess = 0; |
---|
| 349 | goto no_more_push; |
---|
| 350 | } else { |
---|
| 351 | excess -= rem; |
---|
[581] | 352 | (*_excess)[v] += rem; |
---|
| 353 | (*_flow)[a] = (*_capacity)[a]; |
---|
[409] | 354 | } |
---|
| 355 | } else if (next_bucket > (*_bucket)[v]) { |
---|
| 356 | next_bucket = (*_bucket)[v]; |
---|
| 357 | } |
---|
| 358 | } |
---|
| 359 | |
---|
| 360 | for (InArcIt a(_graph, n); a != INVALID; ++a) { |
---|
| 361 | Node v = _graph.source(a); |
---|
| 362 | if (_dormant[(*_bucket)[v]]) continue; |
---|
| 363 | Value rem = (*_flow)[a]; |
---|
| 364 | if (!_tolerance.positive(rem)) continue; |
---|
| 365 | if ((*_bucket)[v] == under_bucket) { |
---|
| 366 | if (!(*_active)[v] && v != target) { |
---|
| 367 | activate(v); |
---|
| 368 | } |
---|
| 369 | if (!_tolerance.less(rem, excess)) { |
---|
[581] | 370 | (*_flow)[a] -= excess; |
---|
| 371 | (*_excess)[v] += excess; |
---|
[409] | 372 | excess = 0; |
---|
| 373 | goto no_more_push; |
---|
| 374 | } else { |
---|
| 375 | excess -= rem; |
---|
[581] | 376 | (*_excess)[v] += rem; |
---|
| 377 | (*_flow)[a] = 0; |
---|
[409] | 378 | } |
---|
| 379 | } else if (next_bucket > (*_bucket)[v]) { |
---|
| 380 | next_bucket = (*_bucket)[v]; |
---|
| 381 | } |
---|
| 382 | } |
---|
| 383 | |
---|
| 384 | no_more_push: |
---|
| 385 | |
---|
[581] | 386 | (*_excess)[n] = excess; |
---|
[409] | 387 | |
---|
| 388 | if (excess != 0) { |
---|
| 389 | if ((*_next)[n] == INVALID) { |
---|
| 390 | typename std::list<std::list<int> >::iterator new_set = |
---|
| 391 | _sets.insert(--_sets.end(), std::list<int>()); |
---|
| 392 | new_set->splice(new_set->end(), _sets.back(), |
---|
| 393 | _sets.back().begin(), ++_highest); |
---|
| 394 | for (std::list<int>::iterator it = new_set->begin(); |
---|
| 395 | it != new_set->end(); ++it) { |
---|
| 396 | _dormant[*it] = true; |
---|
| 397 | } |
---|
| 398 | while (_highest != _sets.back().end() && |
---|
| 399 | !(*_active)[_first[*_highest]]) { |
---|
| 400 | ++_highest; |
---|
| 401 | } |
---|
| 402 | } else if (next_bucket == _node_num) { |
---|
| 403 | _first[(*_bucket)[n]] = (*_next)[n]; |
---|
[581] | 404 | (*_prev)[(*_next)[n]] = INVALID; |
---|
[409] | 405 | |
---|
| 406 | std::list<std::list<int> >::iterator new_set = |
---|
| 407 | _sets.insert(--_sets.end(), std::list<int>()); |
---|
| 408 | |
---|
| 409 | new_set->push_front(bucket_num); |
---|
[581] | 410 | (*_bucket)[n] = bucket_num; |
---|
[409] | 411 | _first[bucket_num] = _last[bucket_num] = n; |
---|
[581] | 412 | (*_next)[n] = INVALID; |
---|
| 413 | (*_prev)[n] = INVALID; |
---|
[409] | 414 | _dormant[bucket_num] = true; |
---|
| 415 | ++bucket_num; |
---|
| 416 | |
---|
| 417 | while (_highest != _sets.back().end() && |
---|
| 418 | !(*_active)[_first[*_highest]]) { |
---|
| 419 | ++_highest; |
---|
| 420 | } |
---|
| 421 | } else { |
---|
| 422 | _first[*_highest] = (*_next)[n]; |
---|
[581] | 423 | (*_prev)[(*_next)[n]] = INVALID; |
---|
[409] | 424 | |
---|
| 425 | while (next_bucket != *_highest) { |
---|
| 426 | --_highest; |
---|
| 427 | } |
---|
| 428 | |
---|
| 429 | if (_highest == _sets.back().begin()) { |
---|
| 430 | _sets.back().push_front(bucket_num); |
---|
| 431 | _dormant[bucket_num] = false; |
---|
| 432 | _first[bucket_num] = _last[bucket_num] = INVALID; |
---|
| 433 | ++bucket_num; |
---|
| 434 | } |
---|
| 435 | --_highest; |
---|
| 436 | |
---|
[581] | 437 | (*_bucket)[n] = *_highest; |
---|
| 438 | (*_next)[n] = _first[*_highest]; |
---|
[409] | 439 | if (_first[*_highest] != INVALID) { |
---|
[581] | 440 | (*_prev)[_first[*_highest]] = n; |
---|
[409] | 441 | } else { |
---|
| 442 | _last[*_highest] = n; |
---|
| 443 | } |
---|
| 444 | _first[*_highest] = n; |
---|
| 445 | } |
---|
| 446 | } else { |
---|
| 447 | |
---|
| 448 | deactivate(n); |
---|
| 449 | if (!(*_active)[_first[*_highest]]) { |
---|
| 450 | ++_highest; |
---|
| 451 | if (_highest != _sets.back().end() && |
---|
| 452 | !(*_active)[_first[*_highest]]) { |
---|
| 453 | _highest = _sets.back().end(); |
---|
| 454 | } |
---|
| 455 | } |
---|
| 456 | } |
---|
| 457 | } |
---|
| 458 | |
---|
| 459 | if ((*_excess)[target] < _min_cut) { |
---|
| 460 | _min_cut = (*_excess)[target]; |
---|
| 461 | for (NodeIt i(_graph); i != INVALID; ++i) { |
---|
[581] | 462 | (*_min_cut_map)[i] = true; |
---|
[409] | 463 | } |
---|
| 464 | for (std::list<int>::iterator it = _sets.back().begin(); |
---|
| 465 | it != _sets.back().end(); ++it) { |
---|
| 466 | Node n = _first[*it]; |
---|
| 467 | while (n != INVALID) { |
---|
[581] | 468 | (*_min_cut_map)[n] = false; |
---|
[409] | 469 | n = (*_next)[n]; |
---|
| 470 | } |
---|
| 471 | } |
---|
| 472 | } |
---|
| 473 | |
---|
| 474 | { |
---|
| 475 | Node new_target; |
---|
| 476 | if ((*_prev)[target] != INVALID || (*_next)[target] != INVALID) { |
---|
| 477 | if ((*_next)[target] == INVALID) { |
---|
| 478 | _last[(*_bucket)[target]] = (*_prev)[target]; |
---|
| 479 | new_target = (*_prev)[target]; |
---|
| 480 | } else { |
---|
[581] | 481 | (*_prev)[(*_next)[target]] = (*_prev)[target]; |
---|
[409] | 482 | new_target = (*_next)[target]; |
---|
| 483 | } |
---|
| 484 | if ((*_prev)[target] == INVALID) { |
---|
| 485 | _first[(*_bucket)[target]] = (*_next)[target]; |
---|
| 486 | } else { |
---|
[581] | 487 | (*_next)[(*_prev)[target]] = (*_next)[target]; |
---|
[409] | 488 | } |
---|
| 489 | } else { |
---|
| 490 | _sets.back().pop_back(); |
---|
| 491 | if (_sets.back().empty()) { |
---|
| 492 | _sets.pop_back(); |
---|
| 493 | if (_sets.empty()) |
---|
| 494 | break; |
---|
| 495 | for (std::list<int>::iterator it = _sets.back().begin(); |
---|
| 496 | it != _sets.back().end(); ++it) { |
---|
| 497 | _dormant[*it] = false; |
---|
| 498 | } |
---|
| 499 | } |
---|
| 500 | new_target = _last[_sets.back().back()]; |
---|
| 501 | } |
---|
| 502 | |
---|
[581] | 503 | (*_bucket)[target] = 0; |
---|
[409] | 504 | |
---|
[581] | 505 | (*_source_set)[target] = true; |
---|
[409] | 506 | for (OutArcIt a(_graph, target); a != INVALID; ++a) { |
---|
| 507 | Value rem = (*_capacity)[a] - (*_flow)[a]; |
---|
| 508 | if (!_tolerance.positive(rem)) continue; |
---|
| 509 | Node v = _graph.target(a); |
---|
| 510 | if (!(*_active)[v] && !(*_source_set)[v]) { |
---|
| 511 | activate(v); |
---|
| 512 | } |
---|
[581] | 513 | (*_excess)[v] += rem; |
---|
| 514 | (*_flow)[a] = (*_capacity)[a]; |
---|
[409] | 515 | } |
---|
| 516 | |
---|
| 517 | for (InArcIt a(_graph, target); a != INVALID; ++a) { |
---|
| 518 | Value rem = (*_flow)[a]; |
---|
| 519 | if (!_tolerance.positive(rem)) continue; |
---|
| 520 | Node v = _graph.source(a); |
---|
| 521 | if (!(*_active)[v] && !(*_source_set)[v]) { |
---|
| 522 | activate(v); |
---|
| 523 | } |
---|
[581] | 524 | (*_excess)[v] += rem; |
---|
| 525 | (*_flow)[a] = 0; |
---|
[409] | 526 | } |
---|
| 527 | |
---|
| 528 | target = new_target; |
---|
| 529 | if ((*_active)[target]) { |
---|
| 530 | deactivate(target); |
---|
| 531 | } |
---|
| 532 | |
---|
| 533 | _highest = _sets.back().begin(); |
---|
| 534 | while (_highest != _sets.back().end() && |
---|
| 535 | !(*_active)[_first[*_highest]]) { |
---|
| 536 | ++_highest; |
---|
| 537 | } |
---|
| 538 | } |
---|
| 539 | } |
---|
| 540 | } |
---|
| 541 | |
---|
| 542 | void findMinCutIn() { |
---|
| 543 | |
---|
| 544 | for (NodeIt n(_graph); n != INVALID; ++n) { |
---|
[581] | 545 | (*_excess)[n] = 0; |
---|
[597] | 546 | (*_source_set)[n] = false; |
---|
[409] | 547 | } |
---|
| 548 | |
---|
| 549 | for (ArcIt a(_graph); a != INVALID; ++a) { |
---|
[581] | 550 | (*_flow)[a] = 0; |
---|
[409] | 551 | } |
---|
| 552 | |
---|
[411] | 553 | int bucket_num = 0; |
---|
| 554 | std::vector<Node> queue(_node_num); |
---|
| 555 | int qfirst = 0, qlast = 0, qsep = 0; |
---|
[409] | 556 | |
---|
| 557 | { |
---|
| 558 | typename Digraph::template NodeMap<bool> reached(_graph, false); |
---|
| 559 | |
---|
[581] | 560 | reached[_source] = true; |
---|
[409] | 561 | |
---|
| 562 | bool first_set = true; |
---|
| 563 | |
---|
| 564 | for (NodeIt t(_graph); t != INVALID; ++t) { |
---|
| 565 | if (reached[t]) continue; |
---|
| 566 | _sets.push_front(std::list<int>()); |
---|
[440] | 567 | |
---|
[411] | 568 | queue[qlast++] = t; |
---|
[581] | 569 | reached[t] = true; |
---|
[409] | 570 | |
---|
[411] | 571 | while (qfirst != qlast) { |
---|
| 572 | if (qsep == qfirst) { |
---|
| 573 | ++bucket_num; |
---|
| 574 | _sets.front().push_front(bucket_num); |
---|
| 575 | _dormant[bucket_num] = !first_set; |
---|
| 576 | _first[bucket_num] = _last[bucket_num] = INVALID; |
---|
| 577 | qsep = qlast; |
---|
| 578 | } |
---|
[409] | 579 | |
---|
[411] | 580 | Node n = queue[qfirst++]; |
---|
| 581 | addItem(n, bucket_num); |
---|
| 582 | |
---|
| 583 | for (OutArcIt a(_graph, n); a != INVALID; ++a) { |
---|
| 584 | Node u = _graph.target(a); |
---|
| 585 | if (!reached[u] && _tolerance.positive((*_capacity)[a])) { |
---|
[581] | 586 | reached[u] = true; |
---|
[411] | 587 | queue[qlast++] = u; |
---|
[409] | 588 | } |
---|
| 589 | } |
---|
| 590 | } |
---|
| 591 | first_set = false; |
---|
| 592 | } |
---|
| 593 | |
---|
[411] | 594 | ++bucket_num; |
---|
[581] | 595 | (*_bucket)[_source] = 0; |
---|
[409] | 596 | _dormant[0] = true; |
---|
| 597 | } |
---|
[581] | 598 | (*_source_set)[_source] = true; |
---|
[409] | 599 | |
---|
| 600 | Node target = _last[_sets.back().back()]; |
---|
| 601 | { |
---|
| 602 | for (InArcIt a(_graph, _source); a != INVALID; ++a) { |
---|
| 603 | if (_tolerance.positive((*_capacity)[a])) { |
---|
| 604 | Node u = _graph.source(a); |
---|
[581] | 605 | (*_flow)[a] = (*_capacity)[a]; |
---|
| 606 | (*_excess)[u] += (*_capacity)[a]; |
---|
[409] | 607 | if (!(*_active)[u] && u != _source) { |
---|
| 608 | activate(u); |
---|
| 609 | } |
---|
| 610 | } |
---|
| 611 | } |
---|
| 612 | if ((*_active)[target]) { |
---|
| 613 | deactivate(target); |
---|
| 614 | } |
---|
| 615 | |
---|
| 616 | _highest = _sets.back().begin(); |
---|
| 617 | while (_highest != _sets.back().end() && |
---|
| 618 | !(*_active)[_first[*_highest]]) { |
---|
| 619 | ++_highest; |
---|
| 620 | } |
---|
| 621 | } |
---|
| 622 | |
---|
| 623 | |
---|
| 624 | while (true) { |
---|
| 625 | while (_highest != _sets.back().end()) { |
---|
| 626 | Node n = _first[*_highest]; |
---|
| 627 | Value excess = (*_excess)[n]; |
---|
| 628 | int next_bucket = _node_num; |
---|
| 629 | |
---|
| 630 | int under_bucket; |
---|
| 631 | if (++std::list<int>::iterator(_highest) == _sets.back().end()) { |
---|
| 632 | under_bucket = -1; |
---|
| 633 | } else { |
---|
| 634 | under_bucket = *(++std::list<int>::iterator(_highest)); |
---|
| 635 | } |
---|
| 636 | |
---|
| 637 | for (InArcIt a(_graph, n); a != INVALID; ++a) { |
---|
| 638 | Node v = _graph.source(a); |
---|
| 639 | if (_dormant[(*_bucket)[v]]) continue; |
---|
| 640 | Value rem = (*_capacity)[a] - (*_flow)[a]; |
---|
| 641 | if (!_tolerance.positive(rem)) continue; |
---|
| 642 | if ((*_bucket)[v] == under_bucket) { |
---|
| 643 | if (!(*_active)[v] && v != target) { |
---|
| 644 | activate(v); |
---|
| 645 | } |
---|
| 646 | if (!_tolerance.less(rem, excess)) { |
---|
[581] | 647 | (*_flow)[a] += excess; |
---|
| 648 | (*_excess)[v] += excess; |
---|
[409] | 649 | excess = 0; |
---|
| 650 | goto no_more_push; |
---|
| 651 | } else { |
---|
| 652 | excess -= rem; |
---|
[581] | 653 | (*_excess)[v] += rem; |
---|
| 654 | (*_flow)[a] = (*_capacity)[a]; |
---|
[409] | 655 | } |
---|
| 656 | } else if (next_bucket > (*_bucket)[v]) { |
---|
| 657 | next_bucket = (*_bucket)[v]; |
---|
| 658 | } |
---|
| 659 | } |
---|
| 660 | |
---|
| 661 | for (OutArcIt a(_graph, n); a != INVALID; ++a) { |
---|
| 662 | Node v = _graph.target(a); |
---|
| 663 | if (_dormant[(*_bucket)[v]]) continue; |
---|
| 664 | Value rem = (*_flow)[a]; |
---|
| 665 | if (!_tolerance.positive(rem)) continue; |
---|
| 666 | if ((*_bucket)[v] == under_bucket) { |
---|
| 667 | if (!(*_active)[v] && v != target) { |
---|
| 668 | activate(v); |
---|
| 669 | } |
---|
| 670 | if (!_tolerance.less(rem, excess)) { |
---|
[581] | 671 | (*_flow)[a] -= excess; |
---|
| 672 | (*_excess)[v] += excess; |
---|
[409] | 673 | excess = 0; |
---|
| 674 | goto no_more_push; |
---|
| 675 | } else { |
---|
| 676 | excess -= rem; |
---|
[581] | 677 | (*_excess)[v] += rem; |
---|
| 678 | (*_flow)[a] = 0; |
---|
[409] | 679 | } |
---|
| 680 | } else if (next_bucket > (*_bucket)[v]) { |
---|
| 681 | next_bucket = (*_bucket)[v]; |
---|
| 682 | } |
---|
| 683 | } |
---|
| 684 | |
---|
| 685 | no_more_push: |
---|
| 686 | |
---|
[581] | 687 | (*_excess)[n] = excess; |
---|
[409] | 688 | |
---|
| 689 | if (excess != 0) { |
---|
| 690 | if ((*_next)[n] == INVALID) { |
---|
| 691 | typename std::list<std::list<int> >::iterator new_set = |
---|
| 692 | _sets.insert(--_sets.end(), std::list<int>()); |
---|
| 693 | new_set->splice(new_set->end(), _sets.back(), |
---|
| 694 | _sets.back().begin(), ++_highest); |
---|
| 695 | for (std::list<int>::iterator it = new_set->begin(); |
---|
| 696 | it != new_set->end(); ++it) { |
---|
| 697 | _dormant[*it] = true; |
---|
| 698 | } |
---|
| 699 | while (_highest != _sets.back().end() && |
---|
| 700 | !(*_active)[_first[*_highest]]) { |
---|
| 701 | ++_highest; |
---|
| 702 | } |
---|
| 703 | } else if (next_bucket == _node_num) { |
---|
| 704 | _first[(*_bucket)[n]] = (*_next)[n]; |
---|
[581] | 705 | (*_prev)[(*_next)[n]] = INVALID; |
---|
[409] | 706 | |
---|
| 707 | std::list<std::list<int> >::iterator new_set = |
---|
| 708 | _sets.insert(--_sets.end(), std::list<int>()); |
---|
| 709 | |
---|
| 710 | new_set->push_front(bucket_num); |
---|
[581] | 711 | (*_bucket)[n] = bucket_num; |
---|
[409] | 712 | _first[bucket_num] = _last[bucket_num] = n; |
---|
[581] | 713 | (*_next)[n] = INVALID; |
---|
| 714 | (*_prev)[n] = INVALID; |
---|
[409] | 715 | _dormant[bucket_num] = true; |
---|
| 716 | ++bucket_num; |
---|
| 717 | |
---|
| 718 | while (_highest != _sets.back().end() && |
---|
| 719 | !(*_active)[_first[*_highest]]) { |
---|
| 720 | ++_highest; |
---|
| 721 | } |
---|
| 722 | } else { |
---|
| 723 | _first[*_highest] = (*_next)[n]; |
---|
[581] | 724 | (*_prev)[(*_next)[n]] = INVALID; |
---|
[409] | 725 | |
---|
| 726 | while (next_bucket != *_highest) { |
---|
| 727 | --_highest; |
---|
| 728 | } |
---|
| 729 | if (_highest == _sets.back().begin()) { |
---|
| 730 | _sets.back().push_front(bucket_num); |
---|
| 731 | _dormant[bucket_num] = false; |
---|
| 732 | _first[bucket_num] = _last[bucket_num] = INVALID; |
---|
| 733 | ++bucket_num; |
---|
| 734 | } |
---|
| 735 | --_highest; |
---|
| 736 | |
---|
[581] | 737 | (*_bucket)[n] = *_highest; |
---|
| 738 | (*_next)[n] = _first[*_highest]; |
---|
[409] | 739 | if (_first[*_highest] != INVALID) { |
---|
[581] | 740 | (*_prev)[_first[*_highest]] = n; |
---|
[409] | 741 | } else { |
---|
| 742 | _last[*_highest] = n; |
---|
| 743 | } |
---|
| 744 | _first[*_highest] = n; |
---|
| 745 | } |
---|
| 746 | } else { |
---|
| 747 | |
---|
| 748 | deactivate(n); |
---|
| 749 | if (!(*_active)[_first[*_highest]]) { |
---|
| 750 | ++_highest; |
---|
| 751 | if (_highest != _sets.back().end() && |
---|
| 752 | !(*_active)[_first[*_highest]]) { |
---|
| 753 | _highest = _sets.back().end(); |
---|
| 754 | } |
---|
| 755 | } |
---|
| 756 | } |
---|
| 757 | } |
---|
| 758 | |
---|
| 759 | if ((*_excess)[target] < _min_cut) { |
---|
| 760 | _min_cut = (*_excess)[target]; |
---|
| 761 | for (NodeIt i(_graph); i != INVALID; ++i) { |
---|
[581] | 762 | (*_min_cut_map)[i] = false; |
---|
[409] | 763 | } |
---|
| 764 | for (std::list<int>::iterator it = _sets.back().begin(); |
---|
| 765 | it != _sets.back().end(); ++it) { |
---|
| 766 | Node n = _first[*it]; |
---|
| 767 | while (n != INVALID) { |
---|
[581] | 768 | (*_min_cut_map)[n] = true; |
---|
[409] | 769 | n = (*_next)[n]; |
---|
| 770 | } |
---|
| 771 | } |
---|
| 772 | } |
---|
| 773 | |
---|
| 774 | { |
---|
| 775 | Node new_target; |
---|
| 776 | if ((*_prev)[target] != INVALID || (*_next)[target] != INVALID) { |
---|
| 777 | if ((*_next)[target] == INVALID) { |
---|
| 778 | _last[(*_bucket)[target]] = (*_prev)[target]; |
---|
| 779 | new_target = (*_prev)[target]; |
---|
| 780 | } else { |
---|
[581] | 781 | (*_prev)[(*_next)[target]] = (*_prev)[target]; |
---|
[409] | 782 | new_target = (*_next)[target]; |
---|
| 783 | } |
---|
| 784 | if ((*_prev)[target] == INVALID) { |
---|
| 785 | _first[(*_bucket)[target]] = (*_next)[target]; |
---|
| 786 | } else { |
---|
[581] | 787 | (*_next)[(*_prev)[target]] = (*_next)[target]; |
---|
[409] | 788 | } |
---|
| 789 | } else { |
---|
| 790 | _sets.back().pop_back(); |
---|
| 791 | if (_sets.back().empty()) { |
---|
| 792 | _sets.pop_back(); |
---|
| 793 | if (_sets.empty()) |
---|
| 794 | break; |
---|
| 795 | for (std::list<int>::iterator it = _sets.back().begin(); |
---|
| 796 | it != _sets.back().end(); ++it) { |
---|
| 797 | _dormant[*it] = false; |
---|
| 798 | } |
---|
| 799 | } |
---|
| 800 | new_target = _last[_sets.back().back()]; |
---|
| 801 | } |
---|
| 802 | |
---|
[581] | 803 | (*_bucket)[target] = 0; |
---|
[409] | 804 | |
---|
[581] | 805 | (*_source_set)[target] = true; |
---|
[409] | 806 | for (InArcIt a(_graph, target); a != INVALID; ++a) { |
---|
| 807 | Value rem = (*_capacity)[a] - (*_flow)[a]; |
---|
| 808 | if (!_tolerance.positive(rem)) continue; |
---|
| 809 | Node v = _graph.source(a); |
---|
| 810 | if (!(*_active)[v] && !(*_source_set)[v]) { |
---|
| 811 | activate(v); |
---|
| 812 | } |
---|
[581] | 813 | (*_excess)[v] += rem; |
---|
| 814 | (*_flow)[a] = (*_capacity)[a]; |
---|
[409] | 815 | } |
---|
| 816 | |
---|
| 817 | for (OutArcIt a(_graph, target); a != INVALID; ++a) { |
---|
| 818 | Value rem = (*_flow)[a]; |
---|
| 819 | if (!_tolerance.positive(rem)) continue; |
---|
| 820 | Node v = _graph.target(a); |
---|
| 821 | if (!(*_active)[v] && !(*_source_set)[v]) { |
---|
| 822 | activate(v); |
---|
| 823 | } |
---|
[581] | 824 | (*_excess)[v] += rem; |
---|
| 825 | (*_flow)[a] = 0; |
---|
[409] | 826 | } |
---|
| 827 | |
---|
| 828 | target = new_target; |
---|
| 829 | if ((*_active)[target]) { |
---|
| 830 | deactivate(target); |
---|
| 831 | } |
---|
| 832 | |
---|
| 833 | _highest = _sets.back().begin(); |
---|
| 834 | while (_highest != _sets.back().end() && |
---|
| 835 | !(*_active)[_first[*_highest]]) { |
---|
| 836 | ++_highest; |
---|
| 837 | } |
---|
| 838 | } |
---|
| 839 | } |
---|
| 840 | } |
---|
| 841 | |
---|
| 842 | public: |
---|
| 843 | |
---|
[596] | 844 | /// \name Execution Control |
---|
[409] | 845 | /// The simplest way to execute the algorithm is to use |
---|
[559] | 846 | /// one of the member functions called \ref run(). |
---|
[409] | 847 | /// \n |
---|
[596] | 848 | /// If you need better control on the execution, |
---|
| 849 | /// you have to call one of the \ref init() functions first, then |
---|
| 850 | /// \ref calculateOut() and/or \ref calculateIn(). |
---|
[409] | 851 | |
---|
| 852 | /// @{ |
---|
| 853 | |
---|
[596] | 854 | /// \brief Initialize the internal data structures. |
---|
[409] | 855 | /// |
---|
[596] | 856 | /// This function initializes the internal data structures. It creates |
---|
| 857 | /// the maps and some bucket structures for the algorithm. |
---|
| 858 | /// The first node is used as the source node for the push-relabel |
---|
| 859 | /// algorithm. |
---|
[409] | 860 | void init() { |
---|
| 861 | init(NodeIt(_graph)); |
---|
| 862 | } |
---|
| 863 | |
---|
[596] | 864 | /// \brief Initialize the internal data structures. |
---|
[409] | 865 | /// |
---|
[596] | 866 | /// This function initializes the internal data structures. It creates |
---|
[877] | 867 | /// the maps and some bucket structures for the algorithm. |
---|
[596] | 868 | /// The given node is used as the source node for the push-relabel |
---|
| 869 | /// algorithm. |
---|
[409] | 870 | void init(const Node& source) { |
---|
| 871 | _source = source; |
---|
| 872 | |
---|
| 873 | _node_num = countNodes(_graph); |
---|
| 874 | |
---|
[411] | 875 | _first.resize(_node_num); |
---|
| 876 | _last.resize(_node_num); |
---|
[409] | 877 | |
---|
[411] | 878 | _dormant.resize(_node_num); |
---|
[409] | 879 | |
---|
| 880 | if (!_flow) { |
---|
| 881 | _flow = new FlowMap(_graph); |
---|
| 882 | } |
---|
| 883 | if (!_next) { |
---|
| 884 | _next = new typename Digraph::template NodeMap<Node>(_graph); |
---|
| 885 | } |
---|
| 886 | if (!_prev) { |
---|
| 887 | _prev = new typename Digraph::template NodeMap<Node>(_graph); |
---|
| 888 | } |
---|
| 889 | if (!_active) { |
---|
| 890 | _active = new typename Digraph::template NodeMap<bool>(_graph); |
---|
| 891 | } |
---|
| 892 | if (!_bucket) { |
---|
| 893 | _bucket = new typename Digraph::template NodeMap<int>(_graph); |
---|
| 894 | } |
---|
| 895 | if (!_excess) { |
---|
| 896 | _excess = new ExcessMap(_graph); |
---|
| 897 | } |
---|
| 898 | if (!_source_set) { |
---|
| 899 | _source_set = new SourceSetMap(_graph); |
---|
| 900 | } |
---|
| 901 | if (!_min_cut_map) { |
---|
| 902 | _min_cut_map = new MinCutMap(_graph); |
---|
| 903 | } |
---|
| 904 | |
---|
| 905 | _min_cut = std::numeric_limits<Value>::max(); |
---|
| 906 | } |
---|
| 907 | |
---|
| 908 | |
---|
[596] | 909 | /// \brief Calculate a minimum cut with \f$ source \f$ on the |
---|
[409] | 910 | /// source-side. |
---|
| 911 | /// |
---|
[596] | 912 | /// This function calculates a minimum cut with \f$ source \f$ on the |
---|
[412] | 913 | /// source-side (i.e. a set \f$ X\subsetneq V \f$ with |
---|
[596] | 914 | /// \f$ source \in X \f$ and minimal outgoing capacity). |
---|
[915] | 915 | /// It updates the stored cut if (and only if) the newly found one |
---|
| 916 | /// is better. |
---|
[596] | 917 | /// |
---|
| 918 | /// \pre \ref init() must be called before using this function. |
---|
[409] | 919 | void calculateOut() { |
---|
| 920 | findMinCutOut(); |
---|
| 921 | } |
---|
| 922 | |
---|
[596] | 923 | /// \brief Calculate a minimum cut with \f$ source \f$ on the |
---|
| 924 | /// sink-side. |
---|
[409] | 925 | /// |
---|
[596] | 926 | /// This function calculates a minimum cut with \f$ source \f$ on the |
---|
| 927 | /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with |
---|
| 928 | /// \f$ source \notin X \f$ and minimal outgoing capacity). |
---|
[915] | 929 | /// It updates the stored cut if (and only if) the newly found one |
---|
| 930 | /// is better. |
---|
[596] | 931 | /// |
---|
| 932 | /// \pre \ref init() must be called before using this function. |
---|
[409] | 933 | void calculateIn() { |
---|
| 934 | findMinCutIn(); |
---|
| 935 | } |
---|
| 936 | |
---|
| 937 | |
---|
[596] | 938 | /// \brief Run the algorithm. |
---|
[409] | 939 | /// |
---|
[915] | 940 | /// This function runs the algorithm. It chooses source node, |
---|
| 941 | /// then calls \ref init(), \ref calculateOut() |
---|
[409] | 942 | /// and \ref calculateIn(). |
---|
| 943 | void run() { |
---|
| 944 | init(); |
---|
| 945 | calculateOut(); |
---|
| 946 | calculateIn(); |
---|
| 947 | } |
---|
| 948 | |
---|
[596] | 949 | /// \brief Run the algorithm. |
---|
[409] | 950 | /// |
---|
[915] | 951 | /// This function runs the algorithm. It calls \ref init(), |
---|
| 952 | /// \ref calculateOut() and \ref calculateIn() with the given |
---|
| 953 | /// source node. |
---|
[409] | 954 | void run(const Node& s) { |
---|
| 955 | init(s); |
---|
| 956 | calculateOut(); |
---|
| 957 | calculateIn(); |
---|
| 958 | } |
---|
| 959 | |
---|
| 960 | /// @} |
---|
| 961 | |
---|
| 962 | /// \name Query Functions |
---|
| 963 | /// The result of the %HaoOrlin algorithm |
---|
[596] | 964 | /// can be obtained using these functions.\n |
---|
[877] | 965 | /// \ref run(), \ref calculateOut() or \ref calculateIn() |
---|
[596] | 966 | /// should be called before using them. |
---|
[409] | 967 | |
---|
| 968 | /// @{ |
---|
| 969 | |
---|
[596] | 970 | /// \brief Return the value of the minimum cut. |
---|
[409] | 971 | /// |
---|
[915] | 972 | /// This function returns the value of the best cut found by the |
---|
| 973 | /// previously called \ref run(), \ref calculateOut() or \ref |
---|
| 974 | /// calculateIn(). |
---|
[596] | 975 | /// |
---|
[877] | 976 | /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() |
---|
[596] | 977 | /// must be called before using this function. |
---|
[409] | 978 | Value minCutValue() const { |
---|
| 979 | return _min_cut; |
---|
| 980 | } |
---|
| 981 | |
---|
| 982 | |
---|
[596] | 983 | /// \brief Return a minimum cut. |
---|
[409] | 984 | /// |
---|
[915] | 985 | /// This function gives the best cut found by the |
---|
| 986 | /// previously called \ref run(), \ref calculateOut() or \ref |
---|
| 987 | /// calculateIn(). |
---|
| 988 | /// |
---|
| 989 | /// It sets \c cutMap to the characteristic vector of the found |
---|
| 990 | /// minimum value cut - a non-empty set \f$ X\subsetneq V \f$ |
---|
| 991 | /// of minimum outgoing capacity (i.e. \c cutMap will be \c true exactly |
---|
[596] | 992 | /// for the nodes of \f$ X \f$). |
---|
| 993 | /// |
---|
| 994 | /// \param cutMap A \ref concepts::WriteMap "writable" node map with |
---|
| 995 | /// \c bool (or convertible) value type. |
---|
| 996 | /// |
---|
| 997 | /// \return The value of the minimum cut. |
---|
| 998 | /// |
---|
[877] | 999 | /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() |
---|
[596] | 1000 | /// must be called before using this function. |
---|
| 1001 | template <typename CutMap> |
---|
| 1002 | Value minCutMap(CutMap& cutMap) const { |
---|
[409] | 1003 | for (NodeIt it(_graph); it != INVALID; ++it) { |
---|
[596] | 1004 | cutMap.set(it, (*_min_cut_map)[it]); |
---|
[409] | 1005 | } |
---|
| 1006 | return _min_cut; |
---|
| 1007 | } |
---|
| 1008 | |
---|
| 1009 | /// @} |
---|
| 1010 | |
---|
| 1011 | }; //class HaoOrlin |
---|
| 1012 | |
---|
| 1013 | } //namespace lemon |
---|
| 1014 | |
---|
| 1015 | #endif //LEMON_HAO_ORLIN_H |
---|