[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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)


ok, some clarification. 

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

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

  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:

  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_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.


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 

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]