next up previous contents index
Next: Node Priority Queues ( Up: Graphs and Related Data Previous: Lists of Nodes (   Contents   Index


Node Partitions ( node_partition )

Definition

An instance P of the data type node$\_$partition is a partition of the nodes of a graph G.

#include < LEDA/graph/node_partition.h >

Creation

node_partition P(const 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 positive integer if v and w belong to the same block of P, 0 otherwise.

void P.union_blocks(node v, node w)
    unites the blocks of P containing nodes v and w.

void P.split(const list<node>& L)
    makes all nodes in L to singleton blocks.
Precondition L is a union of blocks.

node P.find(node v) returns a canonical representative node of the block that contains node v.

void P.make_rep(node v) makes v the canonical representative of the block containing v.

int P.size(node v) returns the size of the block that contains node v.

int P.number_of_blocks() returns the number of blocks of P.

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.


next up previous contents index
Next: Node Priority Queues ( Up: Graphs and Related Data Previous: Lists of Nodes (   Contents   Index