Introduzione
In tutti i linguaggi di programmazione, i modelli di strutture dati risultano un elemento importantissimo per la gestione di una programmazione avanzata. Quindi è importantissimo avere familiarità con loro e su come utilizzarli. Una struttura dati molto importante è quella dei grafi. In Python non esiste una struttura dati primitiva per poter gestire questo genere di modelli, ed è quindi necessario implementarla. In questo articolo vedremo cosa sono i grafi, le loro carattersitiche e come implementare tutta quella serie di funzioni utili per la loro gestione e manipolazione dei dati contenuti all’interno.
I grafi
Per prima cosa, vediamo che cosa sono i grafi. Nel corso dell’articolo, il concetto di grafo diverrà via via più semplice man mano che verranno specificate le sue caratteristiche tramite delle definizioni e delle illustrazioni grafiche.
Per prima cosa si può cominciare con il dire che un grafo è costituito da una serie di nodi (nodes), generalmente indicati con dei pallini, alcuni dei quali sono connessi tra di loro. Le connessioni (edges) invece sono rappresentate tramite delle linee che congiungono due nodi.
La figura seguente mostra una tipica rappresentazione di un grafo.
Le connessioni possono essere rappresentate in due diversi modi: con una semplice linea se la connessione non ha una direzione, altrimenti con una freccia se la connessione è diretta da un nodo verso un altro (arc). Un grafo che possiede connessioni con delle direzioni viene generalmente indicato come grafo orientato (directed graph).
Certamente avrai notato che moltissimi sistemi seguono questo tipo di modello. Basta pensare per esempio all’informatica, come per esempio i computer connessi all’interno di una rete, oppure a Facebook con gli utenti e le loro amicizie o appartenenze a gruppi. Ma questo modello si può trovare anche in tantissimi altri sistemi del mondo della fisica, della biologia, della chimica (basta pensare alle molecole), e anche della statistica e dell’economia.
I modelli di queste strutture dati infatti servono ad organizzare e a contenere oggetti o elementi ed è quindi fondamentale la loro implementazione attraverso linguaggi di programmazione. In particolar modo quando si necessita di lavorare su strutture dati che seguono questa tipologia di modello.
Prima di incominciare, una piccola premessa: per quanto riguarda l’implementazione in Python, Gran parte del codice presente in questo articolo è stato preso dalla pagina sui grafi sul sito di Python Course. In questo articolo, ho effettuato alcune modifiche al codice per renderlo più leggibile e facilmente adattabile alle esigenze didattiche.
Implementazione di un grafo in Python: i dizionari
Python, come del resto molti altri linguaggi di programmazione, non ha strutture dati di default per specificare i grafi, ed è quindi necessario implementare questo modello. A tale scopo si utilizzano generalmente strutture dati più semplici, e per quanto riguarda Python, una di queste strutture dati che fa proprio al caso nostro è il dizionario. Infatti, sfrutteremo la sua struttura chiave-valore per indicare un qualsiasi grafo, utilizzando la minor sintassi possibile.
Una cosa importante di cui tenere conto: la scelta dei dizionari non è obbligatoria, anzi si possono utilizzare anche altre strutture dati. Ma una volta fatta la scelta della struttura dati base per rappresentare il modello, non si potrà più tornare indietro, dato che tutte le funzioni implementate successivamente faranno riferimento strettamente ad essa.
Se prendiamo come riferimento il grafo rappresentato nella figura precedente, si avrà la seguente implementazione:
graph = { "A" : ["B", "C"],
"B" : ["D", "E", "A"],
"C" : ["A"],
"D" : ["B", "E"],
"E" : ["B", "D"]
}Come possiamo vedere, le chiavi del dizionario indicano i nodi del grafo, e come valore per ciascuno di essi si esprime l’elenco dei nodi connessi ad esso, tramite una lista.
L’unico problema con questa rappresentazione del grafo è che non si hanno espresse esplicitamente le connessioni tra i vari nodi ma è possibile implementare una funzione che ne generi la lista, passando come argomento il grafo.
Ogni connessione verrà espressa tramite una tupla a 2 valori che conterrà al suo interno i due nodi connessi.
(“A”, “B”)
Implementiamo quindi la funzione che ci darà in output una lista contenente tutte le connessioni (edges).
def edges(graph):
edges = []
for node in graph:
for neighbour in graph[node]:
edges.append((node, neighbour))
return edges
print(edges(graph))
Se eseguite il codice otterrete il seguente risultato:
Ma come vediamo subito, esistono dei doppioni. Per esempio la funzione ci restituisce la connessione dal nodo A al nodo C, ma anche quella dal nodo C al nodo A. Ora se abbiamo a che fare con un grafo orientato, l’ordine degli elementi all’interno della connessione dovrebbe essere rilevante, quindi (A,C) non sarebbe uguale a (C,A). Se non fosse orientato allora (A,C) e (C,A) rappresenterebbero la stessa connessione (edge). Inoltre l’esistenza allo stesso tempo sia di (A,C) che di (C,A) in un grafo orientato potrebbe creare dei problemi (qual è la direzione di quella connessione?).
Quindi è più corretto filtrare le connessioni ridondanti (tenendo conto che il grafo non sia orientato). Nel caso fosse orientato, non si avrebbe la doppia rappresentazione nel modello, ma solo una delle due.
Modifichiamo quindi la funzione indicata sopra con questa:
def edges(graph):
edges = []
for node in graph:
for neighbour in graph[node]:
if (neighbour, node) not in edge
edges.append((node, neighbour))
return edges
print(edges(graph))
Eseguendo questa volta il codice, si ottiene:
Implementazione di un grafo tramite una classe
L’implementazione che abbiamo utilizzato finora segue un ambito di programmazione funzionale. Anche se è adatta per i primi approcci implementativi, la programmazione da tenere in considerazione dovrebbe essere quella orientata agli oggetti. Per questo motivo, implementeremo la rappresentazione dei grafi tramite una classe.
class Graph(object):
def __init__(self, graph=None):
if graph == None:
graph = {}
self.__graph = graphIn questa definizione di classe abbiamo fatto in modo che se il costruttore della classe possa essere chiamato anche senza alcun argomento:
Graph()
nel tal caso creerà un grafo vuoto (senza nodi e connessioni) utilizzando un dizionario come struttura dati. Se invece il costruttore verrà chiamato con un dizionario passato come argomento:
Graph(graph)
quest’ultimo verrà convertito in un grafo.
Adesso che abbiamo implementato la classe ed il costruttore, sarà necessario implementare alcuni metodi.
Il primo metodo di cui dobbiamo tenere conto è quello che permette l’aggiunta di un nodo all’oggetto grafo istanziato. Questo non farà altro che aggiungere un nodo al modello, e quindi nell’implementazione, una nuova coppia chiave-valore al dizionario.
def add_node(self, node):
if node not in self.__graph_dict:
self.__graph_dict[node] = []
Una cosa molto importante da tenere in considerazione, è quello di controllare che il nodo che stiamo inserendo nel grafo non esista già al suo interno. Solo in caso negativo, si avrà l’aggiunta di un nuovo nodo.
Dal codice potrete vedere che il nodo che viene aggiunto non ha alcuna connessione con il resto dei nodi presenti nel grafo. Questo tipo di nodo viene chiamato nodo isolato.
Un secondo metodo molto importante da implementare è quindi quello che ci permetta di creare delle connessioni tra i nodi all’interno del grafo.
def add_edge(self, edge):
edge = set(edge)
(node1, node2) = tuple(edge)
if node1 in self.__graph:
self.__graph[node1].append(node2)
else:
self.__graph[node1] = [node2]
In questo caso, il controllo interno da effettuare è quello di verificare l’esistenza dei due nodi all’interno del grafo. In caso positivo si creerà quindi una connessione tra di essi, aggiungendo alla chiave del dizionario corrispondente al nodo, il valore dell’altro nodo nella lista dei nodi connessi.
Infine altri due metodi necessari, soprattutto per testare il corretto funzionamento di quello che stiamo implementando, sono quelli che ci permettono di conoscere i nodi e le connessioni (edges) presenti correntemente all’interno del grafo. Creiamo quindi questi due metodi chiamandoli appunto nodes() ed edges().
def nodes(self):
return list(self.__graph_dict.keys())
def edges(self):
edges = []
for node in self.__graph:
for neighbour in self.__graph[node]:
if (neighbour, node) not in edges:
edges.append((node, neighbour))
return edges
Infine per poter vedere lo stato di un grafo, abbiamo bisogno di visualizzare sia i nodi che le connessioni correnti su console. A tale scopo implementeremo il metodo __str__() che ci permetterà di visualizzare il grafo, passandolo direttamente come argomento nella funzione print().
def __str__(self):
res = "nodes: "
for node in self.nodes():
res += str(node) + " "
res += "\nedges: "
for edge in self.edges():
res += str(edge) + " "
return res
Proviamo il codice
Adesso che abbiamo implementato tutto ciò che ci serve come base di un modello dei grafi. Facciamo qualche esempio per vedere come funziona e se tutto è stato fatto correttamente
Per prima cosa abbiamo già definito il grafo:
graph = { "A" : ["B", "C"],
"B" : ["D", "E"],
"C" : ["A"],
"D" : ["B", "E"],
"E" : ["B", "D"]
}
g = Graph(graph)L’istanza g corrisponderà al seguente grafo:
Se vogliamo vedere il grafo su console, possiamo scrivere:
print(g)
ed otterremo:
Adesso aggiungiamo il nodo F.
g.add_node("F")e quindi avremo un nodo isolato.
Se lo visualizziamo su console otterrremo:
Adesso non ci rimane che creare la connessione tra il nodo C ed il nodo F.
g.add_edge(("C","F"))ed ottenere il grafo
I Path nei Grafi
Dall’esempio precedente possiamo vedere che abbiamo già a disposizione una buona base per il modello dei grafi. Infatti è già possibile rappresentare tutti i grafi in maniera semplice e allo stesso tempo controllare lo stato corrente del grafo.
Ora passiamo a considerare una serie di operazioni che generalmente si effettuano sui grafi. Queste operazioni, più o meno semplici servono ad effettuare delle analisi sullo stato dei grafi. Infatti anche se il grafo dell’esempio è molto semplice da considerare, esistono grafi di enorme complessità e quindi è spesso necessario utilizzare degli automatismi per effettuare delle analisi.
La prima operazione che prenderemo in analisi è il calcolo dei path, cioè i percorsi possibili che si possono tracciare su di un grafo partendo da un nodo per raggiungerne un altro, sfruttando le connessioni presenti tra di essi.
Il path in un grafo non orientato è infatti:
- una sequenza di nodi P = ( n1, n2, …, nn ) adiacenti (connessi) tra di loro che definisce un possibile percorso da un nodo di partenza n1 ad uno di destinazione nn.
- quando il percorso non passa per più di una volta sullo stesso nodo.
Adesso che abbiamo una definizione di cosa sia un path, riprendiamo il nostro grafo di esempio, e valutiamo un possibile path che parta dal nodo A per finire nel nodo E.
Ma un’altro path possibile è quello che invece di passare per D, passi direttamente dal nodo B al nodo D.
Quindi, su quel poco che abbiamo visto, possiamo fare alcune considerazioni. Il grafo di esempio è davvero molto semplice dato che è composto da soli 5 nodi. Nonostante ciò esistono due path possibili tra il nodo A ed il nodo E. In esempi reali, con centinaia di nodi, possiamo immaginare la complessità nello stabilire il numero dei path possibili.
Inoltre è chiaro che tra tutti i path possibili, quello che certamente sarà di nostro interesse, sarà il path più breve, cioè quello che attraverserà il minor numero di nodi possibile. Quindi sarà davvero importante disporre di una serie di funzioni che ci permettano di trovare programmaticamente il path più breve avendo definito un qualsiasi grafo possibile.
Implementiamo la funzione seguente all’interno della classe (metodo).
def find_path(self, start_node, end_node, path=None):
if path == None:
path = []
graph = self.__graph_dict
path = path + [start_node]
if start_node == end_node:
return path
if start_node not in graph:
return None
for node in graph[start_node]:
if node not in path:
extended_path = self.find_path(node,
end_node,
path)
if extended_path:
return extended_path
return None
Analizzando la funzione all’interno si può vedere come sia una funzione ricorsiva, dato che richiama se stessa all’interno. Partendo dal nodo di partenza, ad ogni ricorsione, aggiunge via via un nodo al path, controllando che
- il nodo non sia il nodo di arrivo
- il nodo non sia già presente nel path
Se la utilizziamo con il grafo dell’esempio precedente:
g = Graph(graph)
path = g.find_path("A","E")
print(path)otteniamo:
Comunque questo metodo, così come è implementato non è di grande utilità, dato che trova un solo path. Quello di cui abbiamo bisogno è per esempio quello di conoscere tutti i path possibili tra due nodi. Definiamo quindi un nuovo metodo.
def find_all_paths(self, start_vertex, end_vertex, path=[]):
""" find all paths from start_vertex to
end_vertex in graph """
graph = self.__graph_dict
path = path + [start_vertex]
if start_vertex == end_vertex:
return [path]
if start_vertex not in graph:
return []
paths = []
for vertex in graph[start_vertex]:
if vertex not in path:
extended_paths = self.find_all_paths(vertex,
end_vertex,
path)
for p in extended_paths:
paths.append(p)
return paths
Riproviamo il codice utilizzando questa volta il nuovo metodo:
g = Graph(graph)
paths = g.find_all_paths("A","E")
print(paths)otteniamo giustamente tutti i path possibili all’interno del grafo tra i nodi A ed E:
Abbiamo ottenuto una lista di path. Ora per conoscere quale tra questi è il più breve basta usare il comando:
print(min(paths, key=len))
Conclusioni
In questa prima parte abbiamo visto come implementare in Python il modello dei grafi utilizzando una classe in modo da seguire la programmazione orientata agli oggetti. Abbiamo inoltre cominciato ad implementare alcune operazioni base come il calcolo dei path possibili e la ricerca di quello più breve. Nel prossimo articolo vedremo altri concetti correlati ai grafi come il grado di un grafo e la degree sequence.