Module Unionfind.Make

Parameters

• S : SetS
• M : MapS with type key = S.elt

Signature

type elt = S.elt

The type of elements in the partition

type set = S.t

A set structure over elements

type t

The type of partitions

val create : unit -> t

Initialise an empty partition

val add : elt -> t -> unit

Add (in place) an element in the partition, or do nothing if the element is already in the partition.

val find : elt -> t -> elt

Find the canonical representative of an element. Raise not_found if the element isn't known yet.

val union : elt -> elt -> t -> unit

Merge (in place) the equivalence classes of two elements. This will add the elements in the partition if necessary.

val union_set : set -> t -> unit

Merge (in place) the equivalence classes of many elements.

val partition : t -> set list

Listing the different components of the partition