彩色图同构:1(红色) - > 2(蓝色)vs 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

假

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

Answer 1

(我发布第一个黑客作为答案,以保持问题整洁.这个黑客并不总是有效,因此是错误的,请参阅下面的第二个例子.

对于有效的黑客,请查看我的第二个答案或其他人的答案!)

我找到了标签的规范排列,然后是这个新规范图的规范着色,然后我可以使用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

真正

失败的例子:

对于此示例,它不起作用:

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 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 所解释的那样。