igraph-help
[Top][All Lists]

## Re: [igraph] Question about mincut implementation

 From: Gabor Csardi Subject: Re: [igraph] Question about mincut implementation Date: Mon, 24 Mar 2008 11:56:21 +0100 User-agent: Mutt/1.5.13 (2006-08-11)

```Thomas,

ok, some clarification.

igraph_st_mincut_value
gives you the value of the minimum s-t cut, works both for
directed and undirected graphs

igraph_mincut_value
gives the value of the minimum cut (aming all pairs of vertices),
it works both for directed and undirected graphs

igraph_mincut
gives the minimum cut itself (not just the value),
i.e. the minimum among all pairs of vertices, but it works
only for undirected graphs currently, the directed version
is not implemented.

Some of these functions are implemented via a push-relabel
maximum flow calculation: igraph_st_mincut_value (both for
directed and undirecte), igraph_mincut_value (only for directed).

Others use an implementation of the Stoer-Wagner algorithm:
igraph_mincut_value and igraph_mincut, both for undirected graphs.

What is missing from igraph currently is:

igraph_st_mincut
this would give the actual minimum s-t cut (not just the value),
between a source and a target vertex. The igraph_maxflow_value
function should be modified to calculate it, it is not trivial,
see the Cherkassky-Goldberg paper in the code/docs. This algorithm
works for directed graphs, but an undirected graph can be easily
converted to a directed one, just like it is done in
igraph_i_maxflow_value_undirected.

igraph_mincut implementation for directed graphs
the easiest way to implement this would be to just call
igraph_st_mincut for all pairs of vertices, but there might be
a simpler algorithm.

Other algorithms could be useful for calculating _all_ minimum
(s-t or not s-t) cuts.

Hope it is clear now. Unfortunately it seems that you're looking
for something (minimum s-t cut in undirected graphs), that is
not implemented yet.

Gabor

ps. it is ok if you don't subscribe the list, but then
i need to acknowledge them by hand to avoid spam and
2) you might miss some answers that are sent to the list
only.

On Sun, Mar 23, 2008 at 08:45:09PM +0100, Thomas VILLENEUVE wrote:
> Good evening,
>
> I'm working on Gomory-Hu's algorithm implementation with igraph, and I'm
> looking for a way to get the mincut ( for given source and sink) value and the
> partitions issues by this cut.
>
> Actually, on documentation, I only have a way to get the cutmin value (s-t
> given) (igraph_st_cutmin_value)
> or partitions + cutmin value without choosing source and sink.
>
> I tried to work on "igraph_i_mincut_undirected" function - from flow.h/c -,
> but
> I couldn't choose sink and source.
>
> Is already there a function to get what I want, or could someone help me to
> see
> where I need to modify the "igraph_i_mincut_undirected" function.
>
> Thank you,
>
> Villeneuve Thomas

> _______________________________________________
> igraph-help mailing list