     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& 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( (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: Node Priority Queues ( Up: Graphs and Related Data Previous: Lists of Nodes (   Contents   Index