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.