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