Hi Daniel, Thanks for the clarification. What I really need to is to find source set of a min-cut between s(source) and t(target) in a directed graph, and hence a maximum closure of the graph. So, I need to find a s-t min-cut, not just any min-cut. Can Stoer-Wager's min-cut be forced to find s-t min-cut only (and thus has reduced time complexity)? If not then, I guess I'll have to stick with a max-flow algorithm. Thanks, Dan
Date: Mon, 5 Jul 2010 13:51:41 -0400 From: dtrebbien@gmail.com To: boost@lists.boost.org Subject: Re: [boost] [BGL] Stoer–Wagner min-cut algorithm
Hi Daniel, I wonder if your min-cut algorithm can be used to find max flow, since min-cut and max-flow are dual? I am currently using two max-flow implementations in BOOST (i.e, Goldberg and Kolmogorov). What is the complexity compared to the two max-flow implementations in BOOST. I am looking for fastest max flow implementation available. Another related question: does BOOST offer parallel implementation of any max-flow algorithm? Thanks Dan
Hi Dan,
I should have been more precise. Given two vertices s and t where s is called the source and t is called the sink, the maximum flow from s to t is equal to the weight of a minimum s-t cut. Thus, a maximum flow algorithm can compute a minimum s-t cut of a graph. The Stoer–Wagner algorithm which I implemented calculates a min-cut of the graph, which is a slightly different problem.
A cut of an undirected graph G = (V, E) is a partition of the vertices into two, non-empty sets X and Y = V - X. The weight w(X, Y) of a cut is the number of edges between X and Y if G is unweighted, or the sum of the weights of edges between X and Y if G is weighted. Given two vertices s and t, an s-t cut is a cut (X, Y) that separates s and t; that is, either s is in X and t is in Y or t is in X and s is in Y. A minimum s-t cut is an s-t cut of minimal weight.
Historically, one way of computing a min-cut of a graph was to calculate the max-flow for every pair of vertices (s, t) and simply pick a minimum s-t cut of minimal weight. This would be a min-cut.
I think that it is correct to say that if a min-cut is (X, Y), then for all x in X and y in Y, (X, Y) is also a minimum x-y cut with the max-flow from x to y and vice versa (because G is undirected) being the min-cut weight w(X, Y). I think that it is also correct to say that the least maximum flow between any two vertices of a graph is the weight of a min-cut.
Intuitively speaking, because maximum flow is calculated between a given source and sink, then a maximum flow algorithm will be better than an min-cut algorithm, which has to consider all pairs of vertices. So, if you are given two vertices s and t and you want to know the maximum flow from s to t, you should use a maximum flow algorithm. Also, a min-cut (X, Y) of G as returned by the Stoer–Wagner algorithm might not be a minimum s-t cut; both s and t could be in X or Y.
As far as parallel implementations of maximum flow algorithms, I do not know whether Parallel BGL offers parallel maximum flow algorithm implementations. _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
_________________________________________________________________ Turn down-time into play-time with Messenger games http://go.microsoft.com/?linkid=9734385