Quantcast

minimum cut in a directed graph

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

minimum cut in a directed graph

Joris Kinable
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: minimum cut in a directed graph

Ahmed Abdeen Hamed
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 <[hidden email]> 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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users



------------------------------------------------------------------------------
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: minimum cut in a directed graph

Joris Kinable
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 <[hidden email]> 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 <[hidden email]> 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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users




------------------------------------------------------------------------------
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
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: minimum cut in a directed graph

keshete
Found this thread 2 years after it was originally created... This is something I also need. I tried the link you posted regarding the C code, but it isn't available anymore...
Do you by any chance still have some kind of sample code for this? I'm looking for a quick solution and this seems promising.

Thanks!
Keshet
Loading...