I made this simple graph:
http://rpi.edu/~doriad/graph.png
The min cut between node 0 and node 3 should be 11, right? But it is returning 7.
My code is below:
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kolmogorov_max_flow.hpp>
using namespace boost;
typedef adjacency_list_traits < vecS, vecS, directedS > Traits;
typedef adjacency_list < vecS, vecS, directedS,
property < vertex_name_t, std::string,
property < vertex_index_t, long,
property < vertex_color_t, boost::default_color_type,
property < vertex_distance_t, long,
property < vertex_predecessor_t, Traits::edge_descriptor > > > > >,
property < edge_capacity_t, double,
property < edge_residual_capacity_t, double,
property < edge_reverse_t, Traits::edge_descriptor > > > > Graph;
Traits::edge_descriptor AddEdge(Traits::vertex_descriptor &v1, Traits::vertex_descriptor &v2, property_map < Graph, edge_reverse_t >::type &rev, const double capacity, Graph &g);
int main(int, char*[])
{
Graph g; //a graph with 0 vertices
property_map < Graph, edge_reverse_t >::type rev = get(edge_reverse, g);
//add a source and sink node, and store them in s and t, respectively
Traits::vertex_descriptor v0 = add_vertex(g);
Traits::vertex_descriptor v1 = add_vertex(g);
Traits::vertex_descriptor v2 = add_vertex(g);
Traits::vertex_descriptor v3 = add_vertex(g);
AddEdge(v0, v1, rev, 6.0, g);
AddEdge(v0, v2, rev, 5.0, g);
AddEdge(v1, v2, rev, 8.0, g);
AddEdge(v2, v3, rev, 7.0, g);
//find min cut
double flow = kolmogorov_max_flow(g, v0, v3); // a list of sources will be returned in s, and a list of sinks will be returned in t
std::cout << "Max flow is: " << flow << std::endl;
property_map<Graph, edge_capacity_t>::type
capacity = get(edge_capacity, g);
property_map<Graph, edge_residual_capacity_t>::type
residual_capacity = get(edge_residual_capacity, g);
graph_traits<Graph>::vertex_iterator u_iter, u_end;
graph_traits<Graph>::out_edge_iterator ei, e_end;
for (tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter)
for (tie(ei, e_end) = out_edges(*u_iter, g); ei != e_end; ++ei)
if (capacity[*ei] > 0)
std::cout << "Source: " << *u_iter << " destination: " << target(*ei, g) << " capacity: " << capacity[*ei] << "residual cap: " << residual_capacity[*ei] << " diff: "
<< (capacity[*ei] - residual_capacity[*ei]) << std::endl;
return 0;
}
Traits::edge_descriptor AddEdge(Traits::vertex_descriptor &v1, Traits::vertex_descriptor &v2, property_map < Graph, edge_reverse_t >::type &rev, const double capacity, Graph &g)
{
Traits::edge_descriptor e1 = add_edge(v1, v2, g).first;
Traits::edge_descriptor e2 = add_edge(v2, v1, g).first;
put(edge_capacity, g, e1, capacity);
put(edge_capacity, g, e2, capacity);
rev[e1] = e2;
rev[e2] = e1;
}
The output is:
Max flow is: 7
Source: 0 destination: 1 capacity: 6residual cap: 4 diff: 2
Source: 0 destination: 2 capacity: 5residual cap: 0 diff: 5
Source: 1 destination: 0 capacity: 6residual cap: 8 diff: -2
Source: 1 destination: 2 capacity: 8residual cap: 6 diff: 2
Source: 2 destination: 0 capacity: 5residual cap: 5 diff: 0
Source: 2 destination: 1 capacity: 8residual cap: 10 diff: -2
Source: 2 destination: 3 capacity: 7residual cap: 0 diff: 7
Source: 3 destination: 2 capacity: 7residual cap: 9 diff: -2
Here are my questions:
1) Why is the max flow wrong?
2) I'm confused what that output is showing - for example, there is a Source 1 Destination 2 edge that is not a real edge. It is also missing the edge from node 3 to node 1.
3) What is the best way to determine which nodes are on the source side of the cut, and which are on the sink side? The goal is to partition the graph into two sets.
4) Is it possible to pass a list of sources and a list of sinks to kolmogorov_max_flow instead of just a single source node and a single sink node? (Or can a different boost maxflow algorithm handle that?) These are just additional constraints on where the cut should be allowed to be placed.
Maybe this is not the type of thing BGL is intended for? If it is, I really think the answers to these questions should be added to the documentation!
Thanks,
David