1.1 --- a/src/work/edmonds_karp.h	Wed Mar 17 17:04:41 2004 +0000
     1.2 +++ b/src/work/edmonds_karp.h	Wed Mar 17 18:18:26 2004 +0000
     1.3 @@ -551,10 +551,11 @@
     1.4      typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
     1.5      typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
     1.6      typedef typename AugGraph::Edge AugEdge;
     1.7 +    typename Graph::NodeMap<int> used; //0
     1.8  
     1.9    public:
    1.10      MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) : 
    1.11 -      G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity) { }
    1.12 +      G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
    1.13      bool augmentOnShortestPath() {
    1.14        AugGraph res_graph(*G, *flow, *capacity);
    1.15        bool _augment=false;
    1.16 @@ -563,14 +564,14 @@
    1.17        BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
    1.18        typename AugGraph::NodeMap<AugEdge> pred(res_graph); 
    1.19        for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
    1.20 -	if (S->get(s)) {
    1.21 -	  Number u=0;
    1.22 -	  for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
    1.23 -	    u+=flow->get(e);
    1.24 -	  if (u<1) {
    1.25 +	if ((S->get(s)) && (used.get(s)<1) ) {
    1.26 +	  //Number u=0;
    1.27 +	  //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
    1.28 +	  //u+=flow->get(e);
    1.29 +	  //if (u<1) {
    1.30  	    res_bfs.pushAndSetReached(s);
    1.31  	    pred.set(s, AugEdge(INVALID));
    1.32 -	  }
    1.33 +	    //}
    1.34  	}
    1.35        }
    1.36        
    1.37 @@ -590,14 +591,14 @@
    1.38  	    free.set(w, res_graph.free(e)); 
    1.39  	  }
    1.40  	  n=res_graph.head(e);
    1.41 -	  if (T->get(n)) { 
    1.42 -	    Number u=0;
    1.43 -	    for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
    1.44 -	      u+=flow->get(f);
    1.45 -	    if (u<1) {
    1.46 +	  if (T->get(n) && (used.get(n)<1) ) { 
    1.47 +	    //Number u=0;
    1.48 +	    //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
    1.49 +	    //u+=flow->get(f);
    1.50 +	    //if (u<1) {
    1.51  	      _augment=true; 
    1.52  	      break; 
    1.53 -	    }
    1.54 +	      //}
    1.55  	  }
    1.56  	}
    1.57  	
    1.58 @@ -606,12 +607,14 @@
    1.59  
    1.60        if (_augment) {
    1.61  	//Node n=t;
    1.62 +	used.set(n, 1); //mind2 vegen jav
    1.63  	Number augment_value=free.get(n);
    1.64  	while (res_graph.valid(pred.get(n))) { 
    1.65  	  AugEdge e=pred.get(n);
    1.66  	  res_graph.augment(e, augment_value); 
    1.67  	  n=res_graph.tail(e);
    1.68  	}
    1.69 +	used.set(n, 1); //mind2 vegen jav
    1.70        }
    1.71  
    1.72        return _augment;