package unionFind

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

Install

Dune Dependency

Authors

Maintainers

Sources

archive.tar.gz
md5=5fa4eaeba9ce2a83eacfdbbaeabe3c2b
sha512=0fe9ae31893a6159287b5528953ccda2d229a5ae90a22776b8e9861bba9953024bb4ab7ecdb60c46c43968229b4aaa2d9e5baedb4337f3a25086f2ae00e021c0

Description

Published: 28 Aug 2019

README

UnionFind: implementations of the union-find data structure

The OCaml library unionFind offers two implementations of Tarjan's union-find data structure. Both implementations use path compression and linking-by-rank. The direct implementation uses heap-allocated mutable state. The indirect implementation is parameterized over an implementation of the signature STORE (link), and its operations explicitly take and return a store, so it is possible to use a persistent store, a store-in-an-array, etc.

Installation

To install the latest released version, type opam install unionFind.

To install from source, clone this repository and type make install.

Overview of the direct implementation

This implementation (link) offers a type 'a UnionFind.elem of "elements" and a number of functions that manipulate elements, including UnionFind.make, UnionFind.union, UnionFind.find, and so on.

Overview of the indirect implementation

This implementation (link) offers a functor UnionFind.Make whose input is an implementation of the signature STORE (link). Its output is another implementation of the signature STORE, which in addition to the standard operations on references also offers a union operation.

A number of implementations of the signature STORE are provided:

  • UnionFind.StoreMap (link) implements a store as an immutable integer map. Thus, UnionFind.Make(UnionFind.StoreMap) offers a persistent union-find data structure.

  • UnionFind.StoreRef (link) implements a store in terms of heap-allocated mutable state. There is no compelling reason to use UnionFind.Make(UnionFind.StoreRef), because the direct implementation UnionFind is more efficient.

  • UnionFind.StoreTransactionalRef (link) implements a mutable store that supports a form of transaction. Thus, UnionFind.Make(UnionFind.StoreTransactionalRef) offers a union-find data structure that also supports transactions.

    The higher-order function UnionFind.StoreTransactionalRef.tentatively is used to delimit the scope of a transaction. tentatively s f runs the function f within a new transaction on the store s. If f raises an exception, then the transaction is aborted, and any updates performed by f are rolled back. Otherwise, the updates performed by f are committed.

  • UnionFind.StoreVector (link) implements a store as a mutable vector, that is, a mutable extensible array. Thus, UnionFind.Make(UnionFind.StoreVector) offers an ephemeral union-find data structure, just like UnionFind.Make(UnionFind.StoreRef) and UnionFind.

Dependencies (2)

  1. dune >= "1.4"
  2. ocaml >= "4.03"

Dev Dependencies

None

Used by

None

Conflicts

None

OCaml

Innovation. Community. Security.