lemon/gomory_hu.h
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 15 Oct 2009 12:55:41 +0200
changeset 771 8452ca46e29a
parent 596 293551ad254f
child 786 e20173729589
permissions -rw-r--r--
Add citations to the min mean cycle classes (#179, #184)
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
  /// Therefore once this tree is computed, the minimum cut between any pair
alpar@544
    46
  /// of nodes can easily be obtained.
tapolcai@543
    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,
kpeter@546
    63
	    typename CAP>
kpeter@546
    64
#else
kpeter@546
    65
  template <typename GR,
kpeter@546
    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;
tapolcai@543
    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) {
tapolcai@543
    92
	_pred = new typename Graph::template NodeMap<Node>(_graph);
tapolcai@543
    93
      }
tapolcai@543
    94
      if (!_weight) {
tapolcai@543
    95
	_weight = new typename Graph::template NodeMap<Value>(_graph);
tapolcai@543
    96
      }
tapolcai@543
    97
      if (!_order) {
tapolcai@543
    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) {
tapolcai@543
   104
	delete _pred;
tapolcai@543
   105
      }
tapolcai@543
   106
      if (_weight) {
tapolcai@543
   107
	delete _weight;
tapolcai@543
   108
      }
tapolcai@543
   109
      if (_order) {
tapolcai@543
   110
	delete _order;
tapolcai@543
   111
      }
tapolcai@543
   112
    }
tapolcai@543
   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@545
   121
    GomoryHu(const Graph& graph, const Capacity& capacity) 
tapolcai@543
   122
      : _graph(graph), _capacity(capacity),
tapolcai@543
   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:
kpeter@546
   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;
kpeter@581
   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) {
tapolcai@543
   157
	if (n == _root) continue;
tapolcai@543
   158
tapolcai@543
   159
	Node pn = (*_pred)[n];
tapolcai@543
   160
	fa.source(n);
tapolcai@543
   161
	fa.target(pn);
tapolcai@543
   162
tapolcai@543
   163
	fa.runMinCut();
tapolcai@543
   164
kpeter@581
   165
	(*_weight)[n] = fa.flowValue();
tapolcai@543
   166
tapolcai@543
   167
	for (NodeIt nn(_graph); nn != INVALID; ++nn) {
tapolcai@543
   168
	  if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
kpeter@581
   169
	    (*_pred)[nn] = n;
tapolcai@543
   170
	  }
tapolcai@543
   171
	}
tapolcai@543
   172
	if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
kpeter@581
   173
	  (*_pred)[n] = (*_pred)[pn];
kpeter@581
   174
	  (*_pred)[pn] = n;
kpeter@581
   175
	  (*_weight)[n] = (*_weight)[pn];
kpeter@581
   176
	  (*_weight)[pn] = fa.flowValue();
tapolcai@543
   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) {
tapolcai@543
   184
	std::vector<Node> st;
tapolcai@543
   185
	Node nn = n;
tapolcai@543
   186
	while ((*_order)[nn] == -1) {
tapolcai@543
   187
	  st.push_back(nn);
tapolcai@543
   188
	  nn = (*_pred)[nn];
tapolcai@543
   189
	}
tapolcai@543
   190
	while (!st.empty()) {
kpeter@581
   191
	  (*_order)[st.back()] = index++;
tapolcai@543
   192
	  st.pop_back();
tapolcai@543
   193
	}
tapolcai@543
   194
      }
tapolcai@543
   195
    }
tapolcai@543
   196
kpeter@546
   197
  public:
kpeter@546
   198
alpar@544
   199
    ///\name Execution Control
alpar@544
   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@544
   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
    ///
kpeter@596
   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
kpeter@596
   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();
tapolcai@543
   266
      
tapolcai@543
   267
      while (sn != tn) {
tapolcai@543
   268
	if ((*_order)[sn] < (*_order)[tn]) {
alpar@544
   269
	  if ((*_weight)[tn] <= value) value = (*_weight)[tn];
tapolcai@543
   270
	  tn = (*_pred)[tn];
tapolcai@543
   271
	} else {
alpar@544
   272
	  if ((*_weight)[sn] <= value) value = (*_weight)[sn];
tapolcai@543
   273
	  sn = (*_pred)[sn];
tapolcai@543
   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@596
   297
    Value minCutMap(const Node& s, ///< 
alpar@544
   298
                    const Node& t,
kpeter@596
   299
                    ///< 
alpar@544
   300
                    CutMap& cutMap
kpeter@596
   301
                    ///< 
alpar@544
   302
                    ) const {
tapolcai@543
   303
      Node sn = s, tn = t;
alpar@544
   304
      bool s_root=false;
tapolcai@543
   305
      Node rn = INVALID;
tapolcai@543
   306
      Value value = std::numeric_limits<Value>::max();
tapolcai@543
   307
      
tapolcai@543
   308
      while (sn != tn) {
tapolcai@543
   309
	if ((*_order)[sn] < (*_order)[tn]) {
alpar@544
   310
	  if ((*_weight)[tn] <= value) {
tapolcai@543
   311
	    rn = tn;
alpar@544
   312
            s_root = false;
tapolcai@543
   313
	    value = (*_weight)[tn];
tapolcai@543
   314
	  }
tapolcai@543
   315
	  tn = (*_pred)[tn];
tapolcai@543
   316
	} else {
alpar@544
   317
	  if ((*_weight)[sn] <= value) {
tapolcai@543
   318
	    rn = sn;
alpar@544
   319
            s_root = true;
tapolcai@543
   320
	    value = (*_weight)[sn];
tapolcai@543
   321
	  }
tapolcai@543
   322
	  sn = (*_pred)[sn];
tapolcai@543
   323
	}
tapolcai@543
   324
      }
tapolcai@543
   325
tapolcai@543
   326
      typename Graph::template NodeMap<bool> reached(_graph, false);
kpeter@581
   327
      reached[_root] = true;
alpar@544
   328
      cutMap.set(_root, !s_root);
kpeter@581
   329
      reached[rn] = true;
alpar@544
   330
      cutMap.set(rn, s_root);
tapolcai@543
   331
alpar@544
   332
      std::vector<Node> st;
tapolcai@543
   333
      for (NodeIt n(_graph); n != INVALID; ++n) {
alpar@544
   334
	st.clear();
alpar@544
   335
        Node nn = n;
tapolcai@543
   336
	while (!reached[nn]) {
tapolcai@543
   337
	  st.push_back(nn);
tapolcai@543
   338
	  nn = (*_pred)[nn];
tapolcai@543
   339
	}
tapolcai@543
   340
	while (!st.empty()) {
tapolcai@543
   341
	  cutMap.set(st.back(), cutMap[nn]);
tapolcai@543
   342
	  st.pop_back();
tapolcai@543
   343
	}
tapolcai@543
   344
      }
tapolcai@543
   345
      
tapolcai@543
   346
      return value;
tapolcai@543
   347
    }
tapolcai@543
   348
alpar@544
   349
    ///@}
alpar@544
   350
alpar@544
   351
    friend class MinCutNodeIt;
alpar@544
   352
alpar@544
   353
    /// Iterate on the nodes of a minimum cut
alpar@544
   354
    
alpar@544
   355
    /// This iterator class lists the nodes of a minimum cut found by
kpeter@596
   356
    /// GomoryHu. Before using it, you must allocate a GomoryHu class
alpar@545
   357
    /// and call its \ref GomoryHu::run() "run()" method.
alpar@544
   358
    ///
alpar@544
   359
    /// This example counts the nodes in the minimum cut separating \c s from
alpar@544
   360
    /// \c t.
alpar@544
   361
    /// \code
kpeter@713
   362
    /// GomoryHu<Graph> gom(g, capacities);
alpar@544
   363
    /// gom.run();
kpeter@546
   364
    /// int cnt=0;
kpeter@713
   365
    /// for(GomoryHu<Graph>::MinCutNodeIt n(gom,s,t); n!=INVALID; ++n) ++cnt;
alpar@544
   366
    /// \endcode
alpar@544
   367
    class MinCutNodeIt
alpar@544
   368
    {
alpar@544
   369
      bool _side;
alpar@544
   370
      typename Graph::NodeIt _node_it;
alpar@544
   371
      typename Graph::template NodeMap<bool> _cut;
alpar@544
   372
    public:
alpar@544
   373
      /// Constructor
alpar@544
   374
kpeter@546
   375
      /// Constructor.
alpar@544
   376
      ///
alpar@545
   377
      MinCutNodeIt(GomoryHu const &gomory,
alpar@545
   378
                   ///< The GomoryHu class. You must call its
alpar@544
   379
                   ///  run() method
kpeter@546
   380
                   ///  before initializing this iterator.
kpeter@546
   381
                   const Node& s, ///< The base node.
alpar@544
   382
                   const Node& t,
kpeter@546
   383
                   ///< The node you want to separate from node \c s.
alpar@544
   384
                   bool side=true
alpar@544
   385
                   ///< If it is \c true (default) then the iterator lists
alpar@544
   386
                   ///  the nodes of the component containing \c s,
alpar@544
   387
                   ///  otherwise it lists the other component.
alpar@544
   388
                   /// \note As the minimum cut is not always unique,
alpar@544
   389
                   /// \code
alpar@544
   390
                   /// MinCutNodeIt(gomory, s, t, true);
alpar@544
   391
                   /// \endcode
alpar@544
   392
                   /// and
alpar@544
   393
                   /// \code
alpar@544
   394
                   /// MinCutNodeIt(gomory, t, s, false);
alpar@544
   395
                   /// \endcode
alpar@544
   396
                   /// does not necessarily give the same set of nodes.
alpar@544
   397
                   /// However it is ensured that
alpar@544
   398
                   /// \code
alpar@544
   399
                   /// MinCutNodeIt(gomory, s, t, true);
alpar@544
   400
                   /// \endcode
alpar@544
   401
                   /// and
alpar@544
   402
                   /// \code
alpar@544
   403
                   /// MinCutNodeIt(gomory, s, t, false);
alpar@544
   404
                   /// \endcode
alpar@544
   405
                   /// together list each node exactly once.
alpar@544
   406
                   )
alpar@544
   407
        : _side(side), _cut(gomory._graph)
alpar@544
   408
      {
alpar@544
   409
        gomory.minCutMap(s,t,_cut);
alpar@544
   410
        for(_node_it=typename Graph::NodeIt(gomory._graph);
alpar@544
   411
            _node_it!=INVALID && _cut[_node_it]!=_side;
alpar@544
   412
            ++_node_it) {}
alpar@544
   413
      }
kpeter@546
   414
      /// Conversion to \c Node
alpar@544
   415
kpeter@546
   416
      /// Conversion to \c Node.
alpar@544
   417
      ///
alpar@544
   418
      operator typename Graph::Node() const
alpar@544
   419
      {
alpar@544
   420
        return _node_it;
alpar@544
   421
      }
alpar@544
   422
      bool operator==(Invalid) { return _node_it==INVALID; }
alpar@544
   423
      bool operator!=(Invalid) { return _node_it!=INVALID; }
alpar@544
   424
      /// Next node
alpar@544
   425
kpeter@546
   426
      /// Next node.
alpar@544
   427
      ///
alpar@544
   428
      MinCutNodeIt &operator++()
alpar@544
   429
      {
alpar@544
   430
        for(++_node_it;_node_it!=INVALID&&_cut[_node_it]!=_side;++_node_it) {}
alpar@544
   431
        return *this;
alpar@544
   432
      }
alpar@544
   433
      /// Postfix incrementation
alpar@544
   434
kpeter@546
   435
      /// Postfix incrementation.
alpar@544
   436
      ///
alpar@544
   437
      /// \warning This incrementation
kpeter@546
   438
      /// returns a \c Node, not a \c MinCutNodeIt, as one may
alpar@544
   439
      /// expect.
alpar@544
   440
      typename Graph::Node operator++(int)
alpar@544
   441
      {
alpar@544
   442
        typename Graph::Node n=*this;
alpar@544
   443
        ++(*this);
alpar@544
   444
        return n;
alpar@544
   445
      }
alpar@544
   446
    };
alpar@544
   447
    
alpar@544
   448
    friend class MinCutEdgeIt;
alpar@544
   449
    
alpar@544
   450
    /// Iterate on the edges of a minimum cut
alpar@544
   451
    
alpar@544
   452
    /// This iterator class lists the edges of a minimum cut found by
kpeter@596
   453
    /// GomoryHu. Before using it, you must allocate a GomoryHu class
alpar@545
   454
    /// and call its \ref GomoryHu::run() "run()" method.
alpar@544
   455
    ///
alpar@544
   456
    /// This example computes the value of the minimum cut separating \c s from
alpar@544
   457
    /// \c t.
alpar@544
   458
    /// \code
kpeter@713
   459
    /// GomoryHu<Graph> gom(g, capacities);
alpar@544
   460
    /// gom.run();
alpar@544
   461
    /// int value=0;
kpeter@713
   462
    /// for(GomoryHu<Graph>::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e)
alpar@544
   463
    ///   value+=capacities[e];
alpar@544
   464
    /// \endcode
kpeter@596
   465
    /// The result will be the same as the value returned by
kpeter@596
   466
    /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)".
alpar@544
   467
    class MinCutEdgeIt
alpar@544
   468
    {
alpar@544
   469
      bool _side;
alpar@544
   470
      const Graph &_graph;
alpar@544
   471
      typename Graph::NodeIt _node_it;
alpar@544
   472
      typename Graph::OutArcIt _arc_it;
alpar@544
   473
      typename Graph::template NodeMap<bool> _cut;
alpar@544
   474
      void step()
alpar@544
   475
      {
alpar@544
   476
        ++_arc_it;
alpar@544
   477
        while(_node_it!=INVALID && _arc_it==INVALID)
alpar@544
   478
          {
alpar@544
   479
            for(++_node_it;_node_it!=INVALID&&!_cut[_node_it];++_node_it) {}
alpar@544
   480
            if(_node_it!=INVALID)
alpar@544
   481
              _arc_it=typename Graph::OutArcIt(_graph,_node_it);
alpar@544
   482
          }
alpar@544
   483
      }
alpar@544
   484
      
alpar@544
   485
    public:
kpeter@596
   486
      /// Constructor
kpeter@596
   487
kpeter@596
   488
      /// Constructor.
kpeter@596
   489
      ///
alpar@545
   490
      MinCutEdgeIt(GomoryHu const &gomory,
alpar@545
   491
                   ///< The GomoryHu class. You must call its
alpar@544
   492
                   ///  run() method
kpeter@546
   493
                   ///  before initializing this iterator.
kpeter@546
   494
                   const Node& s,  ///< The base node.
alpar@544
   495
                   const Node& t,
kpeter@546
   496
                   ///< The node you want to separate from node \c s.
alpar@544
   497
                   bool side=true
alpar@544
   498
                   ///< If it is \c true (default) then the listed arcs
alpar@544
   499
                   ///  will be oriented from the
kpeter@596
   500
                   ///  nodes of the component containing \c s,
alpar@544
   501
                   ///  otherwise they will be oriented in the opposite
alpar@544
   502
                   ///  direction.
alpar@544
   503
                   )
alpar@544
   504
        : _graph(gomory._graph), _cut(_graph)
alpar@544
   505
      {
alpar@544
   506
        gomory.minCutMap(s,t,_cut);
alpar@544
   507
        if(!side)
alpar@544
   508
          for(typename Graph::NodeIt n(_graph);n!=INVALID;++n)
alpar@544
   509
            _cut[n]=!_cut[n];
alpar@544
   510
alpar@544
   511
        for(_node_it=typename Graph::NodeIt(_graph);
alpar@544
   512
            _node_it!=INVALID && !_cut[_node_it];
alpar@544
   513
            ++_node_it) {}
alpar@544
   514
        _arc_it = _node_it!=INVALID ?
alpar@544
   515
          typename Graph::OutArcIt(_graph,_node_it) : INVALID;
alpar@544
   516
        while(_node_it!=INVALID && _arc_it == INVALID)
alpar@544
   517
          {
alpar@544
   518
            for(++_node_it; _node_it!=INVALID&&!_cut[_node_it]; ++_node_it) {}
alpar@544
   519
            if(_node_it!=INVALID)
alpar@544
   520
              _arc_it= typename Graph::OutArcIt(_graph,_node_it);
alpar@544
   521
          }
alpar@544
   522
        while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
alpar@544
   523
      }
kpeter@546
   524
      /// Conversion to \c Arc
alpar@544
   525
kpeter@546
   526
      /// Conversion to \c Arc.
alpar@544
   527
      ///
alpar@544
   528
      operator typename Graph::Arc() const
alpar@544
   529
      {
alpar@544
   530
        return _arc_it;
alpar@544
   531
      }
kpeter@546
   532
      /// Conversion to \c Edge
alpar@544
   533
kpeter@546
   534
      /// Conversion to \c Edge.
alpar@544
   535
      ///
alpar@544
   536
      operator typename Graph::Edge() const
alpar@544
   537
      {
alpar@544
   538
        return _arc_it;
alpar@544
   539
      }
alpar@544
   540
      bool operator==(Invalid) { return _node_it==INVALID; }
alpar@544
   541
      bool operator!=(Invalid) { return _node_it!=INVALID; }
alpar@544
   542
      /// Next edge
alpar@544
   543
kpeter@546
   544
      /// Next edge.
alpar@544
   545
      ///
alpar@544
   546
      MinCutEdgeIt &operator++()
alpar@544
   547
      {
alpar@544
   548
        step();
alpar@544
   549
        while(_arc_it!=INVALID && _cut[_graph.target(_arc_it)]) step();
alpar@544
   550
        return *this;
alpar@544
   551
      }
alpar@544
   552
      /// Postfix incrementation
alpar@544
   553
      
kpeter@546
   554
      /// Postfix incrementation.
alpar@544
   555
      ///
alpar@544
   556
      /// \warning This incrementation
kpeter@546
   557
      /// returns an \c Arc, not a \c MinCutEdgeIt, as one may expect.
alpar@544
   558
      typename Graph::Arc operator++(int)
alpar@544
   559
      {
alpar@544
   560
        typename Graph::Arc e=*this;
alpar@544
   561
        ++(*this);
alpar@544
   562
        return e;
alpar@544
   563
      }
alpar@544
   564
    };
alpar@544
   565
tapolcai@543
   566
  };
tapolcai@543
   567
tapolcai@543
   568
}
tapolcai@543
   569
tapolcai@543
   570
#endif