Changeset 986:e997802b855c in lemon-0.x for src/work/marci/oldies/edmonds_karp.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/marci/oldies/edmonds_karp.h
r921 r986 60 60 ResGWOutEdgeIt e=bfs; 61 61 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 62 Node v=res_graph. tail(e);63 Node w=res_graph. head(e);62 Node v=res_graph.source(e); 63 Node w=res_graph.target(e); 64 64 pred.set(w, e); 65 65 if (res_graph.valid(pred[v])) { … … 68 68 free.set(w, res_graph.resCap(e)); 69 69 } 70 if (res_graph. head(e)==t) { _augment=true; break; }70 if (res_graph.target(e)==t) { _augment=true; break; } 71 71 } 72 72 … … 80 80 ResGWEdge e=pred[n]; 81 81 res_graph.augment(e, augment_value); 82 n=res_graph. tail(e);82 n=res_graph.source(e); 83 83 } 84 84 } … … 102 102 // return dist[n]; } 103 103 // bool get(const typename MapGraphWrapper::Edge& e) const { 104 // return (dist.get(g-> tail(e))<dist.get(g->head(e))); }104 // return (dist.get(g->source(e))<dist.get(g->target(e))); } 105 105 bool operator[](const typename MapGraphWrapper::Edge& e) const { 106 return (dist[g-> tail(e)]<dist[g->head(e)]);106 return (dist[g->source(e)]<dist[g->target(e)]); 107 107 } 108 108 }; … … 124 124 ResGWOutEdgeIt e=bfs; 125 125 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 126 dist.set(res_graph. head(e), dist[res_graph.tail(e)]+1);126 dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); 127 127 } 128 128 ++bfs; … … 153 153 typename FilterResGW::EdgeIt e; 154 154 for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) { 155 //if (dist.get(res_graph. head(e))==dist.get(res_graph.tail(e))+1) {156 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph. tail(e)], res_graph_to_F[res_graph.head(e)]);155 //if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { 156 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]); 157 157 original_edge.update(); 158 158 original_edge.set(f, e); … … 207 207 typename MG::Edge e=pred[n]; 208 208 res_graph.augment(original_edge[e], augment_value); 209 n=F. tail(e);209 n=F.source(e); 210 210 if (residual_capacity[e]==augment_value) 211 211 F.erase(e); … … 255 255 if (res_graph.valid(e)) { 256 256 if (bfs.isBNodeNewlyReached()) { 257 dist.set(res_graph. head(e), dist[res_graph.tail(e)]+1);258 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph. tail(e)], res_graph_to_F[res_graph.head(e)]);257 dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); 258 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]); 259 259 original_edge.update(); 260 260 original_edge.set(f, e); … … 262 262 residual_capacity.set(f, res_graph.resCap(e)); 263 263 } else { 264 if (dist[res_graph. head(e)]==(dist[res_graph.tail(e)]+1)) {265 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph. tail(e)], res_graph_to_F[res_graph.head(e)]);264 if (dist[res_graph.target(e)]==(dist[res_graph.source(e)]+1)) { 265 typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.source(e)], res_graph_to_F[res_graph.target(e)]); 266 266 original_edge.update(); 267 267 original_edge.set(f, e); … … 317 317 typename MG::Edge e=pred[n]; 318 318 res_graph.augment(original_edge[e], augment_value); 319 n=F. tail(e);319 n=F.source(e); 320 320 if (residual_capacity[e]==augment_value) 321 321 F.erase(e); … … 344 344 ResGWOutEdgeIt e=bfs; 345 345 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 346 dist.set(res_graph. head(e), dist[res_graph.tail(e)]+1);346 dist.set(res_graph.target(e), dist[res_graph.source(e)]+1); 347 347 } 348 348 ++bfs; … … 441 441 typename ErasingResGW::OutEdgeIt e=pred[n]; 442 442 res_graph.augment(e, augment_value); 443 n=erasing_res_graph. tail(e);443 n=erasing_res_graph.source(e); 444 444 if (res_graph.resCap(e)==0) 445 445 erasing_res_graph.erase(e); … … 536 536 // AugOutEdgeIt e=bfs; 537 537 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 538 // Node v=res_graph. tail(e);539 // Node w=res_graph. head(e);538 // Node v=res_graph.source(e); 539 // Node w=res_graph.target(e); 540 540 // pred.set(w, e); 541 541 // if (res_graph.valid(pred.get(v))) { … … 544 544 // free.set(w, res_graph.free(e)); 545 545 // } 546 // n=res_graph. head(e);546 // n=res_graph.target(e); 547 547 // if (T->get(n) && (used.get(n)<1) ) { 548 548 // //Num u=0; … … 566 566 // AugEdge e=pred.get(n); 567 567 // res_graph.augment(e, augment_value); 568 // n=res_graph. tail(e);568 // n=res_graph.source(e); 569 569 // } 570 570 // used.set(n, 1); //mind2 vegen jav … … 607 607 // // AugOutEdgeIt e=bfs; 608 608 // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 609 // // dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);609 // // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 610 610 // // } 611 611 … … 629 629 // // //which are in some shortest paths 630 630 // // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { 631 // // if (dist.get(res_graph. head(e))==dist.get(res_graph.tail(e))+1) {632 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph. tail(e)), res_graph_to_F.get(res_graph.head(e)));631 // // if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { 632 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); 633 633 // // original_edge.update(); 634 634 // // original_edge.set(f, e); … … 682 682 // // typename MutableGraph::Edge e=pred.get(n); 683 683 // // res_graph.augment(original_edge.get(e), augment_value); 684 // // n=F. tail(e);684 // // n=F.source(e); 685 685 // // if (residual_capacity.get(e)==augment_value) 686 686 // // F.erase(e); … … 733 733 // typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::OutEdgeIt e=bfs; 734 734 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 735 // dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);735 // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 736 736 // } 737 737 // ++bfs; … … 810 810 // EAugEdge e=pred.get(n); 811 811 // res_graph.augment(e, augment_value); 812 // n=res_graph. tail(e);812 // n=res_graph.source(e); 813 813 // if (res_graph.free(e)==0) 814 814 // res_graph.erase(e); … … 903 903 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); 904 904 // // if (e.valid() && bfs.isBNodeNewlyReached()) { 905 // // Node v=res_graph. tail(e);906 // // Node w=res_graph. head(e);905 // // Node v=res_graph.source(e); 906 // // Node w=res_graph.target(e); 907 907 // // pred.set(w, e); 908 908 // // if (pred.get(v).valid()) { … … 911 911 // // free.set(w, e.free()); 912 912 // // } 913 // // if (TMap.get(res_graph. head(e))) {913 // // if (TMap.get(res_graph.target(e))) { 914 914 // // _augment=true; 915 // // reached_t_node=res_graph. head(e);915 // // reached_t_node=res_graph.target(e); 916 916 // // break; 917 917 // // } … … 927 927 // // AugEdge e=pred.get(n); 928 928 // // e.augment(augment_value); 929 // // n=res_graph. tail(e);929 // // n=res_graph.source(e); 930 930 // // } 931 931 // // }
Note: See TracChangeset
for help on using the changeset viewer.