LEDA

LEDA (Library of Efficient Data types and Algorithms) is a C++ library of foundational data structures and algorithms, with a strong emphasis on graphs, combinatorial optimization, and computational geometry. It was originally developed in the 1990s at the Max Planck Institute for Informatics in Saarbrücken. From 2001 to 2023 it was maintained and commercially distributed by Algorithmic Solutions Software GmbH; since 2024 a free edition (LEDA-7) has been available from the University of Trier (leda.uni-trier.de).

At its core is a flexible graph type supporting directed and undirected graphs, parallel edges, and self-loops, together with node/edge arrays and maps that let algorithms attach typed data to each vertex and edge. LEDA is distinguished by exact-arithmetic number types (integer, rational, bigfloat, and real) that avoid floating-point rounding errors, and by its use of certifying algorithms: many routines return a machine-checkable "witness" alongside their result, so callers can verify correctness independently. The precompiled implementation ships as a set of linkable libraries (libL, libG, libW, lib3D and others) covering basic types, graphs, windows/GUI, and geometry.

For the graph-data and format-conversion world, LEDA is relevant mainly through its native file formats. A LEDA graph is serialized as a plain-text .lgr file listing nodes then edges, each with optional typed labels; the GraphWin .gw format extends this with an optional layout section recording node coordinates, shapes, colors, fonts, and edge geometry (polylines, Bezier and spline bends) for drawing. Because LEDA is a compact, widely recognized exchange format, importers exist in many ecosystems, and general graph converters such as Graph::Easy and libraries like igraph and NetworkX read or write it. Conceptually LEDA sits alongside other general-purpose graph/algorithm libraries such as Boost Graph Lib, LEMON, and OGDF.

Strengths include exact and certified computation, mature and well-documented graph and geometry algorithms, and an integrated GraphWin editor. Limitations are practical: LEDA is a large C++ dependency with a historically commercial, non-permissive license, its plain-text formats carry no schema or namespacing (unlike GraphML), and modern users often prefer lighter open-source alternatives for routine work.