COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/gomory_hu_tree.h @ 2529:93de38566e6c

Last change on this file since 2529:93de38566e6c was 2528:e6bc5c0032e9, checked in by Balazs Dezso, 16 years ago

Gomory-Hu tree algorithm

File size: 7.8 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
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 <lemon/preflow.h>
23#include <lemon/concept_check.h>
24#include <lemon/concepts/maps.h>
25
26/// \ingroup min_cut
27/// \file
28/// \brief Gomory-Hu cut tree in undirected graphs.
29
30namespace lemon {
31
32  /// \ingroup min_cut
33  ///
34  /// \brief Gomory-Hu cut tree algorithm
35  ///
36  /// The Gomory-Hu tree is a tree on the nodeset of the graph, but it
37  /// may contain edges which are not in the original graph. It helps
38  /// to calculate the minimum cut between all pairs of nodes, because
39  /// the minimum capacity edge on the tree path between two nodes has
40  /// the same weight as the minimum cut in the graph between these
41  /// nodes. Moreover this edge separates the nodes to two parts which
42  /// determine this minimum cut.
43  ///
44  /// The algorithm calculates \e n-1 distinict minimum cuts with
45  /// preflow algorithm, therefore the algorithm has
46  /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a
47  /// rooted Gomory-Hu tree, the structure of the tree and the weights
48  /// can be obtained with \c predNode() and \c predValue()
49  /// functions. The \c minCutValue() and \c minCutMap() calculates
50  /// the minimum cut and the minimum cut value between any two node
51  /// in the graph.
52  template <typename _UGraph,
53            typename _Capacity = typename _UGraph::template UEdgeMap<int> >
54  class GomoryHuTree {
55  public:
56
57    /// The undirected graph type
58    typedef _UGraph UGraph;
59    /// The capacity on undirected edges
60    typedef _Capacity Capacity;
61    /// The value type of capacities
62    typedef typename Capacity::Value Value;
63   
64  private:
65
66    UGRAPH_TYPEDEFS(typename UGraph);
67
68    const UGraph& _ugraph;
69    const Capacity& _capacity;
70
71    Node _root;
72    typename UGraph::template NodeMap<Node>* _pred;
73    typename UGraph::template NodeMap<Value>* _weight;
74    typename UGraph::template NodeMap<int>* _order;
75
76    void createStructures() {
77      if (!_pred) {
78        _pred = new typename UGraph::template NodeMap<Node>(_ugraph);
79      }
80      if (!_weight) {
81        _weight = new typename UGraph::template NodeMap<Value>(_ugraph);
82      }
83      if (!_order) {
84        _order = new typename UGraph::template NodeMap<int>(_ugraph);
85      }
86    }
87
88    void destroyStructures() {
89      if (_pred) {
90        delete _pred;
91      }
92      if (_weight) {
93        delete _weight;
94      }
95      if (_order) {
96        delete _order;
97      }
98    }
99 
100  public:
101
102    /// \brief Constructor
103    ///
104    /// Constructor
105    /// \param ugraph The undirected graph type.
106    /// \param capacity The capacity map.
107    GomoryHuTree(const UGraph& ugraph, const Capacity& capacity)
108      : _ugraph(ugraph), _capacity(capacity),
109        _pred(0), _weight(0), _order(0)
110    {
111      checkConcept<concepts::ReadMap<UEdge, Value>, Capacity>();
112    }
113
114
115    /// \brief Destructor
116    ///
117    /// Destructor
118    ~GomoryHuTree() {
119      destroyStructures();
120    }
121
122    /// \brief Initializes the internal data structures.
123    ///
124    /// Initializes the internal data structures.
125    ///
126    void init() {
127      createStructures();
128
129      _root = NodeIt(_ugraph);
130      for (NodeIt n(_ugraph); n != INVALID; ++n) {
131        _pred->set(n, _root);
132        _order->set(n, -1);
133      }
134      _pred->set(_root, INVALID);
135      _weight->set(_root, std::numeric_limits<Value>::max());
136    }
137
138
139    /// \brief Starts the algorithm
140    ///
141    /// Starts the algorithm.
142    void start() {
143      Preflow<UGraph, Capacity> fa(_ugraph, _capacity, _root, INVALID);
144
145      for (NodeIt n(_ugraph); n != INVALID; ++n) {
146        if (n == _root) continue;
147
148        Node pn = (*_pred)[n];
149        fa.source(n);
150        fa.target(pn);
151
152        fa.runMinCut();
153
154        _weight->set(n, fa.flowValue());
155
156        for (NodeIt nn(_ugraph); nn != INVALID; ++nn) {
157          if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
158            _pred->set(nn, n);
159          }
160        }
161        if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
162          _pred->set(n, (*_pred)[pn]);
163          _pred->set(pn, n);
164          _weight->set(n, (*_weight)[pn]);
165          _weight->set(pn, fa.flowValue());     
166        }
167      }
168
169      _order->set(_root, 0);
170      int index = 1;
171
172      for (NodeIt n(_ugraph); n != INVALID; ++n) {
173        std::vector<Node> st;
174        Node nn = n;
175        while ((*_order)[nn] == -1) {
176          st.push_back(nn);
177          nn = (*_pred)[nn];
178        }
179        while (!st.empty()) {
180          _order->set(st.back(), index++);
181          st.pop_back();
182        }
183      }
184    }
185
186    /// \brief Runs the Gomory-Hu algorithm. 
187    ///
188    /// Runs the Gomory-Hu algorithm.
189    /// \note gh.run() is just a shortcut of the following code.
190    /// \code
191    ///   ght.init();
192    ///   ght.start();
193    /// \endcode
194    void run() {
195      init();
196      start();
197    }
198
199    /// \brief Returns the predecessor node in the Gomory-Hu tree.
200    ///
201    /// Returns the predecessor node in the Gomory-Hu tree. If the node is
202    /// the root of the Gomory-Hu tree, then it returns \c INVALID.
203    Node predNode(const Node& node) {
204      return (*_pred)[node];
205    }
206
207    /// \brief Returns the weight of the predecessor edge in the
208    /// Gomory-Hu tree.
209    ///
210    /// Returns the weight of the predecessor edge in the Gomory-Hu
211    /// tree.  If the node is the root of the Gomory-Hu tree, the
212    /// result is undefined.
213    Value predValue(const Node& node) {
214      return (*_weight)[node];
215    }
216
217    /// \brief Returns the minimum cut value between two nodes
218    ///
219    /// Returns the minimum cut value between two nodes. The
220    /// algorithm finds the nearest common ancestor in the Gomory-Hu
221    /// tree and calculates the minimum weight edge on the paths to
222    /// the ancestor.
223    Value minCutValue(const Node& s, const Node& t) const {
224      Node sn = s, tn = t;
225      Value value = std::numeric_limits<Value>::max();
226     
227      while (sn != tn) {
228        if ((*_order)[sn] < (*_order)[tn]) {
229          if ((*_weight)[tn] < value) value = (*_weight)[tn];
230          tn = (*_pred)[tn];
231        } else {
232          if ((*_weight)[sn] < value) value = (*_weight)[sn];
233          sn = (*_pred)[sn];
234        }
235      }
236      return value;
237    }
238
239    /// \brief Returns the minimum cut between two nodes
240    ///
241    /// Returns the minimum cut value between two nodes. The
242    /// algorithm finds the nearest common ancestor in the Gomory-Hu
243    /// tree and calculates the minimum weight edge on the paths to
244    /// the ancestor. Then it sets all nodes to the cut determined by
245    /// this edge. The \c cutMap should be \ref concepts::ReadWriteMap
246    /// "ReadWriteMap".
247    template <typename CutMap>
248    Value minCutMap(const Node& s, const Node& t, CutMap& cutMap) const {
249      Node sn = s, tn = t;
250
251      Node rn = INVALID;
252      Value value = std::numeric_limits<Value>::max();
253     
254      while (sn != tn) {
255        if ((*_order)[sn] < (*_order)[tn]) {
256          if ((*_weight)[tn] < value) {
257            rn = tn;
258            value = (*_weight)[tn];
259          }
260          tn = (*_pred)[tn];
261        } else {
262          if ((*_weight)[sn] < value) {
263            rn = sn;
264            value = (*_weight)[sn];
265          }
266          sn = (*_pred)[sn];
267        }
268      }
269
270      typename UGraph::template NodeMap<bool> reached(_ugraph, false);
271      reached.set(_root, true);
272      cutMap.set(_root, false);
273      reached.set(rn, true);
274      cutMap.set(rn, true);
275
276      for (NodeIt n(_ugraph); n != INVALID; ++n) {
277        std::vector<Node> st;
278        Node nn = n;
279        while (!reached[nn]) {
280          st.push_back(nn);
281          nn = (*_pred)[nn];
282        }
283        while (!st.empty()) {
284          cutMap.set(st.back(), cutMap[nn]);
285          st.pop_back();
286        }
287      }
288     
289      return value;
290    }
291
292  };
293
294}
295
296#endif
Note: See TracBrowser for help on using the repository browser.