Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 Bib Ind

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

Goto Chapter: Top 1 2 3 4 5 6 7 8 9 10 11 Bib Ind

generated by GAPDoc2HTML