LEDA

A Platform for Combinatorial and Geometric Computing

Stefan Näher Martin-Luther Universität Halle

Combinatorial and geometric computing is a core area of computer science. However, in contrast to many other areas of computing, there is no standard library of combinatorial and geometric data structures and algorithms. The lack of a library severely limits the impact of the area on computer science as a whole. The continuous reimplementation of basic data structures and algorithms slows down progress within research and even more so outside. The latter is due to the fact that outside research the investment for implementing an efficient solution is frequently not made, since it is doubtful whether the implementation can be reused, and therefore methods which are known to be less efficient are used instead. As a consequence, scientific discoveries migrate only slowly into practice. Why is it like this? One of the major differences between combinatorial and geometric computing and other areas of computing such as statistics, numerical analysis, and linear programming is the use of complex data types. Whilst the built-in types, such as integers, reals, vectors and matrices, usually suffice in the other areas, combinatorial and geometric computing relies heavily on types like stacks, queues, lists, dictionaries, sequences, graphs, points, lines, convex hulls, … and therefore asks for a programming language where all these types are available. Only with the advent of object-oriented programming did it become feasible to provide such an extension in a clean way. In 1989, we started the LEDA project (\underline{L}ibrary of \underline{E}fficient \underline{D}ata Types and \underline{A}lgorithms) to build a library of the data types and algorithms of combinatorial and geometric computing. The features of LEDA are:

• LEDA provides a sizable collection of data types and algorithms in a form which allows them to be used by non-experts. This collection includes most of the data types and algorithms described in the text books of the area, i.e., stacks, queues, lists, sets, dictionaries, ordered sequences, partitions, priority queues, directed, undirected, and planar graphs, lines, points, planes and many algorithms in graph and network theory and computational geometry.

• LEDA gives a precise and readable specification for each of the data types and algorithms mentioned above. The specifications are short (typically not more than a page), general (so as to allow several implementations) and abstract (so as to hide all details of the implementation). Many data types in LEDA are parameterized, e.g., the dictionary type works for arbitrary key and information type. A specific instance D with key type string and information type int is for example defined by dictionary < string, int > D;

• LEDA contains the most efficient realizations known for its types. For many data types the user may even choose between different implementations, e.g., between ab-trees, BB[α]-trees, dynamic perfect hashing, skip lists, … for dictionaries. dictionary < string, int, skip list > D; realizes dictionary D by skip lists.

• LEDA contains a comfortable data type graph. It offers the standard iterations such as “for all nodes v of a graph G do” (written forall nodes(v, G)) or “for all neighbors w of v do” (written forall adj nodes(w, v)), it allows the addition and deletion of nodes and edges and it offers arrays and matrices indexed by nodes and edges, . . .. The data type graph allows to write programs for graph problems in a form close to the typical text book presentation.

• Many geometric algorithms use arbitrary precision arithmetic and are therefore free from failures due to rounding errors. Moreover, they can handle all degenerate cases.

• LEDA is realized in C++. All its data types and algorithms are available as precompiled object-modules that can be linked easily with application programs. Together with the fact that the high expressive power of LEDA keeps application programs short this leads to short compile times.

• LEDA supports applications in a broad range of areas. It has already been used in such diverse areas as code optimization, VLSI design, robot motion planning, traffic scheduling, machine learning and computational biology.