Re: [igraph] help with cohesion.blocks (again...)

[Gabor Csardi]

Peter, thanks, i'll read over the paper(s) and see what to do.

Btw. i found this while playing with the old implementation:

> example(cohesive.blocks)
> gBlocks$blocks
[[1]]
 [1]  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17

[[2]]
[1] 12 13 14 15 16

[[3]]
 [1]  0  1  2  3  4  6  7  8  9 10

[[4]]
[1] 12 13 14 15

[[5]]
[1] 6 7 8 9

[[6]]
[1] 0 1 2 3 4
> gBlocks$block.cohesion
[1] 1 2 2 3 3 4
> graph.cohesion( subgraph(g, gBlocks$blocks[[2]]) )
[1] 2
> igraph:::kCutsets( subgraph(g, gBlocks$blocks[[2]]), k=2 )
list()
> igraph:::kCutsets( subgraph(g, gBlocks$blocks[[2]]), k=3 )
[[1]]
[1] 1 2 3

But, clearly, there is a 2-cutset: 

> clusters( delete.vertices(subgraph(g, gBlocks$blocks[[2]]), c(2,3) ) )$no
[1] 2

Which means that i either misunderstood something, or there is a problem
with with kCutsets(). kCutsets2() seems to be better:

> kCutsets2( subgraph(g, gBlocks$blocks[[2]]), k=2 )
[[1]]
[1] 2 3

G.

On Fri, Feb 01, 2008 at 12:30:53PM -0600, address@hidden wrote:
> Hi,
> I did some research into alternate cutset-finding algorithms and found  
> this one from 1995:
> C. Patvardhan, V. C. Prasad, and V. P. Pyara. Vertex cutsets of  
> undirected graphs. Reliability, IEEE
> Transactions on, 44(2):347–353, June 1995.
> 
[...]

-- 
Csardi Gabor <address@hidden>    UNIL DGM