Module Imperative.GenericRelationalValued

Imperative 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.

Performs union by size, and path compression in find.

This is fully imperative and mutable.

  • Create at most one node per 'a Elt.t
  • Do NOT perform union between related nodes

Parameters

Signature

include Signatures.IMPERATIVE_GENERIC_RELATIONAL with type 'a t = 'a Node.t with type ('a, 'b) relation = ('a, 'b) Node.Relation.t
type 'a t = 'a Node.t
type ('a, 'b) relation = ('a, 'b) Node.Relation.t
type 'a node_through_relation =
  1. | NodeThoughRelation : 'b t * ('a, 'b) relation -> 'a node_through_relation

Existential wrapper for returning the representative

val find_representative : 'a t -> 'a node_through_relation

Find the representative of a node, and the associated relation

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

val union : 'a t -> 'b t -> ('a, 'b) relation -> (unit, ('a, 'b) relation) Stdlib.result

union m n r adds the m--(r)-->n relation to the union find returns Ok () on success, Error rel if m and n are already related via another relation rel and r != rel.

type 'a value = 'a Node.Value.t
type 'a value_through_relation =
  1. | ValueThroughRelation : 'b value * ('a, 'b) relation -> 'a value_through_relation

Existential wrapper for returning the value

type 'a node_and_value_through_relation =
  1. | NodeValueThroughRelation : 'b t * 'b value * ('a, 'b) relation -> 'a node_and_value_through_relation

Existential wrapper for returning the value and the representative

Find operations

val find_value : 'a t -> 'a value_through_relation

Find the value of a node, and the associated relation

Find the value and representative of a node, and the associated relation

Other misc operations

val add_value : 'a t -> 'a value -> unit

add_value a v adds 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