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.
L’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.
A 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.
Il 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.
Infine, 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.
Abbiamo 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.
Se 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). Nel prossimo post concluderemo l’implementazione dell’algoritmo di colorazione di una mappa, realizzando il meccanismo ricorsivo che permette di “mettere insieme” tutti i pezzi cha abbiamo descritto fino ad ora.
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.
Se 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…