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-03-01 03:51:27

Hello Andrew,

Andrew Sutton wrote:

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

> This isn't particularly surprising. The people that write the algorithms
> tend to have a specific set of needs and they don't often generalize to
> tasks that should be easy. Consider the task of tracing the edges from one
> vertex to another along the shortest path. It should be easy, but its not,
> nor is there a clear example that demonstrates how its done.

This makes sense.  However, I believe, obtaining a minimum edge cut set
for a linear s-t min-cut problem is one of the most basic graph-related
problems one could think of.  It shouldn't be hard.

Sebastian