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 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 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(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 .

Next: Node Priority Queues ( Up: Graphs and Related Data Previous: Lists of Nodes (   Contents   Index
Christian Uhrig 2017-04-07