Re: [Boost-users] [BGL] maximum flow through push_relabel_max_flow

Aaron Windsor wrote:

On 10/7/07, "Alejandro M. Aragón" wrote:

...

Hello all,

I've been working with the Edmunds & Karp maximum flow algorithm in the BGL for some time without any problems. However, I realized that I could do better in time complexity by moving to the push_relabel_max_flow algorithm so I gave it a try. I've been trying to figure out what the problem with my code is for the entire day without success. I was wondering if someone could tell me what is my mistake.

It is a very simple problem, four vertices, four edges, the result from the algorithm should be two:

2--------1 | | | | | | 0--------3

Source is 0, target is 1, all edges have unit capacity. The code is:

void compute_max_flow(Graph* g_) {

// obtain number of vertices in undirected graph size_t n = num_vertices(*g_);

typedef adjacency_list_traits Traits; typedef adjacency_list, property > > > FlowGraph; typedef graph_traits<FlowGraph>::edge_descriptor EdgeFlow;

FlowGraph g(num_vertices(*this->g_));

property_map::type indexmap = get(vertex_index, g); property_map::type capacity = get(edge_capacity, g); property_map::type rev = get(edge_reverse, g); property_map::type residual_capacity = get(edge_residual_capacity, g);

Traits::vertex_descriptor s, t;

EdgeFlow e1,e2; bool in1,in2;

// add edges, reverse edges and capacities to new graph for flow computation edge_iter ei,ei_end; for (tie(ei,ei_end) = edges(*g_); ei != ei_end; ++ei) { // obtain vertices in the original graph vertex u = source(*ei, *g_); vertex v = target(*ei, *g_); // insert edges in new graph and add unit capacities tie(e1, in1) = add_edge(u,v,g); tie(e2, in2) = add_edge(v,u,g); if(in1 && in2) { // assign reverse edges to property map rev[e1] = e2; rev[e2] = e1; capacity[e1] = 1; capacity[e2] = 0; } }

graph_traits<FlowGraph>::vertex_iterator vvi,vvi_end; for(tie(vvi,vvi_end) = vertices(g); vvi!=vvi_end; ++vvi) { cout<<"index -> "<

graph_traits<FlowGraph>::edge_iterator eei,eei_end; for(tie(eei,eei_end) = edges(g); eei!=eei_end; ++eei) { cout<<"edge -> "<<*eei< "< "<

int flow = push_relabel_max_flow(g, 0, 1, capacity, residual_capacity, rev, indexmap); cout<<"flow -> "<

Results in:

index -> 0 index -> 1 index -> 2 index -> 3 edge -> (0,2) capacity -> 1 rev -> (2,0) edge -> (0,3) capacity -> 1 rev -> (3,0) edge -> (1,2) capacity -> 1 rev -> (2,1) edge -> (1,3) capacity -> 1 rev -> (3,1) edge -> (2,0) capacity -> 0 rev -> (0,2) edge -> (2,1) capacity -> 0 rev -> (1,2) edge -> (3,0) capacity -> 0 rev -> (0,3) edge -> (3,1) capacity -> 0 rev -> (1,3)

flow -> 0

Hi Alejandro,

...

From the output above, it looks like the input graph does have max flow 0 between vertices 0 and 1. The only edges with non-zero capacity are (0,2), (0,3), (1,2) and (1,3), so there isn't even a path with non-zero capacity between 0 and 1. If you want a graph with flow 2 between vertices 0 and 1, you would need to give capacity 1 to (0,2), (0,3), (2,1), and (3,1). So, it looks like it's a problem in translating between the two graph types you're using.

Regards, Aaron

Oh, I see. Thanks Aaron for replying. Well, the thing is that I'm translating the graph from an undirected graph. Now I understand that it previously worked with the Edumnds & Karp algorithm because both capacities are assigned a unit value. I don't really have a way to determine the right direction of the edges. Is there a work around this so I can still use the algorithm with lower complexity? If not I guess that I better use the old code... =/ a²