彩色图形同构:1(红色) - >图2(蓝色)对1(蓝) - > 2(红色)
给定两个简单图:彩色图形同构:1(红色) - >图2(蓝色)对1(蓝) - > 2(红色)
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
?
为避免颜色排列,Bertrand Jouve指出我在nauty
user guide (pages 58-59)中建议的这个技巧。这个想法是重新调整顶点的颜色,然后用于共享相同颜色的所有顶点现在都有一个共同顶点的边。然后我们可以为彩色图表应用经典vf2
。
我的实现:
library(igraph)
isocolor.setup <- function(g){
# Transform a graph so that it can be used in colored isomorphism algorithms
# Args:
# g: graph
# Returns:
# Transformed graph
nvertices <- vcount(g)
colors <- unique(V(g)$color)
g <- add.vertices(g, length(colors), color=max(colors)+1)
for(i in 1:length(colors)){
group <- V(g)[V(g)$color==colors[i]]
aux.id <- nvertices + i
g[from = group, to = rep(aux.id,length(group))] <- TRUE
}
V(g)[1:nvertices]$color <- 1
V(g)[V(g)$color != 1]$color <- 2
return(g)
}
例子:
setup_palette <- function(g){
palette(rainbow(max(2,length(unique(V(g)$color)))))
}
par(mfrow=c(3,2))
# First graph
g1 <- graph.ring(6)
V(g1)$color <- c(1,1,2,2,3,3)
setup_palette(g1)
plot(g1)
g1.mapped <- isocolor.setup(g1)
setup_palette(g1.mapped)
setup_palette(g1.mapped)
plot(g1.mapped)
# Second graph
g2 <- graph.ring(6)
V(g2)$color <- c(2,3,2,3,1,1)
setup_palette(g2)
plot(g2)
g2.mapped<- isocolor.setup(g2)
setup_palette(g2.mapped)
plot(g2.mapped)
title(paste("\ng1 iso g2?", graph.isomorphic.vf2(g1.mapped, g2.mapped)$iso))
# Third graph
g3 <- graph.ring(6)
V(g3)$color <- c(1,1,3,3,2,2)
setup_palette(g3)
plot(g3)
g3.mapped<- isocolor.setup(g3)
setup_palette(g3.mapped)
plot(g3.mapped)
title(paste("\ng1 iso g3?", graph.isomorphic.vf2(g1.mapped, g3.mapped)$iso))
当然,我们应该检查,作为第一个过滤器,它们是否都具有相同的色频由解释@josilber。
(我发表的第一次入侵的回答为保持问题整洁。这个技巧并不总是有效,因此出现故障,请参阅下面的第二个例子。
对于没有工作黑客攻击,请参阅我的第二个答案或其他人的答案!)
我找到标准的规范置换,然后是这个新的规范图的规范着色,然后我可以使用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)
现在会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
故障实例:
在这个例子中,这是行不通的:
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
事实上同构希望彩色标签相匹配。解决方案是排列所有颜色标签并测试它们中的一个是否是同构的。如果是,那么你的图是同构的。
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)现在应该返回TRUE,它也应该给对方的回答的其他测试情况下工作。 它可能会失败的唯一地方是,如果颜色标签没有被系统地选为前n个自然数(1,2,3,4,...),在这种情况下,您需要将它们转换为第一个。
@bisounours_tronconneuse正确地指出,您可以考虑每个从一个图的颜色到另一个图的颜色的映射,使用graph.isomorphic.vf2
来检查重新标记的图是否是同构的。虽然这在数学上是正确的,但它在计算上具有挑战性,因为它需要n! (n阶乘)同构检查一对n个颜色的图。这是对10种颜色的图形进行360万次检查,对20种颜色的图形进行9e157次检查,因此显然它只能用于颜色数量很少的设置。
通过考虑一个附加事实,我们可能会更有效率:如果一对图的颜色频率分布完全匹配,则它们只能是同构的。这意味着我们只需要考虑一对图中具有相同频率的颜色之间的映射。在你的问题中,只有一个可能的映射,因为在每个输入图中有一种颜色出现一次,一种颜色出现两次。除了在图表中许多颜色具有相同频率的病理情况外,这应该会导致更有效的检查同构的过程。
library(igraph)
iso.josilber <- function(g1, g2) {
freq1 <- table(V(g1)$color)
freq2 <- table(V(g2)$color)
col2 <- as.character(V(g2)$color)
if (length(freq1) != length(freq2)) {
return(FALSE) # Different numbers of colors
}
relabels <- as.matrix(do.call(expand.grid, lapply(freq2, function(x) as.numeric(names(freq1[freq1 == x])))))
relabels <- relabels[apply(relabels, 1, function(x) length(unique(x)) == length(x)),]
print(paste("Number of reorderings to check:", nrow(relabels)))
if (nrow(relabels) == 0) {
return(FALSE) # No valid relabels based on frequency distribution
}
for (i in seq(nrow(relabels))) {
V(g2)$color <- relabels[i,][col2]
if(graph.isomorphic.vf2(g1,g2)$iso) {
return(TRUE) # Found an isomorphic relabeling
}
}
return(FALSE) # Checked all valid relabelings; none were isomorphic
}
iso.josilber(g1, g2)
回报TRUE
两个你在你的问题,你的答案带来的微小图形对。为了强调测试过程,考虑g1
,一个有100个节点的随机有向图,0.5个密度和15个随机选择的颜色,以及g2
,这是一个具有这些颜色的随机重新标记版本(又称同构)的相同图。
set.seed(144)
g1 <- erdos.renyi.game(100, 0.5)
V(g1)$color <- sample(1:15, 100, replace=T)
g2 <- g1
V(g2)$color <- sample(1:15)[V(g1)$color]
system.time(print(iso.josilber(g1, g2)))
# [1] "Number of reorderings to check: 144"
# [1] TRUE
# user system elapsed
# 0.172 0.004 0.189
请注意,彻底检查所有颜色映射的方法将需要检查15!颜色映射,或超过一万亿。
警告一句话---虽然这个过程在许多图对上可能比一个更天真的方法更有效,但它仍然具有指数最坏情况下的运行时间,这意味着存在一些图表类,它仍然会执行很慢。
josilber @bisounours_tronconneuse非常感谢!我用避免排列的新解决方案添加了新答案。我想你会喜欢它:)(除非我错过了一些不起作用的情况) – alberto
看起来像'graph.subisomorphic(g1,g2)'返回TRUE?你有没有特别想使用'vf2'算法?您可能想要查看'?graph.subisomorphic.vf2'帮助页面上列出的参考资料,以了解该算法有任何已知的缺点。 – MrFlick
我使用'vf2'的原因是,看着文档,在我看来,唯一的算法是处理颜色。 – alberto