Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.
Close
From: Joris Kinable <deus87@gm...>  20131001 19:18:26
Attachments:
Message as HTML

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 st cut in a directed graph, but this would require me to invoke the algorithm for every st 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 
From: Ahmed Abdeen Hamed <ahmed.elmasri@gm...>  20131001 19:44:25
Attachments:
Message as HTML

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 <deus87@...> 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 st cut in a > directed graph, but this would require me to invoke the algorithm for every > st 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 > _______________________________________________ > jgraphtusers mailing list > jgraphtusers@... > https://lists.sourceforge.net/lists/listinfo/jgraphtusers > > 
From: Joris Kinable <deus87@gm...>  20131001 23:55:20
Attachments:
Message as HTML

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 EdmondsKarp 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 pushrelabel 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/webservices/mathprog/mincut.html see: globaldir.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 <ahmed.elmasri@...>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 <deus87@...> 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 st cut in a >> directed graph, but this would require me to invoke the algorithm for every >> st 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 >> _______________________________________________ >> jgraphtusers mailing list >> jgraphtusers@... >> https://lists.sourceforge.net/lists/listinfo/jgraphtusers >> >> > 