LEDA

LEDA, Library of Efficient Data types and Algorithm:

• Widely used commercial library of algorithms, data structures and data types.
  • containers
  • 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

LEDA Tutorial

CGAL

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 implement:
  • 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>
  OutputIterator
  convex_hull (InputIterator begin, InputIterator end,
               OutputIterator result);
  

• Geometric kernels:

  • basic objects: points, line segments, etc.
  • basic primitives:
    • construction: segment from two points, point as an intersection of two segments, etc.
    • distances
    • comparisons
    • predicates: Are_parallel, Left_turn, Counterclockwise_in_between, etc.
  • 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

  Example

STXXL

STXXL, Standard Template Library for Extra Large Data Sets

• STL-like algorithms and data structures for external memory computation

  • vector, map, stack, priority_queue
  • sort, find, for_each

  stxxl::vector<double> v;
  // ...
  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

• High performance

  • 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