[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


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:

    k <- 0
}else if(min(degree(G))==1){
    k <- 1
    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

reply via email to

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