next up previous contents index
Next: Dictionary Types Up: Basic Data Types Previous: Partitions ( partition )   Contents   Index


Parameterized Partitions ( Partition )

Definition

An instance P of the data type Partition<E> consists of a finite set of items (partition_item) and a partition of this set into blocks. Each item has an associated information of type E.

#include < LEDA/core/partition.h >

Creation

Partition<E> P creates an instance P of type Partition<E> and initializes it to the empty partition.

Operations

partition_item P.make_block(const E& x) returns a new partition_item it, adds the block it to partition P, and associates x with it.

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

const E& P.inf(partition_item it) returns the information associated with it.

void P.change_inf(partition_item it, const E& x)
    changes the information associates with it to x.


next up previous contents index
Next: Dictionary Types Up: Basic Data Types Previous: Partitions ( partition )   Contents   Index