equal
deleted
inserted
replaced
100 int l=level[v]+1; |
100 int l=level[v]+1; |
101 |
101 |
102 ResInEdgeIt e; |
102 ResInEdgeIt e; |
103 for(res_graph.first(e,v); res_graph.valid(e); |
103 for(res_graph.first(e,v); res_graph.valid(e); |
104 res_graph.next(e)) { |
104 res_graph.next(e)) { |
105 Node w=res_graph.tail(e); |
105 Node w=res_graph.source(e); |
106 if ( level[w] == n && w != s ) { |
106 if ( level[w] == n && w != s ) { |
107 bfs_queue.push(w); |
107 bfs_queue.push(w); |
108 Node first=level_list[l]; |
108 Node first=level_list[l]; |
109 if ( G.valid(first) ) left.set(first,w); |
109 if ( G.valid(first) ) left.set(first,w); |
110 right.set(w,first); |
110 right.set(w,first); |
143 |
143 |
144 //the starting flow |
144 //the starting flow |
145 ResOutEdgeIt e; |
145 ResOutEdgeIt e; |
146 for(res_graph.first(e,s); res_graph.valid(e); |
146 for(res_graph.first(e,s); res_graph.valid(e); |
147 res_graph.next(e)) { |
147 res_graph.next(e)) { |
148 Node w=res_graph.head(e); |
148 Node w=res_graph.target(e); |
149 if ( level[w] < n ) { |
149 if ( level[w] < n ) { |
150 if ( excess[w] == 0 && w!=t ) { |
150 if ( excess[w] == 0 && w!=t ) { |
151 next.set(w,active[level[w]]); |
151 next.set(w,active[level[w]]); |
152 active[level[w]]=w; |
152 active[level[w]]=w; |
153 } |
153 } |
188 int l=level[v]+1; |
188 int l=level[v]+1; |
189 |
189 |
190 ResInEdgeIt e; |
190 ResInEdgeIt e; |
191 for(res_graph.first(e,v); |
191 for(res_graph.first(e,v); |
192 res_graph.valid(e); res_graph.next(e)) { |
192 res_graph.valid(e); res_graph.next(e)) { |
193 Node u=res_graph.tail(e); |
193 Node u=res_graph.source(e); |
194 if ( level[u] >= n ) { |
194 if ( level[u] >= n ) { |
195 bfs_queue.push(u); |
195 bfs_queue.push(u); |
196 level.set(u, l); |
196 level.set(u, l); |
197 if ( excess[u] > 0 ) { |
197 if ( excess[u] > 0 ) { |
198 next.set(u,active[l]); |
198 next.set(u,active[l]); |
219 int newlevel=n; //bound on the next level of w |
219 int newlevel=n; //bound on the next level of w |
220 |
220 |
221 ResOutEdgeIt e; |
221 ResOutEdgeIt e; |
222 for(res_graph.first(e,w); res_graph.valid(e); res_graph.next(e)) { |
222 for(res_graph.first(e,w); res_graph.valid(e); res_graph.next(e)) { |
223 |
223 |
224 Node v=res_graph.head(e); |
224 Node v=res_graph.target(e); |
225 if( lev > level[v] ) { |
225 if( lev > level[v] ) { |
226 /*Push is allowed now*/ |
226 /*Push is allowed now*/ |
227 |
227 |
228 if ( excess[v]==0 && v!=t && v!=s ) { |
228 if ( excess[v]==0 && v!=t && v!=s ) { |
229 int lev_v=level[v]; |
229 int lev_v=level[v]; |
398 Node w=queue.front(); |
398 Node w=queue.front(); |
399 queue.pop(); |
399 queue.pop(); |
400 |
400 |
401 OutEdgeIt e; |
401 OutEdgeIt e; |
402 for(G.first(e,w) ; G.valid(e); G.next(e)) { |
402 for(G.first(e,w) ; G.valid(e); G.next(e)) { |
403 Node v=G.head(e); |
403 Node v=G.target(e); |
404 if (!M[v] && flow[e] < capacity[e] ) { |
404 if (!M[v] && flow[e] < capacity[e] ) { |
405 queue.push(v); |
405 queue.push(v); |
406 M.set(v, true); |
406 M.set(v, true); |
407 } |
407 } |
408 } |
408 } |
409 |
409 |
410 InEdgeIt f; |
410 InEdgeIt f; |
411 for(G.first(f,w) ; G.valid(f); G.next(f)) { |
411 for(G.first(f,w) ; G.valid(f); G.next(f)) { |
412 Node v=G.tail(f); |
412 Node v=G.source(f); |
413 if (!M[v] && flow[f] > 0 ) { |
413 if (!M[v] && flow[f] > 0 ) { |
414 queue.push(v); |
414 queue.push(v); |
415 M.set(v, true); |
415 M.set(v, true); |
416 } |
416 } |
417 } |
417 } |
438 queue.pop(); |
438 queue.pop(); |
439 |
439 |
440 |
440 |
441 InEdgeIt e; |
441 InEdgeIt e; |
442 for(G.first(e,w) ; G.valid(e); G.next(e)) { |
442 for(G.first(e,w) ; G.valid(e); G.next(e)) { |
443 Node v=G.tail(e); |
443 Node v=G.source(e); |
444 if (!M[v] && flow[e] < capacity[e] ) { |
444 if (!M[v] && flow[e] < capacity[e] ) { |
445 queue.push(v); |
445 queue.push(v); |
446 M.set(v, true); |
446 M.set(v, true); |
447 } |
447 } |
448 } |
448 } |
449 |
449 |
450 OutEdgeIt f; |
450 OutEdgeIt f; |
451 for(G.first(f,w) ; G.valid(f); G.next(f)) { |
451 for(G.first(f,w) ; G.valid(f); G.next(f)) { |
452 Node v=G.head(f); |
452 Node v=G.target(f); |
453 if (!M[v] && flow[f] > 0 ) { |
453 if (!M[v] && flow[f] > 0 ) { |
454 queue.push(v); |
454 queue.push(v); |
455 M.set(v, true); |
455 M.set(v, true); |
456 } |
456 } |
457 } |
457 } |