@hackage / equivalence

Maintaining an equivalence relation implemented as union-find using STT.

Latest0.4.1.1

About

Metadata

  • Last updated , by AndreasAbel
  • License BSD-3-Clause
  • Categories Algorithms

  • Maintained by: Andreas Abel

  • Lottery factor: 2

Links

Installation

Tested Compilers

  1. 9.12.2
  2. 9.10.2
  3. 9.8.4
  4. 9.6.7
  5. 9.4.8
  6. 9.2.8
  7. 9.0.2
  8. 8.10.7
  9. 8.8.4
  10. 8.6.5
  11. 8.4.4
  12. 8.2.2
  13. 8.0.2

Readme

This is an implementation of Tarjan's Union-Find algorithm (Robert E. Tarjan. "Efficiency of a Good But Not Linear Set Union Algorithm", JACM 22(2), 1975) in order to maintain an equivalence relation. This implementation is a port of the union-find package using the ST monad transformer (instead of the IO monad).