Changeset 374:0fc9cd9b854a in lemon0.x
 Timestamp:
 04/22/04 17:56:05 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@504
 Location:
 src/work/jacint
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

src/work/jacint/preflow.cc
r372 r374 25 25 26 26 Graph::EdgeMap<int> flow(G); 27 Preflow<Graph, int> max_flow_test(G, s, t, cap, flow, 1 );27 Preflow<Graph, int> max_flow_test(G, s, t, cap, flow, 1,1); 28 28 ts.reset(); 29 29 max_flow_test.run(); 30 std::cout << "elapsed time with res: " << ts << std::endl; 31 32 std::cout << "preflow demo ..." << std::endl; 33 34 Graph::EdgeMap<int> flow2(G); 35 Preflow<Graph, int> max_flow_test2(G, s, t, cap, flow, 1,0); 36 ts.reset(); 37 max_flow_test2.run(); 30 38 std::cout << "elapsed time: " << ts << std::endl; 31 39 
src/work/jacint/preflowproba.h
r372 r374 71 71 T value; 72 72 bool constzero; 73 bool res; 73 74 74 75 typedef ResGraphWrapper<const Graph, T, CapMap, FlowMap> ResGW; … … 79 80 public: 80 81 Preflow(Graph& _G, Node _s, Node _t, CapMap& _capacity, 81 FlowMap& _flow, bool _constzero ) :82 G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow), constzero(_constzero) {}82 FlowMap& _flow, bool _constzero, bool _res ) : 83 G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow), constzero(_constzero), res(_res) {} 83 84 84 85 … … 303 304 int l=level[v]+1; 304 305 305 /* ResInEdgeIt e; 306 for(res_graph.first(e,s); res_graph.valid(e); 307 res_graph.next(e)) { 308 Node u=res_graph.tail(e); 309 if ( level[u] >= n ) { 310 bfs_queue.push(u); 311 level.set(u, l); 312 if ( excess[u] > 0 ) { 313 next.set(u,active[l]); 314 active[l]=u; 306 if (res){ 307 ResInEdgeIt e; 308 for(res_graph.first(e,v); res_graph.valid(e); 309 res_graph.next(e)) { 310 Node u=res_graph.tail(e); 311 if ( level[u] >= n ) { 312 bfs_queue.push(u); 313 level.set(u, l); 314 if ( excess[u] > 0 ) { 315 next.set(u,active[l]); 316 active[l]=u; 317 } 315 318 } 316 319 } 317 }*/ 318 InEdgeIt e; 319 for(G.first(e,v); G.valid(e); G.next(e)) { 320 if ( capacity[e] == flow[e] ) continue; 321 Node u=G.tail(e); 322 if ( level[u] >= n ) { 323 bfs_queue.push(u); 324 level.set(u, l); 325 if ( excess[u] > 0 ) { 326 next.set(u,active[l]); 327 active[l]=u; 320 } else { 321 InEdgeIt e; 322 for(G.first(e,v); G.valid(e); G.next(e)) { 323 if ( capacity[e] == flow[e] ) continue; 324 Node u=G.tail(e); 325 if ( level[u] >= n ) { 326 bfs_queue.push(u); 327 level.set(u, l); 328 if ( excess[u] > 0 ) { 329 next.set(u,active[l]); 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 350 b=n2;
Note: See TracChangeset
for help on using the changeset viewer.