Graph cut questions
1) If I do this: (with any of the max_flow algorithms, kolmogorov is just used as an example) double flow = kolmogorov_max_flow(g, SourceNode, SinkNode); I get the value of the max flow, but how do I tell which nodes of g belong to the "source side" of the graph and which nodes belong to the "sink side"? (thinking of it as a min cut rather than a max flow problem) 2) Is it possible to tell the max flow algorithm to use multiple sources/sinks? 3) The max_flow functions seem to require a source and sink to be specified. Shouldn't you be able to find the minimum cut that partitions the graph into two parts even without specifying a source/sink? 4) Currently you must use a bidirectional graph, and specify an edge_reverse_t in the graph traits, then set the reverse edge for every edge. a) this is pretty complicated for someone who is unfamiliar with generic programming. b) If an undirected graph is used, the algorithm should automatically take care of adding these reverse edges if they are required for the cut to be performed. Can these be considered as feature requests if they are not currently possible? I have not found a more promising graph library for c++, so it would be nice if BGL could be molded into the one everyone would like to use! Thanks, David
Hi David, David Doria wrote:
1) If I do this: (with any of the max_flow algorithms, kolmogorov is just used as an example)
double flow = kolmogorov_max_flow(g, SourceNode, SinkNode);
I get the value of the max flow, but how do I tell which nodes of g belong to the "source side" of the graph and which nodes belong to the "sink side"? (thinking of it as a min cut rather than a max flow problem)
This is not as trivial as it sounds and a common problem I myself raised at least two times on this mailing list. The short answer is: in the current state of the boost graph library there is no easy correct way to obtain a minimum cut from the max-flow solution, which is a pitty. The kolmogorov_max_flow supports a colormap with colors "black","white","gray" which should support this. A min-cut can be constructed, according to the documentation by all the edges from "white" to "gray"+"black", another one by all edges from "white"+"gray" to "black". This would be an easy method and "seems to work" for some graphs, but there are cases where the graph constructed either way is not a valid min-cut, i.e. the sum of edge weights in the cut is above the max-flow solution. The other max-flow codes do not support this feature at all and kolmogorov_max_flow is not maintained anymore, so there is no working bug-free solution. The demo-code originally supplied with kolmogorov_max_flow (for image segmentation) does not care and simply uses such cut constructed, even if its not maximal. It would be really nice if a s-t min cut interface would be defined, as this must be one of the very common practical problems one would want to use a graph library for.
2) Is it possible to tell the max flow algorithm to use multiple sources/sinks?
You have to add one global source and sink node and connect everything else to it to achieve this effect.
3) The max_flow functions seem to require a source and sink to be specified. Shouldn't you be able to find the minimum cut that partitions the graph into two parts even without specifying a source/sink?
This is a different problem. The "min-cut" is not the minimum cut among all possible pairs but actually only an "s-t min-cut". Afaik there is no code in boost to obtain the min-cut among all pairs.
4) Currently you must use a bidirectional graph, and specify an edge_reverse_t in the graph traits, then set the reverse edge for every edge. a) this is pretty complicated for someone who is unfamiliar with generic programming. b) If an undirected graph is used, the algorithm should automatically take care of adding these reverse edges if they are required for the cut to be performed.
Further optimization for undirected graphs would be possible, yes. However, the current overhead is pretty small. Kind regards, Sebastian
On Wed, Sep 16, 2009 at 1:25 PM, Sebastian Nowozin <nowozin@gmail.com>wrote:
Hi David,
David Doria wrote:
1) If I do this: (with any of the max_flow algorithms, kolmogorov is just used as an example)
double flow = kolmogorov_max_flow(g, SourceNode, SinkNode);
I get the value of the max flow, but how do I tell which nodes of g belong to the "source side" of the graph and which nodes belong to the "sink side"? (thinking of it as a min cut rather than a max flow problem)
This is not as trivial as it sounds and a common problem I myself raised at least two times on this mailing list. The short answer is: in the current state of the boost graph library there is no easy correct way to obtain a minimum cut from the max-flow solution, which is a pitty.
The kolmogorov_max_flow supports a colormap with colors "black","white","gray" which should support this. A min-cut can be constructed, according to the documentation by all the edges from "white" to "gray"+"black", another one by all edges from "white"+"gray" to "black". This would be an easy method and "seems to work" for some graphs, but there are cases where the graph constructed either way is not a valid min-cut, i.e. the sum of edge weights in the cut is above the max-flow solution. The other max-flow codes do not support this feature at all and kolmogorov_max_flow is not maintained anymore, so there is no working bug-free solution. The demo-code originally supplied with kolmogorov_max_flow (for image segmentation) does not care and simply uses such cut constructed, even if its not maximal.
It would be really nice if a s-t min cut interface would be defined, as this must be one of the very common practical problems one would want to use a graph library for.
2) Is it possible to tell the max flow algorithm to use multiple sources/sinks?
You have to add one global source and sink node and connect everything else to it to achieve this effect.
3) The max_flow functions seem to require a source and sink to be specified. Shouldn't you be able to find the minimum cut that partitions the graph into two parts even without specifying a source/sink?
This is a different problem. The "min-cut" is not the minimum cut among all possible pairs but actually only an "s-t min-cut". Afaik there is no code in boost to obtain the min-cut among all pairs.
4) Currently you must use a bidirectional graph, and specify an edge_reverse_t in the graph traits, then set the reverse edge for every edge. a) this is pretty complicated for someone who is unfamiliar with generic programming. b) If an undirected graph is used, the algorithm should automatically take care of adding these reverse edges if they are required for the cut to be performed.
Further optimization for undirected graphs would be possible, yes. However, the current overhead is pretty small.
Kind regards, Sebastian
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Sebastian, Thanks for your response! Here are some follow up comments (using the same numbering scheme): 1) I agree, an s-t min cut interface *really* should be defined. 2) I guess my phrasing wasn't very clear. Basically what it would be nice to do is specify a list of nodes that are definitely on one side of the cut, and a second list of nodes which are definitely on the other side of the cut. The cut would then be constrained so that these two sets indeed lie on different sides of the cuts. VERY simple examples (a graph with < 10 nodes) should be provided to demonstrate (1) and (2). 3) I agree, this is indeed a different problem - but it would be nice to see it added :) 4) The overhead may be small (especially if you could just copy and paste from a simple example), but again, it is very confusing for people not familiar with the generic programming concepts of boost. Can these things be submitted as a formal feature request somewhere? Or is the mailing list the only option? Is there any hope of them being added relatively quickly (it seems like whoever wrote the max flow should be able to provide a min cut interface VERY quickly)? Or should I continue my search for a graph library elsewhere? Thanks, David
Hi David, David Doria wrote:
2) I guess my phrasing wasn't very clear. Basically what it would be nice to do is specify a list of nodes that are definitely on one side of the cut, and a second list of nodes which are definitely on the other side of the cut. The cut would then be constrained so that these two sets indeed lie on different sides of the cuts. VERY simple examples (a graph with < 10 nodes) should be provided to demonstrate (1) and (2).
Oh. I am not sure this is actually still an easy problem, complexity-wise. In any case it seems to be not easily reformulated into a standard s-t min-cut problem. Regards, Sebastian
Dear David, David Doria wrote:
2) Is it possible to tell the max flow algorithm to use multiple sources/sinks? You have to add one global source and sink node and connect everything else to it to achieve this effect.
2) I guess my phrasing wasn't very clear. Basically what it would be nice to do is specify a list of nodes that are definitely on one side of the cut, and a second list of nodes which are definitely on the other side of the cut. The cut would then be constrained so that these two sets indeed lie on different sides of the cuts. VERY simple examples (a graph with < 10 nodes) should be provided to demonstrate (1) and (2).
Actually, now that I thought about it more carefully, what I said before is the correct way to exactly solve your problem. Consider a weighted digraph and two non-empty disjoint subsets S, T of the vertex set. Then, you can solve for the minimum S-T min-cut by adding two new vertices u, v, and connect u->s for all s in S, and t->v for all t in T. All these new edges receive a weight of positive infinity, thus can never be saturated in a max-flow solution and never be cut in a min-cut. Then, solving for the u-t min-cut will also solve for the S-T min-cut. Sebastian
participants (2)
-
David Doria -
Sebastian Nowozin