Changeset 986:e997802b855c in lemon-0.x for src/work/marci/experiment/edmonds_karp_1.h
- Timestamp:
- 11/13/04 13:53:28 (19 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/experiment/edmonds_karp_1.h
r921 r986 42 42 //Edge(const Edge& e) : resG(e.resG), sym(e.sym) { } 43 43 Number free() const { 44 if (resG->G.aNode(sym)==resG->G. tail(sym)) {44 if (resG->G.aNode(sym)==resG->G.source(sym)) { 45 45 return (resG->capacity.get(sym)-resG->flow.get(sym)); 46 46 } else { … … 50 50 bool valid() const { return sym.valid(); } 51 51 void augment(Number a) const { 52 if (resG->G.aNode(sym)==resG->G. tail(sym)) {52 if (resG->G.aNode(sym)==resG->G.source(sym)) { 53 53 resG->flow.set(sym, resG->flow.get(sym)+a); 54 54 //resG->flow[sym]+=a; … … 98 98 } 99 99 100 Node tail(Edge e) const { return G.aNode(e.sym); }101 Node head(Edge e) const { return G.bNode(e.sym); }100 Node source(Edge e) const { return G.aNode(e.sym); } 101 Node target(Edge e) const { return G.bNode(e.sym); } 102 102 103 103 Node aNode(OutEdgeIt e) const { return G.aNode(e.sym); } … … 225 225 } 226 226 227 Node tail(Edge e) const {227 Node source(Edge e) const { 228 228 return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); } 229 Node head(Edge e) const {229 Node target(Edge e) const { 230 230 return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); } 231 231 … … 287 287 ResGWOutEdgeIt e=bfs; 288 288 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 289 Node v=res_graph. tail(e);290 Node w=res_graph. head(e);289 Node v=res_graph.source(e); 290 Node w=res_graph.target(e); 291 291 pred.set(w, e); 292 292 if (res_graph.valid(pred.get(v))) { … … 295 295 free.set(w, res_graph.resCap(e)); 296 296 } 297 if (res_graph. head(e)==t) { _augment=true; break; }297 if (res_graph.target(e)==t) { _augment=true; break; } 298 298 } 299 299 … … 307 307 ResGWEdge e=pred.get(n); 308 308 res_graph.augment(e, augment_value); 309 n=res_graph. tail(e);309 n=res_graph.source(e); 310 310 } 311 311 } … … 324 324 int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; } 325 325 bool get(const typename MapGraphWrapper::Edge& e) const { 326 return (dist.get(g-> tail(e))<dist.get(g->head(e)));326 return (dist.get(g->source(e))<dist.get(g->target(e))); 327 327 } 328 328 }; … … 343 343 ResGWOutEdgeIt e=bfs; 344 344 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 345 dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);345 dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 346 346 } 347 347 ++bfs; … … 369 369 typename FilterResGW::EdgeIt e; 370 370 for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) { 371 //if (dist.get(res_graph. head(e))==dist.get(res_graph.tail(e))+1) {372 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph. tail(e)), res_graph_to_F.get(res_graph.head(e)));371 //if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { 372 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); 373 373 original_edge.update(); 374 374 original_edge.set(f, e); … … 423 423 typename MG::Edge e=pred.get(n); 424 424 res_graph.augment(original_edge.get(e), augment_value); 425 n=F. tail(e);425 n=F.source(e); 426 426 if (residual_capacity.get(e)==augment_value) 427 427 F.erase(e); … … 468 468 if (res_graph.valid(e)) { 469 469 if (bfs.isBNodeNewlyReached()) { 470 dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);471 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph. tail(e)), res_graph_to_F.get(res_graph.head(e)));470 dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 471 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); 472 472 original_edge.update(); 473 473 original_edge.set(f, e); … … 475 475 residual_capacity.set(f, res_graph.resCap(e)); 476 476 } else { 477 if (dist.get(res_graph. head(e))==(dist.get(res_graph.tail(e))+1)) {478 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph. tail(e)), res_graph_to_F.get(res_graph.head(e)));477 if (dist.get(res_graph.target(e))==(dist.get(res_graph.source(e))+1)) { 478 typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); 479 479 original_edge.update(); 480 480 original_edge.set(f, e); … … 531 531 typename MG::Edge e=pred.get(n); 532 532 res_graph.augment(original_edge.get(e), augment_value); 533 n=F. tail(e);533 n=F.source(e); 534 534 if (residual_capacity.get(e)==augment_value) 535 535 F.erase(e); … … 557 557 ResGWOutEdgeIt e=bfs; 558 558 if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 559 dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);559 dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 560 560 } 561 561 ++bfs; … … 633 633 typename ErasingResGW::OutEdgeIt e=pred.get(n); 634 634 res_graph.augment(e, augment_value); 635 n=erasing_res_graph. tail(e);635 n=erasing_res_graph.source(e); 636 636 if (res_graph.resCap(e)==0) 637 637 erasing_res_graph.erase(e); … … 728 728 // AugOutEdgeIt e=bfs; 729 729 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 730 // Node v=res_graph. tail(e);731 // Node w=res_graph. head(e);730 // Node v=res_graph.source(e); 731 // Node w=res_graph.target(e); 732 732 // pred.set(w, e); 733 733 // if (res_graph.valid(pred.get(v))) { … … 736 736 // free.set(w, res_graph.free(e)); 737 737 // } 738 // n=res_graph. head(e);738 // n=res_graph.target(e); 739 739 // if (T->get(n) && (used.get(n)<1) ) { 740 740 // //Number u=0; … … 758 758 // AugEdge e=pred.get(n); 759 759 // res_graph.augment(e, augment_value); 760 // n=res_graph. tail(e);760 // n=res_graph.source(e); 761 761 // } 762 762 // used.set(n, 1); //mind2 vegen jav … … 799 799 // // AugOutEdgeIt e=bfs; 800 800 // // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 801 // // dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);801 // // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 802 802 // // } 803 803 … … 821 821 // // //which are in some shortest paths 822 822 // // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { 823 // // if (dist.get(res_graph. head(e))==dist.get(res_graph.tail(e))+1) {824 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph. tail(e)), res_graph_to_F.get(res_graph.head(e)));823 // // if (dist.get(res_graph.target(e))==dist.get(res_graph.source(e))+1) { 824 // // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.source(e)), res_graph_to_F.get(res_graph.target(e))); 825 825 // // original_edge.update(); 826 826 // // original_edge.set(f, e); … … 874 874 // // typename MutableGraph::Edge e=pred.get(n); 875 875 // // res_graph.augment(original_edge.get(e), augment_value); 876 // // n=F. tail(e);876 // // n=F.source(e); 877 877 // // if (residual_capacity.get(e)==augment_value) 878 878 // // F.erase(e); … … 925 925 // typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs; 926 926 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 927 // dist.set(res_graph. head(e), dist.get(res_graph.tail(e))+1);927 // dist.set(res_graph.target(e), dist.get(res_graph.source(e))+1); 928 928 // } 929 929 // ++bfs; … … 1002 1002 // EAugEdge e=pred.get(n); 1003 1003 // res_graph.augment(e, augment_value); 1004 // n=res_graph. tail(e);1004 // n=res_graph.source(e); 1005 1005 // if (res_graph.free(e)==0) 1006 1006 // res_graph.erase(e); … … 1095 1095 // // AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs); 1096 1096 // // if (e.valid() && bfs.isBNodeNewlyReached()) { 1097 // // Node v=res_graph. tail(e);1098 // // Node w=res_graph. head(e);1097 // // Node v=res_graph.source(e); 1098 // // Node w=res_graph.target(e); 1099 1099 // // pred.set(w, e); 1100 1100 // // if (pred.get(v).valid()) { … … 1103 1103 // // free.set(w, e.free()); 1104 1104 // // } 1105 // // if (TMap.get(res_graph. head(e))) {1105 // // if (TMap.get(res_graph.target(e))) { 1106 1106 // // _augment=true; 1107 // // reached_t_node=res_graph. head(e);1107 // // reached_t_node=res_graph.target(e); 1108 1108 // // break; 1109 1109 // // } … … 1119 1119 // // AugEdge e=pred.get(n); 1120 1120 // // e.augment(augment_value); 1121 // // n=res_graph. tail(e);1121 // // n=res_graph.source(e); 1122 1122 // // } 1123 1123 // // }
Note: See TracChangeset
for help on using the changeset viewer.