Implementazione¶
Usando i dizionari, è semplice implementare le liste di adiacenza in Python.
Nella nostra implementazioni del ADT Graph creeremo due classi (vedi Listing 1 e Listing 2), Graph, che mantiene la lista di tutti i vertici,
e Vertex, che rappresenta ogni vertice nel grafo.
Ogni Vertex usa un dizionario per mantenere traccia dei vertici a cui è connesso e del peso di ogni arco. Questo dizionario è chiamato connectedTo. Il codice sotto mostra la classe Vertex. Il costruttore semplicemente inizializza l’id, che tipicamente è una stringa, e il dizionario connectedTo. Il metodo addNeighbor è usato per aggiungere una connessione da questo vertice a un altro. Il metodo getConnections ritorna tutti i vertici nella lista di adiacenza, come rappresentato dalla variabile connectedTo. Il metodo getWeight ritorna il peso di un arco da questo vertice al vertice passato come parametro.
Listing 1
class Vertex:
def __init__(self,key):
self.id = key
self.connectedTo = {}
def addNeighbor(self,nbr,weight=0):
self.connectedTo[nbr] = weight
def __str__(self):
return str(self.id) + ' connectedTo: ' + str([x.id for x in self.connectedTo])
def getConnections(self):
return self.connectedTo.keys()
def getId(self):
return self.id
def getWeight(self,nbr):
return self.connectedTo[nbr]
La classe Graph, mostrata nel codice seguente, contiene un dizionario che mappa nomi in oggetti vertice. In Figura 3 questo oggetto dizionario è rappresentato dalla scatola grigia. La classe Graph fornisce metodi per aggiungere vertici a un grafo e connetterli. Il metodo getVertices ritorna i nomi di tutti i vertici nel grafo. Inoltre, abbiamo implementato il metodo
__iter__ per rendere facile l’iterazione su tutti i vertici di un grafo dato. Insieme, i due metodi permettono di iterare sui vertici di un grafo usando il nome o gli oggetti stessi.
Listing 2
class Graph:
def __init__(self):
self.vertList = {}
self.numVertices = 0
def addVertex(self,key):
self.numVertices = self.numVertices + 1
newVertex = Vertex(key)
self.vertList[key] = newVertex
return newVertex
def getVertex(self,n):
if n in self.vertList:
return self.vertList[n]
else:
return None
def __contains__(self,n):
return n in self.vertList
def addEdge(self,f,t,cost=0):
if f not in self.vertList:
nv = self.addVertex(f)
if t not in self.vertList:
nv = self.addVertex(t)
self.vertList[f].addNeighbor(self.vertList[t], cost)
def getVertices(self):
return self.vertList.keys()
def __iter__(self):
return iter(self.vertList.values())
Usando le classi Graph e Vertex, il seguente codice Python, crea il grafo in Figura 1. Prima creiamo sei vertici numerati da 0 a 5. Successivamente mostriamo il dizionario dei vertici. E’ importante notare che per tutte le chiavi da 0 a 5 abbiamo creato una istanza di un Vertex. Successivamente, aggiungiamo gli archi che connettono i vertici tra di loro. Infine, un ciclo interno controlla che ogni arco è memorizzato correttamente. Possiamo controllare che l’output della lista degli archi corrisponda all’insieme degli archi che avevamo definito per la Figura 1.
>>> g = Graph()
>>> for i in range(6):
... g.addVertex(i)
>>> g.vertList
{0: <adjGraph.Vertex instance at 0x41e18>,
1: <adjGraph.Vertex instance at 0x7f2b0>,
2: <adjGraph.Vertex instance at 0x7f288>,
3: <adjGraph.Vertex instance at 0x7f350>,
4: <adjGraph.Vertex instance at 0x7f328>,
5: <adjGraph.Vertex instance at 0x7f300>}
>>> g.addEdge(0,1,5)
>>> g.addEdge(0,5,2)
>>> g.addEdge(1,2,4)
>>> g.addEdge(2,3,9)
>>> g.addEdge(3,4,7)
>>> g.addEdge(3,5,3)
>>> g.addEdge(4,0,1)
>>> g.addEdge(5,4,8)
>>> g.addEdge(5,2,1)
>>> for v in g:
... for w in v.getConnections():
... print("( %s , %s )" % (v.getId(), w.getId()))
...
( 0 , 5 )
( 0 , 1 )
( 1 , 2 )
( 2 , 3 )
( 3 , 4 )
( 3 , 5 )
( 4 , 0 )
( 5 , 4 )
( 5 , 2 )