[jgrapht-users] minimum cut in a directed graph

[Joris K. <de...@gm...>]

Hi,

I'm looking for an algorithm which computes the Minimum cut in a
*directed*, weighted graph. All weights are positive, and the graph does
not contain self loops. In the jgrapht package, there exists a Stoer Wagner
implementation which computes the minimum cut in an undirected graph. I
need the equivalent for a directed graph.
Jgrapht contains an algorithm for computing the minimum s-t cut in a
directed graph, but this would require me to invoke the algorithm for every
s-t pair, which is way to expensive. Any suggestion is welcome:

1. Do you know an algorithm/paper/book which describes such an algorithm.
2. Do you know a implementation of such an algorithm, preferably in java.

Say for example that you have two vertices, a and b, and two arcs: (a,b)
with capacity 4 and (b,a) with capacity 2. Then the minimum cut would be to
partition the vertices into two sets, S and T, such that the max flow from
S to T equals the minimum cut. For this example, the solution would be:
S={b}, T={a}, max flow: 2.


br,

Joris