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