Graphenalgorithmen

Teil des Talit Programmierkurses.

Was ist der schnellste Weg von der KSR an den Bahnhof Romanshorn? Von Romanshorn nach Rom? Wie kann ein Staubsaugroboter auf dem kürzesten Weg die ganze Wohnung staubsaugen?

Wie können wir die Probleme überhaupt mathematisch formulieren, so dass wir sie mit einem Algorithmus lösen können?

Alle diese Probleme lassen sich mit mit Graphen formulieren und mit Graphenalgorithmen lösen. Graphen sind eine wichtige Datenstruktur in der Informatik. In der Talit kümmern wir uns erst einmal darum, wie wir einen Graph effizient beschreiben können; anschliessend schreiben wir Code, um verschiedene Eigenschaften von Graphen zu untersuchen - und vielleicht schneller nach Rom zu gelangen.

Wie könnten wir das Weg-Problem (von der KSR an den Bahnhof) abstrakt erfassen? Wir könnten die verschiedenen Wege zum Beispiel so erfassen:

Aus was besteht ein Graph? Aus Knoten (en. nodes oder vertices) und Kanten (edges). In unserem Fall haben die Kanten Gewichte, die die Länge oder Fahrtdauer der einzelnen Strecken repräsentieren.

Wie könnten wir diesen Graphen in Python repräsentieren?

Einen Graphen mit m Knoten speichern wir als m*m Matrix. Eine zweidimensionale Matrix ist nichts anderes als eine Liste von Listen gleicher Länge. In jedem Feld speichern wir True, wenn eine Verbindung zwischen den zwei Knoten besteht, sonst False.

matrix.py

graph = [
    # KSR, Sek, Bahnhofstr, Hafenstrasse, Zelgstrasse, Bahnhof
    [ False, True, False, False, False, False],  # KSR
    [ True, False, True, True, True, False],     # Sek
    [ False, True, False, False, False, True],   # Bahnhofstrasse
    [ False, True, False, False, False, True],   # Hafenstrasse
    [ False, True, False, False, False, True],   # Zelgstrasse
    [ False, False, True, True, True, False],    # Bahnhof
]

Hat der Graph Gewichte, speichern wir das Gewicht, -1 falls es keine Verbindung gibt:

matrix.py

graph = [
    # KSR, Sek, Bahnhofstr, Hafenstrasse, Zelgstrasse, Bahnhof
    [ -1, 1, -1, -1, -1, -1],  # KSR
    [ 1, -1, 3, 5, 7, -1],     # Sek
    [ -1, 3, -1, -1, -1, 7],   # Bahnhofstrasse
    [ -1, 5, -1, -1, -1, 6],   # Hafenstrasse
    [ -1, 7, -1, -1, -1, 5],   # Zelgstrasse
    [ -1, -1, 7, 6, 5, -1],    # Bahnhof
]

Codiere eine Funktion, die für eine Adjazenzmatrix und zwei Knotenindices zurückgibt, ob es eine direkte Verbindung gibt zwischen den Knoten:

def has_direct_connection(matrix, n1, n2):
    pass

Hinweis:

Die Matrix wird ziemlich gross, sie wächst mit dem Quadrat der Anzahl Knoten m. Meist existieren aber lange nicht alle möglichen Kanten in einem Graphen, dann ist es viel effizienter, nur die Liste der Kanten abzuspeichern. Das geht am besten mit Dictionaries, das sind Listen, die für jeden Eintrag einen Schlüssel (Key) haben, dem ein Wert (Value) zugeordnet ist.

adjacencylist.py

graph = {
    "ksr": {"sek": 1},
    "sek": {"bahnhofstr": 3, "hafenstr": 5, "zelgstr": 7},
    "bahnhofstr": {"bahnhof": 7},
    "hafenstr": {"bahnhof": 6},
    "zelgstr": {"bahnhof": 5},
    "bahnhof": {},
}

Achtung: Die obige Adjazenzliste codiert einen gerichteten Graphen - die Kanten zwischen zwei Knoten haben eine Richtung. Besteht eine Kante von A nach B, bedeutet das nicht automatisch, dass auch eine Kante von B nach A verläuft.

Schreibe eine Funktion has_direction_connection(list, n1, n2) die für die Adjazenzliste funktioniert.

Hinweise:

>>> graph["ksr"]
{'sek': 1}
>>> graph["ksr"]["sek"]
1

>>> graph["ksr"]["bahnhof"]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 'bahnhof'

>>> "bahnhof" in graph["ksr"]
False
>>> "sek" in graph["ksr"]
True

Bevor wir den schnellsten Weg an den Bahnhof zu finden versuchen, wären wir schon mal nur froh, überhaupt einen Weg zu finden. Es könnte ja auch sein, dass wir uns in die Turnhalle begeben, von wo kein Weg zum Bahnhof führt. Oder dass wir von der Bahnhofstrasse zurück zur KSR gelangen:

{{:talit:pasted:20220521-145117.png?400}}] #### Aufgabe 2 * Codiere obigen Graphen als Adjazenzliste in Python. * Überlege dir, wie du einen möglichen Pfad generieren kannst, der vom ersten zum letzten Knoten führt. Der Pfad soll als Liste von Knotennamen dargestellt werden - z.B. `["KSR", "Sek", "Bahnhofstr", "Bahnhof"]`. ++++Hinweise:| * Python * Schleife über ein Dictionary: `for k,v in graph.items():` * Schleife nur über die Keys: `for k in graph: print(graph[k])` * Die Funktion könnte beispielsweise `def find_path(graph, node, end)` heissen. * Algorithmus: * Wie würdest du in einem Labyrinth vorgehen? * Was ist die Lösung, falls `node == end`? * Hm, damit hätten wir ja schon mal einen Anfang... * ... andernfalls, wenn es einen Pfad von einem Nachbarknoten `neighbor` zu `end` gäbe, was wäre der Pfad von `node` zu `end`? * Wie kannst du dir merken, ob du bereits in einem Raum warst? ++++ <nodisp 1> ++++Lösung:| Untenstehender Code nutzt [[wpde>Rekursion, um das Problem zu lösen:

• falls node == end, so kennen wir eine triviale Lösung, nämlich den Pfad [node] und wir brechen die Suche ab.
• andernfalls versuchen wir, von jedem Nachbarknoten neighbor einen Pfad nach end zu finden
  • für die Suche von den Nachbarn rufen wir rekursiv die gleiche Funktion wieder auf.
  • finden wir einen Pfad path von neighbor nach end, so ist der Pfad [node] + path eine Lösung für den jetzigen Aufruf.
  • gibt es von keinem Nachbarknoten einen Pfad nach end, so gibt es auch von node her keine und wir geben False zurück.

Entscheidend für den Erfolg ist die Vermeidung von unendlicher Rekursion. Wir stellen dies mit zwei Dingen sicher:

1. das Problem wird mit jedem Schritt kleiner (gibt es eine Lösung, so ist der Nachbarknoten einen Schritt näher am Ziel als node).
2. um zu Vermeiden, dass wir einem Zyklus im Graphen folgen, merken wir uns alle besuchten Knoten im Set visited. Falls node bereits besucht worden ist, haben wir einen Zyklus gefunden und brechen die Suche ab. Die Funktion kann für einen Graphen mit n Knoten also höchstens n Mal rekursiv aufgerufen werden.

dfs.py

graph = {
    "ksr": {"turnhalle" : 1, "sek": 2, "weitenzelgstr": 1},
    "turnhalle": {},
    "weitenzelgstr" : {"bahnhofstr" : 8},
    "sek": {"bahnhofstr": 3, "hafenstr": 5, "zelgstr": 7},
    "bahnhofstr": {"bahnhof": 7, "ksr": 4},
    "hafenstr": {"bahnhof": 4},
    "zelgstr": {"bahnhof": 5},
    "bahnhof": {},
}
 
def find_path(graph, node=None, end=None, visited=None):
    """Returns the list of adjacent nodes from 'node' to 'end' if it exists,
       returns False otherwise.
 
       If node is None, the first node in graph is chosen.
       If end if None, the last node in graph is chosen.
    """
    # Choose first and last nodes in graph if not given.
    if node == None:
        node = next(iter(graph))
    if end == None:
        end = list(graph)[-1]
    if visited == None:
        visited = set()
 
    # If node has already been visited, we closed a cycle - return false.
    if node in visited:
        return False
 
    # Local check: if node and end are the same, we have a trivial solution.    
    if node == end:
        return [end]
 
    # Record the current node as visited so that we break cycles should we return to it
    # in the recursion.
    visited.add(node)
 
    # Recursion: If we find a path p from any of our neighbors to end, there is
    # a path from 'node' to end that consists of [node] + p.
    edges = graph[node]
    for neighbor in edges:
        path = find_path(graph, neighbor, end, visited)
        if path:
            # We have found a path from neighbor to end
            # -> the path from node to end is the same path, with node prepended.
            return [node] + path
    # None of our neighbors has a path to 'end' -> give up.
    return False
 
print(find_path(graph))

</nodisp> Obiger Algorithmus heisst Tiefensuche (*Depth First Search* - DFS): Wenn wir an einen neuen Knoten gelangen, suchen wir bei jedem Nachbar-Knoten bis wir entweder eine Lösung gefunden haben oder gescheitert sind. Erst dann besuchen wir den nächsten Nachbar. ### Zyklen finden Tiefensuche können wir auch verwenden, um Zyklen zu finden. Ein Zyklus ist ein Pfad, bei dem vom letzten Knoten wieder der erste erreichbar ist. #### Aufgabe 3a Schreibe Python-Code, der herausfindet, ob ein Graph _zyklenfrei_ ist. D.h. der Code versucht einen Zyklus zu finden und gibt `False` genau dann zurück, wenn er mindestens einen findet. #### Aufgabe 3b Schreibe rekursiven Python-Code, der alle Zyklen in einem Graphen findet. * Funktioniert der Code auch, wenn sich die Zyklen überschneiden? <nodisp 1> ++++Lösung:

def find_cycles(graph):
    # Record visited nodes in a set, which gives us constant-time lookup of
    # nodes.
    visited = set()
    cycles = []
    for node in graph:
        if node in visited:
            continue  # already been here
        find_cycles_from_node(graph, node, visited, cycles, [])
    return cycles
 
def find_cycles_from_node(graph, node, visited, cycles, path):
    if node in path:
        # We have found a cycle from the first occurrence of node
        # to here.
        # Remove prefix up to the first occurrence:
        index = path.index(node)
        cycle = path[index:]
        cycles.append(cycle)
        return
 
    visited.add(node)
    path.append(node)
    length = len(path)
    for neighbor in graph[node]:
        # Find cycles forward in graph.
        find_cycles_from_node(graph, neighbor, visited, cycles, path)
        # Crop path to prefix up to current node.
        path = path[:length]

</nodisp>

Wir haben die Tiefensuche nun auf verschiedene Probleme angewendet. Im Allgemeinen haben wir eine Traversierung implementiert, die einen Graphen linearisiert, das heisst, jeden Knoten in einer bestimmten Reihenfolge genau einmal besucht.

Aufgabe: Schreibe eine Funktion dfs(graph), die die Knoten eines Graphen mittels Tiefensuche ausgibt.

• Die Ausgabe kann mit print() erfolgen oder eine Liste zurückgeben.
• Herausforderung: schreibe eine Generator-Funktion mit dem yield Keyword.

def traversierung_dfs(graph, node, sequence=None):
    sequence = sequence or []
    if node in sequence:
        return
    sequence.append(node)
    for neighbor in graph[node]:
        traversierung_dfs(graph, neighbor, sequence)
    return sequence
 
print("dfs:", traversierung_dfs(graph, "ksr"))

def dfs(graph, node, visited=None):
    """ A generator of all nodes in graph, in depth-first order. """
    visited = visited or set()
    if node in visited:
        return
    yield node
    visited.add(node)
    for neighbor in graph[node]:
        yield from dfs(graph, neighbor, visited)
 
for node in dfs(graph, "ksr"): print(node)

Mit der Tiefensuche finden wir Pfade von A nach B in einem Graphen, aber vielleicht nehmen wir dabei grosse Umwege in Kauf, weil wir zuerst weit von A entfernte Knoten besuchen, bevor wir alle Nachbarn von A untersuchen. Wir möchten aber eine Möglichkeit haben, den Graphen der Nähe nach zu besuchen, also die Knoten in aufsteigender Distanz von A zu besuchen. Dieses Verfahren heisst Breitensuche (Breadth First Search - BFS).

Überlege dir, wie du vorgehen könntest, um zuerst die unmittelbaren Knoten des Starts zu besuchen, und nur allmählich weitere Kanten zu traversieren. Ignoriere die Kantengewichte dabei erst mal - du kannst von einem ungewichteten Graphen ausgehen.

Hinweise:

• Breitensuche lässt sich nicht (einfach) mit Rekursion lösen.
• YouTube VisualisierungBFS vs. DFS
• Ordne den Graphen in Schichten nach aufsteigender Distanz (Anzahl Knoten) vom Start.
  • Wir möchten zuerst alle Knoten einer Schicht besuchen, bevor wir uns die nächste Schicht vornehmen:
    1. Zuerst die KSR
    2. Dann die Turnhalle, Weitenzelgstrasse und die Sek
    3. Dann die Bahnhofstrasse, Zelgstrasse, Hafenstrasse
    4. Schlussendlich den Bahnhof
• Wir teilen die Knoten in drei Bereiche:
  • Bereits besuchte Knoten, am effizientesten in einem Set: visited = set().
  • Entdeckte, aber noch nicht besuchte Knoten in einer Liste: candidates = [start]
  • Noch unbekannte Knoten (brauchen wir uns nicht zu merken).
• Solange candidates nicht leer ist, wird der vorderste Knoten node in candidates entfernt.
  • Falls node bereits in visited ist, gehen wir zum nächsten (er wurde mehrfach entdeckt über verschiedene Pfade).
  • Andernfalls: wird node zu visited hinzugefügt.
    • Falls node == end sind wir fertig.
    • Alle Nachbarknoten von node, die noch nicht in visited sind, werden hinten in die candidates eingereiht.

def bfs(graph, start):
    """ A generator of all nodes in graph, in breadth-first order. """
    candidates = [start]
    visited = set()
    while candidates:
        next = candidates.pop(0)
        if next in visited:
            continue
        visited.add(next)
        yield next
        candidates.extend(graph[next])

Implementiere die Pfadsuche auch mit BFS. Wie zeichnen sich die gefundenen Pfade aus?

Hinweise:

def build_path_from_parents(graph, parents, start, end):
    """Builds the path from start to end given a parent dictionary
       for all nodes. Also computes the total path length from 
       the graph adjacency list."""
    path = []
    node = end
    total = 0
    while node != start:
        parent = parents[node]
        edge = graph[parent][node]
        total += edge
        path.insert(0, (node, edge))
        node = parent
    path.insert(0, (start, '0'))
    result = {
        'path': path,
        'length': total
    }
    return result
 
def find_path_bfs(graph, start, end):
    """Finds a path from start to end using BFS. """
    candidates = [start]
    visited = {start: None}
    while candidates:
        next = candidates.pop(0)
        for neighbor in graph[next]:
            if neighbor not in visited:
                visited[neighbor] = next
                candidates.append(neighbor)
                if neighbor == end:
                    return build_path_from_parents(graph, visited, start, end)
    return None  # No path found

Wir wollen unsere Algorithmen an einem etwas grösseren Beispiel testen. Der Schweizer ÖV-Fahrplan listet über 34'000 Haltepunkte auf, und wir wollen Verbindungen zwischen allen möglichen Stationen herausfinden und die Resultate vergleichen.

Der Datenbestand enthält als Adjazenz-Liste alle Haltepunkte, die mit einer Non-Stop-Verbindung zu erreichen sind. Die Nachbarknoten von Romanshorn sind also beispielsweise Amriswil, Egnach und Konstanz, aber nicht Frauenfeld. Zusätzlich enthält die Liste die reine Fahrtdauer in Minuten. Bei Transfer-Verbindungen (Romanshorn - Romanshorn, Bahnhof) ist statt der Fahrzeit die Umsteigezeit angegeben.

>>> import fahrplan
>>> sbb = fahrplan.latest
>>> sbb['Romanshorn']
{'Amriswil': 5, 'Egnach': 1, 'Konstanz': 17, 'Kreuzlingen Hafen': 14, 'Neukirch-Egnach': 2, 'Romanshorn': 3, 'Romanshorn (See)': 5, 'Romanshorn Autoquai': 6, 'Romanshorn, Bahnhof': 3, 'St. Gallen': 18, 'Uttwil': 3, 'Weinfelden': 13, 'Wittenbach': 11}

• Klone das Git Repo https://github.com/tkilla77/ksr_talenta_graphs
• Importiere die Adjacency-List des Schweizer öffentlichen Verkehrs.
  • Details im README.
• Teste deine Implementierungen für DFS und BFS
  • Finde einen Pfad von Romanshorn nach Lugano

import fahrplan
 
# Read schedule
sbb = fahrplan.latest
 
# Find path - depth-first.
# We may need to increase python's recursion depth...
import sys
sys.setrecursionlimit(10000)
 
dfs_path = find_path_dfs(sbb, "Romanshorn", "Lugano")
 
# Find path - breadth-first.
bfs_path = find_path_bfs(sbb, "Romanshorn", "Lugano")

• Hm, der DFS-Pfad scheint nicht wirklich optimal zu sein - weshalb?
• Was hat es mit der Rekursionstiefe auf sich?
• Der BFS-Pfad ist deutlich besser - BFS findet nämlich den Pfad mit den wenigsten Segmenten. Aber ist das bereits der schnellste Pfad?

In einem ungewichteten Graph finden wir mit der Breitensuche den kürzesten Weg, also den Pfad mit den wenigsten Segmenten. Ist der Pfad aber gewichtet (wie der Haltestellen-Graph mit Minuten-Angaben zu den Reisezeiten), so ist der Weg mit den wenigsten Segmenten nicht unbedingt der schnellste.

Unser Ziel ist es, die Knoten in aufsteigender Distanz von start zu besuchen. Wir teilen die Knoten in drei Gruppen:

1. die bereits besuchten Knoten
2. die entdeckten (aber noch nicht besuchten Knoten): candidates
3. alle anderen, noch unentdeckten Knoten

Der Algorithmus basiert auf dem folgenden Prinzip:

• Die Kandidaten sind nach aufsteigender Distanz zum Startknoten sortiert.
  • Hier liegt der Unterschied zu BFS: statt die neu-entdeckten Kandidaten einfach hinten einzureihen, werden sie nach aufsteigender Distanz zum Start sortiert.
  • Für die effiziente Sortierung der Kandidaten benützen wir eine PriorityQueue.
• Der vorderste Kandidat ist immer der nächste Knoten in aufsteigender Distanz von start her.
  • Beweis: gäbe es einen Knoten x der näher bei start liegt, so wäre dessen Vorläufer-Knoten bereits besucht worden und die geringere Distanz von x wäre bereits bekannt geworden.
  • Achtung: für alle weiteren Kandidaten stimmt die Sortierung noch nicht definitiv: möglicherweise gibt es einen kürzeren Pfad als den bekannten via einen weiter vorne liegenden Kandidaten, dessen Nachbarn noch nicht bekannt sind!

import queue.PriorityQueue
# Create the queue.
candidates = PriorityQueue()
# Add a tuple (distance, node) to the queue.
candidates.put((0, start))
 
# ...
 
while candidates:
    # Pop the next candidate off the queue - it is the nearest
    # of all known candidates.
    distance, node = candidates.get()

• Für alle besuchten oder entdeckten Knoten merken wir uns die kürzeste bekannte Distanz von start in einem Dictionary distances.
• Beim Besuch des vordersten Knotens node gehen wir wie folgt vor:
  • wenn node == end, so haben wir den kürzesten Pfad gefunden.
  • alle Nachbarn neighbor von node werden untersucht:

    for neighbor, edge in graph[node].items():

• wir berechnen die Distanz von start zu neighbor via node aus der Distanz von node und der Kantenlänge von node zu neighbor:

        new_distance = distance + edge

• in distances schauen wir nach, ob der Knoten bereits bekannt ist. Die get Funktion eines Dictionary gibt das zweite Argument zurück, wenn der Key nicht gefunden wird - in unserem Fall unendlich (math.inf).

        old_distance = distances.get(neighbor, inf)

• falls die neue Distanz kürzer ist, merken wir uns die Distanz und fügen den Knoten an der richtigen Stelle in candidates ein.
• zusätzlich unterhalten wir wie bei BFS ein Dictionary mit den Elternknoten jedes Knotens, um daraus den Pfad aufzubauen, wenn wir ans Ziel gelangt sind.

Der Aufbau des Pfades mithilfe der Elternknoten erfolgt gleich wie bei BFS.

Mit Folium lassen sich die gefundenen Pfade hübsch visualiseren. Der Code für untenstehende Grafik findet sich auf github.