Eine Klasse zur Verwaltung von Graphen

Graphen als Objekte

Im vorangegangenen Abschnitt wurde gezeigt, dass man Graphen auf unterschiedliche Weise mit Hilfe elementarer Datenstrukturen repräsentieren kann. Für die Verarbeitung von Graphen ist die gewählte Darstellung durchaus wichtig. Noch wichtiger ist es aber, über geeignete Operationen zur Verwaltung und Veränderung von Graphen zu verfügen, die - unabhängig von der zu Grunde liegenden Darstellung - die erforderiche Verarbeitung der Daten durchführen. Günstig ist es, hier objektorientiert vorzugehen und eine Klasse Graph zu konzipieren, die die benötigten Operationen bereitstellt.

Zuständigkeit und Operationen eines Graph-Objekts

Ein Objekt der Klasse Graph soll die Knoten und Kanten eines Graphen verwalten.

Zum einen soll es geeignete Operationen bereit stellen, um einen Graphen aufzubauen und zu verändern. Mit diesen Operationen soll man z.B. neue Knoten hinzufügen oder bereits vorhandene Knoten entfernen können.

Zum anderen soll es Operationen bereit stellen, um an Informationen über den Graphen zu gelangen. So soll man mit einer geeigneten Operation ermitteln können, ob es den Knoten mit vorgegebenem Namen gibt oder ob es eine Kante von einem Knoten zu einem anderen Knoten gibt.

Das folgende Klassendiagramm zeigt eine Zusammenstellung von Operationen, die eine Klasse Graph zur Verfügung stellen sollte.

Beachte, dass die Repräsentation des Graphen hier noch offen gelassen ist. Hier kann man eine Nachbarschaftstabelle oder auch Nachbarschaftslisten benutzen.

Aufgabe 1

Entwickle selbst eine Implementierung der der Klasse Graph.

Verwendung einer vorgegeben Implementierung zur Klasse Graph

Die Datei graph.py enthält eine (etwas aufwendigere) Implementierung der Klasse Graph. Du musst nicht unbedingt alle Details dieser Implementierung verstehen, um die Klasse nutzen zu können.

Mit einem einfachen Programm kann man die Implementierung der Klasse Graph testen.

from graph import *
# Erzeugung des Graph-Objekts
g = Graph()
# Hinzufügen von Knoten und Kanten
g.addKnoten('A')
g.addKnoten('B')
g.addKante('A', 'B')
# Ausgabe der Nachbarschaftslisten
for knoten in g.getAlleKnoten():
    print(knoten, ':', g.getAlleNachbarn(knoten))

Man erhält dann die folgende Ausgabe:

A : ['B']
B : []

Aufgabe 2

(a) Nutze die Implementierung der Klasse Graph, um den folgenden Graphen zu erstellen:

(b) Nimm anschließend folgende Veränderungen am Graphen vor und kontrolliere die Ergebnisse:

1. Kante von B nach C löschen
2. Kante von C nach B löschen
3. Kante von C nach C hinzufügen
4. Knoten B löschen
5. Knoten C löschen