Re: [Boost-users] Incorrect graph cut?

On Thu, Sep 10, 2009 at 9:40 AM, David Doria

wrote:

I made this simple graph: http://rpi.edu/~doriad/graph.png http://rpi.edu/%7Edoriad/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 #include

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::type capacity = get(edge_capacity, g); property_map::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

For anyone wondering - there was just a bug in my graph creation: AddEdge(v1, v2, rev, 8.0, g); should be AddEdge(v1, v3, rev, 8.0, g); Again - I highly recommend this example be added to the graph cut function documentation! That takes care of problems 1) and 2)! However, I am still wondering how to determine which nodes are on each side of the cut, as well as how to use no src/sink nodes as well as many src/sink nodes. Any thoughts on those? Thanks, David