[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] minimum cut; undirected graph
From: |
Gabor Csardi |
Subject: |
Re: [igraph] minimum cut; undirected graph |
Date: |
Thu, 29 Mar 2007 14:42:54 +0200 |
User-agent: |
Mutt/1.5.12-2006-07-14 |
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