Einleitung

  Das Graphenlabor (kurz auch GraLab) wurde mit dem Ziel entwickelt, für die Entwicklung von Anwendungsprogrammen einen abstrakten Datentyp  Graph mit einer möglichst leistungsfähigen Schnittstelle zur Verfügung zu stellen. Insbesondere werden folgende Anforderungen erfüllt:

• Knoten und Kanten sind eigenständige, identifizierbare Objekte.
• Mehrfachkanten, d.h. mehrere Kanten zwischen denselben Knoten, sind möglich.
• Die Kanten sind gerichtet.
• Der einem gerichteten Graphen zugrunde liegende ungerichtete Graph steht unmittelbar zur Verfügung.
• Der Graph kann dynamisch verändert werden, d.h. während der Laufzeit der Anwendung können Knoten und Kanten eingefügt und gelöscht werden.
• Die Kanten, die mit einem Knoten in Berührung stehen, sind in einer vom Programm veränderbaren Reihenfolge angeordnet.
• Alle Knoten , alle Kanten und alle mit einem Knoten inzidenten Kanten können leicht traversiert werden.
• Zur Unterscheidung von Knoten- bzw. Kantenklassen können die Knoten bzw. Kanten typisiert werden.
• Die verwendeten Typen können in einer Subtyp-Relation stehen.
• Die Knoten und Kanten können mit Werten versehen (attributiert ) werden. Das dabei verwendete Attributierungsschema ist vom Typ des jeweiligen Knotens oder der Kante abhängig.
• Die Attributwerte können aus global verfügbaren Wertebereichen gebildet werden. Strukturierte Wertebereiche können mittels Konstruktoren aus Basiswertebereichen gebildet werden.
• Knoten und Kanten können für Algorithmen kurzfristig mit Kontrollinformationen markiert werden. Diese temporäre Attributierung ist unabhängig von den typabhängigen Attributierungsschemata.
• Änderungen am Graphen können in einem Undo -Mechanismus protokolliert und wieder rückgängig gemacht werden.

Die vom Graphenlabor verwalteten Graphen sind i.allg. dynamische, gerichtete, angeordnete, typisierte und attributierte Graphen. Sie werden in der Literatur als  TGraphen (EBERT and FRANZKE, 1995) bezeichnet.