Re: [igraph] minimum cut; undirected graph

[Gabor Csardi]

Greg,

igraph has the following min-cut algorithm for undirected graphs:
http://portal.acm.org/citation.cfm?id=263872
and you're right, it does not calculate the actual cut, 
and there is no function currently in igraph to do that. 

I don't remember the algorithm enough to answer whether it would be 
easy to add the actual minimum cut calculations if it is possible
at all. The sad thing is that the maximum flow-based algorithm 
(currently used for directed graphs only) is also incapable of 
the calculation of the cut, it is possible to add it, but it is 
not trivial, the push-relabel algorithm is not a piece of cake when 
it comes to implementation.

If you check the paper and have some ideas on how to add the min-cut
calculation, that would help.

Gabor

ps. please consider joining the mailing list, non-member emails 
are not let through by default, only after manual confirmation and 
can cause delays, even days in some extreme cases. Thanks.

On Wed, Mar 28, 2007 at 04:57:12PM -0700, gregory benison wrote:
> Hello -
> 
> I am interested in obtaining the minimum cut of an undirected graph,
> like what you can get with igraph_mincut_value(), only obtaining the
> actual partition of the graph (i.e. indices of the vertices in the two
> sets of the partition) rather than the minimum cut value.  Is there a
> way to do that already?  If not, would a modified
> igraph_mincut_value() that remembered partitions as it went do the
> job?
> 
> - Greg
> 
> -- 
> 
> ======================
> Gregory Benison
> Oregon State University
> (541)-737-1876
> gbenison at gmail dot com
> ======================
> 
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help

-- 
Csardi Gabor <address@hidden>    MTA RMKI, ELTE TTK