package unionFind

You can search for identifiers within the package.

in-package search v0.2.0

On This Page

Implementations of the union-find data structure

Install

dune-project

Dependency

md5=a0c130e7c7500fc183a9f8dbc5c7b8a8

sha512=a1f591a3de021c9ce952a15dab904b4ccc4fe36750ccc20a868f9a9630f68cffe694dcf9fc1dca5675fb09b320175eeb3799069b7a4dd05714a5d1bb64ee814e

A concurrent union-find algorithm is now available under the name UnionFind.Concurrent.
OCaml 4.12 is now required. (make test requires OCaml 5.0.)
Fixed and improved documentation for union and merge.

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.

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.

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.

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).

On This Page