Next: Parameterized Partitions ( Partition Up: Basic Data Types Previous: Dynamic Integer Sets (   Contents   Index

# Partitions ( partition )

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& 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).

Next: Parameterized Partitions ( Partition Up: Basic Data Types Previous: Dynamic Integer Sets (   Contents   Index