Re: [igraph] Some problem in s-t mincut

[Gabor Csardi]

On Tue, Oct 30, 2007 at 04:56:15PM +0800, "Jung-Guan Luo (羅中冠)" wrote:
> Hello,
> 
> We have used iGraph to solve s-t mincut problem. In ver. 0.4.4, I
> found igraph library still doesn't support function that shows
> partition set and cut set in directed graph. We have tried to work
> on this issue recently, but we haven't got any idea.  

Hi,

the implementation is based on the following paper:
On Implementing Push-Relabel Method For The Maximum Flow Problem (1994)
Boris V. Cherkassky, Andrew V. Goldberg
http://citeseer.ist.psu.edu/33771.html

There are some differences in the data structures though.

> I have read flow.c and tried to figure out the function
> igraph_maxflow_value(). Unfortunately, we still can't find the way
> to 
> show s-t mincut partition set of directed graph . May I ask will you
> plan to implement the function which can show partition set and cut
> set in s-t mincut in the near future? Or, can you give us some ideas
> to solve this problem. 

Yes, i'll implement this sometime, probably not in the following two
weeks as i'm busy with other things now. You can try to implement it
based on the paper but i think it'll be hard, especially because 
the data structure i used is not documented. But even if you find 
out everything about that, it is not an easy taks, don't expect to do
it on a Saturday afternoon.

You can follow this issue here:
http://code.google.com/p/igraph/issues/detail?id=58

Gabor

> Best wishes
> Lansler
> 
> 
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help

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