COIN-OR::LEMON - Graph Library

source: lemon-1.2/lemon/gomory_hu.h @ 902:79fab87ee483

Last change on this file since 902:79fab87ee483 was 877:141f9c0db4a3, checked in by Alpar Juttner <alpar@…>, 10 years ago

Unify the sources (#339)

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