13

给定两个简单的图表：

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

错误的

最重要的是，如果这不是同构，我怎样才能检测到这种等价性igraph？

4

4 回答 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)

异

现在将被检测为异构体：

#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

失败

于 2015-04-13T14:57:04.407 回答
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！颜色映射，或超过一万亿。

一个警告 --- 尽管这个过程在许多图对上可能比一种更幼稚的方法更有效，但它仍然具有指数最坏情况运行时，这意味着它仍然会执行非常缓慢的图类。

于 2015-04-21T01:36:22.070 回答
2

事实上，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,...)，在这种情况下，您需要先将它们转换为那个。

于 2015-04-19T11:08:32.540 回答
2

为了避免颜色排列，Bertrand Jouve向我指出了nauty用户指南（第 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 解释的相同的颜色频率。

于 2015-04-21T10:34:51.937 回答