LEDA - Erbgut

Monitor - Moniskop

Juli - August 2000
Peter Zanner

Die Nachricht ging wie ein Lauffeuer durch alle Medien: Das menschliche Erbgut soll (je nach Quelle) zu 90 bis 99,9 Prozent
entschlüsselt sein. Mit von der Partie, wenngleich unauffällig, ist die Saarbrücker Softwarefirma Algorithmic
Solutions Software GmbH mit ihrem Produkt "LEDA", einer "Library of Efficient Data types and Algorithms".

LEDA dient in erster Linie dazu, Wissenschaftlern und anderen Nicht-Programmierern das Leben zu erleichtern, indem die
Bibliothek Datentypen und Algorithmen näherungsweise so abbildet, wie "Laien" das gewohnt sind. Das heißt keineswegs,
dass man mit LEDA gar nicht programmieren müsste, ganz im Gegenteil: LEDA ist selbst in C++ geschrieben. Dennoch
bietet dieses Archiv eine weit höhere Abstraktionsebene als in Low-Level Programmiersprachen üblich, sowohl bei den
angebotenen Datentypen als auch den Algorithmen.

Für jeden Datentyp werden höchst effiziente Routinen bereitgestellt, mittels derer die Daten sich bearbeiten lassen:
Fibonacci-Stapel für priorisierte Warteschlangen, "red-black trees" beziehungsweise dynamische "perfekte"
Hash-Algorithmen für Verzeichnisse (diction[n]aries), und so weiter. Besonderen Wert legen die Autoren auch auf den
Zugriff per Index, weshalb auch und gerade dafür ein "Item"-Konzept als Abstraktionsebene eingeführt wurde.

Der Vorteil dieser Abstraktion wird offensichtlich, wenn man sich die auf die Daten anwendbaren Operationen näher zu
Gemüte führt. So erlaubt zum Beispiel der Typ "graph", Iteratoren wie "für alle Knoten k eines Graphen g..." oder "für alle
Nachbarn n von m..." zu formulieren. Scheitelpunkte und Kanten können zu einem Graphen hinzugefügt oder daraus
gelöscht werden, Vektoren und Matritzen können per Kanten oder Knoten adressiert werden... Kurz, die Schreibweise
folgt annähernd der in Fachbüchern üblichen Notation und bietet damit eine beträchtliche Vereinfachung gegenüber selbst
ausprogrammierten Funktionen.

"XXX"

Celera Genomics (http://www.celera.com/) verwendet LEDA insbesondere für die notwendige Zusammensetzung der in der
menschlichen DNA gefundenen Gen-Sequenzen. Mehr als 80 Prozent der Software, die Celera für diese Aufgaben einsetzt,
basiert laut Firmenangaben auf dieser Bibliothek. "Die Firma Celera hat uns gleich nach der sensationellen Nachricht über
den Einsatz von LEDA informiert, und wir sind stolz, an einer solchen Aufgabe mit unserer Software beteiligt zu sein", meint
dazu Dr. Christian Uhrig, Geschäftsführer der Algorithmic Solutions.

Damit ist das Produkt aber noch lange nicht ausgereizt. Graphen- und Netzwerkalgorithmen zusammen mit geometrischen
Datentypen (für 2D und 3D) inklusive Visualisierung und Ein/Ausgabe Routinen erlauben vielfältige
Verwendungsmöglichkeiten. Der Hersteller führt unter anderem diskrete Optimierungen, Verkehrskontrolle und Computer
Aided Design (CAD) als aktuelle Anwendungen an, in welchen LEDA eingesetzt wird.

[... Algorithmic Solutions] selbst ruht sich nicht allein auf LEDA aus, sondern bietet darauf aufbauend zwei weitere Librarys
für ein ähnliches Zielpublikum an: einmal die "Algorithms for Graph Drawing (AGD)", eine Sammlung von 2D-Funktionen
zum Zeichnen von Graphen sowie "Computational Geometric Algorithms Library (CGAL)", welche generische und einfach
zu verwendende C++-Klassen für geometrische Algorithmen zusammenfasst.

"Geschichte"

Algorithmic Solutions Software (http://www.algorithmic-solutions.com/) ist eine Ausgliederung aus dem Max Planck Institut
für Informatik der Universität des Saarlandes. Die Firma als solches besteht seit 1995, die Arbeit an LEDA begann schon
1988. Dass man sich für C++ als Implementationssprache entschied - nachdem auch Testprogramme in Smalltalk, Modula,
Ada und Eiffel geschrieben wurden - lag vorwiegend an der weitgehenden Verfügbarkeit sowie der Effizienz dieser
Sprache.

Auch die Portabilität war von Anfang an ein wichtiges Kriterium, dementsprechend lässt sich LEDA heute auf Unix
beziehungsweise Linux-Systemen mit Gnu-Kompilern genauso einsetzen wie unter Windows mit MS-VC++, Watcom und
anderen Compilern.

© Monitor / Bohmann GmbH
Das Magazin für Informationstechnologie Online
Leberstraße 122
1110 Wien

Informationen:

Monitor Online: http://www.monitor.co.at

LEDA: http://www.algorithmic-solutions.de/leda.htm

Max-Planck-Institut für Informatik: http://www.mpi-sb.mpg.de

Über Algorithmic Solutions:

Algorithmic Solutions Software GmbH ist ein international tätiges Software- und Beratungshaus mit Sitz in Saarbrücken. Algorithmic Solutions wurde 1995 von Mitarbeitern des Max-Planck-Instituts für Informatik gegründet. Das Unternehmen ist spezialisiert auf den industriellen Einsatz effizienter Algorithmen und Datenstrukturen in den Bereichen Graphen- und Netzwerkmanagement, algorithmische Geometrie sowie Visualisierung von logischen Verknüpfungen und Beziehungen.

Algorithmic Solutions Software GmbH
Schützenstraße 3-5
D-66123 Saarbrücken
contact@algorithmic-solutions.de
http://www.algorithmic-solutions.de