彩色图形同构：1（红色） - >图2（蓝色）对1（蓝） - > 2（红色）

Question

给定两个简单图：

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？

Answer 1

为避免颜色排列，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。

Answer 2

（我发表的第一次入侵的回答为保持问题整洁。这个技巧并不总是有效，因此出现故障，请参阅下面的第二个例子。

对于没有工作黑客攻击，请参阅我的第二个答案或其他人的答案！）

我找到标准的规范置换，然后是这个新的规范图的规范着色，然后我可以使用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 

Answer 3

事实上同构希望彩色标签相匹配。解决方案是排列所有颜色标签并测试它们中的一个是否是同构的。如果是，那么你的图是同构的。

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，...），在这种情况下，您需要将它们转换为第一个。

Answer 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！颜色映射，或超过一万亿。

警告一句话---虽然这个过程在许多图对上可能比一个更天真的方法更有效，但它仍然具有指数最坏情况下的运行时间，这意味着存在一些图表类，它仍然会执行很慢。