Module `Functional.GenericRelationalValued`

Functional union find

with generic types (parameterised by 'a)
with relations ('a, 'b) Relation.t on edges between elements and representatives
with values attached to each representative This interface can easily be reused to remove any of the above features if needed.

This is functional and immutable

Parameters

module Elt : Parameters.GENERIC_ELT

module Relation : Parameters.GENERIC_GROUP

module Value : Parameters.GENERIC_VALUE with type ('a, 'b) relation = ('a, 'b) Relation.t

Signature

module EltSet : PatriciaTree.HETEROGENEOUS_SET with type 'a elt = 'a Elt.t

Set of 'a Elt.t

type t

Type of the union-find structure

val pretty : Stdlib.Format.formatter -> t -> unit

Prints equivalence classes

val pretty_debug : Stdlib.Format.formatter -> t -> unit

Prints whole data structure

val equal : t -> t -> bool

val subseteq : t -> t -> bool

val empty : t

Existential wrappers for the return type of find operations

type 'a elt_through_relation =

| EltThroughRel : 'b Elt.t * ('a, 'b) Relation.t -> 'a elt_through_relation

type 'a value_through_relation =

| ValueThroughRelation : 'b Value.t option * ('a, 'b) Relation.t -> 'a value_through_relation

type 'a all_through_relation =

| AllThroughRelation : 'b Elt.t * 'b Value.t option * EltSet.t * ('a, 'b) Relation.t -> 'a all_through_relation

Find operations

val find_representative : t -> 'a Elt.t -> 'a elt_through_relation

Returns the representative of the given element, along with the relation between the given element and its representative. O(1) complexity

val find_class : t -> 'a Elt.t -> EltSet.t

Returns the class of the given element, O(1) complexity

val find_value : t -> 'a Elt.t -> 'a value_through_relation

Returns the value of the given element's representative (None for top), along with the relation between the given element and its representative. O(1) complexity

val find : t -> 'a Elt.t -> 'a all_through_relation

Returns the given element's representative, associated value (None for top), along with the relation between the given element and its representative. O(1) complexity

val check_related : t -> 'a Elt.t -> 'b Elt.t -> ('a, 'b) Relation.t option

check_related uf a b returns the relation between a and b if they are in the same class.

val add_value : t -> 'a Elt.t -> 'a Value.t -> t

add_value uf a v is uf with the value v added to a (Or more precisely, the value is added to the representative of a, via the relation between a and its representative). Intersects with previous value via Value.meet if one is present

Union and join

val union : 
  t ->
  'a Elt.t ->
  'b Elt.t ->
  ('a, 'b) Relation.t ->
  (t, ('a, 'b) Relation.t) Stdlib.result

union uf a b r adds the r a b relation in uf. Returns Ok uf' with the new value if successful, and Error rel if a and b are already related by rel and r != rel.

val join : t -> t -> t

join a b joins the two union find-structures:

The new classes are the intersection of the old classes
The new values are the Value.join of the old values

Module Functional.GenericRelationalValued