Eine erweiterte Klasse zur Verwaltung von Graphen
Verwaltung zusätzlicher Informationen
Graphen in Anwendungssituationen müssen oft so konzipiert werden, dass neben den Knotennamen und den Kanten auch weitere Informationen verwaltet werden.
Die Abbildung zeigt ein vereinfachtes Autobahnnetz rund um Ludwigshafen und Mannheim. Beachte, dass hier viele Autobahnabfahrten nicht berücksichtigt sind.
Zunächst einmal sind hier alle Kanten mit Gewichten versehen. Die Zahlen an den Kanten repräsentieren die Entfernung zwischen den Autobahnknotenpunkten.
An einer der Kanten ist zusätzlich die Autobahnbezeichnung eingetragen. Auch diese Information ist für praktische Anwendungen oft wichtig.
Interessant könnten auch die Geo-Koordinaten von Autobahnknotenpunkten sein. Diese würden benötigt, wenn eine Darstellung auf einer Landkarte angestrebt würde. An einem der Knoten sind solche zusätzlichen Geo-Informationen eingetragen.
Das gezeigte Beispiel verdeutlicht, dass die Klasse Graph
so erweitert werden sollte,
dass auch zusätzliche Daten verwaltet werden können.
Speicherung der Graph-Daten in einer Datei
Die Daten von Graphen werden während der Verarbeitung von einem Objekt der Klasse Graph
verwaltet. Nach der Verarbeitung (wenn das Programm beendet ist) wird das Objekt vernichtet.
Danach sind sämtliche Daten des verwalteten Graphen nicht mehr zugänglich.
Wünschenswert ist eine Möglichkeit, die Daten eines Graphen in einer externen Datei abspeichern zu können
und Daten einer externen Datei wieder einlesen zu können.
Als externes Speicherformat benutzen wir im Folgenden GraphML, ein XML-basiertes Standardformat zur Repräsentation von Graphen.
49.5534891 8.3199207 ...A 6 19 ...
Nutzung einer Implementierung
Wir gehen hier von folgender Modellierung aus.
Die Datei graph.py enthält eine (etwas aufwendigere) Implementierung
der Klasse Graph
sowie der erweiterten Klasse GraphMitDaten
.
Das folgende Testprogramm zeigt, wie man einen erweiterten Graphen aus einer vorgegebenen GraphML-Datei graph_bab_lu_ma.xml mit einem Objekt verwaltet.
from graph import * # Erzeugung des Graph-Objekts g = GraphMitDaten() # Erzeugung der Knoten und Kanten aus einer GraphML-Datei datei = open("graph_bab_lu_ma.xml", "r") xml_quelltext = datei.read() g.graphmlToGraph(xml_quelltext) # Ausgabe der Nachbarschaftslisten for knoten in g.getAlleKnoten(): print(knoten, ':', g.getAlleNachbarn(knoten))
Aufgabe 1
(a) Teste die Klasse GraphMitDaten
. Erzeuge ein Objekt, mit dem
der folgende gewichtete Graph verwaltet wird. Die Daten des Graphen sollen auch in einer externen Datei
gespeichert werden.