MinCut in undirected graph

Topics: algorithm, graph
Dec 3, 2008 at 10:50 AM
Hi everybody,

I need to know the minimum cut in an undirected graph.
The maximum flow algorithms all work with directed graphs only - is there any way other than converting my graph to a directed one with double edges?

Thanks for any help,


P.S.: Even more useful would be some kind of partitioning algorithm that divides the graph into two equally sized parts and minimizes edges between them - but I guess that's not included in QuickGraph, is it..?
Dec 3, 2008 at 12:49 PM
I am also very interest in partitioning.

I googled about this for hours, and without the "CustomizeGoogle" addin for FireFox I would have went insane..
Nothing but links to Cites, and patents.  Must have blocked about 100 sites from googles result list.

Anyway, there are a few packages available.  All large, complex, and C/C++.  I did not have much interest..
Some discussion of theory, but few algorithms available.

This seems to be used a lot in finite element analysis, and social networking sites.

Basically, it is an incredibly difficult problem domain.

What is your underlying data set based upon?
Sep 4, 2009 at 2:57 PM
Edited Sep 4, 2009 at 4:35 PM

hello you can use a reversedEdgeAugmentorAlgorithm and set their value to 0 like at http://quickgraph.codeplex.com/Thread/View.aspx?ThreadId=59583. But i am interested about how you can apply the minimum cut on the maximum flow. Is there a sample of code that do it, or should i just use the residualcapacities graph and apply a connection algorith on it ? 

thz in advance