graph_matrix_dijkstra.py
graph_matrix_dijkstra.py
—
Python Source,
13 KB (14333 bytes)
Dateiinhalt
# Graph mit Adjazenzmatrix und Dijkstra-Implementierung
# Daten: Einzugsgebiet der Kursschüler (Ignaz-Kögler-Gymnasiums LL)
# Prioriätswarteschlange aus heap.py in Verwendung
from turtle import * # Zeichenmodul laden
from heap import Heap # Prioritätswarteschlange
class GKnoten(object):
"Modelliert Graph-Knoten"
def __init__(self,x, y, name, größe, marker):
"Konstruktor"
self.x = x # x-Koordinate
self.y = y # y-Koordinate
self.name = name # Knotenname
self.größe = größe # Knotengröße
self.marker = marker # Markierungsattribut
def __str__(self):
return self.name # Ausgabe Konsole
def __repr__(self):
return self.name # Ausgabe via 'print()'
class GMatrix(object):
"Adjazenzmatrix"
def __init__(self, x,y,name, größe=1, marker=None):
"Konstruktor"
self.gliste=[GKnoten(x,y,name,größe,marker)] # Liste mit Start-GKnoten
self.gmatrix = [[0]] # vorbefüllt
self.tsucheliste = [] # Hilfsliste für Baumdarstellung bei tsuche
def textausgabe(self):
"gibt Matrix in Textform als Tabelle aus"
print("\nvon\\n\t", end="") # Starte Kopfzeile mit Bezeichnern
for i in self.gliste: # durchlaufe die Liste aller GKnoten
print(i.name[:3], end="\t") # nur die ersten drei Zeichen
print() # neue Zeile
for i in range(len(self.gmatrix)): # durchlaufe zeilenweise alle Indexe
print(self.gliste[i].name[:3],
end="\t") # Bezeichner Start-GKnoten
for j in self.gmatrix[i]:
print(j, end="\t") # printe die Entfernungen pro Zeile
print() # neue Zeile
def addGKnoten(self, neuKnot):
"fügt neuen Knoten in gliste ein und erweitert die Matrix"
if neuKnot not in self.gliste: # Knoten neuKnot echt neu?...
self.gliste.append(neuKnot) # ...dann aufnehmen
for i in self.gmatrix: # durchlaufe alle Zeilen...
i.append(0) # ...und füge eine 0 an
self.gmatrix.append([0 for j in self.gliste])# neue 0er-Zeile
else:
print("Graphknoten",neuKnot,"bereits vorhanden")
def addKante(self, startKnoten, zielKnoten, gewicht,rückweg=True):
"fügt Kante zw. startKnoten und zielKnoten mit 'gewicht' ein"
for i in range(len(self.gliste)):
if self.gliste[i].name == startKnoten:
startIndex = i
if self.gliste[i].name == zielKnoten:
zielIndex = i
self.gmatrix[startIndex][zielIndex]=gewicht
if rückweg:
self.gmatrix[zielIndex][startIndex]=gewicht
def zeichneKante(self, v1,v2, farbe, gewicht, stiftbreite=1, geschw=10, verzögerung=0):
"zeichnet Kante zw. 'v1' und 'v2' mit 'gewicht' und 'farbe'"
speed(geschw) # Geschwindigkeit
delay(verzögerung) # Verzögerung
up() # Stift hoch
setpos(v1.x,v1.y) # Position v1
color(farbe) # Farbe setzen
pensize(stiftbreite) # Stiftbreite setzen
pd() # Stift runter
st() # Turtle zeigen
setpos(v2.x,v2.y) # Zeichnet Verbindung zu
ht() # Turtle verstecken
up() # Stift hoch
setpos(v1.x + (v2.x-v1.x)/2,
v1.y + (v2.y-v1.y)/2) # Streckenmitte anvisieren
write(gewicht) # Kantengewicht notieren
def zeichneGKnoten(self,GKnoten, schriftfarbe, gknotenfarbe, geschw=10, verzögerung=0):
"zeichnet GKnoten in 'gknotenfarbe' und beschriftet ihn mit 'schriftfarbe'"
speed(geschw) # Geschwindigkeit
delay(verzögerung) # Verzögerung
ht() # verstecke Turtle
setpos(GKnoten.x,GKnoten.y) # steuere GKnoten-Koordinaten an
pd() # Turtle runter
dot(GKnoten.größe, gknotenfarbe)# zeichnet Punkt entspr. d. Größe
color(schriftfarbe) # wechselt Farbe
write(GKnoten.name) # Ortsnamen schreiben
up() # Turtle wieder hoch
def zeichneGraph(self):
"erstelle Turtle-Abbild des Graphen"
# 0. Voreinstellungen
bgcolor(.8,1,.9) # Hintergrundfarbe (RGB-Modus)
reset();up();pensize(1);speed(0);delay(0) # Zeichenfenster auf Start
setworldcoordinates(-120,-190,450,300) # Koordinaten anpassen
title("Turtle4Dijkstra")
# 1. Kanten zeichnen
for v1 in self.gliste: # durchlaufe Knotenliste vertikal
for v2 in self.gliste: # durchlaufe Knotenliste horizontal
gewicht = self.gmatrix[self.gliste.index(v1)][self.gliste.index(v2)]
if gewicht: # Falls Kantengewicht vorhanden...
self.zeichneKante(v1,v2,"grey",gewicht)
# 2. GKnoten zeichnen
for i in self.gliste: # besuche jeden GKnoten...
self.zeichneGKnoten(i,"black","red")
def starteTsuche(self,vstart): # bereitet Graph auf Tiefensuche vor:
"Startmethode für Tiefensuche"
print("\nTiefensuche startet am GKnoten:", vstart) # Kommentar
namensliste=[] # Liste der Gknotennamen
for i in self.gliste: # iteriere über gliste...
i.marker = False # demarkiere alle Knoten
namensliste.append(i.name) # und füge den Namen in Liste ein
self.tsuche(self.gliste[namensliste.index(vstart)]) # starte Tiefensuche
def tsuche(self,vstart,farbe="green"):
"eigentliche Tiefensuche"
vstart.marker=True # GKnoten markieren
self.zeichneGKnoten(vstart,"black","blue",1,10) # färbe GKnoten blau
for i in self.gliste:
if self.gmatrix[self.gliste.index(vstart)][self.gliste.index(i)] and not i.marker:
print(repr(vstart).ljust(10),"--->",i) # Textausgabe
self.zeichneKante(vstart,i,
vstart in self.tsucheliste and "orange" or "green"
,"",2,1,10) # Kanten zeichnen: grün bzw. orange
self.tsucheliste.append(vstart) # fügt akt. GKnoten in Hilfsliste ein
self.tsuche(i) # rekursiver Aufruf
def dijkstra(self, startknoten, zielknoten=False):
"ermittelt den kürzesten Weg vom Startknoten zu allen/einem Zielknoten"
# Vorbereitung: alle Knoten demarkieren und Startknoten finden...
for i in self.gliste: # iteriere über gliste...
i.marker = False # demarkiere aktuellen Knoten
if i.name == startknoten: # suche nach Knoten aus Namen...
startknoten = i # Namenszug ersetzt durch echten Knoten
if i.name == zielknoten: # suche nach Knoten aus Namen...
zielknoten = i # Namenszug ersetzt durch echten Knoten
# 0. Markiere Startstadt, gib Kennzahl 0, =aktueller Knoten
startknoten.marker = True # Markierung setzen
startknoten.kennzahl = 0 # neues Attribut 'en passant' vergeben
aktknoten = startknoten
h = Heap() # Prioritätswarteschlange erzeugen
while True:
# 1. Gehe vom aktuellen Knoten zu allen Nachbarknoten
for i in self.gliste:
# Berechne die Länge vom aktuellenKnoten zum Nachbarknoten
längeStrecke = self.gmatrix[self.gliste.index(aktknoten)][self.gliste.index(i)]
if längeStrecke and not i.marker:
# hat der Nachbarknoten keine Kennzahl...
if not hasattr(i,"kennzahl"):
# ...weise ihr die Summe als Kennzahl zu und packe den Knoten in die PQ
i.kennzahl = aktknoten.kennzahl + längeStrecke
h.einfügen(i, i.kennzahl)
i.kennknoten = aktknoten # Quasi-Markierung der Strecke
# hat der Nachbarknoten eine Kennzahl größer als berechnete Entfernung..
elif i.kennzahl > aktknoten.kennzahl + längeStrecke:
# ...dann weise ihm die kleinere Kennzahl zu und aktualisiere die PQ
h.neuePrio(i,i.kennzahl,aktknoten.kennzahl + längeStrecke)
i.kennzahl = aktknoten.kennzahl + längeStrecke # neue Kennzahl eintragen
i.kennknoten = aktknoten # Quasi-Markierung der Strecke
# 2.+3. hole den marktieren Knoten mit der kleinsten Kennzahl (aus der PQ)
try:
aktknoten = h.entfernen()[0]
except IndexError:
print("PQ leer")
break
aktknoten.marker = True
## Ausgabe aller kürzesten Wegstrecken, wenn kein Ziel vorgegeben ----------
if not zielknoten:
self.zeichneKante(aktknoten.kennknoten, aktknoten,"magenta",
self.gmatrix[self.gliste.index(aktknoten)]
[self.gliste.index(aktknoten.kennknoten)],3,2,10)
# Ausgabe der kürzesten Wegstrecke vom Start- zum Zielknoten --------------
if zielknoten:
strecke = 0
rückliste=[(zielknoten,"")]
while hasattr(zielknoten,"kennknoten"):
rückliste.insert(0,(zielknoten.kennknoten,
self.gmatrix[self.gliste.index(zielknoten)]
[self.gliste.index(zielknoten.kennknoten)]))
strecke += self.gmatrix[self.gliste.index(zielknoten)]\
[self.gliste.index(zielknoten.kennknoten)]
# Pfad zeichnen ------------------------------------------------------------
self.zeichneKante(zielknoten,zielknoten.kennknoten,"blue",
self.gmatrix[self.gliste.index(zielknoten)]
[self.gliste.index(zielknoten.kennknoten)],3,1,20)
zielknoten=zielknoten.kennknoten
# Pfad in Textform --------------------------------------------------------
color("black") # ab hier: Wegbeschreibung
textausgabe="""Kürzester Pfad\n\n""" # Kopfzeile
for i in rückliste: # Durchlaufe die Wegeliste
textausgabe+="%s\n"%i[0].name # Ortsnamen
textausgabe+=i[1] and "%4s km\n"%i[1] or "\n"# km-Angabe
textausgabe+="Gesamt: %s km"%round(strecke,1) # Gesamtstrecke
setpos(300,150)
write(textausgabe,font=('Courier',10,'bold')) # Ausgabe des Pfades
if __name__ =="__main__":
gm = GMatrix(0,0,"Landsberg",37)
gm.addGKnoten(GKnoten(15,-98,"Pitzling",8,None))
gm.addGKnoten(GKnoten(20,280,"Burching",15,None))
gm.addGKnoten(GKnoten(-22,100,"Kaufering",20,None))
gm.addGKnoten(GKnoten(83,-63,"Pürgen",10,None))
gm.addGKnoten(GKnoten(95,55,"Penzing",13,None))
gm.addGKnoten(GKnoten(97,-4,"Schwifting",8,None))
gm.addGKnoten(GKnoten(90,-120,"Hagenheim",2,None))
gm.addGKnoten(GKnoten(72,-18,"Reisch",5,None))
gm.addGKnoten(GKnoten(180,-80,"Finning",8,None))
gm.addGKnoten(GKnoten(370,40,"Greifenberg",8,None))
gm.addGKnoten(GKnoten(260,90,"Eresing",4,None))
gm.addGKnoten(GKnoten(10,-180,"Mundraching",4,None))
gm.addGKnoten(GKnoten(157,88,"Ramsach",4,None))
gm.addKante("Landsberg","Kaufering",6)
gm.addKante("Landsberg","Penzing",6.6)
gm.addKante("Landsberg","Eresing",14.8)
gm.addKante("Landsberg","Burching",19.4)
gm.addKante("Landsberg","Greifenberg",22.1)
gm.addKante("Landsberg","Schwifting",6.4)
gm.addKante("Pürgen","Finning",6.9)
gm.addKante("Pürgen","Reisch",2.5)
gm.addKante("Schwifting","Reisch",1.5)
gm.addKante("Landsberg","Pitzling",6.9)
gm.addKante("Landsberg","Pürgen",5.8)
gm.addKante("Penzing","Ramsach",4)
gm.addKante("Finning","Schwifting",9.3)
gm.addKante("Hagenheim","Pürgen",4.6)
gm.addKante("Mundraching","Landsberg",14)
gm.addKante("Landsberg","Reisch",4.8)
gm.addKante("Pürgen","Pitzling",3.6)
gm.addKante("Burching","Kaufering",13.8)
gm.addKante("Greifenberg","Eresing",6.5)
gm.addKante("Penzing","Schwifting",2.6)
gm.addKante("Mundraching","Pitzling",10.4)
gm.addKante("Greifenberg","Finning",11)
gm.addKante("Ramsach","Eresing",6.9)
gm.addKante("Ramsach","Kaufering",11.7)
gm.addKante("Schwifting","Pürgen",3)
gm.addKante("Schwifting","Greifenberg",13.4)
gm.addKante("Kaufering","Penzing",7.3)
gm.addKante("Finning","Eresing",10.7)
gm.addKante("Burching","Eresing",18.1)
gm.addKante("Finning","Hagenheim",5)
gm.addKante("Mundraching","Hagenheim",9.6)
#gm.textausgabe()
gm.zeichneGraph()
gm.starteTsuche("Burching")
#gm.dijkstra("Kaufering","Greifenberg")
#gm.dijkstra("Kaufering")
exitonclick()