
Boost : 
Subject: [boost] [graph] kolmogorov_max_flow color map, gray state
From: Sebastian Nowozin (nowozin_at_[hidden])
Date: 20090227 12:44:39
Hello everybody,
I use the boost graph library to find the linear mincut of a directed
graph with exactly one source and one sink node (st mincut). For
this, I setup a linear maxflow 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 maxflow 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
mincut problem seems to be nontrivial using the boost graph library.
I must be doing something wrong.
Thanks,
Sebastian
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk