package unionFind

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

Install

Dune Dependency

Authors

Maintainers

Sources

archive.tar.gz
md5=7238ac49fba7c730e90cf1a577207347
sha512=c49dd3f9a6689f6a5efe39c26efe2c137f8812b4be6ee76c2cc20068cf86ad73c0ac97ec9a543245dddb63792ce8c1904576b3435bf419cc7837bc5e368eee6d

CHANGES.md.html

CHANGES

2022/01/22

  • Strengthen the specification of merge. It is now guaranteed that, if the user function f raises an exception, then the union-find data structure is unaffected.

2022/01/09

  • In UnionFind and UnionFind.Make, introduce a new operation merge, a variant of union that is parameterized with a join function f. The function f is not allowed to perform reentrant accesses to the union-find data structure.

  • In UnionFind only, introduce an optimization that reduces the amount of memory allocation. This leads to a speed improvement of about 10% in the micro-benchmark.

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.