1.1 --- a/src/work/jacint/preflow.cc	Thu Apr 22 14:50:24 2004 +0000
     1.2 +++ b/src/work/jacint/preflow.cc	Thu Apr 22 15:56:05 2004 +0000
     1.3 @@ -24,9 +24,17 @@
     1.4    std::cout << "preflow demo ..." << std::endl;
     1.5    
     1.6    Graph::EdgeMap<int> flow(G);
     1.7 -  Preflow<Graph, int> max_flow_test(G, s, t, cap, flow, 1);
     1.8 +  Preflow<Graph, int> max_flow_test(G, s, t, cap, flow, 1,1);
     1.9    ts.reset();
    1.10    max_flow_test.run();
    1.11 +  std::cout << "elapsed time with res: " << ts << std::endl;
    1.12 +  
    1.13 +  std::cout << "preflow demo ..." << std::endl;
    1.14 +  
    1.15 +  Graph::EdgeMap<int> flow2(G);
    1.16 +  Preflow<Graph, int> max_flow_test2(G, s, t, cap, flow, 1,0);
    1.17 +  ts.reset();
    1.18 +  max_flow_test2.run();
    1.19    std::cout << "elapsed time: " << ts << std::endl;
    1.20    
    1.21    Graph::NodeMap<bool> cut(G);

     2.1 --- a/src/work/jacint/preflowproba.h	Thu Apr 22 14:50:24 2004 +0000
     2.2 +++ b/src/work/jacint/preflowproba.h	Thu Apr 22 15:56:05 2004 +0000
     2.3 @@ -70,6 +70,7 @@
     2.4      FlowMap& flow;
     2.5      T value;
     2.6      bool constzero;
     2.7 +    bool res;
     2.8  
     2.9      typedef ResGraphWrapper<const Graph, T, CapMap, FlowMap> ResGW;
    2.10      typedef typename ResGW::OutEdgeIt ResOutEdgeIt;
    2.11 @@ -78,8 +79,8 @@
    2.12   
    2.13    public:
    2.14      Preflow(Graph& _G, Node _s, Node _t, CapMap& _capacity, 
    2.15 -	    FlowMap& _flow, bool _constzero ) :
    2.16 -      G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow), constzero(_constzero) {}
    2.17 +	    FlowMap& _flow, bool _constzero, bool _res ) :
    2.18 +      G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow), constzero(_constzero), res(_res) {}
    2.19      
    2.20      
    2.21      void run() {
    2.22 @@ -302,46 +303,49 @@
    2.23  	      bfs_queue.pop();
    2.24  	      int l=level[v]+1;
    2.25  	      
    2.26 -	      /*	      ResInEdgeIt e;
    2.27 -	      for(res_graph.first(e,s); res_graph.valid(e); 
    2.28 -		  res_graph.next(e)) {
    2.29 -		Node u=res_graph.tail(e);
    2.30 -		if ( level[u] >= n ) { 
    2.31 -		  bfs_queue.push(u);
    2.32 -		  level.set(u, l);
    2.33 -		  if ( excess[u] > 0 ) {
    2.34 -		    next.set(u,active[l]);
    2.35 -		    active[l]=u;
    2.36 +	      if (res){	
    2.37 +		ResInEdgeIt e;
    2.38 +		for(res_graph.first(e,v); res_graph.valid(e); 
    2.39 +		    res_graph.next(e)) {
    2.40 +		  Node u=res_graph.tail(e);
    2.41 +		  if ( level[u] >= n ) { 
    2.42 +		    bfs_queue.push(u);
    2.43 +		    level.set(u, l);
    2.44 +		    if ( excess[u] > 0 ) {
    2.45 +		      next.set(u,active[l]);
    2.46 +		      active[l]=u;
    2.47 +		    }
    2.48  		  }
    2.49  		}
    2.50 -		}*/
    2.51 -	            InEdgeIt e;
    2.52 -	      for(G.first(e,v); G.valid(e); G.next(e)) {
    2.53 -		if ( capacity[e] == flow[e] ) continue;
    2.54 -		Node u=G.tail(e);
    2.55 -		if ( level[u] >= n ) { 
    2.56 -		  bfs_queue.push(u);
    2.57 -		  level.set(u, l);
    2.58 -		  if ( excess[u] > 0 ) {
    2.59 -		    next.set(u,active[l]);
    2.60 -		    active[l]=u;
    2.61 +	      } else {
    2.62 +	        InEdgeIt e;
    2.63 +		for(G.first(e,v); G.valid(e); G.next(e)) {
    2.64 +		  if ( capacity[e] == flow[e] ) continue;
    2.65 +		  Node u=G.tail(e);
    2.66 +		  if ( level[u] >= n ) { 
    2.67 +		    bfs_queue.push(u);
    2.68 +		    level.set(u, l);
    2.69 +		    if ( excess[u] > 0 ) {
    2.70 +		      next.set(u,active[l]);
    2.71 +		      active[l]=u;
    2.72 +		    }
    2.73 +		  }
    2.74 +		}
    2.75 +		
    2.76 +		OutEdgeIt f;
    2.77 +		for(G.first(f,v); G.valid(f); G.next(f)) {
    2.78 +		  if ( 0 == flow[f] ) continue;
    2.79 +		  Node u=G.head(f);
    2.80 +		  if ( level[u] >= n ) { 
    2.81 +		    bfs_queue.push(u);
    2.82 +		    level.set(u, l);
    2.83 +		    if ( excess[u] > 0 ) {
    2.84 +		      next.set(u,active[l]);
    2.85 +		      active[l]=u;
    2.86 +		    }
    2.87  		  }
    2.88  		}
    2.89  	      }
    2.90 -	    
    2.91 -	      OutEdgeIt f;
    2.92 -	      for(G.first(f,v); G.valid(f); G.next(f)) {
    2.93 -		if ( 0 == flow[f] ) continue;
    2.94 -		Node u=G.head(f);
    2.95 -		if ( level[u] >= n ) { 
    2.96 -		  bfs_queue.push(u);
    2.97 -		  level.set(u, l);
    2.98 -		  if ( excess[u] > 0 ) {
    2.99 -		    next.set(u,active[l]);
   2.100 -		    active[l]=u;
   2.101 -		  }
   2.102 -		}
   2.103 -		}
   2.104  	    }
   2.105  	    b=n-2;
   2.106  	    }