unionFind.mli 1.54 KB
 fpottier committed Mar 01, 2013 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 ``````(* \$Id: unionFind.mli,v 1.5 2005/12/01 16:20:07 regisgia Exp \$ *) (** 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. *) (** 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. *) type 'a point (** [fresh desc] creates a fresh point and returns it. It forms an equivalence class of its own, whose descriptor is [desc]. *) val fresh: 'a -> 'a point (** [find point] returns the descriptor associated with [point]'s equivalence class. *) val find: 'a point -> 'a (** [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 union: 'a point -> 'a point -> unit (** [equivalent point1 point2] tells whether [point1] and [point2] belong to the same equivalence class. *) val equivalent: 'a point -> 'a point -> bool (** [eunion point1 point2] is identical to [union], except it does nothing if [point1] and [point2] are already equivalent. *) val eunion: 'a point -> 'a point -> unit (** [redundant] maps all members of an equivalence class, but one, to [true]. *) val redundant: 'a point -> bool (** [change p d] updates the descriptor of [p] to [d]. *) val change: 'a point -> 'a -> unit``````