Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

5 Union-Find
 5.1 Introduction
 5.2 API

5 Union-Find

5.1 Introduction

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.

5.2 API

5.2-1 IsPartitionDS
‣ IsPartitionDS( arg )( filter )

Returns: true or false

Category of datastructures representing partitions. Equality is identity and family is ignored.

5.2-2 PartitionDS
‣ PartitionDS( filter, n )( operation )

Family containing all partition data structures Returns the trivial partition of the set [1..n].

5.2-3 PartitionDS
‣ PartitionDS( filter, partition )( operation )

Returns the union find structure of partition.

5.2-4 Representative
‣ Representative( unionfind, k )( operation )

Returns: a positive integer

Returns a canonical representative of the part of the partition that k is contained in.

5.2-5 Unite
‣ Unite( unionfind, k1, k2 )( operation )

Fuses the parts of the paritition unionfind containing k1 and k2.

5.2-6 RootsIteratorOfPartitionDS
‣ RootsIteratorOfPartitionDS( unionfind )( operation )

Returns: an iterator

Returns an iterator that runs through canonical representatives of parts of the partition unionfind.

5.2-7 NumberParts
‣ NumberParts( unionfind )( attribute )

Returns: a positive integer

Returns the number of parts of the partition unionfind.

5.2-8 SizeUnderlyingSetDS
‣ SizeUnderlyingSetDS( unionfind )( attribute )

Returns: a positive integer

Returns the size of the underlying set of the partition unionfind.

5.2-9 PartsOfPartitionDS
‣ PartsOfPartitionDS( unionfind )( attribute )

Returns: a list of lists

Returns the partition unionfind as a list of lists.

 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 Bib Ind

generated by GAPDoc2HTML