Re: [igraph] mincut/maxflow efficiency question

[Gabor Csardi]

On Fri, Mar 28, 2008 at 12:17:30PM +0000, Benjamin Fields wrote:
> Hi List - 
> 
> I' m interesting in calculating a number of mincut/maxflow values from and
> unweighted undirected graph in order to determine independent path counts
> between pairs of nodes.  I have a graph of ~15k vertices and ~92k edges and
> there are around 13k vertices pairs I need to determine these values for.  As
> such I'm wondering about the most efficient way to go about this.  My network
> flow analysis background is light at best so I'm starting from the ground up
> here.  My specific question as a first approach is this: at the implementation
> level is there any difference between maxflow_value and mincut_value in terms
> of how fast the run on unweighted undirected graphs?  Also, if anyone has any
> other efficiency suggestions they would be much appreciated.  Thanks in 
> advance
> for any help.

Ben, here is a summary about cuts is in igraph:
http://lists.gnu.org/archive/html/igraph-help/2008-03/msg00060.html

igraph_st_mincut_value just calls igraph_st_maxflow_value.

Just checked, igraph_mincut_value and igraph_maxflow_value are 
actually different for undirected graphs, which is surprising,
one should just call the other....

We also have functions for number of edge/vertex disjoint paths,
these are basically the same problems as maximum flow.

I suggest to go ahead and calculate _st_mincut_value for a couple of pairs,
then you'll be able to estimate the required time. Please tell me know if it 
turns out to be slow, i'll see what i can do then.

Gabor

> cheers
> 
> Ben
> 
> 
> 
> Ben Fields
> PhD Candidate
> Dept. of Computing
> Goldsmiths, University of London
> e: address@hidden
> p: +44 (0) 20 7078 5170
> ---------------------------------------------
> "Which is more musical: a truck passing by a factory or a truck passing by a
> music school?" --John Cage
> 

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


-- 
Csardi Gabor <address@hidden>    UNIL DGM