igraph-help
[Top][All Lists]

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

 From: uxzmdlj02 Subject: Re: [igraph] help with cohesion.blocks (again...) Date: Fri, 1 Feb 2008 12:30:53 -0600

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

```
The article presents an algorithm for finding all minimal vertex cutsets, not minimum-size cutsets, so it will return cutsets of size 3 for a two-cohesive graph as long as no subset of that cutset is also a cutset. I went ahead and implemented it, simply ignoring any cutsets larger than the size we're looking for. I shoehorned it in to Kanevsky's algorithm very inefficiently (lots of redundant searching), but it looks like it goes much much faster, at least on Simone's dataset (about 3 seconds for full cohesive blocks!). I'll include the code here so others can use it, and I'll try to get rid of the redundancy and it use it in the official function itself. I'll do some testing, but I suspect that it will be much faster on smaller graphs with high edge density but might be slower on larger, sparser networks. We'll see.
```
```
In any case here's the code. The funciton kCutsets2() is a replacement for kCutsets, and sets up and calls the two other functions (one wrapper, one recursive).
```
```
kCutsets2 <- function(g, k=NULL, cl=NULL, verbose=igraph.par("verbose")){
```    if(!is.igraph(g)){
stop("g must be an igraph object")
}
if(is.directed(g)) g <- as.undirected(g)
res <- list()
if(is.null(k)){
if(!is.connected(g)){
k <- 0
}else if(min(degree(g))<=1){
k <- 1
} else {
k <- vertex.connectivity(g)
}
}

## quick and simple cases
if(k==0 || vcount(g) <=2) return(list(numeric()))

if(k==1){ # for 1-connected graphs
return(articulation.points(g))
}

## begin algorithm
v <- as.numeric(V(g))
K <- v[order(degree(g), decreasing=TRUE)][1:k] #2a
if(is.cutset(K, g)) res <- c(res, list(K))
for(i in K){
for(j in setdiff(v,K)){
```
if(!(j %in% unlist(neighborhood(g,1,i))) && vertex.connectivity(g,i,j)==k){
```                if(verbose) cat(i,j,";")
minCutSets <- findAllMinimalCutsetsST(g,i,j)
res <- c(res,minCutSets[lapply(minCutSets,length)==k])
}
}
}
if(verbose) cat("\n")
return(unique(lapply(res,sort)))

}

findAllMinimalCutsetsST <- function(g,s,t){
findAllMinimalCutsetsST.recurse(g,s,t,t,list())
}

findAllMinimalCutsetsST.recurse <- function(g,Vs,T,t,res){
## Direct implementation of Algorithm from Patvardhan et al (1995)
#1. Vx set of all vertices adjacent to S but not in S
Vx <- setdiff(unique(unlist(neighborhood(g,1,Vs))),Vs)
#2. If t is in Vx, stop
if(t %in% Vx) return(res)
#3. get component of G-Vx containing T
```
Vt <- unlist(neighborhood(delete.edges(g,E(g) [from(Vx)]),vcount(g),t))
```    #4. Create Z subset of Vx not adjacent to Vt
Z <- setdiff(Vx,unlist(neighborhood(g,1,Vt)))
#5. If Z intersects T then stop
if(any(T %in% Z)) return(res)
#6. Grow Vs
Vs <- union(Vs,Z)
#7. Create  Vc
Vc <- setdiff(Vx,Z)
#8. Output Vc
res <- c(res,list(Vc))
#9. Create Tprime
Tprime <- numeric()
#10. Begin loop
while(length(setdiff(Vc,Tprime))>0){
#11. Remove some v in Vc but not in Tprime
v <- setdiff(Vc,Tprime)[1]
#12. Recurse
```
res <- findAllMinimalCutsetsST.recurse(g,c(Vs,v),c(T,Tprime),t,res)
```        #13. Grow Tprime
Tprime <- c(Tprime,v)
}
res
}

```
On Jan 30, 2008, at 4:39 PM, uxzmdlj02-at-sneakemail.com |igraph-help| wrote:
```
```
Hm, I always assumed that using combn and specifying FUN would be fastest, like using "apply" funcitons.
```
```
I took the graph.antichains algorithm from Kanevsky's article, with modification. The goal is to find all antichains in the graph g, where an antichain is defined as a set of vertices such that for each pair of vertices i and j in the set i is neither a predecessor nor a successor of j. Kanevsky has two algorithms to find antichains, a recursive version (p.419) that I do not understand, and a "parallel" version (p.420) that I sort of understand. My function is a modified version of his parallel algorithm. The difference is that my version is redundant, and relies on R's unique() function. This is a problem, but I do not understand the enumeration he describes in steps 3 and 4. His algorithm is (quoted):
```1. Form a transitive closure L^+ of an input network L.
2. Take every vertex as antichain
```
3. Repeat log(n) times: Find all antichains of the double size using antichains of the current size 4. Find all other antichains of all other sizes using at most log(n) independent sets of sizes of powers of 2.
```5. Find all closed sets in the network using antichains.

```
Step 3 I'm ok with, but step 4 seems very vague. Instead of doing this, my function does not check if the output of step 3 has twice the size as the current size. In fact now that I'm looking at this again, I'm nervous that my version could miss some antichains if they not a subset of one that comes out in step 3.
```
```
I've been trying again for the past while to make sense of his recursive version to check the consistency, but it is still a mystery.
```
Do you have a copy of the article, Gabor? Citation is:
```
A. Kanevsky. On the number of minimum size separating vertex sets in a graph and how to find all of them. Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms, 1:411–21, 1990.
```
Peter

```
On Jan 30, 2008, at 3:20 PM, Gabor Csardi csardi-at-rmki.kfki.hu | igraph-help| wrote:
```
```
On Wed, Jan 30, 2008 at 03:05:57PM -0600, address@hidden wrote:
```Hi Simone,

I checked out your network, and it is taking a very long time. The
hangup is in the graph.antichains() function, which is part of the
```
algorithm for finding all minimal-size cutsets of a graph. Things run
```quickly with your network until you get to the 7th subgraph with
```
cohesion 14. I don't remember precisely, but the best known algorithm for finding all minimal-size cutsets is around O(k^5) for a k- cohesive
```graph. Your network is very dense and has a maximally-cohesive
subgraph of over 14.

Basically, I don't think it's a bug, I just think that it's a tricky
```
network to run cohesive blocking on. I've run the code on some graphs with aobut 170 nodes, but much less dense than yours, and it has taken
```days to finish running parallel on two 2.2Ghz processors. Cohesive
blocking is an inherently slow process. (This is one of the reasons
```
that k-cores are more widely used in the network literature: they are trivial to compute and often map very close to cohesive blocks on real networks.) I've considered rewriting some of the trickier bits of code
```in C instead of interpreted R, which would speed things up
considerably, but that's a ways down the road if ever.

My suggestions for you now are:
```
1) try out using the parallel processing options if you have a multi- core machine or access to an MPI network on multiple computers. Other
```than that there is not much that can be done.
```
```
```
I don't think that would help much with this graph, you need at least 5Gb
```of memory, and that is a very optimistic guess. The main problem is
not that graph.antichains() is slow, but that the memory requirements
are very high. Btw. it can be speeded up easily by not using
combn() for generating the combination, but something faster, i did

tmp <- get.edgelist(graph.full(acount))+1

which is kind of a hack, and that made it run into the memory limit.
Peter, can you summarize in five lines what graph.antichains() is
supposed to do? Just to see if it is worth thinking on a less
demanding implementation.

Thanks,
G.

```
```2) try running the function with verbose output
("cohesive.blocks(mynet,verbose=T)") and see if it's getting hung up
```
on one subgraph for more than a couple of hours or if it's progresing
```slowly.

Sorry I can't be of more help.
Peter

```
On Jan 30, 2008, at 5:10 AM, Simone Gabbriellini simone.gabbriellini-
```at-......... |igraph-help| wrote:

```
```Hello list,

I am experiencing a problem with cohesion.blocks().. I have 25
```
multiplex networks, and everything runs ok for almost all of them, but
```with 6 of them there is a problem: the computation starts but never
ends... I leave the computer calculating the blocks even for 30
minutes, but no result appear..
I have no clue what's happening, I receive no error message from R

simone

this is one of the "incriminated" network (.net format):

*Vertices 41
1 "Aiken"
2 "Ainon"
3 "Aniat"
4 "azor"
5 "Brenn Tantor"
6 "Bube"
7 "Fds"
8 "Flazzer"
9 "Frederick Brae"
10 "Gae"
11 "ginkobiloba"
12 "Hunter999"
13 "Iced"
14 "ilBestio"
15 "Klingo"
16 "Kveldersen"
17 "Lej"
18 "Lukenet"
20 "Manand"
21 "Marco_Rsr"
22 "milordz"
23 "Mondovich"
24 "Nemi"
25 "Nimion"
26 "OrkoPazZo"
27 "Ouba"
28 "Pendragon"
29 "Quill"
30 "reasae"
31 "rukwa"
32 "Sephi"
33 "Shariz"
34 "Shin Xaqer"
35 "Shiny"
36 "Simus"
37 "skyline"
38 "Stryker"
39 "Sualtan"
40 "Tremors"
41 "Yusaku"
*Arcs
9    10    1    c blue
9    27    1    c blue
9    24    1    c blue
9    5    1    c blue
9    37    1    c blue
9    11    1    c blue
9    14    1    c blue
37    10    1    c blue
37    27    1    c blue
37    24    1    c blue
37    5    1    c blue
37    11    1    c blue
37    9    1    c blue
37    14    1    c blue
10    27    1    c blue
10    24    1    c blue
10    5    1    c blue
10    37    1    c blue
10    11    1    c blue
10    9    1    c blue
10    14    1    c blue
8    10    1    c blue
8    19    1    c blue
8    5    1    c blue
8    40    1    c blue
8    26    1    c blue
8    11    1    c blue
8    16    1    c blue
5    10    1    c blue
5    19    1    c blue
5    40    1    c blue
5    8    1    c blue
5    26    1    c blue
5    11    1    c blue
5    16    1    c blue
40    9    1    c blue
40    16    1    c blue
11    10    1    c blue
11    19    1    c blue
11    5    1    c blue
11    40    1    c blue
11    8    1    c blue
11    26    1    c blue
11    16    1    c blue
11    27    1    c blue
11    24    1    c blue
11    37    1    c blue
11    9    1    c blue
11    14    1    c blue
26    10    1    c blue
26    19    1    c blue
26    5    1    c blue
26    40    1    c blue
26    8    1    c blue
26    11    1    c blue
26    16    1    c blue
26    39    1    c blue
26    9    1    c blue
10    19    1    c blue
10    40    1    c blue
10    8    1    c blue
10    26    1    c blue
10    16    1    c blue
39    5    1    c blue
39    40    1    c blue
39    26    1    c blue
39    9    1    c blue
5    39    1    c blue
5    9    1    c blue
40    39    1    c blue
40    5    1    c blue
40    26    1    c blue
9    39    1    c blue
9    40    1    c blue
9    26    1    c blue
12    10    1    c blue
12    27    1    c blue
12    15    1    c blue
12    16    1    c blue
10    15    1    c blue
10    12    1    c blue
16    40    1    c blue
16    9    1    c blue
16    10    1    c blue
16    27    1    c blue
16    15    1    c blue
16    12    1    c blue
15    10    1    c blue
15    27    1    c blue
15    12    1    c blue
15    16    1    c blue
9    16    1    c blue
27    10    1    c blue
27    15    1    c blue
27    12    1    c blue
27    16    1    c blue
16    19    1    c blue
16    5    1    c blue
16    8    1    c blue
16    26    1    c blue
16    11    1    c blue
19    10    1    c blue
19    5    1    c blue
19    40    1    c blue
19    8    1    c blue
19    26    1    c blue
19    11    1    c blue
19    16    1    c blue
40    10    1    c blue
40    19    1    c blue
40    8    1    c blue
40    11    1    c blue
34    10    1    c blue
34    5    1    c blue
34    40    1    c blue
34    11    1    c blue
10    34    1    c blue
37    19    1    c blue
37    40    1    c blue
37    8    1    c blue
37    26    1    c blue
37    21    1    c blue
37    31    1    c blue
27    19    1    c blue
27    5    1    c blue
27    40    1    c blue
27    8    1    c blue
27    26    1    c blue
27    37    1    c blue
27    21    1    c blue
27    31    1    c blue
8    27    1    c blue
8    37    1    c blue
8    21    1    c blue
8    31    1    c blue
31    5    1    c blue
31    11    1    c blue
5    27    1    c blue
5    37    1    c blue
5    21    1    c blue
5    31    1    c blue
5    34    1    c blue
21    10    1    c blue
21    27    1    c blue
21    19    1    c blue
21    5    1    c blue
21    40    1    c blue
21    8    1    c blue
21    26    1    c blue
21    37    1    c blue
21    31    1    c blue
40    27    1    c blue
40    37    1    c blue
40    21    1    c blue
40    31    1    c blue
10    21    1    c blue
10    31    1    c blue
11    34    1    c blue
11    31    1    c blue
40    34    1    c blue
31    10    1    c blue
31    27    1    c blue
31    19    1    c blue
31    40    1    c blue
31    8    1    c blue
31    26    1    c blue
31    37    1    c blue
31    21    1    c blue
19    27    1    c blue
19    37    1    c blue
19    21    1    c blue
19    31    1    c blue
37    2    1    c blue
26    27    1    c blue
26    37    1    c blue
26    21    1    c blue
26    31    1    c blue
16    37    1    c blue
10    2    1    c blue
37    16    1    c blue
5    2    1    c blue
37    18    1    c blue
31    16    1    c blue
7    10    1    c blue
7    27    1    c blue
7    16    1    c blue
31    18    1    c blue
10    7    1    c blue
16    31    1    c blue
16    18    1    c blue
16    7    1    c blue
5    18    1    c blue
36    19    1    c blue
36    5    1    c blue
36    16    1    c blue
5    36    1    c blue
16    36    1    c blue
16    29    1    c blue
16    6    1    c blue
6    29    1    c blue
6    5    1    c blue
6    18    1    c blue
6    16    1    c blue
29    5    1    c blue
29    18    1    c blue
29    6    1    c blue
29    16    1    c blue
27    7    1    c blue
19    36    1    c blue
19    18    1    c blue
5    29    1    c blue
5    6    1    c blue
18    29    1    c blue
18    5    1    c blue
18    6    1    c blue
18    16    1    c blue
18    19    1    c blue
18    37    1    c blue
18    31    1    c blue
24    10    1    c blue
24    27    1    c blue
24    5    1    c blue
24    37    1    c blue
24    11    1    c blue
24    9    1    c blue
24    14    1    c blue
8    6    1    c blue
8    9    1    c blue
9    8    1    c blue
9    6    1    c blue
10    6    1    c blue
27    6    1    c blue
27    9    1    c blue
37    20    1    c blue
20    10    1    c blue
20    5    1    c blue
20    37    1    c blue
10    20    1    c blue
5    20    1    c blue
37    6    1    c blue
26    6    1    c blue
26    20    1    c blue
6    10    1    c blue
6    27    1    c blue
6    8    1    c blue
6    9    1    c blue
6    19    1    c blue
6    26    1    c blue
6    37    1    c blue
6    20    1    c blue
20    19    1    c blue
20    26    1    c blue
20    6    1    c blue
10    39    1    c blue
10    17    1    c blue
5    17    1    c blue
6    39    1    c blue
6    11    1    c blue
6    17    1    c blue
6    34    1    c blue
27    39    1    c blue
27    11    1    c blue
27    17    1    c blue
27    34    1    c blue
16    39    1    c blue
16    17    1    c blue
16    34    1    c blue
39    10    1    c blue
39    27    1    c blue
39    19    1    c blue
39    8    1    c blue
39    6    1    c blue
39    37    1    c blue
39    11    1    c blue
39    17    1    c blue
39    16    1    c blue
39    34    1    c blue
10    36    1    c blue
5    15    1    c blue
9    19    1    c blue
9    17    1    c blue
9    34    1    c blue
39    31    1    c blue
31    39    1    c blue
6    15    1    c blue
6    31    1    c blue
6    36    1    c blue
36    10    1    c blue
36    27    1    c blue
36    26    1    c blue
36    6    1    c blue
36    15    1    c blue
36    11    1    c blue
36    31    1    c blue
31    2    1    c blue
15    5    1    c blue
15    26    1    c blue
15    6    1    c blue
15    11    1    c blue
15    31    1    c blue
15    36    1    c blue
31    6    1    c blue
31    15    1    c blue
31    36    1    c blue
11    6    1    c blue
11    15    1    c blue
11    36    1    c blue
11    39    1    c blue
11    17    1    c blue
19    6    1    c blue
19    20    1    c blue
19    39    1    c blue
19    9    1    c blue
19    17    1    c blue
19    34    1    c blue
27    36    1    c blue
8    2    1    c blue
10    18    1    c blue
10    25    1    c blue
10    3    1    c blue
17    10    1    c blue
17    27    1    c blue
17    39    1    c blue
17    19    1    c blue
17    5    1    c blue
17    8    1    c blue
17    26    1    c blue
17    6    1    c blue
17    37    1    c blue
17    11    1    c blue
17    9    1    c blue
17    16    1    c blue
17    34    1    c blue
34    27    1    c blue
34    39    1    c blue
34    19    1    c blue
34    8    1    c blue
34    26    1    c blue
34    6    1    c blue
34    37    1    c blue
34    9    1    c blue
34    17    1    c blue
34    16    1    c blue
2    10    1    c blue
2    5    1    c blue
2    8    1    c blue
2    31    1    c blue
9    18    1    c blue
9    15    1    c blue
9    25    1    c blue
9    31    1    c blue
9    3    1    c blue
39    24    1    c blue
39    18    1    c blue
39    15    1    c blue
39    25    1    c blue
39    3    1    c blue
3    10    1    c blue
3    27    1    c blue
3    39    1    c blue
3    24    1    c blue
3    5    1    c blue
3    40    1    c blue
3    18    1    c blue
3    8    1    c blue
3    26    1    c blue
3    6    1    c blue
3    15    1    c blue
3    9    1    c blue
3    25    1    c blue
3    31    1    c blue
3    16    1    c blue
37    39    1    c blue
37    17    1    c blue
37    34    1    c blue
26    24    1    c blue
26    18    1    c blue
26    15    1    c blue
26    25    1    c blue
26    3    1    c blue
26    36    1    c blue
26    17    1    c blue
26    34    1    c blue
6    24    1    c blue
6    40    1    c blue
6    25    1    c blue
6    3    1    c blue
5    24    1    c blue
5    25    1    c blue
5    3    1    c blue
8    39    1    c blue
8    17    1    c blue
8    34    1    c blue
8    24    1    c blue
8    18    1    c blue
8    15    1    c blue
8    25    1    c blue
8    3    1    c blue
27    24    1    c blue
27    18    1    c blue
27    25    1    c blue
27    3    1    c blue
24    39    1    c blue
24    40    1    c blue
24    18    1    c blue
24    8    1    c blue
24    26    1    c blue
24    6    1    c blue
24    15    1    c blue
24    25    1    c blue
24    31    1    c blue
24    16    1    c blue
24    3    1    c blue
15    39    1    c blue
15    24    1    c blue
15    40    1    c blue
15    18    1    c blue
15    8    1    c blue
15    9    1    c blue
15    25    1    c blue
15    3    1    c blue
37    30    1    c blue
5    30    1    c blue
31    24    1    c blue
31    9    1    c blue
31    25    1    c blue
31    3    1    c blue
30    10    1    c blue
30    19    1    c blue
30    5    1    c blue
30    37    1    c blue
19    30    1    c blue
25    10    1    c blue
25    27    1    c blue
25    39    1    c blue
25    24    1    c blue
25    5    1    c blue
25    40    1    c blue
25    18    1    c blue
25    8    1    c blue
25    26    1    c blue
25    6    1    c blue
25    15    1    c blue
25    9    1    c blue
25    31    1    c blue
25    16    1    c blue
25    3    1    c blue
18    10    1    c blue
18    26    1    c blue
18    23    1    c blue
26    23    1    c blue
18    27    1    c blue
18    39    1    c blue
18    24    1    c blue
18    40    1    c blue
18    8    1    c blue
18    15    1    c blue
18    9    1    c blue
18    25    1    c blue
18    3    1    c blue
10    30    1    c blue
5    23    1    c blue
16    24    1    c blue
16    25    1    c blue
16    3    1    c blue
10    23    1    c blue
40    24    1    c blue
40    18    1    c blue
40    6    1    c blue
40    15    1    c blue
40    25    1    c blue
40    3    1    c blue
37    36    1    c blue
31    30    1    c blue
31    13    1    c blue
37    13    1    c blue
30    26    1    c blue
30    31    1    c blue
30    2    1    c blue
30    36    1    c blue
30    13    1    c blue
26    30    1    c blue
26    2    1    c blue
26    13    1    c blue
5    13    1    c blue
20    9    1    c blue
9    20    1    c blue
2    26    1    c blue
2    37    1    c blue
2    30    1    c blue
2    36    1    c blue
2    13    1    c blue
6    23    1    c blue
36    37    1    c blue
36    30    1    c blue
36    2    1    c blue
36    13    1    c blue
23    10    1    c blue
23    5    1    c blue
23    18    1    c blue
23    26    1    c blue
23    6    1    c blue
13    5    1    c blue
13    26    1    c blue
13    37    1    c blue
13    30    1    c blue
13    31    1    c blue
13    2    1    c blue
13    36    1    c blue
31    34    1    c blue
13    10    1    c blue
13    11    1    c blue
11    13    1    c blue
18    20    1    c blue
10    13    1    c blue
20    18    1    c blue
34    31    1    c blue
15    19    1    c blue
15    37    1    c blue
41    10    1    c blue
41    27    1    c blue
41    5    1    c blue
41    26    1    c blue
27    41    1    c blue
26    41    1    c blue
10    41    1    c blue
37    15    1    c blue
18    11    1    c blue
5    41    1    c blue
11    18    1    c blue
38    27    1    c blue
38    5    1    c blue
5    38    1    c blue
27    38    1    c blue
19    15    1    c blue
15    28    1    c blue
15    30    1    c blue
15    20    1    c blue
16    28    1    c blue
16    30    1    c blue
16    20    1    c blue
37    28    1    c blue
27    30    1    c blue
5    28    1    c blue
30    8    1    c blue
30    6    1    c blue
30    28    1    c blue
30    15    1    c blue
30    20    1    c blue
30    16    1    c blue
30    27    1    c blue
10    28    1    c blue
6    28    1    c blue
6    30    1    c blue
19    28    1    c blue
20    8    1    c blue
20    28    1    c blue
20    30    1    c blue
20    15    1    c blue
20    16    1    c blue
20    36    1    c blue
1    10    1    c blue
1    5    1    c blue
1    26    1    c blue
1    11    1    c blue
1    9    1    c blue
9    1    1    c blue
5    1    1    c blue
8    28    1    c blue
8    30    1    c blue
8    20    1    c blue
8    36    1    c blue
28    10    1    c blue
28    19    1    c blue
28    5    1    c blue
28    8    1    c blue
28    6    1    c blue
28    37    1    c blue
28    30    1    c blue
28    15    1    c blue
28    20    1    c blue
28    16    1    c blue
28    36    1    c blue
36    8    1    c blue
36    28    1    c blue
36    20    1    c blue
15    2    1    c blue
15    17    1    c blue
31    22    1    c blue
31    28    1    c blue
14    10    1    c blue
14    27    1    c blue
14    24    1    c blue
14    5    1    c blue
14    37    1    c blue
14    11    1    c blue
14    9    1    c blue
9    2    1    c blue
9    22    1    c blue
9    28    1    c blue
9    13    1    c blue
22    28    1    c blue
22    9    1    c blue
22    31    1    c blue
22    2    1    c blue
22    13    1    c blue
28    22    1    c blue
28    9    1    c blue
28    31    1    c blue
28    2    1    c blue
28    13    1    c blue
11    2    1    c blue
11    1    1    c blue
31    29    1    c blue
10    29    1    c blue
27    14    1    c blue
29    10    1    c blue
29    26    1    c blue
29    31    1    c blue
29    2    1    c blue
17    15    1    c blue
17    2    1    c blue
5    14    1    c blue
26    29    1    c blue
35    10    1    c blue
35    5    1    c blue
35    20    1    c blue
35    2    1    c blue
35    16    1    c blue
35    34    1    c blue
5    35    1    c blue
16    2    1    c blue
16    35    1    c blue
20    2    1    c blue
20    34    1    c blue
20    35    1    c blue
10    35    1    c blue
13    22    1    c blue
13    28    1    c blue
13    9    1    c blue
26    1    1    c blue
10    1    1    c blue
2    29    1    c blue
2    16    1    c blue
2    11    1    c blue
2    17    1    c blue
2    20    1    c blue
2    34    1    c blue
2    35    1    c blue
2    22    1    c blue
2    28    1    c blue
2    9    1    c blue
2    15    1    c blue
17    31    1    c blue
31    17    1    c blue
18    2    1    c blue
2    18    1    c blue
34    20    1    c blue
34    2    1    c blue
34    35    1    c blue
4    10    1    c red
4    16    1    c red
4    15    1    c red
5    37    1    c red
5    40    1    c red
5    27    1    c red
5    26    1    c red
10    39    1    c red
10    26    1    c red
10    32    1    c red
10    16    1    c red
10    15    1    c red
10    27    1    c red
10    14    1    c red
10    4    1    c red
10    29    1    c red
10    24    1    c red
14    15    1    c red
14    32    1    c red
14    39    1    c red
14    27    1    c red
14    10    1    c red
15    14    1    c red
15    26    1    c red
15    39    1    c red
15    4    1    c red
15    10    1    c red
15    40    1    c red
15    27    1    c red
15    32    1    c red
15    16    1    c red
15    29    1    c red
16    15    1    c red
16    26    1    c red
16    10    1    c red
16    4    1    c red
16    39    1    c red
24    27    1    c red
24    10    1    c red
26    37    1    c red
26    32    1    c red
26    40    1    c red
26    33    1    c red
26    39    1    c red
26    5    1    c red
26    15    1    c red
26    29    1    c red
26    16    1    c red
26    27    1    c red
26    10    1    c red
27    15    1    c red
27    40    1    c red
27    29    1    c red
27    14    1    c red
27    24    1    c red
27    39    1    c red
27    5    1    c red
27    26    1    c red
27    37    1    c red
27    33    1    c red
27    32    1    c red
27    10    1    c red
29    39    1    c red
29    26    1    c red
29    15    1    c red
29    10    1    c red
29    33    1    c red
29    27    1    c red
32    26    1    c red
32    15    1    c red
32    39    1    c red
32    27    1    c red
32    14    1    c red
32    10    1    c red
33    27    1    c red
33    29    1    c red
33    26    1    c red
37    5    1    c red
37    27    1    c red
37    26    1    c red
37    40    1    c red
39    32    1    c red
39    16    1    c red
39    29    1    c red
39    14    1    c red
39    15    1    c red
39    26    1    c red
39    27    1    c red
39    10    1    c red
40    5    1    c red
40    27    1    c red
40    26    1    c red
40    15    1    c red
40    37    1    c red

_______________________________________________
igraph-help mailing list
http://lists.nongnu.org/mailman/listinfo/igraph-help
```
```

_______________________________________________
igraph-help mailing list
http://lists.nongnu.org/mailman/listinfo/igraph-help
```
```
--

_______________________________________________
igraph-help mailing list
http://lists.nongnu.org/mailman/listinfo/igraph-help
```
```

_______________________________________________
igraph-help mailing list
```