package union-find-lattice

  1. Overview
  2. Docs
package union-find-lattice
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module Union_Find_Lattice.Parameters

Common module types for the various functors creating union-finds lattices.

Nodes

Nodes are the elements on which a union-find operates.

module type NODE = sig ... end

Nodes stored in the union find. Nodes must inject into integers via NODE.to_int.

module type NODE_WITH_COMPARE = sig ... end

Some implementations (namely MemCAD's) require NODEs to be comparable and biject into integers (via NODE.to_int and NODE_WITH_COMPARE.of_int).

module type POLYMORPHIC_NODE = sig ... end

A polymorphic version of NODE, the type NODE.t now has a parameter 'a POLYMORPHIC_NODE.t. This is useful for polymorphic labeled union-find variants.

Relations

Labeled union-find introduces labels, which we call relations here, between NODEs. Classical union find has a single equivalence relation, which can be mimicked with a unit relation (type t = unit or type ('a, 'b) t = Equiv : ('a,'a) t) Relations have a group structure.

module type GROUP = sig ... end

A (possibly non-commutative) group structure, used to represent relations.

module type POLYMORPHIC_GROUP = sig ... end

Polymorphic version of GROUP. Elements now have two parameters 'a and 'b. This helps ensure composition is done in the right way.

Values

Values form a lattice that can be attached to a union-find, each equivalence class can then have an attached value.

module type VALUE = sig ... end

The values associated with each equivalence class in the union-find. Values have a lattice structure. For flexibility, the lattice value operations also take the a NODE (often the representative) as an extra argument. It can be ignored if irrelevant.

module type RELATIONAL_VALUE = sig ... end

For labeled union-find, values and relations (GROUP) interact via a group action apply

module type POLYMORPHIC_VALUE = sig ... end

Polymorphic version of RELATIONAL_VALUE.

Configuration

The first functor argument is typically used to offer various choices for union-find implementation

module type ARRAY_CONFIG = sig ... end

Configuration options for standard array-with-copy union-finds

module type PATRICIA_TREE_CONFIG = ARRAY_CONFIG

Configuration options for patricia tree union-finds

module type PERSISTENT_ARRAY_CONFIG = sig ... end

Configuration options for persistent array union-finds