[boost] [graph] kolmogorov_max_flow color map, gray state

Subject: [boost] [graph] kolmogorov_max_flow color map, gray state
From: Sebastian Nowozin (nowozin_at_[hidden])
Date: 2009-02-27 12:44:39

Hello everybody,

I use the boost graph library to find the linear min-cut of a directed
graph with exactly one source and one sink node (s-t min-cut).  For
this, I setup a linear max-flow problem and solve it using
kolmogorov_max_flow.  The color_map property is supposed to be usable
to recover the edge cut set from the max-flow solution, see the
description on http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/kolmogorov_max_flow.html

However, as long as there are no vertices colored "gray" I can simply
tell which side of the cut a node belongs to by doing something like:

    std::vector<default_color_type> color(num_vertices(g_ab));
    double flow = kolmogorov_max_flow(g_ab, alpha_vertex, beta_vertex,
        color_map(&color[0]));
    bool is_left = (color[node_desc] == tc_color_traits::white());
    bool is_right = (color[node_desc] == tc_color_traits::black());

And this works just fine.  For some problems I am solving there are
gray nodes, and I do not know how to determine their position relative
to the edge cut set.  Is there a code example available in the boost
repository or has anyone had this problem?

It seems surprising to me that obtaining the edge cut set of a linear
min-cut problem seems to be non-trivial using the boost graph library.
 I must be doing something wrong.

Thanks,
Sebastian