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²