LEDA, a Platform for Combinatorial and Geometric Computing:Data Structures and Data Types.

Data Structures and Data Types

Leda contains a large number of data structures from the different areas of combinatorial and geometric computing. However, as indicated in the name of the library, Leda was not designed as a collection of data structures but as a library of (parameterized) data types. For each (abstract) data type in the library there is at least one data structure which implements this type. This separation of specification (by an abstract data type) and implementation (by an actual data structure) is crucial for a software component library. It allows to change the underlying implementation or to choose between different implementations without having to change the application program. In general, there is one default data structure for each of the advanced data types, e.g avl-trees for dictionaries, skiplists for sorted sequences, binary heaps for priority queues, and a union-find structure for partitions. For most of these data types a number of additional data structures are available and can be specified by an optional template argument. For instance dictionary<string,int,skiplist> specifies a dictionary type with key type string and information type int which is implemented by the skiplist data structure (see [27] for more details and Section 41.6.1 for an example).

Basic Data Types

Of course, Leda contains a complete collection of all basic data types, such as strings, stacks, queues, lists, arrays, tuples ... which are ubiquitous in all areas of computing.

Numbers and Matrices

Numbers are at the origin of computing. We all learn about integers, rationals, and real numbers during our education. Unfortunately, the number types int , float , and double provided by C++ are only crude approximations of their mathematical counterparts: there are only finitely many numbers of each type and for floats and doubles the arithmetic incurs rounding errors. Leda offers the additional number types integer , rational , bigfloat , and real . The first two are the exact realization of the corresponding mathematical types and the latter two are better approximations of the real numbers. Vectors and matrices are one- and two-dimensional arrays of numbers, respectively. They provide the basic operations of linear algebra.

Advanced Data Types

A collection of parameterized data types representing sets, partitions, dictionaries, priority queues, sorted sequences, partitions and sparse arrays (maps, dictionary and hashing arrays). Type parameters include the key, information, priority, or element type and (optional) the data structure used for the implementation of the type. The list of data structures includes skiplists (see Chapter 13), (a, b)-trees, avl-trees, red-black trees, bb[α]- trees (see Chapter 10), randomized search trees (see Chapter 13), Fibonacci-heaps, binary heaps, pairing heaps (see Chapter 7), redistributive heaps, union find with path compression (Chapter 33), dynamic perfect hashing, cuckoo hashing (see Chapter 9), Emde-Boas trees, .... This list of data structures is continuously growing and adapted to new results from the area for data structures and algorithms.

Graph Data Structures

The graph data type (Chapter 4) is one of the central data types in Leda. It offers the standard iterations such as “for all nodes v of a graph G do” (written f orall nodes(v, G)) or “for all edges e incident to a node v do” (written f orall out edges(e, v)), it allows to add and delete vertices and edges and it offers arrays and matrices indexed by nodes and edges, (see [27] chapter 6 for details and Section 41.6.2 for an example program). The data type graph allows to write programs for graph problems in a form very close to the typical text book presentation.

Geometry Kernels

Leda offers kernels for two- and three-dimensional geometry, a kernel of arbitrary dimension is available as an extension package. In either case there exists a version of the kernel based on floating point Cartesian coordinates (called float-kernel) as well as a kernel based on rational homogeneous coordinates (called rat-kernel). All kernels provide a complete collection of geometric objects (points, segments, rays, lines, circles, simplices, polygons, planes, etc.) together with a large set of geometric primitives and predicates (orientation of points, side-of-circle tests, side-of-hyperplane, intersection tests and computation, etc.). For a detailed discussion and the precise specification see Chapter 9 of the Leda book ([27]). Note that only for the rational kernel, which is based on exact arithmetic and floating-point filters, all operations and primitives are guaranteed to compute the correct result.

Advanced Geometric Data Structures

In addition to the basic kernel data structures Leda provides many advanced data types for computational geometry. Examples are

• a general polygon type (gen polygon or rat gen polygon) with a complete set of boolean operations. Its implementation is based on an efficient and robust plane sweep algorithms for the construction of the arrangement of a set of straight line segments (see [13] and [27] chapter 10.7 for a detailed description).

• two- and higher-dimensional geometric tree structures, such as range, segment, interval and priority search trees (see Chapter 18).

• partially and fully persistent search trees (Chapter 31).

• different kinds of geometric graphs (triangulations, Voronoi diagrams, and arrangements)

• a dynamic point set data type supporting update, search, closest point, and different types of range query operations on one single representation which is based on a dynamic Delaunay triangulation (see [27] chapter 10.6).