Home · e-mail Index · Suche
Seminare im WS 95/96 Seminare
# 1. LEDA ## Library of Efficient Datatypes and Algorithms Einfuehrung Aufbau der bereitgestellten Klassen Definition Objekte Operationen Implementierung Beispielklasse : Array Uebersicht der abstrakten Datentypen Systemvoraussetzungen und Bezugsquellen Dokumentation und Benutzerfreundlichkeit 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
Boolean | bool
Real Numbers | real
Strings | string
Real-valued vectors | vector
Real-valuated matrices | matrix
Basis-Datentypen
One Dimensional Arrays | array
Two Dimensional Arrays | array2
Stacks | stack
Queues | queue
Bounded Stacks | b_stack
Bounded Queues | b_queue
Lists | list
Sets | set
Integer Sets | int_set
Partitions | partition
Dynamic collections of trees | tree_collection
Prioritätsschlangen und Verzeichnisse
Priority Queues | p_queue
Bounded Priority Queues | b_prio
Dictionaries | dictionary
Dictionariy Arrays | d_array
Hashing Arrays | h_array
Sorted Sequences | sortseq
Persistent Dictionaries | p_dictionary
Graphen und verwandte Datentypen
Graphs | graph
Undirected Graphs | ugraph
Planar Maps | planar_map
Parametrized Graphs | GRAPH
Parametrized Undirected Graphs | UGRAPH
Parametrized Planar Maps | PLANAR_MAP
Node and Edge Arrays | node_array, edge_array
Two Dimensional Node Arrays | node_matrix
Node and Edge Sets | node_set, edge_set
Node Partitions | node_partition
Node Priority Queues | node_pq
Zweidimensionale Geometrie
Two-Dimensional Dictionaries | d2_dictionary
Sets of Points | point_set
Sets of Intervals | interval_set
Sets of Parallel Segments | segement_set
Planar Subdivisions | subdivision
Graphic Windows | window
## 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.
| © FH Wedel 24.01.2002 |