[Boost-users] Incorrect graph cut?

Subject: [Boost-users] Incorrect graph cut?
From: David Doria (daviddoria+boost_at_[hidden])
Date: 2009-09-10 09:40:41

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