[graph] kolmogorov_max_flow color map, gray state
Hello everybody, I use the boost graph library to find the linear min-cut of a directed graph with exactly one source and one sink node (s-t min-cut). For this, I setup a linear max-flow problem and solve it using kolmogorov_max_flow. The color_map property is supposed to be usable to recover the edge cut set from the max-flow solution, see the description on http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/kolmogorov_max_flow.html However, as long as there are no vertices colored "gray" I can simply tell which side of the cut a node belongs to by doing something like: std::vector<default_color_type> color(num_vertices(g_ab)); double flow = kolmogorov_max_flow(g_ab, alpha_vertex, beta_vertex, color_map(&color[0])); bool is_left = (color[node_desc] == tc_color_traits::white()); bool is_right = (color[node_desc] == tc_color_traits::black()); 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? 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. Thanks, Sebastian
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?
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? Andrew Sutton andrew.n.sutton@gmail.com
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
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.
Could those correspond to cycles? I know that with BFS/DFS (and Dijkstra's?), gray vertices tend to indicate that they're still in a buffer, which could indicate that the algorithm is re-pushing some vertices or edges. I'm just guessing here.
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. There's the potential to build a little library around each algorithm, but things haven't quite worked out that way. If you're interested in contributing a framework for this task, we'll certainly try to get it integrated. Andrew Sutton andrew.n.sutton@gmail.com
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
participants (2)
-
Andrew Sutton -
Sebastian Nowozin