[Top][All Lists]

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

Re: [igraph] mincut/maxflow efficiency question

From: Gabor Csardi
Subject: Re: [igraph] mincut/maxflow efficiency question
Date: Mon, 31 Mar 2008 22:53:49 +0200
User-agent: Mutt/1.5.13 (2006-08-11)

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:

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.


> 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

reply via email to

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