Wege finden mit Python

Wir wollen versuchen, die 3 erarbeiteten Algorithmen mit Python umzusetzen und auf zwei verschiedene Graphen anzuwenden, um Wege zwischen zwei Knoten zu finden.

Die Struktur des Graphen, sowie Daten der Knoten und Funktionen um die Wegfindung zu visualisieren sind in der Datei graph.py zusammengefasst. Wir können die Klasse Graph in unserem eigenen Skript importieren und verwenden.

Graph

Eigenschaften

graph.openList
list von Node – Werte mit append hinzufügen, mit remove entfernen oder mit [] direkt auf einen bestimmten Eintrag zugreifen
Hier werden alle «entdeckten» Knoten gespeichert. Zu Beginn ist dies nur der Startknoten. Einer dieser Knoten wird für den nächsten Schritt besucht.
Knoten auf dieser Liste werden Gelb gezeichnet
graph.closedList
list von Node – Werte mit append hinzufügen, mit remove entfernen oder mit [] direkt auf einen bestimmten Eintrag zugreifen
Hier werden alle «besuchten», resp. «definitiv abgeschlossenen» Knoten aufgelistet. Zu Beginn ist diese Liste leer
Knoten auf dieser Liste werden Rot gezeichnet
graph.peers
dictionary: (key: Node, value: list von Node) – zugreifen mit graph.peers[node]
Hier werden die Kanten des Graphen gespeichert. Man kann für einen Knoten eine Liste aller mit ihm verbundenen Knoten abrufen.
graph.startNode
Node
Dies ist der Startknoten der Suche
graph.targetNode
Node
Dies ist der Endknoten der Suche
graph.dist
list von list von int – abrufen mit graph.dist[node1][node2]
Stellt die Distanztabelle dar. Man kann die Distanz zwischen zwei Knoten abrufen, sofern diese durch eine Kante miteinander verbunden sind.
graph.running
boolean – Standardmässig True, graph.running = False
Wenn das Ziel gefunden wurde, dann kann man den Wert auf False stellen
Wenn der Wert False ist, wird versucht ausgehend vom Zielknoten den gefundenen Weg grün darzustellen. Dazu muss aber Node.parent korrekt gesetzt sein

Methoden

Graph(step)
Konstruktor – erzeugt einen neuen Graph, registriert die übergebene Step-Funktion
graph.loadGallenbach()
lädt Daten für den Graph dem Buch von Jens Gallenbach
graph.loadDeutschland()
lädt Daten für den Graph um Würzburg herum
graph.init()
fügt den Startknoten auf die openList
graph.run()
startet das Programm: bei jedem Tastendruck wird step()aufgerufen und der Graph neu gezeichnet

Node

Eigenschaften

g
int – Distanz zum Startknoten, muss berechnet werden: z.B. node.g = node.g + dist[node][othernode]
h
int – Distanz Luftlinie zu Würzburg (fix eingetragen)
parent
Node – Vorgänger-Knoten, muss gesetzt werden. Wird verwendet um Weg zurück zu Startknoten zu finden: z.B. node.peer = parent

Beispiel

  1. Graph importieren
  2. step() definieren
  3. Graph erzeugen
  4. Daten laden
  5. Graph initialisieren
  6. Programm starten
"""
Name: S. Forster
Datum: 21.2.2019
Beschreibung: Demo von Graph
"""

from graph import Graph

def step():
    """
        Schrittfunktion: Stellt ein einzelner Suchschritt dar.
        Muss beim Erzeugen des Graph-Objektes registriert werden.
        Wird dann bei jedem Tastendruck aufgerufen. 
    """
    print(str(graph.openList))
    node = graph.openList[0]
    for peer in graph.peers[node]:
        graph.openList.append(peer)
        dist = graph.dist[node][peer]
        peer.parent = node
        print(str(peer) + " hat eine Distanz von " + str(dist) + " von " + str(node))

graph = Graph(step)          # graph erzeugen und Schrittfunktion registrieren
graph.loadGallenbach()       # Daten laden. Alternative: graph.loadDeutschland()
#graph.startNode  = graph.w   # Startknoten vorbereiten
#graph.targetNode = graph.s   # Zielknotens vorbereiten
graph.init()                 # Startknoten auf openList
graph.run()                  # Loop starten