Colored graph isomorphisms: 1(red)->2(blue) vs 1(blue)->2(red)

Question

Given two simple graphs:

library(igraph)

g <- graph.empty()
g <- g + vertices(1,2,3)
g <- g + path(1,2,3)


g1 <- g
V(g1)$color = c(1,2,2)
g2 <- g
V(g2)$color = c(2,1,1)

which look like:

par(mfrow=c(1,2))
palette(rainbow(3))
plot(g1)
plot(g2)

How come they are not isomorphic?

graph.isomorphic.vf2(g1,g2)$iso

FALSE

and most important, if this is not an isomorphism, how can I detect this kind of equivalence within igraph ?

Answer 1

(I post a first hack as an answer to keep the question uncluttered. This hack does not always work and therefore is faulty, see the second example below.

For a hack that does work, please see either my second answer or the other people answers!)

I find the canonical permutation of labels, then a canonical coloring of this new canonical graph, and then I can use vf2.

Our function to re-color the graph is:

# Convert aaabbccdefaa -> 111223345611
canonical <- function(input){
  labels <- unique(input)
  match(input, labels)
}

And now back to business:

g <- graph.empty()
g <- g + vertices(1,2,3)
g <- g + path(1,2,3)


g1 <- g
V(g1)$color = c(1,2,2)
g2 <- g
V(g2)$color = c(2,1,1)

# Find canonical topological labeling and then canonical coloring
g1 <- permute.vertices(g1, canonical.permutation(g1)$labeling)
g2 <- permute.vertices(g2, canonical.permutation(g2)$labeling)
V(g1)$color <- canonical(V(g1)$color)
V(g2)$color <- canonical(V(g2)$color)                     

par(mfrow=c(1,2))
palette(rainbow(3))
plot(g1)
plot(g2)

Which now will be detected as isomorfic:

#vf2 wants colors to be the same, not "up to a relabeling"
# this is why we use canonical colors
graph.isomorphic.vf2(g1, g2)$iso

TRUE

Failure example:

For this example, it does not work:

g1 <- graph.empty()
g1 <- g1 + vertices(1,2)
g1 <- g1 + edge(1,2)
V(g1)$color = c(1,2)

g2 <- graph.empty()
g2 <- g2 + vertices(1,2)
g2 <- g2 + edge(2,1)
V(g2)$color = c(2,1)

# Find canonical topological labeling and then canonical coloring
g1 <- permute.vertices(g1, canonical.permutation(g1)$labeling)
g2 <- permute.vertices(g2, canonical.permutation(g2)$labeling)
V(g1)$color <- canonical(V(g1)$color)
V(g2)$color <- canonical(V(g2)$color)                     

par(mfrow=c(1,2))
palette(rainbow(3))
plot(g1)
plot(g2)

graph.isomorphic.vf2(g1,g2)$iso
# FALSE 

Answer 2

Indeed Isomorphic wants the colour labels to match. The solution is to permute all colour labels and test whether one of them is isomorphic. If it is, then your graphs are isomorphic.

library(combinat)

colour_isomorphic<-function(g1,g2){

g2_copy<-g2
colour2<-unique(V(g2)$color)
colour2_permutations<-permn(colour2)

for(p in colour2_permutations){
names[p]<-as.character(colour2)
V(g2_copy)$color<-sapply(V(g2)$color, function(x) p[as.character(x)])
test_result<-graph.isomorphic.vf2(g1,g2_copy)$iso
if (test_result) {return(T)}


}

return(F)
}

colour_isomorphic(g1,g2) should now return TRUE and it should also work in the other test case of the other answer given. The only place where it can fail is if the colour labels are nor systematically chosen as the first n natural numbers (1,2,3,4,...) in which case you need to convert them to that first.