Python - Grafici
Un grafico è una rappresentazione pittorica di un insieme di oggetti in cui alcune coppie di oggetti sono collegate da collegamenti. Gli oggetti interconnessi sono rappresentati da punti chiamati vertici e i collegamenti che collegano i vertici sono chiamati bordi. I vari termini e funzionalità associati a un grafico sono descritti in dettaglio nel nostro tutorial qui. In questo capitolo vedremo come creare un grafico e aggiungervi vari elementi di dati usando un programma python. Di seguito sono riportate le operazioni di base che eseguiamo sui grafici.
- Visualizza i vertici del grafico
- Visualizza i bordi del grafico
- Aggiungi un vertice
- Aggiungi un bordo
- Creazione di un grafico
Un grafico può essere facilmente presentato utilizzando i tipi di dati del dizionario python. Rappresentiamo i vertici come chiavi del dizionario e la connessione tra i vertici chiamata anche bordi come valori nel dizionario.
Dai un'occhiata al grafico seguente:
Nel grafico sopra
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}
Possiamo presentare questo grafico in un programma python come di seguito.
# Create the dictionary with graph elements
graph = { "a" : ["b","c"],
"b" : ["a", "d"],
"c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}
# Print the graph
print(graph)
Quando il codice sopra viene eseguito, produce il seguente risultato:
{'c': ['a', 'd'], 'a': ['b', 'c'], 'e': ['d'], 'd': ['e'], 'b': ['a', 'd']}
Visualizza i vertici del grafico
Per visualizzare i vertici del grafico troviamo semplicemente le chiavi del dizionario del grafico. Usiamo il metodo keys ().
class graph:
def __init__(self,gdict=None):
if gdict is None:
gdict = []
self.gdict = gdict
# Get the keys of the dictionary
def getVertices(self):
return list(self.gdict.keys())
# Create the dictionary with graph elements
graph_elements = { "a" : ["b","c"],
"b" : ["a", "d"],
"c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}
g = graph(graph_elements)
print(g.getVertices())
Quando il codice sopra viene eseguito, produce il seguente risultato:
['d', 'b', 'e', 'c', 'a']
Visualizza i bordi del grafico
Trovare i bordi del grafico è un po 'più complicato dei vertici poiché dobbiamo trovare ciascuna delle coppie di vertici che hanno un bordo tra di loro. Quindi creiamo un elenco vuoto di bordi, quindi iteriamo attraverso i valori dei bordi associati a ciascuno dei vertici. Viene formato un elenco contenente il gruppo distinto di bordi trovato dai vertici.
class graph:
def __init__(self,gdict=None):
if gdict is None:
gdict = {}
self.gdict = gdict
def edges(self):
return self.findedges()
# Find the distinct list of edges
def findedges(self):
edgename = []
for vrtx in self.gdict:
for nxtvrtx in self.gdict[vrtx]:
if {nxtvrtx, vrtx} not in edgename:
edgename.append({vrtx, nxtvrtx})
return edgename
# Create the dictionary with graph elements
graph_elements = { "a" : ["b","c"],
"b" : ["a", "d"],
"c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}
g = graph(graph_elements)
print(g.edges())
Quando il codice sopra viene eseguito, produce il seguente risultato:
[{'b', 'a'}, {'b', 'd'}, {'e', 'd'}, {'a', 'c'}, {'c', 'd'}]
Aggiunta di un vertice
L'aggiunta di un vertice è semplice in cui aggiungiamo un'altra chiave aggiuntiva al dizionario del grafico.
class graph:
def __init__(self,gdict=None):
if gdict is None:
gdict = {}
self.gdict = gdict
def getVertices(self):
return list(self.gdict.keys())
# Add the vertex as a key
def addVertex(self, vrtx):
if vrtx not in self.gdict:
self.gdict[vrtx] = []
# Create the dictionary with graph elements
graph_elements = { "a" : ["b","c"],
"b" : ["a", "d"],
"c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}
g = graph(graph_elements)
g.addVertex("f")
print(g.getVertices())
Quando il codice sopra viene eseguito, produce il seguente risultato:
['f', 'e', 'b', 'a', 'c','d']
Aggiunta di un bordo
L'aggiunta di un arco a un grafico esistente implica il trattamento del nuovo vertice come una tupla e la convalida se il bordo è già presente. In caso contrario, viene aggiunto il bordo.
class graph:
def __init__(self,gdict=None):
if gdict is None:
gdict = {}
self.gdict = gdict
def edges(self):
return self.findedges()
# Add the new edge
def AddEdge(self, edge):
edge = set(edge)
(vrtx1, vrtx2) = tuple(edge)
if vrtx1 in self.gdict:
self.gdict[vrtx1].append(vrtx2)
else:
self.gdict[vrtx1] = [vrtx2]
# List the edge names
def findedges(self):
edgename = []
for vrtx in self.gdict:
for nxtvrtx in self.gdict[vrtx]:
if {nxtvrtx, vrtx} not in edgename:
edgename.append({vrtx, nxtvrtx})
return edgename
# Create the dictionary with graph elements
graph_elements = { "a" : ["b","c"],
"b" : ["a", "d"],
"c" : ["a", "d"],
"d" : ["e"],
"e" : ["d"]
}
g = graph(graph_elements)
g.AddEdge({'a','e'})
g.AddEdge({'a','c'})
print(g.edges())
Quando il codice sopra viene eseguito, produce il seguente risultato:
[{'e', 'd'}, {'b', 'a'}, {'b', 'd'}, {'a', 'c'}, {'a', 'e'}, {'c', 'd'}]