Legend:
Library
Module
Module type
Parameter
Class
Class type
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.
discrete s returns the partition with one class per element of s
val refine : 'at->equiv:('a->'a-> bool)->cmp:('a->'a-> int)->'at
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.
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.