1. LEDA

Library of Efficient Datatypes and Algorithms

1. Einfuehrung
2. Aufbau der bereitgestellten Klassen
   1. Definition
   2. Objekte
   3. Operationen
   4. Implementierung
3. Beispielklasse : Array
4. Uebersicht der abstrakten Datentypen
5. Systemvoraussetzungen und Bezugsquellen
6. Dokumentation und Benutzerfreundlichkeit
7. Zusammenfassung

1.1 Einführung

LEDA ist eine Klassenbibliothek, die Datentypen und Algorithmen für die Kombinatorik und Graphentheorie bereitstellt. Während für andere Anwendungsbereiche der Informatik, wie der Statistik, der numerischen Analysis oder der linearen Programmierung, häufig die im Sprachumfang enthaltenen Datentypen ausreich, benötigt die Kombinatorik weitaus komplexere Datentypen und Algorithmen. Zu nennen sind hier beispielsweise : Stapel, Warteschlangen, Verzeichnissbäume, verkettete Listen, Graphen und grundlegende Routinen der Graphen- und Netzwerktheorie.

Die wesentlichen Merkmale von LEDA sind :

• Bereitstellung einer relativ leicht verständlichen und umfassenden Sammlung von abstrakten Datentypen (ADTs) und Algorithmen
• präzise und lesbare Spezifikation der ADTs und Algorithmen. Die Spezifikationen sind zumeist sehr kurz gehalten (selten länger als eine Seite). Sie sind so allgemein, daß verschiedenste Implementierungen möglich sind und so abstrakt, daß die Details der Implementierung verborgen bleiben (Datenabstraktion)
• Strikte Trennung zwischen den abstrakten Datentypen und den konkreten, zur Implementierung verwendeten Datentypen (Kapselung der Daten)
• LEDA beinhaltet einen komfortablen Datentyp "Graph". Dieser bietet elegante Zugriffsmethoden wie "für alle Knoten v eines Graphen G führe aus..." oder "für alle Nachbarn w eines Knoten v führe aus...". Der Datentyp bietet das Einfügen und Löschen von Kanten und Knoten. Er stellt Felder und Matrizen zur Verfügung, die über Knoten und Kanten indiziert werden können.
• Die von LEDA bereitgestellten ADTs sind weitgehend als Templates realisiert und lassen sich somit für die unterschiedlichsten Zwecke anpassen.

1.2 Aufbau der bereitgestellten Klassen

Die Spezifikationen / Definitionen der Klassen bestehen i.d.R. aus vier Teilen :

a) der Definition der Elemente des abstrakten Datentyps (ADT)

b) einer Beschreibung, wie die Objekte des ADTs gebildet werden,

c) der Definition der verfügbaren Operationen auf die Objekte des ADTs,

d) und Informationen darüber, wie die Klasse in eigenen Anwendungen implementiert werden kann.

In einigen Fällen wird zusätzlich noch ein Beispiel für die Implementierung aufgeführt.

1.2.1 Definition

Dieser Teil der Spezifikation definiert die Elemente des ADT. Als Beispiel sei hier der generische ADT "dictionary Array" beschrieben :

Ein Objekt a des ADT d_array<Index,Element> ist ein Feld (Array) mit Elementen vom Typ "Element" und Indizes vom Typ "Index".

Zu beachten ist, daß es sich hier, wie auch bei den meisten anderen ADTs von LEDA, um generische abstrakte Datentypen (Templates) handelt. Die Typen von "Index" und "Element" müssen folglich als Typparameter übergeben werden.

Als Typparameter können alle eingebauten Datentypen, Zeiger und auch benutzerdefinierte Datentypen (Klassen) dienen. Bei Verwendnung von Klassen als Datenelemente gilt es jedoch zu beachten, daß diese die folgenden Operationen bereitstellen müssen :

Den Standardkonstruktor (Konstruktor ohne Argumente)	T::T()
Einen Copy-Konstruktor	T::T(const T&)
einen Zuweisungsoperator	T& T::operator = (const T&)

Falls gefordert sind zusätzlich folgende Funktionen nötig :

eine Funktion zum Einlesen von Daten (Input)	void Read(&T, istream&)
eine Funktion zum Ausgeben von Daten (Output)	void Print(const T&, ostream&)
eine Vergleichsfunktion (compare)	int compare(const T&, const T&)
eine Hash-Funktion	int Hash(const T&)

1.2.2 Bildung von Objekten

Alle Variablen eines Typs der von LEDA bereitgestellten ADTs werden zum Zeitpunkt ihrer Deklaration initialisiert. In vielen Fällen muß der Anwender die Argumente für die Initialisierung bereitstellen.

Eine allgemeine Deklaration einer Variablen y vom Datentyp "XYZ<t1,...,tk>" mit den Argumenten "x1,...,xn" und den Typparametern "t1,...,tk" sieht wie folgt aus :

XYZ<t1,...,tk> y(x1,...,xn)

Die konkrete Deklaration einer Variablen vom Typ "d_array" erfolgt entsprechend :

d_array<string, int> A(0)

In diesem Beispiel wird die Variable A als ein Verzeichnisfeld (dictionary array) vereinbart. Die Indizes sind hierbei vom Typ String, die Elemente vom Typ Int.

1.2.3 Operationen

In diesem Abschnitt werden die Operationen auf die ADTs beschrieben. Neben der Schnittstelle, die gem. der üblichen C++ Syntax aufgebaut ist, erfolgt eine Beschreibung der Rückgabewerte. Die Parameter haben häufig bestimmten Vorbedingungen zu genügen. Werden diese Vorbedingungen verletzt, so sind die Rückgabewerte undefiniert. In einigen dieser Fälle hat das eine Fehlermeldung und einen Programmabbruch zur Folge. Häufig läuft das Programm jedoch ungeachtet des fehlerhaften Wertes weiter.

1.2.4 Implementierung

Abschließend wird dokumentiert, auf welche Weise die einzelnen ADTs implementiert worden sind (z.B. Verktoren als Felder von Real-Werten). An dieser Stelle finden sich in einigen Fällen auch konkrete Anwendungsbeispiele.

Ein Beispiel für den Definitionsteil der Klasse Array findet sich hinter folgendem Link :

1.3 Beispielklasse : Array

1.4 Übersicht der abstrakten Datentypen

Einfache Datentypen

Basis-Datentypen

Prioritätsschlangen und Verzeichnisse

Graphen und verwandte Datentypen

Zweidimensionale Geometrie

1.5 Systemvoraussetzungen und Bezugsquellen

Die Klassenbibliothek kann mit verschiedenen C++ Compilern sowohl unter UNIX als auch MS-DOS und OS/2 verwendet werden. (z.B. AT&T, GNU g++, Turbo C++, etc.)

LEDA ist nicht Public Domain, kann aber für Forschung und Lehre frei benutzt werden. Nähere Informationen zu LEDA und zur kommerziellen Nutzung sind erhältlich ...

... im World Wide Web:
http://www.mpi-sb.mpg.de/LEDA/leda.html

... unter FTP :
ftp://ftp.mpi-sb.mpg.de
im Verzeichnis pub/LEDA

... per Email :
leda@mpi-sb.mpg.de

... per Fax :
+49 681 / 302 5401

... per Telefon :
+49 681 / 302 5354

... oder per konventioneller Post :
Christian Uhrig
Max-Planck-Institut für Informatik
Im Stadtwald
66123 Saarbruecken
Germany

1.6 Dokumentation und Benutzerfreundlichkeit

Die Dokumentation der Klassenbibliothek Leda ist gut strukturiert und verständlich geschrieben. Als Handikap könnte sich allerdings das Format der Dokumentaion erweisen. Sie liegt zum einen als Postscript-Datei auf dem FTP-Server vor und wird ausserdem im Tex-Format mitgeliefert, dabei sind Teile der Dokumentation in den Klassendefinitionen (Header-Files) der jeweiligen ADTs untergebracht. Nach der Installation von Leda finden sich im Verzeichnis "/man" geeignete Werkzeuge, die die entsprechenden Handbuchseiten extrahieren und als DVI- oder Postscript-Dateien aufbereiten.

Die Dokumentation innerhalb der Klassendefinitionen hat den Vorteil, daß bei der Implementierung einzelner ADTs auf langes Nachlesen im Handbuch verzichtet werden kann. Häufig werden am Ende der Klassendefinitionen auch konkrete Beispiele für die Implementierung angeführt.

1.7 Zusammenfassung

LEDA stellt eine umfassende Sammlung komplexer Datentypen bereit. Insbesondere der Datentyp Graph zeichnet sich durch eine sehr komfortable Implementierung aus.

LEDA hat eine falche Klassenhierarchie mit vielen "kleinen Bäumen". Mehrfachvererbung wird nicht unterstützt.

Die Containerllassen von LEDA sind als Templateklassen realisiert, lassen sich also mit verschiedenen Datentypen und eigenen Klassen als Typparameter verwenden.

Die Fehlerbehandlung der LEDA Klassen ist unvollständig. In der Inline-Dokumentation der Klassendefinitionen sind zwar Vorbedingungen für die Funktionsparameter und gültige Rückgabewerte definiert. Werden diese Bedingungen jedoch verletzt, so wird in einigen das Programm abgebrochen, in anderen Fällen läuft das Programm jedoch ungeachtet des Problems weiter.

Ein implizites (automatisches) Speichermanagement (Garbage-Collection) wird nicht unterstützt.