Module Std.Partition

Result of a set partitioning.

A partition of a set S is a set of non-empty subset of set S, such that each element in a set of S is included in one and only one of the subsets and a union of the subsets forms a set S.

All nodes belonging to the same subset (called group in our parlance) represents the equivalence class. The equivalence side can be represented by a particular ordinal number or representative, that can be thought about as an ordinary number. See Equiv for the representation of this ordinal numbers. A particular element of an equivalence class plays a role of «representative element». Depending on the nature of partitioning, this role can have different semantics.

This data structure is used to represent results of partitioning of a graph into groups of nodes, for example, to strongly connected components.

type 'a t = 'a partition
val trivial : ('a, 'b) Core_kernel.Set.t -> 'a t

trivial s creates the trivial partition with a single equivalence class containing every member of s

val discrete : ('a, 'b) Core_kernel.Set.t -> 'a t

discrete s returns the partition with one class per element of s

val refine : 'a t -> equiv:('a -> 'a -> bool) -> cmp:('a -> 'a -> int) -> 'a t

refine p ~rel ~comp takes a partition p, and refines it according to the equivalence relation r, so that the resulting partition corresponds to the classes of r, assuming that those classes are finer that the original p.

Takes an additional comp argument to compare for equality within the equivalence classes.

val union : 'a t -> 'a -> 'a -> 'a t

union p x y returns the partition p with the classes of x and y merged. Returns p unchanged if either x or y are not part of any equivalence class.

val groups : 'a t -> 'a group Regular.Std.seq

groups p returns all partition cells of a partitioning p

val group : 'a t -> 'a -> 'a group option

group p x returns a group of an element x. Note, this function is not total since the set of all values of type 'a is usually larger than the underlying set that was partitioned.

val equiv : 'a t -> 'a -> 'a -> bool

equiv p x y is true of x and y belongs to the same equivalence class (i.e., to the same group).

val number_of_groups : 'a t -> int

number_of_groups p returns the amount of groups in a given partitioning p.

val of_equiv : 'a t -> equiv -> 'a group option

of_equiv p n rebuilds a group from an equivalence class ordinal number.

pp pp_elem p prints partition p using element printer pp_elem