彩色图同构：1(red)->2(blue) vs 1(blue)->2(red)
Colored graph isomorphisms: 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
FALSE
最重要的是，如果这不是同构，我如何检测 igraph 中的这种等价？
(我 post 第一个 hack 作为答案以保持问题的整洁。这个 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
确实 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) 现在应该 return 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) returns 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 个！颜色映射，或超过一万亿。
一个警告词——虽然这个过程在许多图对上可能比更天真的方法更有效，但它仍然具有指数级的最坏情况运行时间，这意味着有 类 个图它仍然会执行得很慢。
为避免颜色排列，Bertrand Jouve pointed to me to this trick suggested in the 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 所解释的相同的颜色频率。
给定两个简单的图表：
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 中的这种等价？
(我 post 第一个 hack 作为答案以保持问题的整洁。这个 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
确实 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) 现在应该 return 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) returns 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 个！颜色映射，或超过一万亿。
一个警告词——虽然这个过程在许多图对上可能比更天真的方法更有效，但它仍然具有指数级的最坏情况运行时间，这意味着有 类 个图它仍然会执行得很慢。
为避免颜色排列，Bertrand Jouve pointed to me to this trick suggested in the 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 所解释的相同的颜色频率。