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

Subject: Re: [boost] [graph] kolmogorov_max_flow color map, gray state
From: Sebastian Nowozin (nowozin_at_[hidden])
Date: 2009-02-28 12:22:54

Hello,

Andrew Sutton wrote:

>> 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?

> I'm not especially familiar with the algorithm, but is it possible that the
> gray nodes are unconnected from the rest of the graph?

I can rule out this possibility: every node except the source and sink
node is connected to both the source and sink.  That is, there exist a
directed path (source,node,sink) for all nodes.

>> 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.

> What is the difficulty?

The difficulty is that the boost graph library does not seem to provide
a way to easily obtain an edge cut set from the max flow solution.  This
is not trivial, because the edge cut set might not be unique.  (That is,
just taking all edges with zero residual capacity does not work.)

  For example, some time ago I had a similar problem with the
edmunds_karp_max_flow algorithm.  What one needs to do there is to apply
the labeling algorithm once on the max-flow solution.  The edges which
have one adjacent node in the labeled set and one in the unlabeled set
define one minimum edge cut set.  As the labeling algorithm is used
internally by edmunds_karp_max_flow, there should be an easy way in the
boost graph library to obtain one minimum cut edge set from the max flow
solution.  Either I am missing it, or its simply not there.  I ended up
writing the labeling algorithm myself.

  For the kolmogorov_max_flow algorithm, there is a remark on the
documentation that the necessary information is kept in the color_map
property map.  However, it is not clear to me how to construct a minimum
edge cut set from it.  Of course, I could simply run the edmunds-karp
labeling algorithm once on the residual capacities as I have done
before, but it seems like a waste of computation resources, if this
information has already been computed by the max-flow algorithm.

So, is there a simple example code that computes one minimum edge cut
set using the boost graph library?

Sebastian