LEDA - The Library of Efficient Data Types and Algorithms (3.1.2)

  The library is an attempt to bring together a set of reusable components for use in combinatorial computing. It consists of a set of data types and algorithms, with several implementations of most of the standard textbook data structures, and a set of two dimensional graphing and geometry types and algorithms.

The library provides stacks, queues, sets, sequences and other structured data types, and algorithms for graph and network theory, and 2D geometry. The class hierarchy is relatively flat, and appears easy to extend - for example, additional implementations of dictionaries can be easily added to the dictionary templates.

Parameterised containers are implemented with templates, and are used by the geometry algorithms/classes. For example

list<point> c.intersection(segment s)

The library provides the following classes (taken from the contents page of the LEDA manual[18]):

Basic Data Types

One and Two Dimensional Arrays, Stacks, Queues, and Bounded Stacks and Queues Lists, Sets, Integer Sets, Partitions and Dynamic collections of trees.

Priority Queues and Dictionaries

Priority Queues and Bounded Priority Queues, Dictionaries and Dictionary Arrays, Hashing Arrays, Sorted Sequences, Persistent Dictionaries.

Graphs and Related Data Types

Graphs and Undirected Graphs, Planar Maps, Parameterised Graphs, Undirected Graphs and Planar Maps, Node and Edge Arrays, Two Dimensional Node Arrays, Node and Edge Sets and Node Partitions and Priority Queues.

Two-Dimensional Geometry

Two-Dimensional Dictionaries, Sets of Points, Intervals, and Parallel Segments, Planar Subdivision and Graphic Windows.

A simple list of classes just not do justice to LEDA, as it also provideds a sizable collection of different implementations of the containers, and also implementations of many algorithms.

For example:

#include <LEDA/_d_array.h>
#include <LEDA/impl/ch_hash.h>
// define a (naive) hash function for strings
int Hash(const string& x) {return (x.length()>0)? x[o] : 0;}
main()
{
  _d_array<string,int,ch_hash> N9o);
  string s;
  while (cin >> s) N[s]++;
  forall_defined(s,N) cout << s << " " << N[s] << endl;
}

In addition to the many different implementations of the containers provided, several algorithms are included for the graph and network types.

Note that there are no special facilities for persistence, or for garbage collection/memory management, other than a pooled block allocation system used internally.

Error handling is either via an internal handler, that usually results in the termination of the program, or via a user supplied error handler.

Summary

Provides

A collection of data types and algorithms including:

stacks, queues, lists, sets, dictionaries, ordered sequences, partitions, priority queues, directed, undirected, and planar graphs, lines, points, planes and basic algorithms in graph and network theory and 2D computational geometry.

Many of the containers are particularly flexible, being parameterised on implementation - ex. dictionaries implemented with skip lists, AVL trees, dynamic perfect hashing etc.

The documentation is concise, readable, and the containers and algorithms are well specified. Short examples are given in the manual, and larger example programs supplied.

Dependencies

None. Although LEDA does use templates, it does not use very recent features.

Limitations

There are problems with containers that have implementation parameters (ex. _dictionary<K,I,impl>) on cfront based compilers. There are minor problems with g++ 2.6.3 due to compiler bugs.

Although data types for geometry are provided, they are restricted to 2 dimensions only.

Availability

The library[18] is `not in the public domain, but can be freely used for research and teaching'. Source code and resonably comprehensive documentation (texinfo) is provided.

Version

Version 3.1.2 was released in February 1995.

Author

Stefan Naher.