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