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 ?

Adjazenzmatrix

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
]

Aufgabe 1a

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:

Adjazenzliste

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.

Aufgabe 1b

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

Hinweise:

Zugriff auf ein Dictionary mittels Key:

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

Aber auch:

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

Existenztest:

>>> "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:

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:

Lösung:

Untenstehender Code nutzt 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:

das Problem wird mit jedem Schritt kleiner (gibt es eine Lösung, so ist der Nachbarknoten einen Schritt näher am Ziel als node).
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))

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.

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?

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]

Aufgabe 4 - Graph Walk

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.

Lösung:

Dieser Code gibt die Liste aller Knoten des Graphs aus, wie sie bei einem Tree-Walk in depth-first Reihenfolge zum ersten Mal vorkommen würden.

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"))

Untenstehender Code macht dasselbe als Generator. Ein Generator ist eine Funktion, die eine Sequenz generiert, aber ohne bereits beim ersten Aufruf die ganze Liste zu berechnen. Stattdessen berechnet der Generator nur das nächste Element und gibt es mit yield zurück; dabei wird der Zustand der Funktion automatisch gespeichert, so dass die Ausführung an derselben Stelle wieder aufgenommen wird, an der das letzte Mal yield aufgerufen wurde. Eine Funktion, die das yield Keyword verwendet, wird automatisch zum Generator.

Mit yield from <other> wird ein anderer Generator other in die Sequenz des aufrufenden Generators eingebaut.

Vorteil: Bei einem sehr grossen Graphen muss nicht der ganze Graph abgearbeitet werden, um erste Resultate liefern zu können. Werden nur die ersten paar Elemente benötigt, ist der Aufruf viel schneller.

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).

Aufgabe 5

Ü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.

Lösung:

bfs.py

def traversierung_bfs(graph, start):
    """Returns the list of nodes in graph reachable from start, in breadth-first order."""
    sequence=[]  # list of nodes in breadth-first order
    candidates = [start]  # known nodes we should process
 
    while candidates:
        # Handle the next candidate:
        #  - remove from list
        #  - if not visited yet: add to sequence and add its neighbors
        node = candidates.pop(0)
        if node in sequence:
            continue
        sequence.append(node)
        for neighbor in graph[node]:
            candidates.append(neighbor)
    return sequence
 
print("bfs: ", traversierung_bfs(graph, "ksr"))

Oder als Generator:

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])

Aufgabe 6: Pfadsuche mit BFS

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

Hinweise:

Lösung:

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}

Aufgabe 7: Real-World Beispiel

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")

Fragen

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:

die bereits besuchten Knoten
die entdeckten (aber noch nicht besuchten Knoten): candidates
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.

Lösung

dijkstra.py

from math import inf
from queue import PriorityQueue
def shortest_path(graph, start, end):
    """Dijkstra shortest path."""
    # Candidates to process next, ordered by increasing distance.
    # The head of the queue is guaranteed to be the next node to be visited,
    # while the order of subsequent nodes could still be reordered if and preceding
    # node offers a shorter path to them.
    candidates = PriorityQueue()
    candidates.put((0, start))
    parents = {}
    # In addition to BFS, we record for each discovered node the currently known shortest
    # distance from start.
    distances = {start: 0}
    while candidates:
        # print(distances)
        # print(candidates.queue)
        # input()
 
        # Let's visit the closest node not yet visited. The first candidate node is
        # guaranteed to be the closest one of the candidates.
        distance, node = candidates.get()
        if node == end:  # We're done.
            return build_path_from_parents(graph, parents, start, end)
        if distances.get(node, inf) < distance:
            continue  # Node was already visited. See comment below.
 
        for neighbor, edge in graph[node].items():
            new_distance = distance + edge
            old_distance = distances.get(neighbor, inf)
            if old_distance <= new_distance:
                continue  # Neighbor already discovered via some shorter path
            # Otherwise: we discovered a shorter (or new) path to neighbor - record it
            # and add to candidates.
            distances[neighbor] = new_distance
 
            # To be correct, we'd need to remove any old record (old_distance, neighbor) 
            # in the candidates, but that is expensive. Instead, we leave it in and
            # rely on the fact that the neighbor will be visited only once through the shortest
            # path.
            candidates.put((new_distance, neighbor))
            parents[neighbor] = node
    return None  # No path found

Dies ist eine alte Version des Dokuments!

Graphenalgorithmen

Graphen

Graphen repräsentieren

Adjazenzmatrix

Aufgabe 1a

Adjazenzliste

Aufgabe 1b

Tiefensuche

Aufgabe 2

Zyklen finden

Aufgabe 3a

Aufgabe 3b

Aufgabe 4 - Graph Walk

Breitensuche

Aufgabe 5

Aufgabe 6: Pfadsuche mit BFS

Scale it up - Pfadsuche im öffentlichen Verkehr

Aufgabe 7: Real-World Beispiel

Fragen

Dijkstra - Kürzeste Pfade

**Dies ist eine alte Version des Dokuments!**

Graphenalgorithmen

Graphen

Graphen repräsentieren

Adjazenzmatrix

Aufgabe 1a

Adjazenzliste

Aufgabe 1b

Tiefensuche

Aufgabe 2

Zyklen finden

Aufgabe 3a

Aufgabe 3b

Aufgabe 4 - Graph Walk

Breitensuche

Aufgabe 5

Aufgabe 6: Pfadsuche mit BFS

Scale it up - Pfadsuche im öffentlichen Verkehr

Aufgabe 7: Real-World Beispiel

Fragen

Dijkstra - Kürzeste Pfade

Dies ist eine alte Version des Dokuments!