Changeset 986:e997802b855c in lemon-0.x for src/work/jacint/max_flow.h
- Timestamp:
- 11/13/04 13:53:28 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1376
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/jacint/max_flow.h
r921 r986 327 327 OutEdgeIt e; 328 328 for(g->first(e,w) ; g->valid(e); g->next(e)) { 329 Node v=g-> head(e);329 Node v=g->target(e); 330 330 if (!M[v] && (*flow)[e] < (*capacity)[e] ) { 331 331 queue.push(v); … … 336 336 InEdgeIt f; 337 337 for(g->first(f,w) ; g->valid(f); g->next(f)) { 338 Node v=g-> tail(f);338 Node v=g->source(f); 339 339 if (!M[v] && (*flow)[f] > 0 ) { 340 340 queue.push(v); … … 371 371 InEdgeIt e; 372 372 for(g->first(e,w) ; g->valid(e); g->next(e)) { 373 Node v=g-> tail(e);373 Node v=g->source(e); 374 374 if (M[v] && (*flow)[e] < (*capacity)[e] ) { 375 375 queue.push(v); … … 380 380 OutEdgeIt f; 381 381 for(g->first(f,w) ; g->valid(f); g->next(f)) { 382 Node v=g-> head(f);382 Node v=g->target(f); 383 383 if (M[v] && (*flow)[f] > 0 ) { 384 384 queue.push(v); … … 434 434 435 435 if ( (*flow)[e] >= (*capacity)[e] ) continue; 436 Node v=g-> head(e);436 Node v=g->target(e); 437 437 438 438 if( lev > level[v] ) { //Push is allowed now … … 467 467 468 468 if( (*flow)[e] <= 0 ) continue; 469 Node v=g-> tail(e);469 Node v=g->source(e); 470 470 471 471 if( lev > level[v] ) { //Push is allowed now … … 522 522 InEdgeIt e; 523 523 for(g->first(e,v); g->valid(e); g->next(e)) { 524 Node w=g-> tail(e);524 Node w=g->source(e); 525 525 if ( level[w] == n && w != s ) { 526 526 bfs_queue.push(w); … … 540 540 Num c=(*capacity)[e]; 541 541 if ( c <= 0 ) continue; 542 Node w=g-> head(e);542 Node w=g->target(e); 543 543 if ( level[w] < n ) { 544 544 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); … … 567 567 for(g->first(e,v); g->valid(e); g->next(e)) { 568 568 if ( (*capacity)[e] <= (*flow)[e] ) continue; 569 Node w=g-> tail(e);569 Node w=g->source(e); 570 570 if ( level[w] == n && w != s ) { 571 571 bfs_queue.push(w); … … 581 581 for(g->first(f,v); g->valid(f); g->next(f)) { 582 582 if ( 0 >= (*flow)[f] ) continue; 583 Node w=g-> head(f);583 Node w=g->target(f); 584 584 if ( level[w] == n && w != s ) { 585 585 bfs_queue.push(w); … … 600 600 Num rem=(*capacity)[e]-(*flow)[e]; 601 601 if ( rem <= 0 ) continue; 602 Node w=g-> head(e);602 Node w=g->target(e); 603 603 if ( level[w] < n ) { 604 604 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); … … 612 612 { 613 613 if ( (*flow)[f] <= 0 ) continue; 614 Node w=g-> tail(f);614 Node w=g->source(f); 615 615 if ( level[w] < n ) { 616 616 if ( excess[w] <= 0 && w!=t ) active[level[w]].push(w); … … 711 711 // return dist[n]; } 712 712 // bool get(const typename MapGraphWrapper::Edge& e) const { 713 // return (dist.get(g-> tail(e))<dist.get(g->head(e))); }713 // return (dist.get(g->source(e))<dist.get(g->target(e))); } 714 714 bool operator[](const typename MapGraphWrapper::Edge& e) const { 715 return (dist[g-> tail(e)]<dist[g->head(e)]);715 return (dist[g->source(e)]<dist[g->target(e)]); 716 716 } 717 717 }; … … 861 861 for(g->first(e,v); g->valid(e); g->next(e)) { 862 862 if ( (*capacity)[e] <= (*flow)[e] ) continue; 863 Node u=g-> tail(e);863 Node u=g->source(e); 864 864 if ( level[u] >= n ) { 865 865 bfs_queue.push(u); … … 872 872 for(g->first(f,v); g->valid(f); g->next(f)) { 873 873 if ( 0 >= (*flow)[f] ) continue; 874 Node u=g-> head(f);874 Node u=g->target(f); 875 875 if ( level[u] >= n ) { 876 876 bfs_queue.push(u); … … 926 926 ResGWOutEdgeIt e=bfs; 927 927 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 928 Node v=res_graph. tail(e);929 Node w=res_graph. head(e);928 Node v=res_graph.source(e); 929 Node w=res_graph.target(e); 930 930 pred.set(w, e); 931 931 if (res_graph.valid(pred[v])) { … … 934 934 free.set(w, res_graph.resCap(e)); 935 935 } 936 if (res_graph. head(e)==t) { _augment=true; break; }936 if (res_graph.target(e)==t) { _augment=true; break; } 937 937 } 938 938 … … 946 946 ResGWEdge e=pred[n]; 947 947 res_graph.augment(e, augment_value); 948 n=res_graph. tail(e);948 n=res_graph.source(e); 949 949 } 950 950 } … … 984 984 ResGWOutEdgeIt e=bfs; 985 985 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 986 Node v=res_graph. tail(e);987 Node w=res_graph. head(e);986 Node v=res_graph.source(e); 987 Node w=res_graph.target(e); 988 988 pred.set(w, e); 989 989 if (res_graph.valid(pred[v])) { … … 992 992 free.set(w, res_graph.resCap(e)); 993 993 } 994 if (res_graph. head(e)==t) { _augment=true; break; }994 if (res_graph.target(e)==t) { _augment=true; break; } 995 995 } 996 996 … … 1004 1004 ResGWEdge e=pred[n]; 1005 1005 res_graph.augment(e, augment_value); 1006 n=res_graph. tail(e);1006 n=res_graph.source(e); 1007 1007 } 1008 1008 } … … 1051 1051 if (res_graph.valid(e)) { 1052 1052 if (bfs.isBNodeNewlyReached()) { 1053 dist.set(res_graph. head(e), dist[res_graph.tail(e)]+1);1054 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph. tail(e)],1055 res_graph_to_F[res_graph. head(e)]);1053 dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); 1054 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], 1055 res_graph_to_F[res_graph.target(e)]); 1056 1056 original_edge.update(); 1057 1057 original_edge.set(f, e); … … 1059 1059 residual_capacity.set(f, res_graph.resCap(e)); 1060 1060 } else { 1061 if (dist[res_graph. head(e)]==(dist[res_graph.tail(e)]+1)) {1062 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph. tail(e)],1063 res_graph_to_F[res_graph. head(e)]);1061 if (dist[res_graph.target(e)]==(dist[res_graph.source(e)]+1)) { 1062 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], 1063 res_graph_to_F[res_graph.target(e)]); 1064 1064 original_edge.update(); 1065 1065 original_edge.set(f, e); … … 1115 1115 typename MG::Edge e=pred[n]; 1116 1116 res_graph.augment(original_edge[e], augment_value); 1117 n=F. tail(e);1117 n=F.source(e); 1118 1118 if (residual_capacity[e]==augment_value) 1119 1119 F.erase(e); … … 1148 1148 ResGWOutEdgeIt e=bfs; 1149 1149 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 1150 dist.set(res_graph. head(e), dist[res_graph.tail(e)]+1);1150 dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); 1151 1151 } 1152 1152 ++bfs; … … 1248 1248 typename ErasingResGW::OutEdgeIt e=pred[n]; 1249 1249 res_graph.augment(e, augment_value); 1250 n=erasing_res_graph. tail(e);1250 n=erasing_res_graph.source(e); 1251 1251 if (res_graph.resCap(e)==0) 1252 1252 erasing_res_graph.erase(e);
Note: See TracChangeset
for help on using the changeset viewer.