fastgreedy.community segfaults on non-simple graph

[Nick Hamblet]

While the following work fine:

fastgreedy.community(graph(c(1,1), directed=FALSE))
fastgreedy.community(graph(c(1,1,1,2), directed=FALSE))
fastgreedy.community(graph(c(1,1,1,2,2,2), directed=FALSE))

The following causes a segfault:

fastgreedy.community(graph(c(1,1,2,2), directed=FALSE)

This is with igraph_0.6-1 in R:
> library(igraph)
> sessionInfo()
R version 2.15.2 (2012-10-26)
Platform: x86_64-pc-linux-gnu (64-bit)

locale:
 [1] LC_CTYPE=en_US.utf8 LC_NUMERIC=C
 [3] LC_TIME=en_US.utf8 LC_COLLATE=en_US.utf8
 [5] LC_MONETARY=en_US.utf8 LC_MESSAGES=en_US.utf8
 [7] LC_PAPER=C LC_NAME=C
 [9] LC_ADDRESS=C LC_TELEPHONE=C
[11] LC_MEASUREMENT=en_US.utf8 LC_IDENTIFICATION=C

attached base packages:
[1] stats graphics grDevices utils datasets methods base

other attached packages:
[1] igraph_0.6-1

[Gábor Csárdi (gabor.csardi)]

Hi, I started the release process for 0.6.4, so I postponed this to 0.6.5, sorry about that.

[Tamás Nepusz (ntamas)]

No worries, at least it gives me more time to fix it ;)

[Tamás Nepusz (ntamas)]

The bug appears only if the graph contains isolated vertices with loop edges. One can work around it by removing these vertices or their loop edges. I will commit a proper bugfix soon.

[Nick Hamblet (nick-hamblet)]

Tamás, I've got a graph for which is.connected returns TRUE, but fastgreedy.community still segfaults. It has two multiple edges, but I think no loop edges. Unfortunately, it's a bit large. I'm going to work on getting a smaller example to post here.

[Tamás Nepusz (ntamas)]

That would be awesome. I know it's a bit cumbersome when it comes to segfaults, but try removing nodes iteratively until you are not getting the segfault any more.

[Nick Hamblet (nick-hamblet)]

Focusing on the neighborhood of vertices associated with my parallel edges, I've got the following test case:

fastgreedy.community(graph(c(2,1,3,1,3,1),directed=FALSE), weights=c(.0714, 3, .167)) # SEGFAULT

Note that it seems to depend on the weights, as the following goes fine:

fastgreedy.community(graph(c(2,1,3,1,3,1),directed=FALSE), weights=c(1,1,1))

[Tamás Nepusz (ntamas)]

Okay, the bug is not really in fastgreedy.community(). It is true that the current implementation of this algorithm is not designed for graphs with multiple edges, but the thing is that the implementation _checks_ whether the graph has multiple edges or not, and _should_ have terminated with an error when you tried to run it on a graph with multiple edges.

The bug lies in the igraph_has_multiple function of the C core, which claims that this graph has no multiple edges while it has. Since we are very close to the release of igraph 0.6.4, I will not bother with upgrading the implementation of fastgreedy.community to a new version which handles multiple edges (since you can collapse multiple edges into a single one using simplify() anyway) but I will fix igraph_has_multiple instead.

[Tamás Nepusz (ntamas)]

I mean, not in igraph 0.6.4 (for which the release process has started already) but in igraph 0.6.5.

[Tamás Nepusz (ntamas)]

Fixed in #3081 in 0.6-main and in #3116 in trunk.

[Gábor Csárdi (gabor.csardi)]

The development of igraph has moved to github, so please do not comment on this bug here. You are of course welcome to comment on github, here:
https://github.com/igraph/igraph/issues/131