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