lemon/gomory_hu.h
author Alpar Juttner <alpar@cs.elte.hu>
Mon, 12 Apr 2010 17:05:49 +0200
changeset 887 ca4059d63236
parent 786 e20173729589
child 1080 c5cd8960df74
permissions -rw-r--r--
Merge bugfix #366
alpar@877
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
tapolcai@543
     2
 *
alpar@877
     3
 * This file is a part of LEMON, a generic C++ optimization library.
tapolcai@543
     4
 *
alpar@877
     5
 * Copyright (C) 2003-2010
tapolcai@543
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
tapolcai@543
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
tapolcai@543
     8
 *
tapolcai@543
     9
 * Permission to use, modify and distribute this software is granted
tapolcai@543
    10
 * provided that this copyright notice appears in all copies. For
tapolcai@543
    11
 * precise terms see the accompanying LICENSE file.
tapolcai@543
    12
 *
tapolcai@543
    13
 * This software is provided "AS IS" with no warranty of any kind,
tapolcai@543
    14
 * express or implied, and with no claim as to its suitability for any
tapolcai@543
    15
 * purpose.
tapolcai@543
    16
 *
tapolcai@543
    17
 */
tapolcai@543
    18
tapolcai@543
    19
#ifndef LEMON_GOMORY_HU_TREE_H
tapolcai@543
    20
#define LEMON_GOMORY_HU_TREE_H
tapolcai@543
    21
tapolcai@543
    22
#include <limits>
tapolcai@543
    23
alpar@544
    24
#include <lemon/core.h>
tapolcai@543
    25
#include <lemon/preflow.h>
tapolcai@543
    26
#include <lemon/concept_check.h>
tapolcai@543
    27
#include <lemon/concepts/maps.h>
tapolcai@543
    28
tapolcai@543
    29
/// \ingroup min_cut
alpar@877
    30
/// \file
tapolcai@543
    31
/// \brief Gomory-Hu cut tree in graphs.
tapolcai@543
    32
tapolcai@543
    33
namespace lemon {
tapolcai@543
    34
tapolcai@543
    35
  /// \ingroup min_cut
tapolcai@543
    36
  ///
tapolcai@543
    37
  /// \brief Gomory-Hu cut tree algorithm
tapolcai@543
    38
  ///
kpeter@546
    39
  /// The Gomory-Hu tree is a tree on the node set of a given graph, but it
kpeter@546
    40
  /// may contain edges which are not in the original graph. It has the
alpar@877
    41
  /// property that the minimum capacity edge of the path between two nodes
kpeter@546
    42
  /// in this tree has the same weight as the minimum cut in the graph
alpar@544
    43
  /// between these nodes. Moreover the components obtained by removing
alpar@544
    44
  /// this edge from the tree determine the corresponding minimum cut.
alpar@544
    45
  /// Therefore once this tree is computed, the minimum cut between any pair
alpar@544
    46
  /// of nodes can easily be obtained.
alpar@877
    47
  ///
alpar@544
    48
  /// The algorithm calculates \e n-1 distinct minimum cuts (currently with
kpeter@596
    49
  /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall
kpeter@596
    50
  /// time complexity. It calculates a rooted Gomory-Hu tree.
kpeter@596
    51
  /// The structure of the tree and the edge weights can be
kpeter@596
    52
  /// obtained using \c predNode(), \c predValue() and \c rootDist().
kpeter@596
    53
  /// The functions \c minCutMap() and \c minCutValue() calculate
kpeter@546
    54
  /// the minimum cut and the minimum cut value between any two nodes
kpeter@546
    55
  /// in the graph. You can also list (iterate on) the nodes and the
kpeter@546
    56
  /// edges of the cuts using \c MinCutNodeIt and \c MinCutEdgeIt.
alpar@544
    57
  ///
kpeter@546
    58
  /// \tparam GR The type of the undirected graph the algorithm runs on.
kpeter@596
    59
  /// \tparam CAP The type of the edge map containing the capacities.
kpeter@596
    60
  /// The default map type is \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".
kpeter@546
    61
#ifdef DOXYGEN
alpar@544
    62
  template <typename GR,
alpar@877
    63
            typename CAP>
kpeter@546
    64
#else
kpeter@546
    65
  template <typename GR,
alpar@877
    66
            typename CAP = typename GR::template EdgeMap<int> >
kpeter@546
    67
#endif
alpar@545
    68
  class GomoryHu {
tapolcai@543
    69
  public:
tapolcai@543
    70
kpeter@596
    71
    /// The graph type of the algorithm
alpar@544
    72
    typedef GR Graph;
kpeter@596
    73
    /// The capacity map type of the algorithm
alpar@544
    74
    typedef CAP Capacity;
tapolcai@543
    75
    /// The value type of capacities
tapolcai@543
    76
    typedef typename Capacity::Value Value;
alpar@877
    77
tapolcai@543
    78
  private:
tapolcai@543
    79
tapolcai@543
    80
    TEMPLATE_GRAPH_TYPEDEFS(Graph);
tapolcai@543
    81
tapolcai@543
    82
    const Graph& _graph;
tapolcai@543
    83
    const Capacity& _capacity;
tapolcai@543
    84
tapolcai@543
    85
    Node _root;
tapolcai@543
    86
    typename Graph::template NodeMap<Node>* _pred;
tapolcai@543
    87
    typename Graph::template NodeMap<Value>* _weight;
tapolcai@543
    88
    typename Graph::template NodeMap<int>* _order;
tapolcai@543
    89
tapolcai@543
    90
    void createStructures() {
tapolcai@543
    91
      if (!_pred) {
alpar@877
    92
        _pred = new typename Graph::template NodeMap<Node>(_graph);
tapolcai@543
    93
      }
tapolcai@543
    94
      if (!_weight) {
alpar@877
    95
        _weight = new typename Graph::template NodeMap<Value>(_graph);
tapolcai@543
    96
      }
tapolcai@543
    97
      if (!_order) {
alpar@877
    98
        _order = new typename Graph::template NodeMap<int>(_graph);
tapolcai@543
    99
      }
tapolcai@543
   100
    }
tapolcai@543
   101
tapolcai@543
   102
    void destroyStructures() {
tapolcai@543
   103
      if (_pred) {
alpar@877
   104
        delete _pred;
tapolcai@543
   105
      }
tapolcai@543
   106
      if (_weight) {
alpar@877
   107
        delete _weight;
tapolcai@543
   108
      }
tapolcai@543
   109
      if (_order) {
alpar@877
   110
        delete _order;
tapolcai@543
   111
      }
tapolcai@543
   112
    }
alpar@877
   113
tapolcai@543
   114
  public:
tapolcai@543
   115
tapolcai@543
   116
    /// \brief Constructor
tapolcai@543
   117
    ///
kpeter@596
   118
    /// Constructor.
kpeter@546
   119
    /// \param graph The undirected graph the algorithm runs on.
kpeter@546
   120
    /// \param capacity The edge capacity map.
alpar@877
   121
    GomoryHu(const Graph& graph, const Capacity& capacity)
tapolcai@543
   122
      : _graph(graph), _capacity(capacity),
alpar@877
   123
        _pred(0), _weight(0), _order(0)
tapolcai@543
   124
    {
tapolcai@543
   125
      checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();
tapolcai@543
   126
    }
tapolcai@543
   127
tapolcai@543
   128
tapolcai@543
   129
    /// \brief Destructor
tapolcai@543
   130
    ///
kpeter@596
   131
    /// Destructor.
alpar@545
   132
    ~GomoryHu() {
tapolcai@543
   133
      destroyStructures();
tapolcai@543
   134
    }
tapolcai@543
   135
kpeter@546
   136
  private:
alpar@877
   137
kpeter@546
   138
    // Initialize the internal data structures
tapolcai@543
   139
    void init() {
tapolcai@543
   140
      createStructures();
tapolcai@543
   141
tapolcai@543
   142
      _root = NodeIt(_graph);
tapolcai@543
   143
      for (NodeIt n(_graph); n != INVALID; ++n) {
kpeter@581
   144
        (*_pred)[n] = _root;
kpeter@581
   145
        (*_order)[n] = -1;
tapolcai@543
   146
      }
kpeter@581
   147
      (*_pred)[_root] = INVALID;
alpar@877
   148
      (*_weight)[_root] = std::numeric_limits<Value>::max();
tapolcai@543
   149
    }
tapolcai@543
   150
tapolcai@543
   151
kpeter@546
   152
    // Start the algorithm
tapolcai@543
   153
    void start() {
tapolcai@543
   154
      Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
tapolcai@543
   155
tapolcai@543
   156
      for (NodeIt n(_graph); n != INVALID; ++n) {
alpar@877
   157
        if (n == _root) continue;
tapolcai@543
   158
alpar@877
   159
        Node pn = (*_pred)[n];
alpar@877
   160
        fa.source(n);
alpar@877
   161
        fa.target(pn);
tapolcai@543
   162
alpar@877
   163
        fa.runMinCut();
tapolcai@543
   164
alpar@877
   165
        (*_weight)[n] = fa.flowValue();
tapolcai@543
   166
alpar@877
   167
        for (NodeIt nn(_graph); nn != INVALID; ++nn) {
alpar@877
   168
          if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
alpar@877
   169
            (*_pred)[nn] = n;
alpar@877
   170
          }
alpar@877
   171
        }
alpar@877
   172
        if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
alpar@877
   173
          (*_pred)[n] = (*_pred)[pn];
alpar@877
   174
          (*_pred)[pn] = n;
alpar@877
   175
          (*_weight)[n] = (*_weight)[pn];
alpar@877
   176
          (*_weight)[pn] = fa.flowValue();
alpar@877
   177
        }
tapolcai@543
   178
      }
tapolcai@543
   179
kpeter@581
   180
      (*_order)[_root] = 0;
tapolcai@543
   181
      int index = 1;
tapolcai@543
   182
tapolcai@543
   183
      for (NodeIt n(_graph); n != INVALID; ++n) {
alpar@877
   184
        std::vector<Node> st;
alpar@877
   185
        Node nn = n;
alpar@877
   186
        while ((*_order)[nn] == -1) {
alpar@877
   187
          st.push_back(nn);
alpar@877
   188
          nn = (*_pred)[nn];
alpar@877
   189
        }
alpar@877
   190
        while (!st.empty()) {
alpar@877
   191
          (*_order)[st.back()] = index++;
alpar@877
   192
          st.pop_back();
alpar@877
   193
        }
tapolcai@543
   194
      }
tapolcai@543
   195
    }
tapolcai@543
   196
kpeter@546
   197
  public:
kpeter@546
   198
alpar@544
   199
    ///\name Execution Control
alpar@877
   200
alpar@544
   201
    ///@{
alpar@544
   202
alpar@544
   203
    /// \brief Run the Gomory-Hu algorithm.
tapolcai@543
   204
    ///
alpar@544
   205
    /// This function runs the Gomory-Hu algorithm.
tapolcai@543
   206
    void run() {
tapolcai@543
   207
      init();
tapolcai@543
   208
      start();
tapolcai@543
   209
    }
alpar@877
   210
alpar@544
   211
    /// @}
tapolcai@543
   212
alpar@544
   213
    ///\name Query Functions
alpar@544
   214
    ///The results of the algorithm can be obtained using these
alpar@544
   215
    ///functions.\n
kpeter@596
   216
    ///\ref run() should be called before using them.\n
kpeter@546
   217
    ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt.
alpar@544
   218
alpar@544
   219
    ///@{
alpar@544
   220
alpar@544
   221
    /// \brief Return the predecessor node in the Gomory-Hu tree.
tapolcai@543
   222
    ///
kpeter@596
   223
    /// This function returns the predecessor node of the given node
kpeter@596
   224
    /// in the Gomory-Hu tree.
kpeter@596
   225
    /// If \c node is the root of the tree, then it returns \c INVALID.
kpeter@596
   226
    ///
kpeter@596
   227
    /// \pre \ref run() must be called before using this function.
kpeter@596
   228
    Node predNode(const Node& node) const {
tapolcai@543
   229
      return (*_pred)[node];
tapolcai@543
   230
    }
tapolcai@543
   231
alpar@544
   232
    /// \brief Return the weight of the predecessor edge in the
tapolcai@543
   233
    /// Gomory-Hu tree.
tapolcai@543
   234
    ///
alpar@877
   235
    /// This function returns the weight of the predecessor edge of the
kpeter@596
   236
    /// given node in the Gomory-Hu tree.
kpeter@596
   237
    /// If \c node is the root of the tree, the result is undefined.
kpeter@596
   238
    ///
kpeter@596
   239
    /// \pre \ref run() must be called before using this function.
kpeter@596
   240
    Value predValue(const Node& node) const {
tapolcai@543
   241
      return (*_weight)[node];
tapolcai@543
   242
    }
tapolcai@543
   243
kpeter@596
   244
    /// \brief Return the distance from the root node in the Gomory-Hu tree.
kpeter@596
   245
    ///
kpeter@596
   246
    /// This function returns the distance of the given node from the root
kpeter@596
   247
    /// node in the Gomory-Hu tree.
kpeter@596
   248
    ///
kpeter@596
   249
    /// \pre \ref run() must be called before using this function.
kpeter@596
   250
    int rootDist(const Node& node) const {
kpeter@596
   251
      return (*_order)[node];
kpeter@596
   252
    }
kpeter@596
   253
alpar@544
   254
    /// \brief Return the minimum cut value between two nodes
tapolcai@543
   255
    ///
kpeter@596
   256
    /// This function returns the minimum cut value between the nodes
alpar@877
   257
    /// \c s and \c t.
kpeter@596
   258
    /// It finds the nearest common ancestor of the given nodes in the
kpeter@596
   259
    /// Gomory-Hu tree and calculates the minimum weight edge on the
kpeter@596
   260
    /// paths to the ancestor.
kpeter@596
   261
    ///
kpeter@596
   262
    /// \pre \ref run() must be called before using this function.
tapolcai@543
   263
    Value minCutValue(const Node& s, const Node& t) const {
tapolcai@543
   264
      Node sn = s, tn = t;
tapolcai@543
   265
      Value value = std::numeric_limits<Value>::max();
alpar@877
   266
tapolcai@543
   267
      while (sn != tn) {
alpar@877
   268
        if ((*_order)[sn] < (*_order)[tn]) {
alpar@877
   269
          if ((*_weight)[tn] <= value) value = (*_weight)[tn];
alpar@877
   270
          tn = (*_pred)[tn];
alpar@877
   271
        } else {
alpar@877
   272
          if ((*_weight)[sn] <= value) value = (*_weight)[sn];
alpar@877
   273
          sn = (*_pred)[sn];
alpar@877
   274
        }
tapolcai@543
   275
      }
tapolcai@543
   276
      return value;
tapolcai@543
   277
    }
tapolcai@543
   278
alpar@544
   279
    /// \brief Return the minimum cut between two nodes
tapolcai@543
   280
    ///
alpar@544
   281
    /// This function returns the minimum cut between the nodes \c s and \c t
kpeter@546
   282
    /// in the \c cutMap parameter by setting the nodes in the component of
kpeter@546
   283
    /// \c s to \c true and the other nodes to \c false.
alpar@544
   284
    ///
kpeter@596
   285
    /// For higher level interfaces see MinCutNodeIt and MinCutEdgeIt.
kpeter@596
   286
    ///
kpeter@596
   287
    /// \param s The base node.
kpeter@596
   288
    /// \param t The node you want to separate from node \c s.
kpeter@596
   289
    /// \param cutMap The cut will be returned in this map.
kpeter@596
   290
    /// It must be a \c bool (or convertible) \ref concepts::ReadWriteMap
kpeter@596
   291
    /// "ReadWriteMap" on the graph nodes.
kpeter@596
   292
    ///
kpeter@596
   293
    /// \return The value of the minimum cut between \c s and \c t.
kpeter@596
   294
    ///
kpeter@596
   295
    /// \pre \ref run() must be called before using this function.
tapolcai@543
   296
    template <typename CutMap>
kpeter@786
   297
    Value minCutMap(const Node& s,
alpar@544
   298
                    const Node& t,
alpar@544
   299
                    CutMap& cutMap
alpar@544
   300
                    ) const {
tapolcai@543
   301
      Node sn = s, tn = t;
alpar@544
   302
      bool s_root=false;
tapolcai@543
   303
      Node rn = INVALID;
tapolcai@543
   304
      Value value = std::numeric_limits<Value>::max();
alpar@877
   305
tapolcai@543
   306
      while (sn != tn) {
alpar@877
   307
        if ((*_order)[sn] < (*_order)[tn]) {
alpar@877
   308
          if ((*_weight)[tn] <= value) {
alpar@877
   309
            rn = tn;
alpar@544
   310
            s_root = false;
alpar@877
   311
            value = (*_weight)[tn];
alpar@877
   312
          }
alpar@877
   313
          tn = (*_pred)[tn];
alpar@877
   314
        } else {
alpar@877
   315
          if ((*_weight)[sn] <= value) {
alpar@877
   316
            rn = sn;
alpar@544
   317
            s_root = true;
alpar@877
   318
            value = (*_weight)[sn];
alpar@877
   319
          }
alpar@877
   320
          sn = (*_pred)[sn];
alpar@877
   321
        }
tapolcai@543
   322
      }
tapolcai@543
   323
tapolcai@543
   324
      typename Graph::template NodeMap<bool> reached(_graph, false);
kpeter@581
   325
      reached[_root] = true;
alpar@544
   326
      cutMap.set(_root, !s_root);
kpeter@581
   327
      reached[rn] = true;
alpar@544
   328
      cutMap.set(rn, s_root);
tapolcai@543
   329
alpar@544
   330
      std::vector<Node> st;
tapolcai@543
   331
      for (NodeIt n(_graph); n != INVALID; ++n) {
alpar@877
   332
        st.clear();
alpar@544
   333
        Node nn = n;
alpar@877
   334
        while (!reached[nn]) {
alpar@877
   335
          st.push_back(nn);
alpar@877
   336
          nn = (*_pred)[nn];
alpar@877
   337
        }
alpar@877
   338
        while (!st.empty()) {
alpar@877
   339
          cutMap.set(st.back(), cutMap[nn]);
alpar@877
   340
          st.pop_back();
alpar@877
   341
        }
tapolcai@543
   342
      }
alpar@877
   343
tapolcai@543
   344
      return value;
tapolcai@543
   345
    }
tapolcai@543
   346
alpar@544
   347
    ///@}
alpar@544
   348
alpar@544
   349
    friend class MinCutNodeIt;
alpar@544
   350
alpar@544
   351
    /// Iterate on the nodes of a minimum cut
alpar@877
   352
alpar@544
   353
    /// This iterator class lists the nodes of a minimum cut found by
kpeter@596
   354
    /// GomoryHu. Before using it, you must allocate a GomoryHu class
alpar@545
   355
    /// and call its \ref GomoryHu::run() "run()" method.
alpar@544
   356
    ///
alpar@544
   357
    /// This example counts the nodes in the minimum cut separating \c s from
alpar@544
   358
    /// \c t.
alpar@544
   359
    /// \code
kpeter@713
   360
    /// GomoryHu<Graph> gom(g, capacities);
alpar@544
   361
    /// gom.run();
kpeter@546
   362
    /// int cnt=0;
kpeter@713
   363
    /// for(GomoryHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
alpar@544
   364
    /// \endcode
alpar@544
   365
    class MinCutNodeIt
alpar@544
   366
    {
alpar@544
   367
      bool _side;
alpar@544
   368
      typename Graph::NodeIt _node_it;
alpar@544
   369
      typename Graph::template NodeMap<bool> _cut;
alpar@544
   370
    public:
alpar@544
   371
      /// Constructor
alpar@544
   372
kpeter@546
   373
      /// Constructor.
alpar@544
   374
      ///
alpar@545
   375
      MinCutNodeIt(GomoryHu const &gomory,
alpar@545
   376
                   ///< The GomoryHu class. You must call its
alpar@544
   377
                   ///  run() method
kpeter@546
   378
                   ///  before initializing this iterator.
kpeter@546
   379
                   const Node& s, ///< The base node.
alpar@544
   380
                   const Node& t,
kpeter@546
   381
                   ///< The node you want to separate from node \c s.
alpar@544
   382
                   bool side=true
alpar@544
   383
                   ///< If it is \c true (default) then the iterator lists
alpar@544
   384
                   ///  the nodes of the component containing \c s,
alpar@544
   385
                   ///  otherwise it lists the other component.
alpar@544
   386
                   /// \note As the minimum cut is not always unique,
alpar@544
   387
                   /// \code
alpar@544
   388
                   /// MinCutNodeIt(gomory, s, t, true);
alpar@544
   389
                   /// \endcode
alpar@544
   390
                   /// and
alpar@544
   391
                   /// \code
alpar@544
   392
                   /// MinCutNodeIt(gomory, t, s, false);
alpar@544
   393
                   /// \endcode
alpar@544
   394
                   /// does not necessarily give the same set of nodes.
kpeter@786
   395
                   /// However, it is ensured that
alpar@544
   396
                   /// \code
alpar@544
   397
                   /// MinCutNodeIt(gomory, s, t, true);
alpar@544
   398
                   /// \endcode
alpar@544
   399
                   /// and
alpar@544
   400
                   /// \code
alpar@544
   401
                   /// MinCutNodeIt(gomory, s, t, false);
alpar@544
   402
                   /// \endcode
alpar@544
   403
                   /// together list each node exactly once.
alpar@544
   404
                   )
alpar@544
   405
        : _side(side), _cut(gomory._graph)
alpar@544
   406
      {
alpar@544
   407
        gomory.minCutMap(s,t,_cut);
alpar@544
   408
        for(_node_it=typename Graph::NodeIt(gomory._graph);
alpar@544
   409
            _node_it!=INVALID && _cut[_node_it]!=_side;
alpar@544
   410
            ++_node_it) {}
alpar@544
   411
      }
kpeter@546
   412
      /// Conversion to \c Node
alpar@544
   413
kpeter@546
   414
      /// Conversion to \c Node.
alpar@544
   415
      ///
alpar@544
   416
      operator typename Graph::Node() const
alpar@544
   417
      {
alpar@544
   418
        return _node_it;
alpar@544
   419
      }
alpar@544
   420
      bool operator==(Invalid) { return _node_it==INVALID; }
alpar@544
   421
      bool operator!=(Invalid) { return _node_it!=INVALID; }
alpar@544
   422
      /// Next node
alpar@544
   423
kpeter@546
   424
      /// Next node.
alpar@544
   425
      ///
alpar@544
   426
      MinCutNodeIt &operator++()
alpar@544
   427
      {
alpar@544
   428
        for(++_node_it;_node_it!=INVALID&&_cut[_node_it]!=_side;++_node_it) {}
alpar@544
   429
        return *this;
alpar@544
   430
      }
alpar@544
   431
      /// Postfix incrementation
alpar@544
   432
kpeter@546
   433
      /// Postfix incrementation.
alpar@544
   434
      ///
alpar@544
   435
      /// \warning This incrementation
kpeter@546
   436
      /// returns a \c Node, not a \c MinCutNodeIt, as one may
alpar@544
   437
      /// expect.
alpar@544
   438
      typename Graph::Node operator++(int)
alpar@544
   439
      {
alpar@544
   440
        typename Graph::Node n=*this;
alpar@544
   441
        ++(*this);
alpar@544
   442
        return n;
alpar@544
   443
      }
alpar@544
   444
    };
alpar@877
   445
alpar@544
   446
    friend class MinCutEdgeIt;
alpar@877
   447
alpar@544
   448
    /// Iterate on the edges of a minimum cut
alpar@877
   449
alpar@544
   450
    /// This iterator class lists the edges of a minimum cut found by
kpeter@596
   451
    /// GomoryHu. Before using it, you must allocate a GomoryHu class
alpar@545
   452
    /// and call its \ref GomoryHu::run() "run()" method.
alpar@544
   453
    ///
alpar@544
   454
    /// This example computes the value of the minimum cut separating \c s from
alpar@544
   455
    /// \c t.
alpar@544
   456
    /// \code
kpeter@713
   457
    /// GomoryHu<Graph> gom(g, capacities);
alpar@544
   458
    /// gom.run();
alpar@544
   459
    /// int value=0;
kpeter@713
   460
    /// for(GomoryHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
alpar@544
   461
    ///   value+=capacities[e];
alpar@544
   462
    /// \endcode
kpeter@596
   463
    /// The result will be the same as the value returned by
kpeter@596
   464
    /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)".
alpar@544
   465
    class MinCutEdgeIt
alpar@544
   466
    {
alpar@544
   467
      bool _side;
alpar@544
   468
      const Graph &_graph;
alpar@544
   469
      typename Graph::NodeIt _node_it;
alpar@544
   470
      typename Graph::OutArcIt _arc_it;
alpar@544
   471
      typename Graph::template NodeMap<bool> _cut;
alpar@544
   472
      void step()
alpar@544
   473
      {
alpar@544
   474
        ++_arc_it;
alpar@544
   475
        while(_node_it!=INVALID && _arc_it==INVALID)
alpar@544
   476
          {
alpar@544
   477
            for(++_node_it;_node_it!=INVALID&&!_cut[_node_it];++_node_it) {}
alpar@544
   478
            if(_node_it!=INVALID)
alpar@544
   479
              _arc_it=typename Graph::OutArcIt(_graph,_node_it);
alpar@544
   480
          }
alpar@544
   481
      }
alpar@877
   482
alpar@544
   483
    public:
kpeter@596
   484
      /// Constructor
kpeter@596
   485
kpeter@596
   486
      /// Constructor.
kpeter@596
   487
      ///
alpar@545
   488
      MinCutEdgeIt(GomoryHu const &gomory,
alpar@545
   489
                   ///< The GomoryHu class. You must call its
alpar@544
   490
                   ///  run() method
kpeter@546
   491
                   ///  before initializing this iterator.
kpeter@546
   492
                   const Node& s,  ///< The base node.
alpar@544
   493
                   const Node& t,
kpeter@546
   494
                   ///< The node you want to separate from node \c s.
alpar@544
   495
                   bool side=true
alpar@544
   496
                   ///< If it is \c true (default) then the listed arcs
alpar@544
   497
                   ///  will be oriented from the
kpeter@596
   498
                   ///  nodes of the component containing \c s,
alpar@544
   499
                   ///  otherwise they will be oriented in the opposite
alpar@544
   500
                   ///  direction.
alpar@544
   501
                   )
alpar@544
   502
        : _graph(gomory._graph), _cut(_graph)
alpar@544
   503
      {
alpar@544
   504
        gomory.minCutMap(s,t,_cut);
alpar@544
   505
        if(!side)
alpar@544
   506
          for(typename Graph::NodeIt n(_graph);n!=INVALID;++n)
alpar@544
   507
            _cut[n]=!_cut[n];
alpar@544
   508
alpar@544
   509
        for(_node_it=typename Graph::NodeIt(_graph);
alpar@544
   510
            _node_it!=INVALID && !_cut[_node_it];
alpar@544
   511
            ++_node_it) {}
alpar@544
   512
        _arc_it = _node_it!=INVALID ?
alpar@544
   513
          typename Graph::OutArcIt(_graph,_node_it) : INVALID;
alpar@544
   514
        while(_node_it!=INVALID && _arc_it == INVALID)
alpar@544
   515
          {
alpar@544
   516
            for(++_node_it; _node_it!=INVALID&&!_cut[_node_it]; ++_node_it) {}
alpar@544
   517
            if(_node_it!=INVALID)
alpar@544
   518
              _arc_it= typename Graph::OutArcIt(_graph,_node_it);
alpar@544
   519
          }
alpar@544
   520
        while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
alpar@544
   521
      }
kpeter@546
   522
      /// Conversion to \c Arc
alpar@544
   523
kpeter@546
   524
      /// Conversion to \c Arc.
alpar@544
   525
      ///
alpar@544
   526
      operator typename Graph::Arc() const
alpar@544
   527
      {
alpar@544
   528
        return _arc_it;
alpar@544
   529
      }
kpeter@546
   530
      /// Conversion to \c Edge
alpar@544
   531
kpeter@546
   532
      /// Conversion to \c Edge.
alpar@544
   533
      ///
alpar@544
   534
      operator typename Graph::Edge() const
alpar@544
   535
      {
alpar@544
   536
        return _arc_it;
alpar@544
   537
      }
alpar@544
   538
      bool operator==(Invalid) { return _node_it==INVALID; }
alpar@544
   539
      bool operator!=(Invalid) { return _node_it!=INVALID; }
alpar@544
   540
      /// Next edge
alpar@544
   541
kpeter@546
   542
      /// Next edge.
alpar@544
   543
      ///
alpar@544
   544
      MinCutEdgeIt &operator++()
alpar@544
   545
      {
alpar@544
   546
        step();
alpar@544
   547
        while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
alpar@544
   548
        return *this;
alpar@544
   549
      }
alpar@544
   550
      /// Postfix incrementation
alpar@877
   551
kpeter@546
   552
      /// Postfix incrementation.
alpar@544
   553
      ///
alpar@544
   554
      /// \warning This incrementation
kpeter@546
   555
      /// returns an \c Arc, not a \c MinCutEdgeIt, as one may expect.
alpar@544
   556
      typename Graph::Arc operator++(int)
alpar@544
   557
      {
alpar@544
   558
        typename Graph::Arc e=*this;
alpar@544
   559
        ++(*this);
alpar@544
   560
        return e;
alpar@544
   561
      }
alpar@544
   562
    };
alpar@544
   563
tapolcai@543
   564
  };
tapolcai@543
   565
tapolcai@543
   566
}
tapolcai@543
   567
tapolcai@543
   568
#endif