Why does the the R package igraph say that these two graphs aren't isomorphic?

66 Views Asked by At

The code below uses the igraph package of R to generate two graphs, G1 and G2, which should be isomorphic. The first check claims they are not, but the second says they are. The only difference is that I replaced the 6's in the first e1 with 4's in the second e1.

library(igraph)
e1 = c(1,2,1,5,2,1,2,5,2,6,3,5,5,1,5,2,5,3,5,6,6,2,6,5)
e2 = c(1,2,1,3,1,4,1,5,2,1,2,5,3,1,3,5,4,1,5,1,5,2,5,3)
G1 = make_graph(e1)
G2 = make_graph(e2)
isomorphic(G1,G2)

e1 = c(1,2,1,5,2,1,2,5,2,4,3,5,5,1,5,2,5,3,5,4,4,2,4,5)
G1 = make_graph(e1)
isomorphic(G1,G2)

When I drew out the first two graphs it was clear to me that they were in fact isomorphic, as you can see in the image below.

Two isomorphic graphs

Why does the function isomorphic of the R package igraph give an incorrect result? Is it known that in some cases it doesn't work?

1

There are 1 best solutions below

0
On

I think you've been tripped up by the difference in the handling of numeric and character vectors by igraph::make_graph:

library(igraph)
e1 = as.character(c(1,2,1,5,2,1,2,5,2,6,3,5,5,1,5,2,5,3,5,6,6,2,6,5))
e2 = as.character(c(1,2,1,3,1,4,1,5,2,1,2,5,3,1,3,5,4,1,5,1,5,2,5,3))
G1 = make_graph(e1)
G2 = make_graph(e2)
isomorphic(G1,G2)
plot(G1); plot(G2)
#[1] TRUE

The "isolates" parameter is ignored in numeric arguments to make_graph, and it appears that numeric arguments cause a presumption that all values in the range of values are to be included.