Up

module UnionFind

: sig

This module implements a simple and efficient union/find algorithm. See Robert E. Tarjan, ``Efficiency of a Good But Not Linear Set Union Algorithm'', JACM 22(2), 1975.

#
type 'a point

The abstraction defined by this module is a set of points, partitioned into equivalence classes. With each equivalence class, a piece of information, of abstract type 'a, is associated; we call it a descriptor.

#
val fresh : 'a -> 'a point

fresh desc creates a fresh point and returns it. It forms an equivalence class of its own, whose descriptor is desc.

#
val find : 'a point -> 'a

find point returns the descriptor associated with point's equivalence class.

#
val union : 'a point -> 'a point -> unit

union point1 point2 merges the equivalence classes associated with point1 and point2 (which must be distinct) into a single class whose descriptor is that originally associated with point2.

#
val equivalent : 'a point -> 'a point -> bool

equivalent point1 point2 tells whether point1 and point2 belong to the same equivalence class.

#
val eunion : 'a point -> 'a point -> unit

eunion point1 point2 is identical to union, except it does nothing if point1 and point2 are already equivalent.

#
val redundant : 'a point -> bool

redundant maps all members of an equivalence class, but one, to true.

#
val change : 'a point -> 'a -> unit

change p d updates the descriptor of p to d.

end