igraph-help
[Top][All Lists]

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

 From: uxzmdlj02 Subject: [igraph] graph.cohesion/vertex.connectivity request and suggestion Date: Thu, 19 Apr 2007 10:10:54 -0500

```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

```