isomorfismi grafico colorato: 1 (rosso) -> 2 (blu) vs 1 (blu) -> 2 (rosso)

Question

Dati due semplici grafici:

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) 

che sembrano:

par(mfrow=c(1,2)) 
palette(rainbow(3)) 
plot(g1) 
plot(g2) 

Come mai non sono isomorfi?

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

FALSE

e più importante, se questo non è un isomorfismo, come posso rilevare questo tipo di equivalenza entro igraph?

Answer 1

Per evitare permutazioni di colore, Bertrand Jouve mi ha indirizzato a questo trucco suggerito nello nauty user guide (pages 58-59). L'idea è di ricolorare i vertici per essere tutti uguali e quindi tutti i vertici che condividevano lo stesso colore ora hanno un bordo per un vertice comune. E poi possiamo applicare un classico vf2 per grafici colorati.

mia implementazione:

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) 
} 

Esempi:

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)) 

Naturalmente dovremmo controllare, come un primo filtro, se entrambi hanno la stessa frequenza del colore come spiegato da @josilber.

Answer 2

(invio un primo hack come una risposta per mantenere la domanda ordinato. Questo mod non sempre funziona e quindi è difettosa, vedere il secondo esempio riportato di seguito.

Per un hack che funziona, per favore vedi o la mia seconda risposta o le altre persone risposte!)

Trovo la permutazione canonica delle etichette, quindi una colorazione canonica di questo nuovo grafico canonico, e quindi posso usare vf2.

La nostra funzione di ri-colore del grafico è:

# Convert aaabbccdefaa -> 111223345611 
canonical <- function(input){ 
    labels <- unique(input) 
    match(input, labels) 
} 

E ora di nuovo al lavoro:

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) 

Che ora sarà rilevato come 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 

TRUE

Fallimento esempio:

Per questo esempio, non funziona:

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 3

Infatti Isomorphic vuole le etichette di colore per abbinare. La soluzione è di permutare tutte le etichette a colori e verificare se una di esse è isomorfa. Se lo è, allora i tuoi grafici sono isomorfi.

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) dovrebbe restituire TRUE e dovrebbe funzionare anche nell'altro caso prova dell'altra risposta data. L'unico punto in cui può fallire è se le etichette dei colori non sono né sistematicamente scelte come i primi n numeri naturali (1,2,3,4, ...) nel qual caso è necessario convertirle in quella prima.

Answer 4

@bisounours_tronconneuse indica correttamente che è possibile considerare ogni mappatura dai colori di un grafico ai colori dell'altro, usando graph.isomorphic.vf2 per verificare se i grafici reclamati sono isomorfi. Mentre questo è matematicamente vero, è computazionalmente impegnativo perché richiede n! (n factorial) isomorfismo controlla una coppia di grafici con n colori. Si tratta di 3,6 milioni di controlli per i grafici con 10 colori e 9e157 controlli per i grafici con 20 colori, quindi chiaramente potrebbe essere utilizzato solo in un'impostazione con un numero molto piccolo di colori.

Potremmo potenzialmente essere molto più efficienti considerando un fatto aggiuntivo: una coppia di grafici può essere solo isomorfa se le loro distribuzioni di frequenza del colore corrispondono esattamente. Ciò significa che dobbiamo solo considerare le mappature tra i colori con la stessa frequenza nella coppia di grafici. Nella tua domanda, c'è solo una possibile mappatura perché in ogni grafico di input c'è un colore che appare una volta e un colore appare due volte. Tranne che nei casi patologici in cui molti colori hanno frequenze identiche nel tuo grafico, questo dovrebbe portare a una procedura molto più efficiente per il controllo dell'isomorfismo.

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) rendimenti TRUE per entrambi i minuscoli coppie grafico si poneva nella tua domanda e la risposta. Per testare la procedura, prendere in considerazione g1, un grafico orientato casualmente con 100 nodi, densità 0,5 e 15 colori selezionati a caso e g2, un grafico identico con una versione di questi colori (in caso di isomorfismo).

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 

Si noti che l'approccio che controlla in modo esauriente tutte le mappature dei colori sarebbe necessario per controllare 15! mappature dei colori, o più di un trilione.

Un avvertimento --- se questa procedura può essere più efficace in molte coppie grafico di un approccio più naive, ha ancora esponenziale caso peggiore runtime, significa che ci sono classi di grafi dove sarà ancora eseguire molto lentamente .