r - 彩色图同构: 1(red)->2(blue) vs 1(blue)->2(red)

给出两个简单的图:

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)

看起来像:

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

为什么它们不是同构的？

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

最重要的是，如果这不是同构，如何在igraph中检测到这种等效性？

最佳答案

(我发布了第一个hack来作为回答，以使问题更整洁。此hack 并不总是起作用，因此是错误的，请参见下面的第二个示例。

对于确实有效的骇客，请参阅我的第二个答案或其他人的答案!)

我找到标签的规范排列，然后找到这个新规范图的规范着色，然后可以使用vf2。

我们为图形重新着色的功能是:

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

现在回到正题:

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)

现在将其检测为等位同构的:

#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

失败示例:

对于此示例，它不起作用:

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

关于r - 彩色图同构: 1(red)->2(blue) vs 1(blue)->2(red)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29587032/