logo标签列表

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

rgraphigraphisomorphism
14

考虑两个简单图：

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)

graphs

它们为什么不同构？

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

错误

而且最重要的是，如果这不是同构，我如何在igraph中检测这种等价性？

看起来 graph.subisomorphic(g1,g2) 返回了 TRUE？你特别想使用 vf2 算法有什么原因吗？你可能需要检查一下 ?graph.subisomorphic.vf2 帮助页面上列出的参考文献，看看这个算法是否有已知的缺陷。 - MrFlick
我使用 vf2 的原因是，查看文档后，它似乎是唯一处理颜色的算法。 - alberto
4个回答
5

为保持问题清晰，我发布了一篇第一次的解答。这个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)

iso

现在将被检测为同构：

#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

fail

3
为了避免颜色置换，Bertrand Jouve向我指出了一个技巧，建议参考nauty用户指南(第58-59页)。这个想法是将顶点重新着色为相同的颜色，然后所有曾经共享相同颜色的顶点现在都有一条连接到公共顶点的边缘。然后我们可以应用一个经典的针对彩色图的vf2算法。

nauty

我的实现:

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解释的那样，首先检查它们是否具有相同的颜色频率。

2

Indeed 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)现在应该返回TRUE，并且它还应该在给出的另一个答案的另一个测试用例中起作用。 唯一可能失败的地方就是如果颜色标签不是按照第n个自然数（1,2,3,4，...）系统选择的，那么您需要将它们转换为第一个。

2
@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
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接