[Boost-users] redirect flow with Breadth-First-Search - problems with the residual capacities

Subject: [Boost-users] redirect flow with Breadth-First-Search - problems with the residual capacities
From: Benjamin Rupp (benjaminrupp_at_[hidden])
Date: 2009-09-24 10:46:14

Hi,

 

I want to redirect Flow, which I have earlier calculated with Edmonds-Karp,
with Breadth-First-Search (Aim is to determine the maximal free capacity of
an edge by redirecting all possible flow to other edges)

When I call Edmonds-Karp the Maximal Flow is calculated. If I then print out
the values of the residual capacities of the edges, all edges with a
capacity of 0 (this are the reverse edges) have a residual capacity of 0
instead of a capacity equal to the flow of the reverse edge. 

 

I wrote the following code to correct the values:

 

long speicher[num_edges(g)];

 

for(tie(e_iter,e_end)=edges(g); e_iter!=e_end; ++e_iter)

             if(get(e_index,*e_iter) < num_edges(g)/2){

                    speicher[e_index[*e_iter]] = residual_capacity[*e_iter];

                    speicher[e_index[*e_iter]+(num_edges(g)/2)] =
flow[*e_iter];              

             }      

       

       

for(tie(e_iter,e_end)=edges(g); e_iter!=e_end; ++e_iter)

       put(residual_capacity,*e_iter,speicher[e_index[*e_iter]]);

 

 

But this is very time inefficient. 

Does anyone have an idea why the reverse edges do not have the correct
residual capacity?

 

Another strange phenomenon is that if I allocate the correct residual
capacity only to the reverse edges because the others are correct this
change to the residual capacities is not saved. 

 

for(tie(e_iter,e_end)=edges(g); e_iter!=e_end; ++e_iter)

             if(get(e_index,*e_iter) < num_edges(g)/2){

 
put(residual_capacity,reverse_edge[*e_iter],flow[*e_iter]);

             

       

Thanks

 

Benjamin