package inferno

  1. Overview
  2. Docs

Module Inferno.UnionFindSource

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.

Sourcetype '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.

Sourceval 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.

Sourceval find : 'a point -> 'a

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

Sourceval union : ('a -> 'a -> 'a) -> 'a point -> 'a point -> unit

union f point1 point2 merges the equivalence classes associated with point1 and point2 into a single class. Then, (and only then,) it sets the descriptor of this class to the one produced by applying the function f to the descriptors of the two original classes. It has no effect if point1 and point2 are already in the same equivalence class.

Sourceval equivalent : 'a point -> 'a point -> bool

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

Sourceval is_representative : 'a point -> bool

is_representative maps exactly one member of each equivalence class to true.