[Top][All Lists]

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

Re: [igraph] Find the vertex cut from vertex_connectivity

From: Gabor Csardi
Subject: Re: [igraph] Find the vertex cut from vertex_connectivity
Date: Tue, 20 May 2008 08:57:19 +0200
User-agent: Mutt/1.5.13 (2006-08-11)

Sorry for the delay, i was offline for some time. 
It is not that simple to actually extract the cut after the 
maxflow value has been found. It won't make it into the
next (minor) release, but since you're not the first one
asking for this, i'll add it before the next major release.


On Sat, May 17, 2008 at 09:38:59PM +0200, Tamas Nepusz wrote:
> >I am using C. However, the 'modified graph' is (and has to be I think)
> >directed, while igraph_mincut only works for undirected graphs.
> Yes, you're right, sorry; it looks like we have to stick to maxflow  
> then. I am not really familiar with the internals of the maxflow  
> algorithm in igraph (it was Gabor who implemented it), but I took a  
> look at the source code and it looks for me that the vector called  
> `rescap' contains the residual capacities of the edges after  
> termination. I think you can use that to construct the residual  
> network of the graph and recover the partition resulting from the  
> minimum cut that corresponds to the maximum flow. Of course you'll  
> have to do that for every s-t vertex pair, but that's exactly what  
> igraph_vertex_connectivity does anyway.
> -- 
> Tamas
> _______________________________________________
> 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]