Modellierung von Graphklassen

  Bei der Arbeit mit Graphen wird man schnell feststellen, daß sich die Graphen in unterschiedliche Klassen einteilen lassen. Wenn man Stadtpläne in Graphen abbilden will, dann kann man z.B. Kreuzungen durch Knoten und Straßen durch Kanten modellieren. Dadurch werden sich alle Graphen dieser Stadtpläne in ihrer Struktur ähnlich sein: es wird beispielsweise Knoten vom Typ Kreuzung geben, die mit Kanten vom Typ Straße verbunden sind. Dagegen werden Graphen, die andere Sachverhalte darstellen, eine andere Struktur haben. Man kann alle Stadtplangraphen in eine Klasse einsortieren.

Für die Modellierung solcher Graphklassen werden folgende Modellierungsregeln empfohlen (EBERT and FRANZKE, 1995; EBERT et al., 1996):

• Jedes identifizierbare und relevante Objekt der zu modellierenden Welt wird durch einen Knoten dargestellt,
• jede Beziehung zwischen Objekten wird durch eine Kante zwischen deren Knoten dargestellt,
• ähnliche Objekte bzw. Beziehungen werden in Klassen über den Knoten bzw. Kanten zusammengefaßt,
• weitere Informationen zu den Objekten bzw. Beziehungen werden in Attributen an den Knoten bzw. Kanten abgelegt, und
• die Reihenfolge der Beziehungen wird durch die Ordnung über den Kanten realisiert.

Für die formale Spezifikation einer Graphklasse werden erweiterte Entity-Relationship-Diagramme (EER) und GRAL, eine -ähnliche Spezifikationssprache benutzt. EER-Diagramme eignen sich für die Beschreibung der allgemeinen Graphstruktur, da sich die Eigenschaften von TGraphen einfach abbilden lassen:

• Entity-Typen bezeichnen die Knoten-Typen,
• Relationship-Typen bezeichnen die Kanten-Typen,
• Generalisierung beschreibt die Hierarchie der Typen,
• Inzidenzen zwischen Relationship-Typen und Entity-Typen bezeichnen Einschränkungen der Inzidenzstruktur der Knoten,
• Attribute an den Entity- bzw. Relationship-Typen werden für die Knoten- bzw. Kanten-Typen übernommen und

Mit der Sprache GRAL werden weitere Bedingungen beschrieben, die im EER-Diagramm schlecht darstellbar sind. Im Rest des Dokumentes wird nicht mehr auf GRAL eingegangen, da das Graphenlabor diese Bedingungen nicht überprüft.