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

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-10-07 21:34:45

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