给定两个简单的图形:
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
FALSE
最重要的是,如果这不是同构,我如何在
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
TRUE
失败示例 :
对于这个例子,它不起作用:
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/