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