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:
- Kante von B nach C löschen
- Kante von C nach B löschen
- Kante von C nach C hinzufügen
- Knoten B löschen
- Knoten C löschen