[igraph] graph.cohesion/vertex.connectivity request and suggestion

[uxzmdlj02]

Hi,

I've been using the graph.cohesion() (aka vertex.connectivity())  
function pretty heavily for a project I'm working on, and it's great  
in general. However I have one suggestion and one request concerning  
its implementation.

First, a suggested shortcut that I've discovered and have been using  
that might be worth building in to the function. For large graphs,  
the function takes a very long time, and the result is likely to be  
either 0 or 1. There's a theorem somewhere that says that for a graph G
vertex.connectivity(G) <= edge.connectivity(G) <= min(degree(G)) .
I'm running the function on graphs with between 200 and 800 vertices,  
and running it in the following control flow has meant that I rarely  
need to call the function itself and my functions run much more quickly:

if(!is.connected(G)){
    k <- 0
}else if(min(degree(G))==1){
    k <- 1
}else{
    k <- graph.cohesion(G)
}

Calculating the degree takes relatively minimal time compared to  
graph.cohesion, so I thought this might be worth implementing in the  
function itself.


Second, a feature request:
Would it be possible to have a function that both finds the vertex  
conectivity k of a graph and returns a list of the vertex cutsets of  
size k? I don't just need to know minimum size of the cutsets, I need  
to know what cutsets reach that minimum. This shouldn't be too hard  
to get out of the maxflow/mincut algorithm. Right now I have a sort  
of kludgey function in R that does this, and it doesn't take too long  
if k is known, but for vcount(G)>300 it's still a big waste of time  
(not to mention redundant). In any case, either a seperate function  
or an option in the current functions would be a boon to my work.

Thanks overall for the great package, by the way. I hardly need to  
touch Pajek anymore!

Peter McMahan