|
jacint@78
|
1 |
/*
|
|
jacint@78
|
2 |
preflow_push_max_flow_h
|
|
jacint@78
|
3 |
by jacint.
|
|
jacint@78
|
4 |
Runs a preflow push algorithm with the modification,
|
|
jacint@83
|
5 |
that we do not push on nodes with level at least n.
|
|
jacint@83
|
6 |
Moreover, if a level gets empty, we set all nodes above that
|
|
jacint@78
|
7 |
level to level n. Hence, in the end, we arrive at a maximum preflow
|
|
jacint@78
|
8 |
with value of a max flow value. An empty level gives a minimum cut.
|
|
jacint@78
|
9 |
|
|
jacint@78
|
10 |
Member functions:
|
|
jacint@78
|
11 |
|
|
jacint@78
|
12 |
void run() : runs the algorithm
|
|
jacint@78
|
13 |
|
|
jacint@78
|
14 |
The following functions should be used after run() was already run.
|
|
jacint@78
|
15 |
|
|
jacint@78
|
16 |
T maxflow() : returns the value of a maximum flow
|
|
jacint@78
|
17 |
|
|
jacint@83
|
18 |
NodeMap<bool> mincut(): returns a
|
|
jacint@78
|
19 |
characteristic vector of a minimum cut.
|
|
jacint@78
|
20 |
*/
|
|
jacint@78
|
21 |
|
|
jacint@78
|
22 |
#ifndef PREFLOW_PUSH_MAX_FLOW_H
|
|
jacint@78
|
23 |
#define PREFLOW_PUSH_MAX_FLOW_H
|
|
jacint@78
|
24 |
|
|
jacint@78
|
25 |
#include <algorithm>
|
|
jacint@78
|
26 |
#include <vector>
|
|
jacint@78
|
27 |
#include <stack>
|
|
jacint@78
|
28 |
|
|
jacint@78
|
29 |
#include <reverse_bfs.h>
|
|
jacint@78
|
30 |
|
|
jacint@78
|
31 |
|
|
jacint@78
|
32 |
namespace marci {
|
|
jacint@78
|
33 |
|
|
jacint@78
|
34 |
template <typename Graph, typename T>
|
|
jacint@78
|
35 |
class preflow_push_max_flow {
|
|
jacint@78
|
36 |
|
|
jacint@78
|
37 |
typedef typename Graph::NodeIt NodeIt;
|
|
jacint@78
|
38 |
typedef typename Graph::EachNodeIt EachNodeIt;
|
|
jacint@78
|
39 |
typedef typename Graph::OutEdgeIt OutEdgeIt;
|
|
jacint@78
|
40 |
typedef typename Graph::InEdgeIt InEdgeIt;
|
|
jacint@78
|
41 |
|
|
jacint@78
|
42 |
Graph& G;
|
|
jacint@78
|
43 |
NodeIt s;
|
|
jacint@78
|
44 |
NodeIt t;
|
|
jacint@78
|
45 |
typename Graph::EdgeMap<T>& capacity;
|
|
jacint@78
|
46 |
T value;
|
|
jacint@78
|
47 |
typename Graph::NodeMap<bool> mincutvector;
|
|
jacint@78
|
48 |
|
|
jacint@78
|
49 |
|
|
jacint@78
|
50 |
|
|
jacint@78
|
51 |
public:
|
|
jacint@78
|
52 |
|
|
jacint@83
|
53 |
preflow_push_max_flow ( Graph& _G, NodeIt _s, NodeIt _t,
|
|
jacint@83
|
54 |
typename Graph::EdgeMap<T>& _capacity) :
|
|
jacint@83
|
55 |
G(_G), s(_s), t(_t), capacity(_capacity), mincutvector(_G, false) { }
|
|
jacint@78
|
56 |
|
|
jacint@78
|
57 |
|
|
jacint@78
|
58 |
/*
|
|
jacint@83
|
59 |
The run() function runs a modified version of the
|
|
jacint@83
|
60 |
highest label preflow-push, which only
|
|
jacint@78
|
61 |
finds a maximum preflow, hence giving the value of a maximum flow.
|
|
jacint@78
|
62 |
*/
|
|
jacint@78
|
63 |
void run() {
|
|
jacint@78
|
64 |
|
|
jacint@83
|
65 |
typename Graph::EdgeMap<T> flow(G, 0);
|
|
jacint@83
|
66 |
typename Graph::NodeMap<int> level(G);
|
|
jacint@83
|
67 |
typename Graph::NodeMap<T> excess(G);
|
|
jacint@78
|
68 |
|
|
jacint@83
|
69 |
int n=G.nodeNum();
|
|
jacint@78
|
70 |
int b=n-2;
|
|
jacint@83
|
71 |
/*
|
|
jacint@83
|
72 |
b is a bound on the highest level of an active Node.
|
|
jacint@83
|
73 |
In the beginning it is at most n-2.
|
|
jacint@83
|
74 |
*/
|
|
jacint@78
|
75 |
|
|
jacint@83
|
76 |
std::vector<int> numb(n); //The number of Nodes on level i < n.
|
|
jacint@83
|
77 |
std::vector<std::stack<NodeIt> > stack(2*n-1);
|
|
jacint@83
|
78 |
//Stack of the active Nodes in level i.
|
|
jacint@78
|
79 |
|
|
jacint@78
|
80 |
/*Reverse_bfs from t, to find the starting level.*/
|
|
jacint@78
|
81 |
reverse_bfs<Graph> bfs(G, t);
|
|
jacint@78
|
82 |
bfs.run();
|
|
jacint@78
|
83 |
for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v)
|
|
jacint@78
|
84 |
{
|
|
jacint@78
|
85 |
int dist=bfs.dist(v);
|
|
jacint@78
|
86 |
level.set(v, dist);
|
|
jacint@78
|
87 |
++numb[dist];
|
|
jacint@78
|
88 |
}
|
|
jacint@78
|
89 |
|
|
jacint@78
|
90 |
level.set(s,n);
|
|
jacint@78
|
91 |
|
|
jacint@78
|
92 |
/* Starting flow. It is everywhere 0 at the moment. */
|
|
jacint@83
|
93 |
for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e)
|
|
jacint@78
|
94 |
{
|
|
jacint@83
|
95 |
if ( capacity.get(e) > 0 ) {
|
|
jacint@83
|
96 |
NodeIt w=G.head(e);
|
|
jacint@83
|
97 |
flow.set(e, capacity.get(e));
|
|
jacint@83
|
98 |
stack[level.get(w)].push(w);
|
|
jacint@83
|
99 |
excess.set(w, excess.get(w)+capacity.get(e));
|
|
jacint@83
|
100 |
}
|
|
jacint@78
|
101 |
}
|
|
jacint@78
|
102 |
|
|
jacint@78
|
103 |
/*
|
|
jacint@78
|
104 |
End of preprocessing
|
|
jacint@78
|
105 |
*/
|
|
jacint@78
|
106 |
|
|
jacint@78
|
107 |
|
|
jacint@78
|
108 |
|
|
jacint@78
|
109 |
/*
|
|
jacint@78
|
110 |
Push/relabel on the highest level active Nodes.
|
|
jacint@78
|
111 |
*/
|
|
jacint@78
|
112 |
|
|
jacint@78
|
113 |
/*While there exists an active Node.*/
|
|
jacint@78
|
114 |
while (b) {
|
|
jacint@78
|
115 |
|
|
jacint@83
|
116 |
/*We decrease the bound if there is no active node of level b.*/
|
|
jacint@78
|
117 |
if (stack[b].empty()) {
|
|
jacint@78
|
118 |
--b;
|
|
jacint@78
|
119 |
} else {
|
|
jacint@78
|
120 |
|
|
jacint@78
|
121 |
NodeIt w=stack[b].top(); //w is the highest label active Node.
|
|
jacint@78
|
122 |
stack[b].pop(); //We delete w from the stack.
|
|
jacint@78
|
123 |
|
|
jacint@78
|
124 |
int newlevel=2*n-2; //In newlevel we maintain the next level of w.
|
|
jacint@78
|
125 |
|
|
jacint@78
|
126 |
for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
|
|
jacint@78
|
127 |
NodeIt v=G.head(e);
|
|
jacint@78
|
128 |
/*e is the Edge wv.*/
|
|
jacint@78
|
129 |
|
|
jacint@78
|
130 |
if (flow.get(e)<capacity.get(e)) {
|
|
jacint@78
|
131 |
/*e is an Edge of the residual graph */
|
|
jacint@78
|
132 |
|
|
jacint@78
|
133 |
if(level.get(w)==level.get(v)+1) {
|
|
jacint@78
|
134 |
/*Push is allowed now*/
|
|
jacint@78
|
135 |
|
|
jacint@78
|
136 |
if (capacity.get(e)-flow.get(e) > excess.get(w)) {
|
|
jacint@78
|
137 |
/*A nonsaturating push.*/
|
|
jacint@78
|
138 |
|
|
jacint@78
|
139 |
if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
|
|
jacint@78
|
140 |
/*v becomes active.*/
|
|
jacint@78
|
141 |
|
|
jacint@78
|
142 |
flow.set(e, flow.get(e)+excess.get(w));
|
|
jacint@78
|
143 |
excess.set(v, excess.get(v)+excess.get(w));
|
|
jacint@78
|
144 |
excess.set(w,0);
|
|
jacint@78
|
145 |
//std::cout << w << " " << v <<" elore elen nonsat pump " << std::endl;
|
|
jacint@78
|
146 |
break;
|
|
jacint@78
|
147 |
} else {
|
|
jacint@78
|
148 |
/*A saturating push.*/
|
|
jacint@78
|
149 |
|
|
jacint@78
|
150 |
if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
|
|
jacint@78
|
151 |
/*v becomes active.*/
|
|
jacint@78
|
152 |
|
|
jacint@78
|
153 |
excess.set(v, excess.get(v)+capacity.get(e)-flow.get(e));
|
|
jacint@78
|
154 |
excess.set(w, excess.get(w)-capacity.get(e)+flow.get(e));
|
|
jacint@78
|
155 |
flow.set(e, capacity.get(e));
|
|
jacint@78
|
156 |
//std::cout << w <<" " << v <<" elore elen sat pump " << std::endl;
|
|
jacint@78
|
157 |
if (excess.get(w)==0) break;
|
|
jacint@78
|
158 |
/*If w is not active any more, then we go on to the next Node.*/
|
|
jacint@78
|
159 |
|
|
jacint@78
|
160 |
} // if (capacity.get(e)-flow.get(e) > excess.get(w))
|
|
jacint@78
|
161 |
} // if (level.get(w)==level.get(v)+1)
|
|
jacint@78
|
162 |
|
|
jacint@78
|
163 |
else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
|
|
jacint@78
|
164 |
|
|
jacint@78
|
165 |
} //if (flow.get(e)<capacity.get(e))
|
|
jacint@78
|
166 |
|
|
jacint@78
|
167 |
} //for(OutEdgeIt e=G.first_OutEdge(w); e.valid(); ++e)
|
|
jacint@78
|
168 |
|
|
jacint@78
|
169 |
|
|
jacint@78
|
170 |
|
|
jacint@78
|
171 |
for(InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
|
|
jacint@78
|
172 |
NodeIt v=G.tail(e);
|
|
jacint@78
|
173 |
/*e is the Edge vw.*/
|
|
jacint@78
|
174 |
|
|
jacint@78
|
175 |
if (excess.get(w)==0) break;
|
|
jacint@78
|
176 |
/*It may happen, that w became inactive in the first 'for' cycle.*/
|
|
jacint@78
|
177 |
|
|
jacint@78
|
178 |
if(flow.get(e)>0) {
|
|
jacint@78
|
179 |
/*e is an Edge of the residual graph */
|
|
jacint@78
|
180 |
|
|
jacint@78
|
181 |
if(level.get(w)==level.get(v)+1) {
|
|
jacint@78
|
182 |
/*Push is allowed now*/
|
|
jacint@78
|
183 |
|
|
jacint@78
|
184 |
if (flow.get(e) > excess.get(w)) {
|
|
jacint@78
|
185 |
/*A nonsaturating push.*/
|
|
jacint@78
|
186 |
|
|
jacint@78
|
187 |
if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
|
|
jacint@78
|
188 |
/*v becomes active.*/
|
|
jacint@78
|
189 |
|
|
jacint@78
|
190 |
flow.set(e, flow.get(e)-excess.get(w));
|
|
jacint@78
|
191 |
excess.set(v, excess.get(v)+excess.get(w));
|
|
jacint@78
|
192 |
excess.set(w,0);
|
|
jacint@78
|
193 |
//std::cout << v << " " << w << " vissza elen nonsat pump " << std::endl;
|
|
jacint@78
|
194 |
break;
|
|
jacint@78
|
195 |
} else {
|
|
jacint@78
|
196 |
/*A saturating push.*/
|
|
jacint@78
|
197 |
|
|
jacint@78
|
198 |
if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
|
|
jacint@78
|
199 |
/*v becomes active.*/
|
|
jacint@78
|
200 |
|
|
jacint@78
|
201 |
flow.set(e,0);
|
|
jacint@78
|
202 |
excess.set(v, excess.get(v)+flow.get(e));
|
|
jacint@78
|
203 |
excess.set(w, excess.get(w)-flow.get(e));
|
|
jacint@78
|
204 |
//std::cout << v <<" " << w << " vissza elen sat pump " << std::endl;
|
|
jacint@78
|
205 |
if (excess.get(w)==0) { break;}
|
|
jacint@78
|
206 |
} //if (flow.get(e) > excess.get(v))
|
|
jacint@78
|
207 |
} //if(level.get(w)==level.get(v)+1)
|
|
jacint@78
|
208 |
|
|
jacint@78
|
209 |
else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
|
|
jacint@78
|
210 |
//std::cout << "Leveldecrease of Node " << w << " to " << newlevel << std::endl;
|
|
jacint@78
|
211 |
|
|
jacint@78
|
212 |
} //if (flow.get(e)>0)
|
|
jacint@78
|
213 |
|
|
jacint@78
|
214 |
} //for in-Edge
|
|
jacint@78
|
215 |
|
|
jacint@78
|
216 |
|
|
jacint@78
|
217 |
|
|
jacint@78
|
218 |
|
|
jacint@78
|
219 |
/*
|
|
jacint@78
|
220 |
Relabel
|
|
jacint@78
|
221 |
*/
|
|
jacint@78
|
222 |
if (excess.get(w)>0) {
|
|
jacint@78
|
223 |
/*Now newlevel <= n*/
|
|
jacint@78
|
224 |
|
|
jacint@78
|
225 |
int l=level.get(w); //l is the old level of w.
|
|
jacint@78
|
226 |
--numb[l];
|
|
jacint@78
|
227 |
|
|
jacint@78
|
228 |
if (newlevel == n) {
|
|
jacint@78
|
229 |
level.set(w,n);
|
|
jacint@78
|
230 |
|
|
jacint@78
|
231 |
} else {
|
|
jacint@78
|
232 |
|
|
jacint@78
|
233 |
if (numb[l]) {
|
|
jacint@78
|
234 |
/*If the level of w remains nonempty.*/
|
|
jacint@78
|
235 |
|
|
jacint@78
|
236 |
level.set(w,++newlevel);
|
|
jacint@78
|
237 |
++numb[newlevel];
|
|
jacint@78
|
238 |
stack[newlevel].push(w);
|
|
jacint@78
|
239 |
b=newlevel;
|
|
jacint@78
|
240 |
} else {
|
|
jacint@78
|
241 |
/*If the level of w gets empty.*/
|
|
jacint@78
|
242 |
|
|
jacint@78
|
243 |
for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) {
|
|
jacint@78
|
244 |
if (level.get(v) >= l ) {
|
|
jacint@78
|
245 |
level.set(v,n);
|
|
jacint@78
|
246 |
}
|
|
jacint@78
|
247 |
}
|
|
jacint@78
|
248 |
|
|
jacint@78
|
249 |
for (int i=l+1 ; i!=n ; ++i) numb[i]=0;
|
|
jacint@78
|
250 |
} //if (numb[l])
|
|
jacint@78
|
251 |
|
|
jacint@78
|
252 |
} // if (newlevel = n)
|
|
jacint@78
|
253 |
|
|
jacint@78
|
254 |
} // if (excess.get(w)>0)
|
|
jacint@78
|
255 |
|
|
jacint@78
|
256 |
|
|
jacint@78
|
257 |
} //else
|
|
jacint@78
|
258 |
|
|
jacint@78
|
259 |
} //while(b)
|
|
jacint@78
|
260 |
|
|
jacint@78
|
261 |
value=excess.get(t);
|
|
jacint@78
|
262 |
/*Max flow value.*/
|
|
jacint@78
|
263 |
|
|
jacint@78
|
264 |
|
|
jacint@78
|
265 |
|
|
jacint@78
|
266 |
/*
|
|
jacint@78
|
267 |
We find an empty level, e. The Nodes above this level give
|
|
jacint@78
|
268 |
a minimum cut.
|
|
jacint@78
|
269 |
*/
|
|
jacint@78
|
270 |
|
|
jacint@78
|
271 |
int e=1;
|
|
jacint@78
|
272 |
|
|
jacint@78
|
273 |
while(e) {
|
|
jacint@78
|
274 |
if(numb[e]) ++e;
|
|
jacint@78
|
275 |
else break;
|
|
jacint@78
|
276 |
}
|
|
jacint@78
|
277 |
for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) {
|
|
jacint@78
|
278 |
if (level.get(v) > e) mincutvector.set(v, true);
|
|
jacint@78
|
279 |
}
|
|
jacint@78
|
280 |
|
|
jacint@78
|
281 |
|
|
jacint@78
|
282 |
} // void run()
|
|
jacint@78
|
283 |
|
|
jacint@78
|
284 |
|
|
jacint@78
|
285 |
|
|
jacint@78
|
286 |
/*
|
|
jacint@78
|
287 |
Returns the maximum value of a flow.
|
|
jacint@78
|
288 |
*/
|
|
jacint@78
|
289 |
|
|
jacint@78
|
290 |
T maxflow() {
|
|
jacint@78
|
291 |
return value;
|
|
jacint@78
|
292 |
}
|
|
jacint@78
|
293 |
|
|
jacint@78
|
294 |
|
|
jacint@78
|
295 |
|
|
jacint@78
|
296 |
/*
|
|
jacint@78
|
297 |
Returns a minimum cut.
|
|
jacint@78
|
298 |
*/
|
|
jacint@78
|
299 |
|
|
jacint@78
|
300 |
typename Graph::NodeMap<bool> mincut() {
|
|
jacint@78
|
301 |
return mincutvector;
|
|
jacint@78
|
302 |
}
|
|
jacint@78
|
303 |
|
|
jacint@78
|
304 |
|
|
jacint@78
|
305 |
};
|
|
jacint@78
|
306 |
}//namespace marci
|
|
jacint@78
|
307 |
#endif
|
|
jacint@78
|
308 |
|
|
jacint@78
|
309 |
|
|
jacint@78
|
310 |
|
|
jacint@78
|
311 |
|
|
jacint@78
|
312 |
|