COIN-OR::LEMON - Graph Library

source: lemon/lemon/gomory_hu_tree.h @ 590:924887566bf2

Last change on this file since 590:924887566bf2 was 590:924887566bf2, checked in by Janos Tapolcai <tapolcai@…>, 15 years ago

Porting Gomory-Hu algorithm (#66)

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