src/work/preflow_push_hl.hh
changeset 40 ffaa9448964c
parent 20 bf088f14b87a
equal deleted inserted replaced
0:970537cbed73 1:2804563d3bc7
    81 
    81 
    82       /*Reverse_bfs from t, to find the starting level.*/
    82       /*Reverse_bfs from t, to find the starting level.*/
    83 
    83 
    84       reverse_bfs<list_graph> bfs(G, t);
    84       reverse_bfs<list_graph> bfs(G, t);
    85       bfs.run();
    85       bfs.run();
    86       for(each_node_iterator v=G.first_node(); v.is_valid(); ++v) {
    86       for(each_node_iterator v=G.first_node(); v.valid(); ++v) {
    87 	level.put(v, bfs.dist(v)); 
    87 	level.put(v, bfs.dist(v)); 
    88 	//std::cout << "the level of " << v << " is " << bfs.dist(v);
    88 	//std::cout << "the level of " << v << " is " << bfs.dist(v);
    89       }
    89       }
    90 
    90 
    91       /*The level of s is fixed to n*/ 
    91       /*The level of s is fixed to n*/ 
    95 
    95 
    96 
    96 
    97 
    97 
    98       /* Starting flow. It is everywhere 0 at the moment. */
    98       /* Starting flow. It is everywhere 0 at the moment. */
    99      
    99      
   100       for(out_edge_iterator i=G.first_out_edge(s); i.is_valid(); ++i) 
   100       for(out_edge_iterator i=G.first_out_edge(s); i.valid(); ++i) 
   101 	{
   101 	{
   102 	  node_iterator w=G.head(i);
   102 	  node_iterator w=G.head(i);
   103 	  flow.put(i, capacity.get(i)); 
   103 	  flow.put(i, capacity.get(i)); 
   104 	  stack[bfs.dist(w)].push(w); 
   104 	  stack[bfs.dist(w)].push(w); 
   105 	  excess.put(w, capacity.get(i));
   105 	  excess.put(w, capacity.get(i));
   127 	  node_iterator w=stack[b].top();    //w is the highest label active node.
   127 	  node_iterator w=stack[b].top();    //w is the highest label active node.
   128 	  stack[b].pop();                    //We delete w from the stack.
   128 	  stack[b].pop();                    //We delete w from the stack.
   129 	
   129 	
   130 	  int newlevel=2*n-2;                   //In newlevel we maintain the next level of w.
   130 	  int newlevel=2*n-2;                   //In newlevel we maintain the next level of w.
   131 	
   131 	
   132 	  for(out_edge_iterator e=G.first_out_edge(w); e.is_valid(); ++e) {
   132 	  for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) {
   133 	    node_iterator v=G.head(e);
   133 	    node_iterator v=G.head(e);
   134 	    /*e is the edge wv.*/
   134 	    /*e is the edge wv.*/
   135 
   135 
   136 	    if (flow.get(e)<capacity.get(e)) {              
   136 	    if (flow.get(e)<capacity.get(e)) {              
   137 	      /*e is an edge of the residual graph */
   137 	      /*e is an edge of the residual graph */
   168 	    
   168 	    
   169 	      else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
   169 	      else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
   170 	    
   170 	    
   171 	    } //if (flow.get(e)<capacity.get(e))
   171 	    } //if (flow.get(e)<capacity.get(e))
   172 	 
   172 	 
   173 	  } //for(out_edge_iterator e=G.first_out_edge(w); e.is_valid(); ++e) 
   173 	  } //for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) 
   174 	  
   174 	  
   175 
   175 
   176 
   176 
   177 	  for(in_edge_iterator e=G.first_in_edge(w); e.is_valid(); ++e) {
   177 	  for(in_edge_iterator e=G.first_in_edge(w); e.valid(); ++e) {
   178 	    node_iterator v=G.tail(e);
   178 	    node_iterator v=G.tail(e);
   179 	    /*e is the edge vw.*/
   179 	    /*e is the edge vw.*/
   180 
   180 
   181 	    if (excess.get(w)==0) break;
   181 	    if (excess.get(w)==0) break;
   182 	    /*It may happen, that w became inactive in the first for cycle.*/		
   182 	    /*It may happen, that w became inactive in the first for cycle.*/		
   286 
   286 
   287       while (!queue.empty()) {
   287       while (!queue.empty()) {
   288         node_iterator w=queue.front();
   288         node_iterator w=queue.front();
   289 	queue.pop();
   289 	queue.pop();
   290 
   290 
   291 	for(in_edge_iterator e=G.first_in_edge(w) ; e.is_valid(); ++e) {
   291 	for(in_edge_iterator e=G.first_in_edge(w) ; e.valid(); ++e) {
   292 	  node_iterator v=G.tail(e);
   292 	  node_iterator v=G.tail(e);
   293 	  if (mincutvector.get(v) && flow.get(e) < capacity.get(e) ) {
   293 	  if (mincutvector.get(v) && flow.get(e) < capacity.get(e) ) {
   294 	    queue.push(v);
   294 	    queue.push(v);
   295 	    mincutvector.put(v, false);
   295 	    mincutvector.put(v, false);
   296 	  }
   296 	  }
   297 	} // for
   297 	} // for
   298 
   298 
   299 	for(out_edge_iterator e=G.first_out_edge(w) ; e.is_valid(); ++e) {
   299 	for(out_edge_iterator e=G.first_out_edge(w) ; e.valid(); ++e) {
   300 	  node_iterator v=G.head(e);
   300 	  node_iterator v=G.head(e);
   301 	  if (mincutvector.get(v) && flow.get(e) > 0 ) {
   301 	  if (mincutvector.get(v) && flow.get(e) > 0 ) {
   302 	    queue.push(v);
   302 	    queue.push(v);
   303 	    mincutvector.put(v, false);
   303 	    mincutvector.put(v, false);
   304 	  }
   304 	  }