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