Subject: [boost] [graph] kolmogorov_max_flow color map, gray state
From: Sebastian Nowozin (nowozin_at_[hidden])
Date: 2009-02-27 12:44:39
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:
double flow = kolmogorov_max_flow(g_ab, alpha_vertex, beta_vertex,
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk