[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## [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