LEDA, a Platform for Combinatorial and Geometric Computing:Introduction and The Structure of LEDA
Introduction
Leda, the Library of Efficient Data Types and Algorithms, aims at being a comprehensive software platform for the area of combinatorial and geometric computing. It provides a sizable collection of data types and algorithms in C++. This collection includes most of the data types and algorithms described in the text books of the area ([1, 6, 9, 10, 15–17, 19–21]). Leda supports a broad range of applications. It has already been used in such diverse areas as code optimization, VLSI design, graph drawing, graphics, robot motion planning, traffic scheduling, geographic information systems, machine learning and computational biology.
The Leda project was started in 1988 by Kurt Mehlhorn and Stefan Na¨her. The first months they spent on the specification of different data types and on selecting the implementation language. At that time the item concept came up as an abstraction of the notion “pointer into a data structure”. Items provide direct and efficient access to data and are similar to iterators in the standard template library. The item concept worked successfully for all test cases and is now used for most data types in Leda. Concurrently with searching for the correct specifications several languages were investigated for their suitability as an implementation platform. Among the candidates were Smalltalk, Modula, Ada, Eiffel, and C++. The language had to support abstract data types and type parameters (genericity) and should be widely available. Based on the experiences with different example programs C++ was selected because of its flexibility, expressive power, and availability.
We discuss some of the general aspects of the Leda system.
The library is easy to use. In fact, only a small fraction of the users are algorithms experts and many users are not even computer scientists. For these users the broad scope of the library, its ease of use, and the correctness and efficiency of the algorithms in the library are crucial. The Leda manual [11] gives precise and readable specifications for 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).
Combinatorial and geometric computing is a diverse area and hence it is impossible for a library to provide ready-made solutions for all application problems. For this reason it is important that Leda is easily extendible and can be used as a platform for further software development. In many cases Leda programs are very close to the typical text book presentation of the underlying algorithms. The goal is the equation Algorithm + Leda = Program.
Leda extension packages (LEPs) extend Leda into particular application domains and areas of algorithmics not covered by the core system. Leda extension packages satisfy requirements, which guarantee compatibility with the Leda philosophy. LEPs have a Leda-style documentation, they are implemented as platform independent as possible and the installation process allows a close integration into the Leda core library. Currently, the following LEPs are available: PQ-trees, dynamic graph algorithms, a homogeneous d-dimensional geometry kernel, and a library for graph drawing.
Correctness
Programming is a notoriously error-prone task; this is even true when programming is interpreted in a narrow sense: going from a (correct) algorithm to a program. The standard way to guard against coding errors is program testing. The program is exercised on inputs for which the output is known by other means, typically as the output of an alternative program for the same task. Program testing has severe limitations. It is usually only done during the testing phase of a program. Also, it is difficult to determine the “correct” suite of test inputs. Even if appropriate test inputs are known it is usually difficult to determine the correct outputs for these inputs: alternative programs may have different input and output conventions or may be too inefficient to solve the test cases.
Given that program verification, i.e., formal proof of correctness of an implementation, will not be available on a practical scale for some years to come, program checking has been proposed as an extension to testing [3, 4]. The cited papers explored program checking in the area of algebraic, numerical, and combinatorial computing. In [8, 14, 28] program checkers are presented for planarity testing and a variety of geometric tasks. Leda uses program checkers for many of its implementations.
In computational geometry the correctness problem is even more difficult because geometric algorithms are frequently formulated under two unrealistic assumptions: computers are assumed to use exact real arithmetic (in the sense of mathematics) and inputs are assumed to be in general position. The naive use of floating point arithmetic as an approximation to exact real arithmetic very rarely leads to correct implementations. In a sequence of papers [5, 12, 18, 22, 24] the degeneracy and precision issues have been investigated and Leda was extended based on this theoretical work. It now provides exact geometric kernels for two-dimensional and higher dimensional computational geometry [26] and also correct implementations for basic geometric tasks, e.g., two-dimensional convex hulls, Delaunay diagrams, Voronoi diagrams, point location, line segment intersection, and higher-dimensional convex hulls and Delaunay triangulations.
An elegant (theoretical) approach to the degeneracy problem is symbolic perturbation. However, this method of forcing input data into general position can cause some serious problems in practice. In many cases, it increases the complexity of (intermediate) results considerably and furthermore, the final limit process turns out to be very difficult in particular in the presence of combinatorial structures. For this reason, Leda follows a different approach. It copes with degeneracies directly by treating the degenerate case as the “nor- mal” case. This approach proved to be very effective for many geometric problems.
Leda is realized in C++ and can be used on many different platforms with many different compilers. Leda is now used at many academic sites. A commercial version of Leda is marketed by Algorithmic Solutions Software GmbH (<www.algorithmic-solutions.com>).
The Structure of LEDA
Leda uses templates for the implementation of parameterized data types and for generic algorithms. However, it is not a pure template library and therefore is based on a number of object code libraries of precompiled code. Programs using Leda data types or algorithms have to include the appropriate Leda header files into their source code and have to be linked with one or more of these libraries. The four object code libraries are built on top of each other. Here, we only give a short overview. Consult the Leda user manual ([11] or the Leda book ([27]) for a detailed description.
• The Basic Library (libL)
contains system dependent code, basic data structures, numbers and types for linear algebra, dictionaries, priority queues, partitions, and many more basic data structures and algorithms.
• The Graph Library (libG)
contains different types of graphs and a large collection of graph and network algorithms
• The 2D Geometry Library (libP)
contains the two-dimensional geometric kernels advanced geometric data structures, and a large number of algorithms for two-dimensional geometric problems.
• The 3D Geometry Library (libP)
contains the three-dimensional kernels and some algorithms for three-dimensional problems.
• The Window Library(libW)
supports graphical output and user interaction for both the X11 platform (Unix) and Microsoft Windows systems. It also contains animation support: Graph Win, a powerful graph editor, and Geo Win, a interactive tool for the visualization of geometric algorithms. See Section 41.5 for details.
Comments
Post a Comment