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