datastructures defines the interface for mutable data structures representing partitions of [1..n], commonly known as union-find data structures. Key operations are Unite (5.2-5) which fuses two parts of a partition and Representative (5.2-4) which returns a canonical representative of the part containing a given point.
‣ IsPartitionDS( arg ) | ( filter ) |
Returns: true or false
Category of datastructures representing partitions. Equality is identity and family is ignored.
‣ PartitionDS( filter, n ) | ( constructor ) |
Family containing all partition data structures Returns the trivial partition of the set [1..n].
‣ PartitionDS( filter, partition ) | ( constructor ) |
Returns the union find structure of partition.
‣ Representative( unionfind, k ) | ( operation ) |
Returns: a positive integer
Returns a canonical representative of the part of the partition that k is contained in.
‣ Unite( unionfind, k1, k2 ) | ( operation ) |
Fuses the parts of the partition unionfind containing k1 and k2.
‣ RootsIteratorOfPartitionDS( unionfind ) | ( operation ) |
Returns: an iterator
Returns an iterator that runs through canonical representatives of parts of the partition unionfind.
‣ NumberParts( unionfind ) | ( attribute ) |
Returns: a positive integer
Returns the number of parts of the partition unionfind.
‣ SizeUnderlyingSetDS( unionfind ) | ( attribute ) |
Returns: a positive integer
Returns the size of the underlying set of the partition unionfind.
‣ PartsOfPartitionDS( unionfind ) | ( attribute ) |
Returns: a list of lists
Returns the partition unionfind as a list of lists.
generated by GAPDoc2HTML