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

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... =/

a²