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