Definition
An instance P of the data type partition consists of a finite set of items (partition_item) and a partition of this set into blocks.
#include < LEDA/partition.h >
Creation
| partition | P | creates an instance P of type partition and initializes it to the empty partition. |
Operations
| partition_item | P.make_block() | returns a new partition_item it and adds the block it to partition P. |
| partition_item | P.find(partition_item p) | returns a canonical item of the block that
contains item p, i.e., iff P.same_block(p,q)
then P.find(p) and P.find(q) return the same item.
Precondition: p is an item in P. |
| int | P.size(partition_item p) | returns the size of the block containing p. |
| int | P.number_of_blocks() | returns the number of blocks in P. |
| bool | P.same_block(partition_item p, partition_item q) | |
| returns true if p and q belong to the same
block of partition P.
Precondition: p and q are items in P. |
||
| void | P.union_blocks(partition_item p, partition_item q) | |
| unites the blocks of partition P containing
items p and q.
Precondition: p and q are items in P. |
||
| void | P.split(list<partition_item> L) | |
| turns all items in L to singleton blocks.
Precondition: L is a union of blocks. |
||
Implementation
Partitions are implemented by the union find algorithm with weighted union and path compression (cf. [76]). Any sequence of n make_block and m > = n other operations (except for split) takes time O(m alpha (m, n)). The cost of a split is proportional to the size of the blocks dismantled.
Example
Spanning Tree Algorithms (cf. section Graph Algorithms).