The Union-Find Data Structure in Several Guises

The OCaml library unionFind offers two implementations of the union-find data structure. Both implementations are based on disjoint sets forests, with path compression and linking-by-rank, so as to guarantee good asymptotic complexity: every operation requires a quasi-constant number of accesses to the store.

Over Primitive Mutable State

The first implementation uses heap-allocated mutable state. It is provided by the type elem and the operations make, get, set, eq, union, find in the module UnionFind.

• UnionFind This module offers a union-find data structure based on disjoint set forests, with path compression and linking by rank.

Over a User-Provided Store

The second implementation is parameterized over an implementation of stores. Its operations explicitly take a store as a parameter, and update it in place. It is provided by the functor UnionFind.Make. This functor is parameterized over an implementation of stores, described by the signature UnionFind.STORE. Its result signature is also UnionFind.STORE, extended with a union operation that merges two references.

• UnionFind.Make This functor offers a union-find data structure based on disjoint set forests, with path compression and linking by rank. It does not use primitive mutable state. Instead, it is parameterized over an implementation of stores. This allows the user to choose between many different representations of stores, such as stores based on primitive references, stores based on a (possibly extensible) primitive array, stores based on persistent maps, stores based on persistent or semi-persistent arrays, stores based on transactional references, and so on. The result of this functor is also an implementation of stores, extended with a union operation that merges two references.

Stores

The functor UnionFind.Make can be applied to many different implementations of stores, such as persistent stores, mutable stores backed by mutable arrays, and more. The following modules provide several different implementations of stores.

• UnionFind.StoreRef This module offers mutable stores based on primitive mutable references. These stores do not support copy.
• UnionFind.StoreVector This module offers mutable stores based on mutable extensible arrays. These stores support copying, but copy is not cheap; its cost is linear in the size of the store.
• UnionFind.StoreMap This module offers stores based on immutable integer maps. These stores support a constant-time copy operation. The module UnionFind.StoreMap itself is an implementation of stores based on OCaml's Map module. The functor UnionFind.StoreMap.Make can also be used to construct an implementation of stores based on a user-provided implementation of immutable maps.
• UnionFind.StoreTransactionalRef This module offers mutable stores based on mutable transactional references. These stores support a simple form of transactions that can be either aborted or committed. Transactions cannot be nested. These stores do not support copy.