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

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

Hi,

Thanks for all the replies.

@Ahmed: I think you missed my point. You are talking about the standard max
flow min cut algorithm for a given s and t. I was asking for an algorithm
which computes the global min cut, i.e. the min cut for *all* (s,t) pairs
in the graph. Using the standard Ford Fulkerson algorithm is way to slow to
do that. FYI:  last year I implemented this algorithm, and shared it with
the Jgrapht community (see my implementation: MinSourceSinkCut) :). For
this I used the Edmonds-Karp implementation.

@Luc: Thanks for the suggestion. For this project I prefer however a
solution which does not require a solver.

I think I found the solution. Hao and Orlin, A Faster Algorithm for Finding
the Minimum Cut in a Directed Graph (1994) have proposed an efficient
solution for my problem. Implementation details can be found in:
Cherkassky, Goldberg, On Implementing push-relabel method for the maximum
flow problem (1994). Although I couldn't find any Java implementations, a C
implementation can be found here:
http://www.zib.de/en/services/web-services/mathprog/mincut.html
see: global-dir.tar.Z
It is easy to modify the code and if gives exactly what I need: a
partitioning of the nodes in S and T, and the cut weight.
If I find some time in the future, I might consider implementing this in
jgrapht as well.

Thanks for the suggestions,

Joris


On Tue, Oct 1, 2013 at 3:44 PM, Ahmed Abdeen Hamed
<ahm...@gm...>wrote:

> 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
>>
>>
>