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/core/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(const 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. [86]). Any sequence of n make_block and m > = n other operations (except for split) takes time O(m (m, n)) . The cost of a split is proportional to the size of the blocks dismantled.
Example
Spanning Tree Algorithms (cf. section Graph Algorithms).