Other Algorithm Libraries
LEDA, Library of Efficient Data types and Algorithm:
- Widely used commercial library of algorithms,
data structures and data types.
- graphs and graph algorithms
- computational geometry
- number types
- Long history
- Started as an academic project in 1988.
- Precedes and partly overlaps STL.
- High quality library.
- Strong theoretical basis.
- Well optimized and tested implementations.
- Continuous development and support.
- Not based on STL
- Container interface uses items instead of iterators
- STL conformant iterators added later
- Algorithms are not fully generic
- For example, only LEDA graphs
CGAL, Computational Geometry Algorithms Library
- Developed by several European research institutes since 1995.
- Generic algorithms for computational geometry
- convex hulls, triangulations, spatial search etc.
- 2D, 3D, dD
- Computational geometry algorithms are particularly difficult to
- handling degeneracies
- Three points on a line is a problem for many algorithms.
- CGAL algorithms can handle degeneracies.
- numerical robustness
- Intersection of two lines may not be on the line
because of rounding errors.
- CGAL supports
Some features of CGAL:
Based on STL
template <class InputIterator, class OutputIterator>
convex_hull (InputIterator begin, InputIterator end,
- basic objects: points, line segments, etc.
- basic primitives:
- construction: segment from two points, point as an
intersection of two segments, etc.
- predicates: Are_parallel, Left_turn,
- 2D, 3D, and dD kernels
- Cartesian and homogenous coordinates
Kernels are parametrized by a number type
- built-in types, high-precision types, rationals,
exact arithmetic types,
interval arithmetic, lazy exact, etc.
- supports number types from other libraries: LEDA, CORE,
GNU Multiple Precision
Algorithm are parametrized by optional traits:
- basic types and primitives needed by the algorithm
- default traits are derived from the kernel
STXXL, Standard Template Library for Extra Large Data Sets
STL-like algorithms and data structures for external memory
- vector, map, stack, priority_queue
- sort, find, for_each
const unsigned M = 50*1024*1024; // use M bytes of main memory
stxxl::sort (v.begin(), v.end(), std::less<double>(), M);
Can process huge volumes of data (terabytes)
Support for implementing external memory algorithms
- supports parallel disks
- overlapping I/O and computation (asynchronous I/O)
- supports pipelining
- allows (but does not require) fine control of parameters and
access to low level details