The Union-Find Data Structure in Several Guises

The OCaml library unionFind offers several sequential implementations and one concurrent implementation of the union-find data structure.

All implementations are based on disjoint sets forests, with path compression and a balanced linking method, so as to guarantee good asymptotic complexity: every operation requires a quasi-constant number of accesses to the store.

The linking method used in the sequential algorithms is linking by rank. The linking method used in the concurrent algorithm is linking by random index.

Sequential UF Over Primitive Mutable State

This union-find data structure uses heap-allocated mutable state.

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

Concurrent UF Over Primitive Mutable State

This union-find data structure uses heap-allocated mutable state. It is thread-safe: the data structure can be used by several threads simultaneously.

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

Sequential UF Over a User-Provided Store

This union-find data structure 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.