Цветные изоморфизмы графа: 1 (красный) → 2 (синий) против 1 (синий) → 2 (красный)

Ответ 1

Чтобы избежать цветовых перестановок, 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.

Ответ 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)

Что теперь будет обнаружено как изоморфное:

#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 

Ответ 3

Действительно, 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,...), и в этом случае вам нужно преобразовать их в первую.

Ответ 4

@bisounours_tronconneuse правильно указывает, что вы можете просто рассматривать каждое сопоставление от цветов одного графика к цветам другого, используя graph.isomorphic.vf2, чтобы проверить, являются ли перемаркированные графики изоморфными. Хотя это математически верно, это сложно вычислительно, потому что оно требует n! (n факториал) проверяет изоморфность пары графиков с n цветами. Это 3,6 миллиона проверок для графиков с 10 цветами и 9e157 проверок для графиков с 20 цветами, поэтому его можно использовать только в настройках с очень небольшим количеством цветов.

Мы могли бы быть намного эффективнее, учитывая один дополнительный факт: пара графиков может быть только изоморфна, если их цветовые частотные распределения точно совпадают. Это означает, что нам нужно только рассмотреть отображения между цветами с той же частотой в паре графов. В вашем вопросе есть только одно возможное сопоставление, потому что на каждом входном графике появляется один цвет один раз и один цвет появляется дважды. За исключением патологических случаев, когда многие цвета имеют одинаковые частоты в вашем графике, это должно привести к гораздо более эффективной процедуре проверки изоморфизма.

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! цветных отображений или более одного триллиона.

Одно слово предупреждения --- хотя эта процедура может быть более эффективной для многих пар графов, чем более наивный подход, она все еще имеет экспоненциальное худшее время исполнения, то есть есть классы графиков, где она будет выполняться довольно медленно.