Re: [igraph] Question about mincut implementation

[Gabor Csardi]

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 
please consider that 1) your messages will be delayed, 
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
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help


-- 
Csardi Gabor <address@hidden>    UNIL DGM