Graphentechnologie

Beschreibung

Die Graphentechnologie ist ein Ansatz zur Realisierung von Anwendungssystemen durch Graphen und mit Hilfe graphentheoretischer Hilfsmittel und Algorithmen. Graphen werden dabei zur Repräsentation von strukturierten Informationen verwendet.

Den Forschungsschwerpunkt unserer Arbeitsgruppe bilden seit Jahren die eigens entwickelten TGraphen, d.h. typisierte, attributierte, angeordnete und gerichtete Graphen. TGraphen stellen eine sehr generelle Art von Graphen dar. Es existiert eine vielseitige Datenstruktur, mit der alle Eigenschaften von TGraphen repräsentiert werden können.

Im Kontext dieser Forschung wurden bezüglich TGraphen verschiedene Konzepte, Sprachen und Bibliotheken entwickelt - zum Teil von der Arbeitsgruppe Ebert, zum Teil in Zusammenarbeit mit (inter-)nationalen Partnern. Diese werden im Folgenden kurz vorgestellt:

  • Das Graphenlabor (GraLab) ist eine Klassenbibliothek und stellt eine sehr schnelle API zur Verarbeitung von TGraphen dar, von der Versionen in C++ und in Java existieren.
  • Die Graph Unified Modelling Language (GrUML) ist ein Ansatz für die Modellierung von TGraphen mittels einer Teilmenge der Unified Modelling Language (UML).
  • Die Graph Repository Query Language (GReQL) ist eine Anfragesprache für TGraphen, die auf der von der AG Ebert entwickelten Graph Specification Language (GRAL) aufbaut - einer auf Z basierenden objektorientierten Spezifikationssprache für TGraphen.
  • Die Graph Exchange Language (GXL) ist ein Standardformat für den Austausch von Graph-basierten Daten, das unter anderem auf dem von der AG Ebert entwickelten Graph eXchange Format (GraX) basiert.
  • EER/GRAL ist ein deklarativer Modellierungs- und Spezifikationsansatz für TGraphen mittels erweiterten Entity-Relationship (EER) Diagrammen und der von der AG Ebert entwickelten Graph Specification Language (GRAL) - einer auf Z basierenden objektorientierten Spezifikationssprache für TGraphen.

Beispiel

Die folgende Abbildung zeigt einen beispielhaften TGraphen:

graph

Anwendungsgebiet

Die Graphentechnologie kommt zurzeit in unseren Projekten GUPRO und ReDSeeDS zum Einsatz.

 

Literatur

1995

Ebert1995ADA
Ebert, Jürgen; Franzke, Angelika (1995): A Declarative Approach to Graph Based Modeling. In: Mayr, E.; Schmidt, G.; Tinhofer, G.: Graphtheoretic Concepts in Computer Science. Berlin: Springer Verlag. Nr. 903. S. 38-50.

1987

Ebert1987AVD
Ebert, Jürgen (1987): A Versatile Data Structure For Edge-Oriented Graph Algorithms. In: Communications ACM. Bd. 30. Nr. 6. S. 513-519.

1981

Ebert1981EG
Ebert, Jürgen (1981): Effiziente Graphenalgorithmen. Wiesbaden: Akademische Verlagsgesellschaft.