Node Partitions (node_partition)

Definition

An instance P of the data type node_partition is a partition of the nodes of a graph G.

Creation

node_partition	P(graph G);	creates a node_partition P containing for every node v in G a block $\{v\}$.

Operations

int	P.same_block(node v, node w)
		returns true if v and w belong to the same block of P, false otherwise.
void	P.union_blocks(node v, node w)
		unites the blocks of P containing nodes v and w.
void	P.split(list<node> L)	makes all nodes in L to singleton blocks. Precondition: L is a union of blocks.
void	P.make_rep(node v)	makes v the canonical representative of the block containing v.
node	P.find(node v)	returns a canonical representative node of the block that contains node v.
int	P.size(node v)	returns the size of the block that contains node v.
node	P(node v)	returns P.find(v).

Implementation

A node partition for a graph G is implemented by a combination of a partition P and a node array of partition_item associating with each node in G a partition item in P. Initialization takes linear time, union_blocks takes time O(1) (worst-case), and same_block and find take time O(alpha(n)) (amortized). The cost of a split is proportional to the cost of the blocks dismantled. The space requirement is O(n), where n is the number of nodes of G.