> LEDA Guide > Graphs and Related Data Types > Node Partitions

Node Partitions

The data type node_partition is a partition of the nodes of Graphs. Node Partitions can be used to store a decomposition of the nodes of a graph into disjoint subsets called blocks. Node Partitions are specialized versions of Parameterized Partitions.

Example of how to use a node partition

Strengths

  • operations are efficient: initialization only needs linear time, union_blocks() needs constant time in the worst case, and find() is linear for all practical problems.
  • space is proportional to the number of vertices of the graph.

Disadvantages

  • very specialized data type

Tips

Always use node_partition instead of Partition<node>.

See also:

Parameterized Partitions

Manual Entries:

Page Node Partitions


Algorithmic Solutions Software GmbH