Module `Union_Find_Lattice.Labeled`

Labeled union-find: an extension of union find where nodes are related to each other via a relation (for example x --(+2)--> y). This allows representing more complex relation than equality, like equality up to a constant. Relations form a mathematical group.

module ArrayWithCopy
  (Config : Parameters.ARRAY_CONFIG)
  (Node : Parameters.NODE)
  (Relation : Parameters.GROUP) : 
  Sig.LABELED_UNION_FIND_LATTICE
    with type node = Node.t
     and type relation = Relation.t

Array based labeled union-find lattice with values. Warning: this one is NOT persistent, and requires explicit calls to copy on version switch.

module PatriciaTree
  (Config : Parameters.PATRICIA_TREE_CONFIG)
  (Node : Parameters.NODE)
  (Relation : Parameters.GROUP) : 
  Sig.LABELED_UNION_FIND_LATTICE
    with type node = Node.t
     and type relation = Relation.t

Patricia Tree based labeled union-find lattice with values.

module PersistentArray
  (Config : Parameters.PERSISTENT_ARRAY_CONFIG)
  (Node : Parameters.NODE)
  (Relation : Parameters.GROUP) : 
  Sig.LABELED_UNION_FIND_LATTICE
    with type node = Node.t
     and type relation = Relation.t

Persistent array based labeled union-find lattice with values.

module PersistentArrayNCA
  (Config : Parameters.PERSISTENT_ARRAY_CONFIG)
  (Node : Parameters.NODE)
  (Relation : Parameters.GROUP) : 
  Sig.LABELED_UNION_FIND_LATTICE
    with type node = Node.t
     and type relation = Relation.t

Persistent array based labeled union-find lattice with values. Same as PersitentArray, but builds join on the nearest common ancestor instead of one of the branches.

Module Union_Find_Lattice.Labeled

Module `Union_Find_Lattice.Labeled`