Changeset 198:5cec393baade in lemon0.x for src/work/edmonds_karp.h
 Timestamp:
 03/17/04 19:18:26 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@275
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/edmonds_karp.h
r197 r198 552 552 typedef typename AugGraph::OutEdgeIt AugOutEdgeIt; 553 553 typedef typename AugGraph::Edge AugEdge; 554 typename Graph::NodeMap<int> used; //0 554 555 555 556 public: 556 557 MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) : 557 G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity) { }558 G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { } 558 559 bool augmentOnShortestPath() { 559 560 AugGraph res_graph(*G, *flow, *capacity); … … 564 565 typename AugGraph::NodeMap<AugEdge> pred(res_graph); 565 566 for(NodeIt s=G>template first<NodeIt>(); G>valid(s); G>next(s)) { 566 if ( S>get(s)) {567 Number u=0;568 for(OutEdgeIt e=G>template first<OutEdgeIt>(s); G>valid(e); G>next(e))569 570 if (u<1) {567 if ((S>get(s)) && (used.get(s)<1) ) { 568 //Number u=0; 569 //for(OutEdgeIt e=G>template first<OutEdgeIt>(s); G>valid(e); G>next(e)) 570 //u+=flow>get(e); 571 //if (u<1) { 571 572 res_bfs.pushAndSetReached(s); 572 573 pred.set(s, AugEdge(INVALID)); 573 }574 //} 574 575 } 575 576 } … … 591 592 } 592 593 n=res_graph.head(e); 593 if (T>get(n) ) {594 Number u=0;595 for(InEdgeIt f=G>template first<InEdgeIt>(n); G>valid(f); G>next(f))596 597 if (u<1) {594 if (T>get(n) && (used.get(n)<1) ) { 595 //Number u=0; 596 //for(InEdgeIt f=G>template first<InEdgeIt>(n); G>valid(f); G>next(f)) 597 //u+=flow>get(f); 598 //if (u<1) { 598 599 _augment=true; 599 600 break; 600 }601 //} 601 602 } 602 603 } … … 607 608 if (_augment) { 608 609 //Node n=t; 610 used.set(n, 1); //mind2 vegen jav 609 611 Number augment_value=free.get(n); 610 612 while (res_graph.valid(pred.get(n))) { … … 613 615 n=res_graph.tail(e); 614 616 } 617 used.set(n, 1); //mind2 vegen jav 615 618 } 616 619
Note: See TracChangeset
for help on using the changeset viewer.