src/work/preflow_push_max_flow.hh
changeset 31 d93bef0c4ed3
parent 21 181b37336b29
equal deleted inserted replaced
0:4125cd5c8449 1:c6259e7c19bc
    78 
    78 
    79       /*Reverse_bfs from t, to find the starting level.*/
    79       /*Reverse_bfs from t, to find the starting level.*/
    80 
    80 
    81       reverse_bfs<list_graph> bfs(G, t);
    81       reverse_bfs<list_graph> bfs(G, t);
    82       bfs.run();
    82       bfs.run();
    83       for(each_node_iterator v=G.first_node(); v.is_valid(); ++v) 
    83       for(each_node_iterator v=G.first_node(); v.valid(); ++v) 
    84 	{
    84 	{
    85 	  int dist=bfs.dist(v);
    85 	  int dist=bfs.dist(v);
    86 	  level.put(v, dist); 
    86 	  level.put(v, dist); 
    87 	  ++numb[dist];
    87 	  ++numb[dist];
    88 	}
    88 	}
    91       level.put(s,n);
    91       level.put(s,n);
    92 
    92 
    93 
    93 
    94       /* Starting flow. It is everywhere 0 at the moment. */
    94       /* Starting flow. It is everywhere 0 at the moment. */
    95      
    95      
    96       for(out_edge_iterator i=G.first_out_edge(s); i.is_valid(); ++i) 
    96       for(out_edge_iterator i=G.first_out_edge(s); i.valid(); ++i) 
    97 	{
    97 	{
    98 	  node_iterator w=G.head(i);
    98 	  node_iterator w=G.head(i);
    99 	  flow.put(i, capacity.get(i)); 
    99 	  flow.put(i, capacity.get(i)); 
   100 	  stack[bfs.dist(w)].push(w); 
   100 	  stack[bfs.dist(w)].push(w); 
   101 	  excess.put(w, capacity.get(i));
   101 	  excess.put(w, capacity.get(i));
   124 	  node_iterator w=stack[b].top();    //w is the highest label active node.
   124 	  node_iterator w=stack[b].top();    //w is the highest label active node.
   125 	  stack[b].pop();                    //We delete w from the stack.
   125 	  stack[b].pop();                    //We delete w from the stack.
   126 	
   126 	
   127 	  int newlevel=2*n-2;                //In newlevel we maintain the next level of w.
   127 	  int newlevel=2*n-2;                //In newlevel we maintain the next level of w.
   128 	
   128 	
   129 	  for(out_edge_iterator e=G.first_out_edge(w); e.is_valid(); ++e) {
   129 	  for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) {
   130 	    node_iterator v=G.head(e);
   130 	    node_iterator v=G.head(e);
   131 	    /*e is the edge wv.*/
   131 	    /*e is the edge wv.*/
   132 
   132 
   133 	    if (flow.get(e)<capacity.get(e)) {              
   133 	    if (flow.get(e)<capacity.get(e)) {              
   134 	      /*e is an edge of the residual graph */
   134 	      /*e is an edge of the residual graph */
   165 	    
   165 	    
   166 	      else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
   166 	      else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
   167 	    
   167 	    
   168 	    } //if (flow.get(e)<capacity.get(e))
   168 	    } //if (flow.get(e)<capacity.get(e))
   169 	 
   169 	 
   170 	  } //for(out_edge_iterator e=G.first_out_edge(w); e.is_valid(); ++e) 
   170 	  } //for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) 
   171 	  
   171 	  
   172 
   172 
   173 
   173 
   174 	  for(in_edge_iterator e=G.first_in_edge(w); e.is_valid(); ++e) {
   174 	  for(in_edge_iterator e=G.first_in_edge(w); e.valid(); ++e) {
   175 	    node_iterator v=G.tail(e);
   175 	    node_iterator v=G.tail(e);
   176 	    /*e is the edge vw.*/
   176 	    /*e is the edge vw.*/
   177 
   177 
   178 	    if (excess.get(w)==0) break;
   178 	    if (excess.get(w)==0) break;
   179 	    /*It may happen, that w became inactive in the first 'for' cycle.*/		
   179 	    /*It may happen, that w became inactive in the first 'for' cycle.*/		
   241 		stack[newlevel].push(w);
   241 		stack[newlevel].push(w);
   242 		b=newlevel;
   242 		b=newlevel;
   243 	      } else { 
   243 	      } else { 
   244 		/*If the level of w gets empty.*/
   244 		/*If the level of w gets empty.*/
   245 	      
   245 	      
   246 		for (each_node_iterator v=G.first_node() ; v.is_valid() ; ++v) {
   246 		for (each_node_iterator v=G.first_node() ; v.valid() ; ++v) {
   247 		  if (level.get(v) >= l ) { 
   247 		  if (level.get(v) >= l ) { 
   248 		    level.put(v,n);  
   248 		    level.put(v,n);  
   249 		  }
   249 		  }
   250 		}
   250 		}
   251 		
   251 		
   275       
   275       
   276       while(e) {
   276       while(e) {
   277 	if(numb[e]) ++e;
   277 	if(numb[e]) ++e;
   278 	else break;
   278 	else break;
   279       } 
   279       } 
   280       for (each_node_iterator v=G.first_node(); v.is_valid(); ++v) {
   280       for (each_node_iterator v=G.first_node(); v.valid(); ++v) {
   281 	if (level.get(v) > e) mincutvector.put(v, true);
   281 	if (level.get(v) > e) mincutvector.put(v, true);
   282       }
   282       }
   283       
   283       
   284 
   284 
   285     } // void run()
   285     } // void run()