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