Definition
An instance P of the data type nodepartition 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 partitionitem 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.