Re: [jgrapht-users] minimum cut in a directed graph

[Ahmed A. H. <ahm...@gm...>]

Hello Joris,

The Min Cut is indeed a also a Max Flow problem. For this you can use the
Ford Fulkerson algorithm. Here are some slides that you might need to read
before you actually do the implementation:
http://www.cs.princeton.edu/courses/archive/spr04/cos226/lectures/maxflow.4up.pdf

I don't know if jgraph has it but it might because it is one of the
fundamental algorithms in Network  Flow. I would respectfully advise that
you understand the theory very well before you do the coding. When you do,
you might find yourself designing a very neat algorithm and make a
discovery. Hopefully you will be generous it with the rest of us ;)

Good luck!

-Ahmed




On Tue, Oct 1, 2013 at 3:18 PM, Joris Kinable <de...@gm...> wrote:

> 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
>
>
> ------------------------------------------------------------------------------
> October Webinars: Code for Performance
> Free Intel webinars can help you accelerate application performance.
> Explore tips for MPI, OpenMP, advanced profiling, and more. Get the most
> from
> the latest Intel processors and coprocessors. See abstracts and register >
> http://pubads.g.doubleclick.net/gampad/clk?id=60134791&iu=/4140/ostg.clktrk
> _______________________________________________
> jgrapht-users mailing list
> jgr...@li...
> https://lists.sourceforge.net/lists/listinfo/jgrapht-users
>
>