Boost logo

Boost Users :

From: Alejandro M. Aragón (aaragon2_at_[hidden])
Date: 2007-10-07 23:48:13


Aaron Windsor wrote:
> On 10/7/07, "Alejandro M. Aragón" <aaragon2_at_[hidden]> 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<vecS, vecS, directedS> Traits;
>> typedef adjacency_list<listS, vecS, directedS,
>> property<vertex_index_t, int>,
>> property<edge_capacity_t, int,
>> property<edge_residual_capacity_t, int,
>> property<edge_reverse_t, Traits::edge_descriptor> > >
>> > FlowGraph;
>> typedef graph_traits<FlowGraph>::edge_descriptor EdgeFlow;
>>
>> FlowGraph g(num_vertices(*this->g_));
>>
>> property_map<FlowGraph, vertex_index_t>::type indexmap =
>> get(vertex_index, g);
>> property_map<FlowGraph, edge_capacity_t>::type capacity =
>> get(edge_capacity, g);
>> property_map<FlowGraph, edge_reverse_t>::type rev =
>> get(edge_reverse, g);
>> property_map<FlowGraph, edge_residual_capacity_t>::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 -> "<<indexmap[*vvi]<<endl;
>> }
>>
>> graph_traits<FlowGraph>::edge_iterator eei,eei_end;
>> for(tie(eei,eei_end) = edges(g); eei!=eei_end; ++eei) {
>> cout<<"edge -> "<<*eei<<endl;
>> cout<<"capacity -> "<<capacity[*eei]<<endl;
>> cout<<"rev -> "<<rev[*eei]<<endl;
>> }
>>
>> int flow = push_relabel_max_flow(g, 0, 1, capacity,
>> residual_capacity, rev, indexmap);
>> cout<<"flow -> "<<flow<<endl;
>> }
>>
>> 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... =/



Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net