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.
The first implementation uses heap-allocated mutable state. It is provided by the type
elem and the operations
find in the module
UnionFindThis module offers a union-find data structure based on disjoint set forests, with path compression and linking by rank.
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.MakeThis 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
unionoperation that merges two references.
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.StoreRefThis module offers mutable stores based on primitive mutable references. These stores do not support
UnionFind.StoreVectorThis module offers mutable stores based on mutable extensible arrays. These stores support copying, but
copyis not cheap; its cost is linear in the size of the store.
UnionFind.StoreMapThis module offers stores based on immutable integer maps. These stores support a constant-time
copyoperation. The module
UnionFind.StoreMapitself is an implementation of stores based on OCaml's
Mapmodule. The functor
UnionFind.StoreMap.Makecan also be used to construct an implementation of stores based on a user-provided implementation of immutable maps.
UnionFind.StoreTransactionalRefThis 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