[BGL] maximum flow through push_relabel_max_flow
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²
On 10/7/07, "Alejandro M. Aragón" <aaragon2@uiuc.edu> 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
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
Hi Alejandro, translating between the two graph types you're using. Regards, Aaron
Aaron Windsor wrote:
On 10/7/07, "Alejandro M. Aragón" <aaragon2@uiuc.edu> 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²
On 10/7/07, "Alejandro M. Aragón" <aaragon2@uiuc.edu> wrote:
Aaron Windsor wrote:
On 10/7/07, "Alejandro M. Aragón" <aaragon2@uiuc.edu> 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:
<snip>
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... =/
I don't know enough about your problem to suggest a workaround. For instance, why can you not just start with the directed graph in the first place? If you know at some point the correct capacities and directions of the edges, there should be a way to construct a graph that's usable without going through an intermediary undirected graph and losing all of that information. Also, in the example you gave, if you just allowed all edges to have unit capacity, you would have gotten a max flow of 2 from vertex 0 to vertex 1 - but maybe you're not just dealing with unit capacity graphs in general. Regards, Aaron
Aaron Windsor wrote:
On 10/7/07, "Alejandro M. Aragón" <aaragon2@uiuc.edu> wrote:
Aaron Windsor wrote:
On 10/7/07, "Alejandro M. Aragón" <aaragon2@uiuc.edu> 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:
<snip>
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... =/
I don't know enough about your problem to suggest a workaround. For instance, why can you not just start with the directed graph in the first place? If you know at some point the correct capacities and directions of the edges, there should be a way to construct a graph that's usable without going through an intermediary undirected graph and losing all of that information.
Also, in the example you gave, if you just allowed all edges to have unit capacity, you would have gotten a max flow of 2 from vertex 0 to vertex 1 - but maybe you're not just dealing with unit capacity graphs in general.
Regards, Aaron
Well, I tried that in the beginning but I got a segmentation fault at the point of the call to the push_relabel_max_flow algorithm. Then I read in the documentation that I have to assign a zero capacity to the reverse edge and then I had no more segmentation faults. If I could assign a unit capacity to all edges, even reverse edges as I do in the Edmunds & Karp algorithm, that would be perfect. Is this segmentation fault a bug in the algorithm? About the directed graph, my problem is basically to find the direction of the flow so I cannot assign directions a priori. a²
On 10/8/07, "Alejandro M. Aragón" <aaragon2@uiuc.edu> wrote:
Aaron Windsor wrote:
On 10/7/07, "Alejandro M. Aragón" <aaragon2@uiuc.edu> wrote:
Aaron Windsor wrote:
On 10/7/07, "Alejandro M. Aragón" <aaragon2@uiuc.edu> 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:
<snip>
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... =/
I don't know enough about your problem to suggest a workaround. For instance, why can you not just start with the directed graph in the first place? If you know at some point the correct capacities and directions of the edges, there should be a way to construct a graph that's usable without going through an intermediary undirected graph and losing all of that information.
Also, in the example you gave, if you just allowed all edges to have unit capacity, you would have gotten a max flow of 2 from vertex 0 to vertex 1 - but maybe you're not just dealing with unit capacity graphs in general.
Regards, Aaron
Well, I tried that in the beginning but I got a segmentation fault at the point of the call to the push_relabel_max_flow algorithm. Then I read in the documentation that I have to assign a zero capacity to the reverse edge and then I had no more segmentation faults. If I could assign a unit capacity to all edges, even reverse edges as I do in the Edmunds & Karp algorithm, that would be perfect. Is this segmentation fault a bug in the algorithm?
About the directed graph, my problem is basically to find the direction of the flow so I cannot assign directions a priori.
You're right - the documentation does say that reverse edges need to have 0 capacity for the Push-Relabel algorithm. Stephan Diederich added a nice implementation of Kolmogorov's algorithm for max flow to the BGL recently - in tests, it was shown to be comparable to the push-relabel algorithm and even outperformed it in some cases. It also has the advantage of not restricting reverse edges to 0 capacity. It's going to be released in Boost 1.35, but you could pull it from our subversion repository now if you'd like. Regards, Aaron
participants (2)
-
"Alejandro M. Aragón" -
Aaron Windsor