package unionFind

  1. Overview
  2. Docs
Implementations of the union-find data structure

Install

Dune Dependency

Authors

Maintainers

Sources

archive.tar.gz
md5=b92f29d7b920cf99651e0681aef1faf7
sha512=c4830c54269752706d90f29afe174a14c235b860c720ef3a873ca7672738e7f342d1dad381f7b1021a8d5f8a86f33774756dcf1fc23e0b4cfcbcb468e718a860

CHANGES.md.html

CHANGES

2022/01/07

  • Incompatible changes in the signature STORE, which appears in the type of the functor UnionFind.Make.

    • Instead of having every operation return a possibly-updated store, we assume that stores are updated in place. A new copy operation is introduced, so a persistent store is now simulated by a mutable store that can be copied in constant time. The main motivation for this change is that it makes UnionFind.Make much more pleasant to use in practice.

    • The operation union is no longer parameterized with a join function f. This API was flawed and could lead to meaningless behavior if the function f provided by the user performed reentrant calls to the union-find algorithm.

    • The operation union now returns a reference of type 'a rref instead of a unit value. This makes UnionFind.Make analogous to UnionFind, which it was not.

  • Expose find among the operations offered by UnionFind.Make.

  • Add is_representative to the operations offered by UnionFind and by UnionFind.Make.

  • Add a micro-benchmark, which is executed by make test.

2022/01/01

  • Improved documentation.

2020/03/20

  • Add a fast path (an optimization) in the find and eq functions, both in the basic union-find (UnionFind) and the one that is parameterized over a store (UnionFind.Make).

2019/08/27

  • Initial release of the package.

OCaml

Innovation. Community. Security.