|
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 |
|
32 namespace 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 |