Colorazione di una mappa: il codice
Nel libro descriviamo un algoritmo per colorare una mappa cartografica con al più sei colori, ma non forniamo al lettore il codice Julia in grado di eseguire tale algoritmo. Colmiamo qui questa lacuna. Poiché il codice è abbastanza lungo e “complicato” lo presentiamo a piccoli passi.
Notiamo anzitutto come sia possibile rappresentare il grafo delle vicinanze tra nazioni mediante una tabella delle adiacenze g. Poiché è possibile fare degli errori quando si scrive la tabella delle adiacenze, il programma include anche una funzione check che verifica che ogni nodo non sia adiacente a se stesso e che la tabella sia simmetrica (ciò ovviamente non garantisce che la tabella rappresenti in modo corretto la mappa dell’Europa). In altre parole, questa funzione verifica che una nazione non sia vicina di se stessa e che, se una nazione A è vicina di una nazione B, allora la nazione B sia vicina della nazione A.
Provate a modificare un elemento della tabella (trasformando uno 0 in un 1 o viceversa) e vedrete che la funzione check vi segnalerà un errore.
# Questa e' la tabella di adiacenza del grafo che rappresenta la
# relazione di vicinato delle 28 nazioni europee a cui si fa
# riferimento nelle pagine 29-34 del libro
g = [
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0],
[0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1],
[0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0],
[0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,1],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,1,0,1],
[0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,0,0,0,1],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,1],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,0,1,0],
[0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,1,0],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,1],
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,1,0,0,1],
[0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,1,0,0,0,1,1,0]
]
# Questa funzione verifica che la tabella di adiacenza del grafo
# di cui vogliamo calcolare la colorazione mediante 6 colori, sia
# simmetrica: se un nodo i e' collegato a un nodo j, allora il
# nodo j deve essere collegato al nodo i. Se la tabella non e'
# simmetrica, la funzione mostra le coppie di indici i e j, per le
# quali g[i][j] e' diverso da g[j][i]. La funzione verifica anche che
# un nodo non sia adiacente di se stesso.
function check(g)
for i in 1:length(g)
if g[i][i] != 0
println(i," ",i)
return false
end
for j in 1:length(g)
if (g[i][j] != g[j][i])
println(i," ",j)
return false
end
end
end
return true
endL’algoritmo per la colorazione della mappa europea, descritto nel libro, opera nel modo seguente. Fintanto che il grafo contiene dei nodi con un numero di vicini maggiore o uguale a sei, cerchiamo un nodo con un numero di vicini minore di sei e lo cancelliamo dal grafo (tale nodo deve esistere in quanto il numero medio di vicini è inizialmente inferiore a 6 e, ogni volta che cancelliamo un nodo, tale numero medio rimane inferiore a sei). Mostriamo ora come sia possibile cancellare un nodo dal grafo, calcolare il massimo numero di vicini di un nodo e cercare un nodo con un numero di vicini inferiore a sei.
Per quello che riguarda la cancellazione di un nodo, possiamo usare un “trucco” abbastanza frequente in applicazioni informatiche: invece di cancellare “fisicamente” il nodo, ricalcolando una nuova tabella delle adiacenze, possiamo “marcare” il nodo come “cancellato” modificando il valore della tabella delle adiacenze corrispondente alla linea e alla colonna i, dove i è l’indice del nodo. Tale valore è inizialmente uguale a 0, in quanto un nodo non è vicino di se stesso: per cancellare “logicamente” il nodo, possiamo quindi impostare questo valore a -1. In conclusione, se la tabella delle adiacenze contiene nella casella corrispondente alla linea i e alla colonna i il valore -1, allora questo vuol dire che il nodo i non è, al momento, presente nel grafo. In modo simile, possiamo “riattivare” il nodo i quando dovremo reinserirlo nel grafo: a tale scopo sarà sufficiente impostare nuovamente il valore della casella corrispondente alla linea i e alla colonna i a 0. Queste due operazioni di cancellazione e ripristino di un nodo sono realizzate dalle due funzioni deletenode e restorenode.
# Questa funzione effettua una cancellazione 'logica' di un
# nodo del grafo, impostando il valore della tabella di adiacenza
# in riga i e colonna i a -1.
function deletenode(g,i)
g[i][i] = -1
end
# Questa funzione ripristina un nodo precedentemente cancellato,
# impostando di nuovo il valore della tabella di adiacenza in
# riga i e colonna i a 0.
function restorenode(g,i)
g[i][i] = 0
endA questo punto, il numero di vicini di un nodo i può essere facilmente calcolato analizzando i valori inclusi nella linea i: per ciascuna colonna j, se il nodo j non è stato “cancellato” (ovvero se il valore contenuto nella casella corrispondente alla linea j e alla colonna j non è 1) il numero di vicini del nodo i aumenta di 1 se il nodo i è collegato al nodo j (ovvero se se il valore contenuto nella casella corrispondente alla linea i e alla colonna j è 1). Questo è quanto viene fatto dalla funzione nodedegree.
# Questa funzione calcola il grado di un nodo non cancellato,
# semplicemente sommando il numero di 1 presenti nella riga
# corrispondente al nodo.
function nodedegree(g,i)
d = 0
for j in 1:length(g)
if (g[j][j] == 0)
d = d+g[i][j]
end
end
return d
endIl massimo numero di vicini di un nodo può essere ottenuto calcolando, per ogni nodo i che non sia stato cancellato (ovvero tale che il valore contenuto nella casella corrispondente alla linea i e alla colonna i non sia -1), il suo numero di vicini: se tale numero è maggiore del massimo numero di vicini attualmente noto, allora aggiorniamo il massimo numero di vicini. Questo è quanto viene fatto dalla funzione maxdegree.
# Questa funzione calcola il massimo grado dei nodi non cancellati,
# usando la funzione che calcola il grado di ogni nodo non cancellato
# e in modo simile alla funzione descritta nel libro per trovare il
# massimo valore in una sequenza.
function maxdegree(g)
max = 0
for i in 1:length(g)
if (g[i][i] == 0)
d = nodedegree(g,i)
if (max < d)
max = d
end
end
end
return max
endInfine, nella funzione nextnode cerchiamo un nodo con un numero di vicini minore di sei e con un massimo numero di vicini (in modo da eliminare più collegamenti possibili e “avvicinarci” più velocemente a un grafo in cui tutti i nodi abbiano un numero di vicini inferiore a sei). Tale funzione è praticamente identica alla funzione maxdegree: l’unica differenza è che in essa i nodi con grado maggiore o uguale sei non sono considerati e che memorizziamo anche l’indice del nodo attualmente corrispondente al massimo numero di vicini.
# Questa funzione cerca un nodo non cancellato di grado massimo,
# tra tutti i nodi non cancellati di grado al piu' 5.
function nextnode(g)
max,imax = 0,0
for i in 1:length(g)
if (g[i][i] == 0)
d = nodedegree(g,i)
if (d < 6 && max <= d)
max = d
imax = i
end
end
end
return imax
endAbbiamo quindi visto come sia possibile cancellare “virtualmente” i nodi di un grafo e utilizzare questa funzionalità per ricondurci, nel caso della mappa europea, a un grafo in cui ogni nodo ha al più cinque vicini. A questo punto, possiamo colorare con sei colori i nodi ancora “vivi” usando un semplice algoritmo goloso: esaminiamo un nodo dopo l’altro (non considerando i nodi cancellati, ovvero i nodi con indice i tali che il valore contenuto nella casella della tabella delle adiacenze corrispondente alla linea i e alla colonna i non è 1) e gli assegna uno qualunque dei colori non usati dai suoi vicini (ancora “vivi”) e già colorati (poiché il numero di vicini di ogni nodo è al più uguale a 5, ci sarà sempre un colore a disposizione tra 1 e 6).
Questo è quanto viene fatto dalla funzione simplecolor. I colori assegnati ai nodi sono memorizzati nell’array c: il colore del nodo con indice i e’ uguale a c[i]. Tale funzione utilizza la funzione nodecolor che esamina i colori dei nodi vicini di un nodo con indice i, considerando solo quelli che hanno già assegnato un colore (ovvero solo i nodi con indice j tali che c[j] è diverso da zero). Per ogni nodo esaminato, la funzione memorizza i colori usati in un array dc: se il colore k è stato usato, allora dc[k] è posto uguale a 1. Alla fine la funzione assegna al nodo i il primo colore non utilizzato dai suoi vicini, ovvero il primo indice ic tale che dc[ic] è uguale a zero.
# Questa funzione restituisce un colore che possa essere usato
# per colorare un nodo, che assumiamo abbia grado al piu' 5.
# A tale scopo esamina tutti i vicini colorati, imposta
# come non disponibile il colore da essi usato e restituisce
# il primo colore disponibile.
function nodecolor(g,i,c)
dc = zeros(Int64,6)
for j in 1:length(g)
if (g[i][j] == 1 && c[j] != 0)
dc[c[j]] = 1
end
end
ic = 1
while (dc[ic] > 0)
ic = ic+1
end
return ic
end
# Questa funzione colora un grafo in cui tutti i nodi
# hanno grado al piu' 5, esaminando un nodo dopo l'altro
# e assegnandogli uno dei colori non usati dai suoi
# vicini gia' colorati.
function simplecolor(g)
c = zeros(Int64,length(g))
for i in 1:length(g)
if (g[i][i] == 0)
c[i] = nodecolor(g,i,c)
end
end
return c
endSe eseguiamo la funzione simplecolor sulla tabella delle adiacenze della mappa europea ottenuta dopo aver cancellato i nodi corrispondenti a Austria, Francia, Polonia e Ungheria, otteniamo la seguente colorazione dei rimanenti paesi:
[1,1,1,1,1,1,1,1,2,2,2,1,2,1,1,1,2,1,1,2,0,1,2,2,0,0,0,3]
(come si può vedere, solo tre colori sono effettivamente usati e i paesi corrispondenti ai nodi cancellati hanno assegnato il colore 0).
Completiamo ora l’implementazione dell’algoritmo per colorare una mappa con al più sei colori, , realizzando il meccanismo ricorsivo che permette di “mettere insieme” tutti i pezzi cha abbiamo descritto fino ad ora. Il programma include le funzioni che abbiamo visto in precedenza e un’ultima funzione color che implementa l’algoritmo ricorsivo descritto nel libro. Se il numero massimo di vicini non cancellati è inferiore a 6, allora tale funzione usa l’algoritmo goloso implementato nella funzione simplecolor vista nel post precedente. Altrimenti, la funzione cerca un nodo con al più cinque vicini mediante la funzione nextnode che abbiamo esaminato in precedenza, lo cancella “virtualmente” dal grafo e ricorsivamente colora il grafo così ottenuto. Al termine dell’invocazione ricorsiva, la funzione reinserisce il nodo cancellato e lo colora con uno dei sei colori che non e’ stato utilizzato da alcuno dei suoi al più cinque vicini.
# Questa funzione colora il grafo usando l'algoritmo
# ricorsivo descritto nel libro, che 'cancella' un nodo
# di grado inferiore a 6, colora in modo ricorsivo il grafo
# restante, ripristina il nodo 'cancellato' e lo colora con
# uno dei colori non usati dai suoi vicini.
function color(g)
if (maxdegree(g)<6)
return simplecolor(g)
else
u = nextnode(g)
deletenode(g,u)
c = color(g)
restorenode(g,u)
c[u] = nodecolor(g,u,c)
return c
end
endSe eseguiamo la funzione color sulla tabella delle adiacenze della mappa europea, otteniamo la seguente colorazione dei 28 paesi:
[1,1,1,1,1,1,1,1,2,2,2,1,2,1,1,1,2,1,1,2,4,1,2,2,3,4,4,3]
Come si può vedere, solo quattro colori sono effettivamente usati: effettivamente, il ben noto teorema dei quattro colori afferma che ogni mappa può essere colorato con al più quattro colori: ma questa è un’altra storia…