Library of Efficient Data types and Algorithms

The Library of Efficient Data types and Algorithms (LEDA) is a proprietarily-licensed software library providing C++ implementations of a broad variety of algorithms for graph theory and computational geometry.^[1] It was originally developed by the Max Planck Institute for Informatics Saarbrücken.^[2] Since 2001, LEDA is further developed and distributed by the Algorithmic Solutions Software GmbH.

LEDA is available as Free, Research, and Professional edition. The Free edition is freeware, with source code access available for purchase. The Research and Professional editions require payment of licensing fees for any use. Since October 2017, LEDA graph algorithms are also available for Java development environment.

YouTube Encyclopedic

1/3
Views:
1 199 878
667
520 808

Transcription

Technical details

Data types

Numerical representations

LEDA provides four additional numerical representations alongside those built-in to C++: integer, rational, bigfloat, and real:

LEDA's integer type offers an improvement over the built-in int datatype by eliminating the problem of overflow at the cost of unbounded memory usage for increasingly large numbers.
It follows that LEDA's rational type has the same resistance to overflow because it is based directly on the mathematical definition of rational as the quotient of two integers.
The bigfloat type improves on the C++ floating-point types by allowing for mantissa to be set to an arbitrary level of precision instead of following the IEEE standard.
LEDA's real type allows for precise representations of real numbers, and can be used to compute the sign of a radical expression.^[1]

Error checking

LEDA makes use of certifying algorithms to demonstrate that the results of a function are mathematically correct. In addition to the input and output of a function, LEDA computes a third "witness" value which can be used as an input to checker programs to validate the output of the function. LEDA's checker programs were developed in Simpl, an imperative programming language, and validated using Isabelle/HOL, a software tool for checking the correctness of mathematical proofs.^[3]

The nature of a witness value often depends on the type of mathematical calculation being performed. For LEDA's planarity testing function, If the graph is planar, a combinatorial embedding is produced as a witness. If not, a Kuratowski subgraph is returned. These values can then be passed directly to checker functions to confirm their validity. A developer only needs to understand the inner-workings of these checker functions to be confident that the result is correct, which greatly reduces the learning curve compared to gaining a full understanding of LEDA's planarity testing algorithm.^[4]

Use cases

LEDA is useful in the field of computational geometry due to its support for exact representations of real numbers via the leda_real datatype. This provides an advantage in accuracy over floating-point arithmetic. For example, calculations involving radicals are considerably more accurate when computed using leda_real. Algorithms such as parametric search, a technique for solving a subset of optimization problems, and others under the real RAM model of computation rely upon real number parameters to produce accurate results.^[5]

Alternatives

Boost and LEMON are potential alternative libraries with some benefits in efficiency due to different implementations of fundamental algorithms and data structures. However, neither employs a similar set of correctness checking, particularly when dealing with floating-point arithmetic.^[3]

References

^ ^a ^b Mehlhorn, Kurt; Näher, Stefan (1999), LEDA: A Platform for Combinatorial and Geometric Computing, Cambridge University Press, ISBN 978-0-521-56329-1.
^ "LEDA - A Library of Efficient Data Types and Algorithms". Stony Brook University. Retrieved 21 February 2019.
^ ^a ^b Abdulaziz, Mohammad; Mehlhorn, Kurt; Nipkow, Tobias (2019). "Trustworthy graph algorithms". In Rossmanith, Peter; Heggernes, Pinar; Katoen, Joost-Pieter (eds.). 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany. LIPIcs. Vol. 138. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 1:1–1:22. arXiv:1907.04065. doi:10.4230/LIPIcs.MFCS.2019.1.
^ Mehlhorn, Kurt; Näher, Stefan (1998), Brim, Luboš; Gruska, Jozef; Zlatuška, Jiří (eds.), "From algorithms to working programs: On the use of program checking in LEDA", Mathematical Foundations of Computer Science 1998, Springer Berlin Heidelberg, vol. 1450, pp. 84–93, doi:10.1007/bfb0055759, ISBN 978-3-540-64827-7, retrieved 2019-11-22
^ Mehlhorn, Kurt; Schirra, Stefan (2001). "Exact Computation with leda_real - Theory and Geometric Applications" (PDF). Symbolic Algebraic Methods and Verification Methods. Vienna: Springer Verlag: 163–172. doi:10.1007/978-3-7091-6280-4_16. ISBN 978-3-211-83593-7.