Implementierung
Implementierung des Algorithmus von Moore
Hier noch einmal der Algorithmus von Moore:
ALGORITHMUS # von Moore Übergabedaten: Graph, startKnoten, zielKnoten # Vorbereitung des Graphen für alle knoten des Graphen: setze abstand auf 'u' setze herkunft auf None setze abstand von startKnoten.abstand auf 0 füge startKnoten in eine Schlange zuVerarbeiten ein # Verarbeitung der Knoten SOLANGE die Schlange zuVerarbeiten nicht leer ist: ausgewaehlterKnoten ist das erste Element aus zuVerarbeiten entferne ausgewaehlterKnoten aus zuVerarbeiten für alle nachbarKnoten von ausgewaehlterKnoten: wenn abstand von nachbarKnoten == 'u': füge nachbarKnoten hinten in die Schlange zuVerarbeiten ein neuerAbstand = (abstand von ausgewahlterKnoten) + 1 setze abstand von nachbarKnoten auf neuerAbstand setze herkunft von nachbarKnoten auf ausgewaehlterKnoten weglaenge = abstand von zielKnoten # Erzeugung des Weges zum zielKnoten weg = [] knoten = zielKnoten SOLANGE knoten != startKnoten und herkunft von knoten != None: weg = [(herkunft von knoten, knoten)] + weg knoten = herkunft von knoten Rückgabedaten: (weg, weglaenge)
Die folgende Implementierung dieses Algorithmus beruht auf einer Darstellung von Graphen mit Nachbarschaftlisten.
def existiertKnoten(graph, knoten): ergebnis = False for eintrag in graph: if eintrag[0] == knoten: ergebnis = True return ergebnis def getAlleKnoten(graph): knotenListe = [] for eintrag in graph: knotenListe = knotenListe + [eintrag[0]] return knotenListe def getAlleNachbarn(graph, knoten): nachbarListe = [] for eintrag in graph: if eintrag[0] == knoten: nachbarListe = eintrag[1] return nachbarListe def getAbstand(erweiterterGraph, knoten): ergebnis = None for eintrag in erweiterterGraph: if eintrag[0] == knoten: ergebnis = eintrag[1] return ergebnis def getHerkunft(erweiterterGraph, knoten): ergebnis = None for eintrag in erweiterterGraph: if eintrag[0] == knoten: ergebnis = eintrag[2] return ergebnis def setAbstand(erweiterterGraph, knoten, wert): erweiterterGraphNeu = [] for eintrag in erweiterterGraph: if eintrag[0] == knoten: eintragNeu = [eintrag[0], wert, eintrag[2], eintrag[3]] erweiterterGraphNeu = erweiterterGraphNeu + [eintragNeu] else: erweiterterGraphNeu = erweiterterGraphNeu + [eintrag] return erweiterterGraphNeu def setHerkunft(erweiterterGraph, knoten, wert): erweiterterGraphNeu = [] for eintrag in erweiterterGraph: if eintrag[0] == knoten: eintragNeu = [eintrag[0], eintrag[1], wert, eintrag[3]] erweiterterGraphNeu = erweiterterGraphNeu + [eintragNeu] else: erweiterterGraphNeu = erweiterterGraphNeu + [eintrag] return erweiterterGraphNeu def initErweiterterGraph(graph, startKnoten): erweiterterGraph = [] for eintrag in graph: if eintrag[0] == startKnoten: eintragNeu = [eintrag[0], 0, None, eintrag[1]] erweiterterGraph = erweiterterGraph + [eintragNeu] else: eintragNeu = [eintrag[0], 'u', None, eintrag[1]] erweiterterGraph = erweiterterGraph + [eintragNeu] return erweiterterGraph def kuerzesterWegMoore(graph, startKnoten, zielKnoten): if existiertKnoten(graph, startKnoten) and existiertKnoten(graph, zielKnoten): # Vorbereitung erweiterterGraph = initErweiterterGraph(graph, startKnoten) zuVerarbeiten = [startKnoten] # Verarbeitung der Knoten while zuVerarbeiten != []: # bestimme einen Knoten ausgewaehlterKnoten aus zuVerarbeiten ausgewaehlterKnoten = zuVerarbeiten[0] # entferne ausgewaehlterKnoten aus zuVerarbeiten zuVerarbeiten = zuVerarbeiten[1:] # bearbeite die Nachbarn von ausgewaehlterKnoten for nachbarKnoten in getAlleNachbarn(graph, ausgewaehlterKnoten): if getAbstand(erweiterterGraph, nachbarKnoten) == 'u': zuVerarbeiten = zuVerarbeiten + [nachbarKnoten] neuerAbstand = getAbstand(erweiterterGraph, ausgewaehlterKnoten)+ 1 erweiterterGraph = setAbstand(erweiterterGraph, nachbarKnoten, neuerAbstand) erweiterterGraph = setHerkunft(erweiterterGraph, nachbarKnoten, ausgewaehlterKnoten) weglaenge = getAbstand(erweiterterGraph, zielKnoten) # Erzeugung des Weges zum zielKnoten weg = [] knoten = zielKnoten while knoten != startKnoten and getHerkunft(erweiterterGraph, knoten) != None: weg = [(getHerkunft(erweiterterGraph, knoten), knoten)] + weg knoten = getHerkunft(erweiterterGraph, knoten) else: weg = [] weglaenge = 'u' return (weg, weglaenge) # Erzeugung des Testgraphen testgraph_ohne_gewichte = \ [ ['A', ['C', 'E', 'G']], ['B', ['C', 'D']], ['C', ['A', 'D', 'E']], ['D', ['B', 'E']], ['E', ['D', 'G']], ['F', ['B', 'D', 'H']], ['G', ['D']], ['H', ['F', 'G']] ] # Test des Moore-Algorithmus start = 'A' ziel = 'B' print('kürzester Weg von', start, 'nach', ziel, ':') (weg, laenge) = kuerzesterWegMoore(testgraph_ohne_gewichte, start, ziel) for w in weg: print(w) print('Weglänge:', laenge)
Aufgabe 1
(a) Teste zunächst separat die Funktion initErweiterterGraph
. Was leistet diese Funktion?
Teste auch die Funktionen getAbstand
, getHerkunft
,
setAbstand
und setHerkunft
?
(b) Ergänze Ausgaben in der Funktion kuerzesterWegMoore
so, dass die Verarbeitung
des Graphen Schritt für Schritt (wie in den Abbildungen im Abschnitt
Der Algorithmus von Moore)
nachvollzogen werden kann.
(c) Führe weitere Tests der Funktion kuerzesterWegMoore
aus.
Aufgabe 2
Eine weitere Implementierung des Algorithmus von Moore findest du in der Klasse GraphMoore
(siehe graph_moore.txt).
Objekte der Klasse GraphMoore
stellen die Operation kuerzesterWegMoore
zur Verfügung, mit der man Wege mit geringster Anzahl von Zwischenknoten in Graphen bestimmen kann.
Teste auch diese Implementierung des Algorithmus von Moore.
Das folgende Testprogramm
verdeutlicht die Verwendung der Klasse GraphMoore
am Demo-Graphen graph_ohne_gewichte.xml.
from graph_moore import * # Erzeugung des Graph-Objekts g = GraphMoore() # Erzeugung der Knoten und Kanten aus einer GraphML-Datei datei = open("graph_ohne_gewichte.xml", "r") xml_quelltext = datei.read() g.graphmlToGraph(xml_quelltext) # Kontrollausgabe des Graphen print('Graph:') for knoten in g.getAlleKnoten(): print(knoten, ':', g.getAlleNachbarn(knoten)) print() # Test des Moore-Algorithmus start = 'A' ziel = 'B' print('kürzester Weg von', start, 'nach', ziel, ':') (weg, laenge) = g.kuerzesterWegMoore(start, ziel) for w in weg: print(w) print('Weglänge:', laenge)
Implementierung des Algorithmus von Dijkstra
Der Algorithmus von Dijkstra lässt sich so formulieren:
ALGORITHMUS # von Dijkstra Übergabedaten: Graph, startKnoten, zielKnoten # Vorbereitung des Graphen für alle knoten des Graphen: setze abstand auf 'u' setze herkunft auf None setze abstand von startKnoten.abstand auf 0 füge startKnoten in eine Liste zuVerarbeiten ein # Verarbeitung der Knoten SOLANGE die Liste zuVerarbeiten nicht leer ist: bestimme einen Knoten minKnoten aus zuVerarbeiten mit minimalem Abstand entferne minKnoten aus zuVerarbeiten für alle nachbarKnoten von minKnoten: gewicht = Gewicht der Kante von minKnoten zu nachbarKnoten neuerAbstand = (abstand von minKnoten) + gewicht WENN abstand von nachbarKnoten == 'u': füge nachbarKnoten in die Liste zuVerarbeiten ein (z.B. am Listenende) setze abstand von nachbarKnoten auf neuerAbstand setze herkunft von nachbarKnoten auf minKnoten SONST: WENN nachbarKnoten in zuVerarbeiten liegt: WENN abstand von nachbarKnoten > neuerAbstand: setze abstand von nachbarKnoten auf neuerAbstand setze herkunft von nachbarKnoten auf minKnoten weglaenge = abstand von zielKnoten # Erzeugung des Weges zum zielKnoten weg = [] knoten = zielKnoten SOLANGE knoten != startKnoten und herkunft von knoten != None: weg = [(herkunft von knoten, knoten)] + weg knoten = herkunft von knoten Rückgabedaten: (weg, weglaenge)
Aufgabe 3
Mit den Hilfsfunktionen initErweiterterGraph
, getAbstand
, getHerkunft
,
setAbstand
, setHerkunft
, ... lässt sich auch der Algorithmus von Dijkstra
implementieren. Du kannst dich an der Implementierung des Algorithmus von Moore orientieren. Zum Testen
kannst du das folgende Testprogramm nutzen und variieren.
# Erzeugung des Testgraphen testgraph_mit_gewichten = \ [ ['A', [('C', 20), ('E', 2), ('G', 9)]], ['B', [('C', 1), ('D', 8)]], ['C', [('A', 20), ('D', 10), ('E', 13)]], ['D', [('B', 8), ('E', 16)]], ['E', [('D', 16), ('G', 5)]], ['F', [('B', 3), ('D', 4), ('H', 5)]], ['G', [('D', 2)]], ['H', [('F', 5), ('G', 7)]] ] # Test des Dijkstra-Algorithmus start = 'A' ziel = 'B' print('kürzester Weg von', start, 'nach', ziel, ':') (weg, laenge) = kuerzesterWegDijkstra(testgraph_mit_gewichten, start, ziel) for w in weg: print(w) print('Weglänge:', laenge)
Aufgabe 4
Eine weitere Implementierung des Algorithmus von Dijkstra findest du in der Klasse GraphDijkstra
(siehe graph_dijkstra.txt).
Objekte der Klasse GraphDijkstra
stellen die Operation kuerzesterWegDijkstra
zur Verfügung, mit der man Wege mit geringster Anzahl von Zwischenknoten in Graphen bestimmen kann.
Teste auch diese Implementierung des Algorithmus von Dijkstra.
Das folgende Testprogramm
verdeutlicht die Verwendung der Klasse GraphDijkstra
am Demo-Graphen graph_mit_gewichten.xml.
from graph_dijkstra import * # Erzeugung des Graph-Objekts g = GraphDijkstra() # Erzeugung der Knoten und Kanten aus einer GraphML-Datei datei = open("graph_mit_gewichten.xml", "r") xml_quelltext = datei.read() g.graphmlToGraph(xml_quelltext) # Kontrollausgabe des Graphen print('Graph:') for knoten in g.getAlleKnoten(): print(knoten, ':', g.getAlleNachbarn(knoten)) print() # Test des Dijkstra-Algorithmus start = 'A' ziel = 'B' print('kürzester Weg von', start, 'nach', ziel, ':') (weg, laenge) = g.kuerzesterWegDijkstra(start, ziel) for w in weg: print(w) print('Weglänge:', laenge)