68 Node t; |
68 Node t; |
69 const CapMap& capacity; |
69 const CapMap& capacity; |
70 FlowMap& flow; |
70 FlowMap& flow; |
71 T value; |
71 T value; |
72 bool constzero; |
72 bool constzero; |
|
73 bool res; |
73 |
74 |
74 typedef ResGraphWrapper<const Graph, T, CapMap, FlowMap> ResGW; |
75 typedef ResGraphWrapper<const Graph, T, CapMap, FlowMap> ResGW; |
75 typedef typename ResGW::OutEdgeIt ResOutEdgeIt; |
76 typedef typename ResGW::OutEdgeIt ResOutEdgeIt; |
76 typedef typename ResGW::InEdgeIt ResInEdgeIt; |
77 typedef typename ResGW::InEdgeIt ResInEdgeIt; |
77 typedef typename ResGW::Edge ResEdge; |
78 typedef typename ResGW::Edge ResEdge; |
78 |
79 |
79 public: |
80 public: |
80 Preflow(Graph& _G, Node _s, Node _t, CapMap& _capacity, |
81 Preflow(Graph& _G, Node _s, Node _t, CapMap& _capacity, |
81 FlowMap& _flow, bool _constzero ) : |
82 FlowMap& _flow, bool _constzero, bool _res ) : |
82 G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow), constzero(_constzero) {} |
83 G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow), constzero(_constzero), res(_res) {} |
83 |
84 |
84 |
85 |
85 void run() { |
86 void run() { |
86 |
87 |
87 ResGW res_graph(G, capacity, flow); |
88 ResGW res_graph(G, capacity, flow); |
300 |
301 |
301 Node v=bfs_queue.front(); |
302 Node v=bfs_queue.front(); |
302 bfs_queue.pop(); |
303 bfs_queue.pop(); |
303 int l=level[v]+1; |
304 int l=level[v]+1; |
304 |
305 |
305 /* ResInEdgeIt e; |
306 if (res){ |
306 for(res_graph.first(e,s); res_graph.valid(e); |
307 ResInEdgeIt e; |
307 res_graph.next(e)) { |
308 for(res_graph.first(e,v); res_graph.valid(e); |
308 Node u=res_graph.tail(e); |
309 res_graph.next(e)) { |
309 if ( level[u] >= n ) { |
310 Node u=res_graph.tail(e); |
310 bfs_queue.push(u); |
311 if ( level[u] >= n ) { |
311 level.set(u, l); |
312 bfs_queue.push(u); |
312 if ( excess[u] > 0 ) { |
313 level.set(u, l); |
313 next.set(u,active[l]); |
314 if ( excess[u] > 0 ) { |
314 active[l]=u; |
315 next.set(u,active[l]); |
|
316 active[l]=u; |
|
317 } |
315 } |
318 } |
316 } |
319 } |
317 }*/ |
320 } else { |
318 InEdgeIt e; |
321 InEdgeIt e; |
319 for(G.first(e,v); G.valid(e); G.next(e)) { |
322 for(G.first(e,v); G.valid(e); G.next(e)) { |
320 if ( capacity[e] == flow[e] ) continue; |
323 if ( capacity[e] == flow[e] ) continue; |
321 Node u=G.tail(e); |
324 Node u=G.tail(e); |
322 if ( level[u] >= n ) { |
325 if ( level[u] >= n ) { |
323 bfs_queue.push(u); |
326 bfs_queue.push(u); |
324 level.set(u, l); |
327 level.set(u, l); |
325 if ( excess[u] > 0 ) { |
328 if ( excess[u] > 0 ) { |
326 next.set(u,active[l]); |
329 next.set(u,active[l]); |
327 active[l]=u; |
330 active[l]=u; |
|
331 } |
|
332 } |
|
333 } |
|
334 |
|
335 OutEdgeIt f; |
|
336 for(G.first(f,v); G.valid(f); G.next(f)) { |
|
337 if ( 0 == flow[f] ) continue; |
|
338 Node u=G.head(f); |
|
339 if ( level[u] >= n ) { |
|
340 bfs_queue.push(u); |
|
341 level.set(u, l); |
|
342 if ( excess[u] > 0 ) { |
|
343 next.set(u,active[l]); |
|
344 active[l]=u; |
|
345 } |
328 } |
346 } |
329 } |
347 } |
330 } |
348 } |
331 |
|
332 OutEdgeIt f; |
|
333 for(G.first(f,v); G.valid(f); G.next(f)) { |
|
334 if ( 0 == flow[f] ) continue; |
|
335 Node u=G.head(f); |
|
336 if ( level[u] >= n ) { |
|
337 bfs_queue.push(u); |
|
338 level.set(u, l); |
|
339 if ( excess[u] > 0 ) { |
|
340 next.set(u,active[l]); |
|
341 active[l]=u; |
|
342 } |
|
343 } |
|
344 } |
|
345 } |
349 } |
346 b=n-2; |
350 b=n-2; |
347 } |
351 } |
348 |
352 |
349 } |
353 } |