package graphlib

  1. Overview
  2. Docs
package graphlib
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 partioning of a graph into groups of nodes, for example, to strongly connected components.

type 'a t = 'a partition
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