2 つの単純なグラフがあるとします。
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でしょうか?
（質問を整理するために、最初のハックを回答として投稿します。このハックは常に機能するとは限らないため、問題があります。以下の2番目の例を参照してください。
機能するハックについては、私の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
色の順列を避けるために、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 で説明されているように、両方が同じ色周波数を持っているかどうかを確認する必要があります。
graph.isomorphic.vf2@bisounours_tronconneuse は、1 つのグラフの色から別のグラフの色へのすべてのマッピングを検討して、再ラベル付けされたグラフが同型かどうかを確認できることを正しく指摘しています。これは数学的には正しいのですが、n! が必要なため計算が困難です。(n factorial) isomorphism は、n 色のグラフのペアをチェックします。これは、10 色のグラフで 360 万チェック、20 色のグラフで 9e157 チェックなので、非常に少ない色数の設定でしか使用できないことは明らかです。
1 つの追加の事実を考慮することで、はるかに効率的になる可能性があります。グラフのペアは、色の頻度分布が正確に一致する場合にのみ同形になる可能性があります。これは、グラフのペアで同じ頻度を持つ色間のマッピングのみを考慮する必要があることを意味します。あなたの質問では、各入力グラフに 1 つの色が 1 回表示され、1 つの色が 2 回表示されるため、可能なマッピングは 1 つだけです。グラフ内で多くの色が同一の周波数を持つ病理学的なケースを除いて、これは同形性をチェックするためのはるかに効率的な手順につながるはずです。
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質問と回答で提示した小さなグラフのペアの両方を返します。手順のストレス テストを行うには、g1100 個のノード、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 をチェックする必要があることに注意してください。カラー マッピング、または 1 兆以上。
警告の一言 --- この手順は、多くのグラフ ペアに対してより単純なアプローチよりも効率的かもしれませんが、最悪の場合の実行時間は依然として指数関数的です。
実際、Isomorphic はカラー ラベルを一致させたいと考えています。解決策は、すべてのカラー ラベルを並べ替えて、そのうちの 1 つが同型かどうかをテストすることです。そうであれば、グラフは同形です。
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)
}
color_isomorphic(g1,g2) は TRUE を返すようになり、指定された他の回答の他のテスト ケースでも機能するはずです。失敗する可能性がある唯一の場所は、カラーラベルが最初の n 個の自然数 (1,2,3,4,...) として体系的に選択されていない場合です。この場合、それらを最初に変換する必要があります。