jacint@131
|
1 |
// -*- C++ -*-
|
jacint@131
|
2 |
/*
|
jacint@131
|
3 |
preflow.h with 'j_graph interface'
|
jacint@131
|
4 |
by jacint.
|
jacint@131
|
5 |
Heuristics:
|
jacint@131
|
6 |
2 phase
|
jacint@131
|
7 |
gap
|
jacint@131
|
8 |
list 'level_list' on the nodes on level i implemented by hand
|
jacint@131
|
9 |
stack 'active' on the active nodes on level i implemented by hand
|
jacint@131
|
10 |
runs heuristic 'highest label' for H1*n relabels
|
jacint@131
|
11 |
runs heuristic 'bound decrease' for H0*n relabels, starts with 'highest label'
|
jacint@131
|
12 |
|
jacint@131
|
13 |
Parameters H0 and H1 are initialized to 20 and 10.
|
jacint@131
|
14 |
|
jacint@131
|
15 |
The best preflow I could ever write.
|
jacint@131
|
16 |
|
jacint@131
|
17 |
The constructor runs the algorithm.
|
jacint@131
|
18 |
|
jacint@131
|
19 |
Members:
|
jacint@131
|
20 |
|
jacint@131
|
21 |
T maxFlow() : returns the value of a maximum flow
|
jacint@131
|
22 |
|
jacint@131
|
23 |
T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e)
|
jacint@131
|
24 |
|
jacint@131
|
25 |
FlowMap Flow() : returns the fixed maximum flow x
|
jacint@131
|
26 |
|
jacint@131
|
27 |
void minMinCut(CutMap& M) : sets M to the characteristic vector of the
|
jacint@131
|
28 |
minimum min cut. M should be a map of bools initialized to false.
|
jacint@131
|
29 |
|
jacint@131
|
30 |
void maxMinCut(CutMap& M) : sets M to the characteristic vector of the
|
jacint@131
|
31 |
maximum min cut. M should be a map of bools initialized to false.
|
jacint@131
|
32 |
|
jacint@131
|
33 |
void minCut(CutMap& M) : sets M to the characteristic vector of
|
jacint@131
|
34 |
a min cut. M should be a map of bools initialized to false.
|
jacint@131
|
35 |
|
jacint@131
|
36 |
*/
|
jacint@131
|
37 |
|
jacint@131
|
38 |
#ifndef PREFLOW_H
|
jacint@131
|
39 |
#define PREFLOW_H
|
jacint@131
|
40 |
|
jacint@131
|
41 |
#define H0 20
|
jacint@131
|
42 |
#define H1 1
|
jacint@131
|
43 |
|
jacint@131
|
44 |
#include <vector>
|
jacint@131
|
45 |
#include <queue>
|
jacint@131
|
46 |
|
jacint@131
|
47 |
#include<iostream>
|
jacint@131
|
48 |
|
jacint@131
|
49 |
#include <time_measure.h>
|
jacint@131
|
50 |
|
jacint@131
|
51 |
namespace hugo {
|
jacint@131
|
52 |
|
jacint@131
|
53 |
template <typename Graph, typename T,
|
jacint@131
|
54 |
typename FlowMap=typename Graph::EdgeMap<T>,
|
jacint@131
|
55 |
typename CapMap=typename Graph::EdgeMap<T> >
|
jacint@131
|
56 |
class preflow {
|
jacint@131
|
57 |
|
jacint@131
|
58 |
typedef typename Graph::TrivNodeIt NodeIt;
|
jacint@131
|
59 |
typedef typename Graph::TrivEdgeIt EdgeIt;
|
jacint@131
|
60 |
typedef typename Graph::NodeIt EachNodeIt;
|
jacint@131
|
61 |
typedef typename Graph::OutEdgeIt OutEdgeIt;
|
jacint@131
|
62 |
typedef typename Graph::InEdgeIt InEdgeIt;
|
jacint@131
|
63 |
|
jacint@131
|
64 |
Graph& G;
|
jacint@131
|
65 |
NodeIt s;
|
jacint@131
|
66 |
NodeIt t;
|
jacint@131
|
67 |
FlowMap flow;
|
jacint@131
|
68 |
CapMap& capacity;
|
jacint@131
|
69 |
T value;
|
jacint@131
|
70 |
|
jacint@131
|
71 |
public:
|
jacint@131
|
72 |
double time;
|
jacint@131
|
73 |
preflow(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity ) :
|
jacint@131
|
74 |
G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity)
|
jacint@131
|
75 |
{
|
jacint@131
|
76 |
|
jacint@131
|
77 |
bool phase=0; //phase 0 is the 1st phase, phase 1 is the 2nd
|
jacint@131
|
78 |
int n=G.numNodes();
|
jacint@131
|
79 |
int heur0=(int)(H0*n); //time while running 'bound decrease'
|
jacint@131
|
80 |
int heur1=(int)(H1*n); //time while running 'highest label'
|
jacint@131
|
81 |
int heur=heur1; //starting time interval (#of relabels)
|
jacint@131
|
82 |
bool what_heur=1;
|
jacint@131
|
83 |
/*
|
jacint@131
|
84 |
what_heur is 0 in case 'bound decrease'
|
jacint@131
|
85 |
and 1 in case 'highest label'
|
jacint@131
|
86 |
*/
|
jacint@131
|
87 |
bool end=false;
|
jacint@131
|
88 |
/*
|
jacint@131
|
89 |
Needed for 'bound decrease', 'true'
|
jacint@131
|
90 |
means no active nodes are above bound b.
|
jacint@131
|
91 |
*/
|
jacint@131
|
92 |
int relabel=0;
|
jacint@131
|
93 |
int k=n-2; //bound on the highest level under n containing a node
|
jacint@131
|
94 |
int b=k; //bound on the highest level under n of an active node
|
jacint@131
|
95 |
|
jacint@131
|
96 |
typename Graph::NodeMap<int> level(G,n);
|
jacint@131
|
97 |
typename Graph::NodeMap<T> excess(G);
|
jacint@131
|
98 |
|
jacint@131
|
99 |
std::vector<NodeIt> active(n);
|
jacint@131
|
100 |
typename Graph::NodeMap<NodeIt> next(G);
|
jacint@131
|
101 |
//Stack of the active nodes in level i < n.
|
jacint@131
|
102 |
//We use it in both phases.
|
jacint@131
|
103 |
|
jacint@131
|
104 |
typename Graph::NodeMap<NodeIt> left(G);
|
jacint@131
|
105 |
typename Graph::NodeMap<NodeIt> right(G);
|
jacint@131
|
106 |
std::vector<NodeIt> level_list(n);
|
jacint@131
|
107 |
/*
|
jacint@131
|
108 |
List of the nodes in level i<n.
|
jacint@131
|
109 |
*/
|
jacint@131
|
110 |
|
jacint@131
|
111 |
/*Reverse_bfs from t, to find the starting level.*/
|
jacint@131
|
112 |
level.set(t,0);
|
jacint@131
|
113 |
std::queue<NodeIt> bfs_queue;
|
jacint@131
|
114 |
bfs_queue.push(t);
|
jacint@131
|
115 |
|
jacint@131
|
116 |
while (!bfs_queue.empty()) {
|
jacint@131
|
117 |
|
jacint@131
|
118 |
NodeIt v=bfs_queue.front();
|
jacint@131
|
119 |
bfs_queue.pop();
|
jacint@131
|
120 |
int l=level.get(v)+1;
|
jacint@131
|
121 |
|
jacint@131
|
122 |
for(InEdgeIt e=G.firstIn(v); e; G.next(e)) {
|
jacint@131
|
123 |
NodeIt w=G.tail(e);
|
jacint@131
|
124 |
if ( level.get(w) == n && w != s ) {
|
jacint@131
|
125 |
bfs_queue.push(w);
|
jacint@131
|
126 |
NodeIt first=level_list[l];
|
jacint@131
|
127 |
if ( first ) left.set(first,w);
|
jacint@131
|
128 |
right.set(w,first);
|
jacint@131
|
129 |
level_list[l]=w;
|
jacint@131
|
130 |
level.set(w, l);
|
jacint@131
|
131 |
}
|
jacint@131
|
132 |
}
|
jacint@131
|
133 |
}
|
jacint@131
|
134 |
|
jacint@131
|
135 |
level.set(s,n);
|
jacint@131
|
136 |
|
jacint@131
|
137 |
|
jacint@131
|
138 |
/* Starting flow. It is everywhere 0 at the moment. */
|
jacint@131
|
139 |
for(OutEdgeIt e=G.firstOut(s); e; G.next(e))
|
jacint@131
|
140 |
{
|
jacint@131
|
141 |
T c=capacity.get(e);
|
jacint@131
|
142 |
if ( c == 0 ) continue;
|
jacint@131
|
143 |
NodeIt w=G.head(e);
|
jacint@131
|
144 |
if ( level.get(w) < n ) {
|
jacint@131
|
145 |
if ( excess.get(w) == 0 && w!=t ) {
|
jacint@131
|
146 |
next.set(w,active[level.get(w)]);
|
jacint@131
|
147 |
active[level.get(w)]=w;
|
jacint@131
|
148 |
}
|
jacint@131
|
149 |
flow.set(e, c);
|
jacint@131
|
150 |
excess.set(w, excess.get(w)+c);
|
jacint@131
|
151 |
}
|
jacint@131
|
152 |
}
|
jacint@131
|
153 |
|
jacint@131
|
154 |
/*
|
jacint@131
|
155 |
End of preprocessing
|
jacint@131
|
156 |
*/
|
jacint@131
|
157 |
|
jacint@131
|
158 |
|
jacint@131
|
159 |
|
jacint@131
|
160 |
/*
|
jacint@131
|
161 |
Push/relabel on the highest level active nodes.
|
jacint@131
|
162 |
*/
|
jacint@131
|
163 |
while ( true ) {
|
jacint@131
|
164 |
|
jacint@131
|
165 |
if ( b == 0 ) {
|
jacint@131
|
166 |
if ( phase ) break;
|
jacint@131
|
167 |
|
jacint@131
|
168 |
if ( !what_heur && !end && k > 0 ) {
|
jacint@131
|
169 |
b=k;
|
jacint@131
|
170 |
end=true;
|
jacint@131
|
171 |
} else {
|
jacint@131
|
172 |
phase=1;
|
jacint@131
|
173 |
time=currTime();
|
jacint@131
|
174 |
level.set(s,0);
|
jacint@131
|
175 |
std::queue<NodeIt> bfs_queue;
|
jacint@131
|
176 |
bfs_queue.push(s);
|
jacint@131
|
177 |
|
jacint@131
|
178 |
while (!bfs_queue.empty()) {
|
jacint@131
|
179 |
|
jacint@131
|
180 |
NodeIt v=bfs_queue.front();
|
jacint@131
|
181 |
bfs_queue.pop();
|
jacint@131
|
182 |
int l=level.get(v)+1;
|
jacint@131
|
183 |
|
jacint@131
|
184 |
for(InEdgeIt e=G.firstIn(v); e; G.next(e)) {
|
jacint@131
|
185 |
if ( capacity.get(e) == flow.get(e) ) continue;
|
jacint@131
|
186 |
NodeIt u=G.tail(e);
|
jacint@131
|
187 |
if ( level.get(u) >= n ) {
|
jacint@131
|
188 |
bfs_queue.push(u);
|
jacint@131
|
189 |
level.set(u, l);
|
jacint@131
|
190 |
if ( excess.get(u) > 0 ) {
|
jacint@131
|
191 |
next.set(u,active[l]);
|
jacint@131
|
192 |
active[l]=u;
|
jacint@131
|
193 |
}
|
jacint@131
|
194 |
}
|
jacint@131
|
195 |
}
|
jacint@131
|
196 |
|
jacint@131
|
197 |
for(OutEdgeIt e=G.firstOut(v); e; G.next(e)) {
|
jacint@131
|
198 |
if ( 0 == flow.get(e) ) continue;
|
jacint@131
|
199 |
NodeIt u=G.head(e);
|
jacint@131
|
200 |
if ( level.get(u) >= n ) {
|
jacint@131
|
201 |
bfs_queue.push(u);
|
jacint@131
|
202 |
level.set(u, l);
|
jacint@131
|
203 |
if ( excess.get(u) > 0 ) {
|
jacint@131
|
204 |
next.set(u,active[l]);
|
jacint@131
|
205 |
active[l]=u;
|
jacint@131
|
206 |
}
|
jacint@131
|
207 |
}
|
jacint@131
|
208 |
}
|
jacint@131
|
209 |
}
|
jacint@131
|
210 |
b=n-2;
|
jacint@131
|
211 |
}
|
jacint@131
|
212 |
|
jacint@131
|
213 |
}
|
jacint@131
|
214 |
|
jacint@131
|
215 |
|
jacint@131
|
216 |
if ( !active[b] ) --b;
|
jacint@131
|
217 |
else {
|
jacint@131
|
218 |
end=false;
|
jacint@131
|
219 |
|
jacint@131
|
220 |
NodeIt w=active[b];
|
jacint@131
|
221 |
active[b]=next.get(w);
|
jacint@131
|
222 |
int lev=level.get(w);
|
jacint@131
|
223 |
T exc=excess.get(w);
|
jacint@131
|
224 |
int newlevel=n; //bound on the next level of w
|
jacint@131
|
225 |
|
jacint@131
|
226 |
for(OutEdgeIt e=G.firstOut(w); e; G.next(e)) {
|
jacint@131
|
227 |
|
jacint@131
|
228 |
if ( flow.get(e) == capacity.get(e) ) continue;
|
jacint@131
|
229 |
NodeIt v=G.head(e);
|
jacint@131
|
230 |
//e=wv
|
jacint@131
|
231 |
|
jacint@131
|
232 |
if( lev > level.get(v) ) {
|
jacint@131
|
233 |
/*Push is allowed now*/
|
jacint@131
|
234 |
|
jacint@131
|
235 |
if ( excess.get(v)==0 && v!=t && v!=s ) {
|
jacint@131
|
236 |
int lev_v=level.get(v);
|
jacint@131
|
237 |
next.set(v,active[lev_v]);
|
jacint@131
|
238 |
active[lev_v]=v;
|
jacint@131
|
239 |
}
|
jacint@131
|
240 |
|
jacint@131
|
241 |
T cap=capacity.get(e);
|
jacint@131
|
242 |
T flo=flow.get(e);
|
jacint@131
|
243 |
T remcap=cap-flo;
|
jacint@131
|
244 |
|
jacint@131
|
245 |
if ( remcap >= exc ) {
|
jacint@131
|
246 |
/*A nonsaturating push.*/
|
jacint@131
|
247 |
|
jacint@131
|
248 |
flow.set(e, flo+exc);
|
jacint@131
|
249 |
excess.set(v, excess.get(v)+exc);
|
jacint@131
|
250 |
exc=0;
|
jacint@131
|
251 |
break;
|
jacint@131
|
252 |
|
jacint@131
|
253 |
} else {
|
jacint@131
|
254 |
/*A saturating push.*/
|
jacint@131
|
255 |
|
jacint@131
|
256 |
flow.set(e, cap);
|
jacint@131
|
257 |
excess.set(v, excess.get(v)+remcap);
|
jacint@131
|
258 |
exc-=remcap;
|
jacint@131
|
259 |
}
|
jacint@131
|
260 |
} else if ( newlevel > level.get(v) ){
|
jacint@131
|
261 |
newlevel = level.get(v);
|
jacint@131
|
262 |
}
|
jacint@131
|
263 |
|
jacint@131
|
264 |
} //for out edges wv
|
jacint@131
|
265 |
|
jacint@131
|
266 |
|
jacint@131
|
267 |
if ( exc > 0 ) {
|
jacint@131
|
268 |
for( InEdgeIt e=G.firstIn(w); e; G.next(e)) {
|
jacint@131
|
269 |
|
jacint@131
|
270 |
if( flow.get(e) == 0 ) continue;
|
jacint@131
|
271 |
NodeIt v=G.tail(e);
|
jacint@131
|
272 |
//e=vw
|
jacint@131
|
273 |
|
jacint@131
|
274 |
if( lev > level.get(v) ) {
|
jacint@131
|
275 |
/*Push is allowed now*/
|
jacint@131
|
276 |
|
jacint@131
|
277 |
if ( excess.get(v)==0 && v!=t && v!=s ) {
|
jacint@131
|
278 |
int lev_v=level.get(v);
|
jacint@131
|
279 |
next.set(v,active[lev_v]);
|
jacint@131
|
280 |
active[lev_v]=v;
|
jacint@131
|
281 |
}
|
jacint@131
|
282 |
|
jacint@131
|
283 |
T flo=flow.get(e);
|
jacint@131
|
284 |
|
jacint@131
|
285 |
if ( flo >= exc ) {
|
jacint@131
|
286 |
/*A nonsaturating push.*/
|
jacint@131
|
287 |
|
jacint@131
|
288 |
flow.set(e, flo-exc);
|
jacint@131
|
289 |
excess.set(v, excess.get(v)+exc);
|
jacint@131
|
290 |
exc=0;
|
jacint@131
|
291 |
break;
|
jacint@131
|
292 |
} else {
|
jacint@131
|
293 |
/*A saturating push.*/
|
jacint@131
|
294 |
|
jacint@131
|
295 |
excess.set(v, excess.get(v)+flo);
|
jacint@131
|
296 |
exc-=flo;
|
jacint@131
|
297 |
flow.set(e,0);
|
jacint@131
|
298 |
}
|
jacint@131
|
299 |
} else if ( newlevel > level.get(v) ) {
|
jacint@131
|
300 |
newlevel = level.get(v);
|
jacint@131
|
301 |
}
|
jacint@131
|
302 |
} //for in edges vw
|
jacint@131
|
303 |
|
jacint@131
|
304 |
} // if w still has excess after the out edge for cycle
|
jacint@131
|
305 |
|
jacint@131
|
306 |
excess.set(w, exc);
|
jacint@131
|
307 |
|
jacint@131
|
308 |
/*
|
jacint@131
|
309 |
Relabel
|
jacint@131
|
310 |
*/
|
jacint@131
|
311 |
|
jacint@131
|
312 |
|
jacint@131
|
313 |
if ( exc > 0 ) {
|
jacint@131
|
314 |
//now 'lev' is the old level of w
|
jacint@131
|
315 |
|
jacint@131
|
316 |
if ( phase ) {
|
jacint@131
|
317 |
level.set(w,++newlevel);
|
jacint@131
|
318 |
next.set(w,active[newlevel]);
|
jacint@131
|
319 |
active[newlevel]=w;
|
jacint@131
|
320 |
b=newlevel;
|
jacint@131
|
321 |
} else {
|
jacint@131
|
322 |
//unlacing starts
|
jacint@131
|
323 |
NodeIt right_n=right.get(w);
|
jacint@131
|
324 |
NodeIt left_n=left.get(w);
|
jacint@131
|
325 |
|
jacint@131
|
326 |
if ( right_n ) {
|
jacint@131
|
327 |
if ( left_n ) {
|
jacint@131
|
328 |
right.set(left_n, right_n);
|
jacint@131
|
329 |
left.set(right_n, left_n);
|
jacint@131
|
330 |
} else {
|
jacint@131
|
331 |
level_list[lev]=right_n;
|
jacint@131
|
332 |
left.set(right_n, NodeIt());
|
jacint@131
|
333 |
}
|
jacint@131
|
334 |
} else {
|
jacint@131
|
335 |
if ( left_n ) {
|
jacint@131
|
336 |
right.set(left_n, NodeIt());
|
jacint@131
|
337 |
} else {
|
jacint@131
|
338 |
level_list[lev]=NodeIt();
|
jacint@131
|
339 |
|
jacint@131
|
340 |
}
|
jacint@131
|
341 |
}
|
jacint@131
|
342 |
//unlacing ends
|
jacint@131
|
343 |
|
jacint@131
|
344 |
//gapping starts
|
jacint@131
|
345 |
if ( !level_list[lev] ) {
|
jacint@131
|
346 |
|
jacint@131
|
347 |
for (int i=lev; i!=k ; ) {
|
jacint@131
|
348 |
NodeIt v=level_list[++i];
|
jacint@131
|
349 |
while ( v ) {
|
jacint@131
|
350 |
level.set(v,n);
|
jacint@131
|
351 |
v=right.get(v);
|
jacint@131
|
352 |
}
|
jacint@140
|
353 |
level_list[i]=NodeIt();
|
jacint@131
|
354 |
if ( !what_heur ) active[i]=NodeIt();
|
jacint@131
|
355 |
}
|
jacint@131
|
356 |
|
jacint@131
|
357 |
level.set(w,n);
|
jacint@131
|
358 |
b=lev-1;
|
jacint@131
|
359 |
k=b;
|
jacint@131
|
360 |
//gapping ends
|
jacint@131
|
361 |
} else {
|
jacint@131
|
362 |
|
jacint@131
|
363 |
if ( newlevel == n ) level.set(w,n);
|
jacint@131
|
364 |
else {
|
jacint@131
|
365 |
level.set(w,++newlevel);
|
jacint@131
|
366 |
next.set(w,active[newlevel]);
|
jacint@131
|
367 |
active[newlevel]=w;
|
jacint@131
|
368 |
if ( what_heur ) b=newlevel;
|
jacint@131
|
369 |
if ( k < newlevel ) ++k;
|
jacint@131
|
370 |
NodeIt first=level_list[newlevel];
|
jacint@131
|
371 |
if ( first ) left.set(first,w);
|
jacint@131
|
372 |
right.set(w,first);
|
jacint@131
|
373 |
left.set(w,NodeIt());
|
jacint@131
|
374 |
level_list[newlevel]=w;
|
jacint@131
|
375 |
}
|
jacint@131
|
376 |
}
|
jacint@131
|
377 |
|
jacint@131
|
378 |
|
jacint@131
|
379 |
++relabel;
|
jacint@131
|
380 |
if ( relabel >= heur ) {
|
jacint@131
|
381 |
relabel=0;
|
jacint@131
|
382 |
if ( what_heur ) {
|
jacint@131
|
383 |
what_heur=0;
|
jacint@131
|
384 |
heur=heur0;
|
jacint@131
|
385 |
end=false;
|
jacint@131
|
386 |
} else {
|
jacint@131
|
387 |
what_heur=1;
|
jacint@131
|
388 |
heur=heur1;
|
jacint@131
|
389 |
b=k;
|
jacint@131
|
390 |
}
|
jacint@131
|
391 |
}
|
jacint@131
|
392 |
} //phase 0
|
jacint@131
|
393 |
|
jacint@131
|
394 |
|
jacint@131
|
395 |
} // if ( exc > 0 )
|
jacint@131
|
396 |
|
jacint@131
|
397 |
|
jacint@131
|
398 |
} // if stack[b] is nonempty
|
jacint@131
|
399 |
|
jacint@131
|
400 |
} // while(true)
|
jacint@131
|
401 |
|
jacint@131
|
402 |
|
jacint@131
|
403 |
value = excess.get(t);
|
jacint@131
|
404 |
/*Max flow value.*/
|
jacint@131
|
405 |
|
jacint@131
|
406 |
} //void run()
|
jacint@131
|
407 |
|
jacint@131
|
408 |
|
jacint@131
|
409 |
|
jacint@131
|
410 |
|
jacint@131
|
411 |
|
jacint@131
|
412 |
/*
|
jacint@131
|
413 |
Returns the maximum value of a flow.
|
jacint@131
|
414 |
*/
|
jacint@131
|
415 |
|
jacint@131
|
416 |
T maxFlow() {
|
jacint@131
|
417 |
return value;
|
jacint@131
|
418 |
}
|
jacint@131
|
419 |
|
jacint@131
|
420 |
|
jacint@131
|
421 |
|
jacint@131
|
422 |
/*
|
jacint@131
|
423 |
For the maximum flow x found by the algorithm,
|
jacint@131
|
424 |
it returns the flow value on edge e, i.e. x(e).
|
jacint@131
|
425 |
*/
|
jacint@131
|
426 |
|
jacint@131
|
427 |
T flowOnEdge(EdgeIt e) {
|
jacint@131
|
428 |
return flow.get(e);
|
jacint@131
|
429 |
}
|
jacint@131
|
430 |
|
jacint@131
|
431 |
|
jacint@131
|
432 |
|
jacint@131
|
433 |
FlowMap Flow() {
|
jacint@131
|
434 |
return flow;
|
jacint@131
|
435 |
}
|
jacint@131
|
436 |
|
jacint@131
|
437 |
|
jacint@131
|
438 |
|
jacint@131
|
439 |
void Flow(FlowMap& _flow ) {
|
jacint@131
|
440 |
for(EachNodeIt v=G.firstNode() ; v; G.next(v))
|
jacint@131
|
441 |
_flow.set(v,flow.get(v));
|
jacint@131
|
442 |
}
|
jacint@131
|
443 |
|
jacint@131
|
444 |
|
jacint@131
|
445 |
|
jacint@131
|
446 |
/*
|
jacint@131
|
447 |
Returns the minimum min cut, by a bfs from s in the residual graph.
|
jacint@131
|
448 |
*/
|
jacint@131
|
449 |
|
jacint@131
|
450 |
template<typename _CutMap>
|
jacint@131
|
451 |
void minMinCut(_CutMap& M) {
|
jacint@131
|
452 |
|
jacint@131
|
453 |
std::queue<NodeIt> queue;
|
jacint@131
|
454 |
|
jacint@131
|
455 |
M.set(s,true);
|
jacint@131
|
456 |
queue.push(s);
|
jacint@131
|
457 |
|
jacint@131
|
458 |
while (!queue.empty()) {
|
jacint@131
|
459 |
NodeIt w=queue.front();
|
jacint@131
|
460 |
queue.pop();
|
jacint@131
|
461 |
|
jacint@131
|
462 |
for(OutEdgeIt e=G.firstOut(w) ; e; G.next(e)) {
|
jacint@131
|
463 |
NodeIt v=G.head(e);
|
jacint@131
|
464 |
if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
|
jacint@131
|
465 |
queue.push(v);
|
jacint@131
|
466 |
M.set(v, true);
|
jacint@131
|
467 |
}
|
jacint@131
|
468 |
}
|
jacint@131
|
469 |
|
jacint@131
|
470 |
for(InEdgeIt e=G.firstIn(w) ; e; G.next(e)) {
|
jacint@131
|
471 |
NodeIt v=G.tail(e);
|
jacint@131
|
472 |
if (!M.get(v) && flow.get(e) > 0 ) {
|
jacint@131
|
473 |
queue.push(v);
|
jacint@131
|
474 |
M.set(v, true);
|
jacint@131
|
475 |
}
|
jacint@131
|
476 |
}
|
jacint@131
|
477 |
}
|
jacint@131
|
478 |
}
|
jacint@131
|
479 |
|
jacint@131
|
480 |
|
jacint@131
|
481 |
|
jacint@131
|
482 |
/*
|
jacint@131
|
483 |
Returns the maximum min cut, by a reverse bfs
|
jacint@131
|
484 |
from t in the residual graph.
|
jacint@131
|
485 |
*/
|
jacint@131
|
486 |
|
jacint@131
|
487 |
template<typename _CutMap>
|
jacint@131
|
488 |
void maxMinCut(_CutMap& M) {
|
jacint@131
|
489 |
|
jacint@131
|
490 |
std::queue<NodeIt> queue;
|
jacint@131
|
491 |
|
jacint@131
|
492 |
M.set(t,true);
|
jacint@131
|
493 |
queue.push(t);
|
jacint@131
|
494 |
|
jacint@131
|
495 |
while (!queue.empty()) {
|
jacint@131
|
496 |
NodeIt w=queue.front();
|
jacint@131
|
497 |
queue.pop();
|
jacint@131
|
498 |
|
jacint@131
|
499 |
for(InEdgeIt e=G.firstIn(w) ; e; G.next(e)) {
|
jacint@131
|
500 |
NodeIt v=G.tail(e);
|
jacint@131
|
501 |
if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
|
jacint@131
|
502 |
queue.push(v);
|
jacint@131
|
503 |
M.set(v, true);
|
jacint@131
|
504 |
}
|
jacint@131
|
505 |
}
|
jacint@131
|
506 |
|
jacint@131
|
507 |
for(OutEdgeIt e=G.firstOut(w) ; e; G.next(e)) {
|
jacint@131
|
508 |
NodeIt v=G.head(e);
|
jacint@131
|
509 |
if (!M.get(v) && flow.get(e) > 0 ) {
|
jacint@131
|
510 |
queue.push(v);
|
jacint@131
|
511 |
M.set(v, true);
|
jacint@131
|
512 |
}
|
jacint@131
|
513 |
}
|
jacint@131
|
514 |
}
|
jacint@131
|
515 |
|
jacint@131
|
516 |
for(EachNodeIt v=G.firstNode() ; v; G.next(v)) {
|
jacint@131
|
517 |
M.set(v, !M.get(v));
|
jacint@131
|
518 |
}
|
jacint@131
|
519 |
|
jacint@131
|
520 |
}
|
jacint@131
|
521 |
|
jacint@131
|
522 |
|
jacint@131
|
523 |
|
jacint@131
|
524 |
template<typename CutMap>
|
jacint@131
|
525 |
void minCut(CutMap& M) {
|
jacint@131
|
526 |
minMinCut(M);
|
jacint@131
|
527 |
}
|
jacint@131
|
528 |
|
jacint@131
|
529 |
|
jacint@131
|
530 |
};
|
jacint@131
|
531 |
}//namespace marci
|
jacint@131
|
532 |
#endif
|
jacint@131
|
533 |
|
jacint@131
|
534 |
|
jacint@131
|
535 |
|
jacint@131
|
536 |
|