3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_GOMORY_HU_TREE_H
20 #define LEMON_GOMORY_HU_TREE_H
24 #include <lemon/preflow.h>
25 #include <lemon/concept_check.h>
26 #include <lemon/concepts/maps.h>
30 /// \brief Gomory-Hu cut tree in graphs.
36 /// \brief Gomory-Hu cut tree algorithm
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.
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
54 template <typename _Graph,
55 typename _Capacity = typename _Graph::template EdgeMap<int> >
61 /// The capacity on edges
62 typedef _Capacity Capacity;
63 /// The value type of capacities
64 typedef typename Capacity::Value Value;
68 TEMPLATE_GRAPH_TYPEDEFS(Graph);
71 const Capacity& _capacity;
74 typename Graph::template NodeMap<Node>* _pred;
75 typename Graph::template NodeMap<Value>* _weight;
76 typename Graph::template NodeMap<int>* _order;
78 void createStructures() {
80 _pred = new typename Graph::template NodeMap<Node>(_graph);
83 _weight = new typename Graph::template NodeMap<Value>(_graph);
86 _order = new typename Graph::template NodeMap<int>(_graph);
90 void destroyStructures() {
104 /// \brief 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)
113 checkConcept<concepts::ReadMap<Edge, Value>, Capacity>();
117 /// \brief Destructor
124 /// \brief Initializes the internal data structures.
126 /// Initializes the internal data structures.
131 _root = NodeIt(_graph);
132 for (NodeIt n(_graph); n != INVALID; ++n) {
133 _pred->set(n, _root);
136 _pred->set(_root, INVALID);
137 _weight->set(_root, std::numeric_limits<Value>::max());
141 /// \brief Starts the algorithm
143 /// Starts the algorithm.
145 Preflow<Graph, Capacity> fa(_graph, _capacity, _root, INVALID);
147 for (NodeIt n(_graph); n != INVALID; ++n) {
148 if (n == _root) continue;
150 Node pn = (*_pred)[n];
156 _weight->set(n, fa.flowValue());
158 for (NodeIt nn(_graph); nn != INVALID; ++nn) {
159 if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) {
163 if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) {
164 _pred->set(n, (*_pred)[pn]);
166 _weight->set(n, (*_weight)[pn]);
167 _weight->set(pn, fa.flowValue());
171 _order->set(_root, 0);
174 for (NodeIt n(_graph); n != INVALID; ++n) {
175 std::vector<Node> st;
177 while ((*_order)[nn] == -1) {
181 while (!st.empty()) {
182 _order->set(st.back(), index++);
188 /// \brief Runs the Gomory-Hu algorithm.
190 /// Runs the Gomory-Hu algorithm.
191 /// \note gh.run() is just a shortcut of the following code.
201 /// \brief Returns the predecessor node in the Gomory-Hu tree.
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];
209 /// \brief Returns the weight of the predecessor arc in the
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];
219 /// \brief Returns the minimum cut value between two nodes
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
225 Value minCutValue(const Node& s, const Node& t) const {
227 Value value = std::numeric_limits<Value>::max();
230 if ((*_order)[sn] < (*_order)[tn]) {
231 if ((*_weight)[tn] < value) value = (*_weight)[tn];
234 if ((*_weight)[sn] < value) value = (*_weight)[sn];
241 /// \brief Returns the minimum cut between two nodes
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
249 template <typename CutMap>
250 Value minCutMap(const Node& s, const Node& t, CutMap& cutMap) const {
254 Value value = std::numeric_limits<Value>::max();
257 if ((*_order)[sn] < (*_order)[tn]) {
258 if ((*_weight)[tn] < value) {
260 value = (*_weight)[tn];
264 if ((*_weight)[sn] < value) {
266 value = (*_weight)[sn];
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);
278 for (NodeIt n(_graph); n != INVALID; ++n) {
279 std::vector<Node> st;
281 while (!reached[nn]) {
285 while (!st.empty()) {
286 cutMap.set(st.back(), cutMap[nn]);