Re: [Boost-users] Incorrect graph cut?

Subject: Re: [Boost-users] Incorrect graph cut?
From: David Doria (daviddoria+boost_at_[hidden])
Date: 2009-09-11 08:53:37

On Thu, Sep 10, 2009 at 9:40 AM, David Doria
<daviddoria+boost_at_[hidden]<daviddoria%2Bboost_at_[hidden]>
> 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 <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
>

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