@hackage disjoint-set0.1

Persistent disjoint-sets, a.k.a union-find.

  • Categories

    • License

      LicenseRef-LGPL

    • Maintainer

      Maxwell Sayles <maxwellsayles@gmail.com>

    • Links

    • Versions

      • 0.2 Mon, 15 Oct 2012
      • 0.1 Wed, 10 Oct 2012

    This is a persistent data structure for disjoint sets.

    The algorithm is described in "Introduction to Algorithms" by Cormen, et al. The implementation here uses both union by rank and path compression. We incur an O(logn) overhead because of the use of persistent maps.

    Data.IntDisjointSet is as strict as possible.