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

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

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

I would appreciate any inputs on this. Thank you,

a²