Re: [Boost-users] [BGL] Question about push_relabel_max_flow

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-03-18 15:27:51

On Mar 18, 2005, at 8:10 AM, Matthias Linkenheil wrote:
> 		  tie(e1, in1) = add_edge(vertex(node_nr, g), vertex(right, g), g);
> 		  tie(e2, in2) = add_edge(vertex(right, g), vertex(node_nr, g), g);
> 			if (in1 && in2){		
> 				cap[e1] = cap_ptr->cap;
> 				cap[e2] = cap_ptr->inv_cap;
> 				rev_edge[e1] = e2;
> 				rev_edge[e2] = e1;
> 			}
>
> 		  *cap_ptr=myintensity.get_cap_below(node_nr, below);
> 		
> 		  tie(e1, in1) = add_edge(vertex(node_nr, g), vertex(below, g), g);
> 		  tie(e2, in2) = add_edge(vertex(below, g), vertex(node_nr, g), g);
> 			if (in1 && in2){		
> 				cap[e1] = cap_ptr->cap;
> 				cap[e2] = cap_ptr->inv_cap;
> 				rev_edge[e1] = e2;
> 				rev_edge[e2] = e1;
> 			}
> 		  ++matrix_counter;
> 	  }
> 	  ++matrix_counter;
>   }
>   matrix_counter = ((x_size*y_size)-x_size);
>   for (int spalten_counter = 0; spalten_counter <= (x_size-2); 
> ++spalten_counter){
> 	  node_nr = matrix_counter;
> 	  right = matrix_counter + 1;
> 		
> 	  *cap_ptr=myintensity.get_cap_right(node_nr, right);
>
> 	  tie(e1, in1) = add_edge(vertex(node_nr, g), vertex(right, g), g);
> 	  tie(e2, in2) = add_edge(vertex(right, g), vertex(node_nr, g), g);
> 	  if (in1 && in2){		
> 		 cap[e1] = cap_ptr->cap;
> 		 cap[e2] = cap_ptr->inv_cap;
> 		 rev_edge[e1] = e2;
> 		 rev_edge[e2] = e1;
> 	  }

I'm not sure if the initialization of the graph is correct for the 
max-flow algorithms. For each edge (u, v) the graph needs an edge (v, 
u) such that the rev_edge map maps back and forth (okay so far) and the 
capacity of (v, u) is zero (I'm just quoting from the 
push_relabel_max_flow docs). However, it looks like the capacity of the 
reverse edge (called "e2" in the above snippets) is always set to 
cap_ptr->inv_cap, which is not necessarily zero. If I change the 
capacity of these reverse edges to 0, the example completes and gives a 
max_flow of 0 (with both max-flow algorithms). However, I don't have 
enough of an understanding of max-flow problems to know whether that is 
a reasonably answer or not :(

        Doug