union_find_example.C File Reference

Disjoint Set Union (Union-Find) data structure demonstration. More...

#include <iostream>
#include <string>
#include <vector>
#include <tpl_union.H>

Include dependency graph for union_find_example.C:

Go to the source code of this file.

Classes
struct	Edge

Functions
void	demo_basic_operations ()
void	demo_network_connectivity ()
void	demo_kruskal_simulation ()
void	demo_path_compression ()
int	main ()

Detailed Description

Disjoint Set Union (Union-Find) data structure demonstration.

This example demonstrates the Union-Find (also called Disjoint Set Union or DSU) data structure, one of the most elegant and efficient data structures in computer science. Despite its simplicity, it achieves near-constant-time operations through clever optimizations.

What is Union-Find?

Union-Find maintains a collection of disjoint (non-overlapping) sets and supports two main operations:

• Union: Merge two sets into one
• Find: Determine which set an element belongs to

It's perfect for tracking connectivity and equivalence relationships.

Key Operations

make_set(x)

• Create a new set containing only element x
• Time: O(1)
• Use: Initialize the data structure

find(x)

• Find the representative (root) of x's set
• Uses path compression for efficiency
• Time: O(α(n)) amortized (effectively O(1))
• Use: Check which set an element belongs to

union(x, y)

• Merge the sets containing x and y
• Uses union by rank to keep trees shallow
• Time: O(α(n)) amortized (effectively O(1))
• Use: Connect two elements/sets

same_set(x, y)

• Check if x and y are in the same set
• Time: O(α(n)) amortized
• Use: Test connectivity/equivalence

Optimizations

Union by Rank

• Always attach smaller tree under larger tree
• Keeps tree height logarithmic
• Prevents degenerate linear structures

Path Compression

• During find, make all nodes point directly to root
• Flattens tree structure
• Future finds become faster

Combined Effect

• Together, these optimizations achieve O(α(n)) per operation
• α(n) is the inverse Ackermann function
• For all practical purposes, α(n) ≤ 5 (effectively constant!)

Implementation Variants

Relation (Node-Based)

• Stores elements as nodes in a tree
• More flexible, can store additional data per element
• Best for: Variable number of elements, need element metadata

Fixed_Relation (Array-Based)

• Uses array indexed by element ID
• More memory-efficient, faster access
• Best for: Fixed set of elements (0 to n-1), maximum performance

Applications

Graph Algorithms

• Kruskal's MST: Track connected components while adding edges
• Connected components: Find all components in a graph
• Cycle detection: Detect cycles in undirected graphs

Network Analysis

• Network connectivity: Determine if nodes are connected
• Social networks: Find friend groups, communities
• Infrastructure: Check if cities are connected by roads

Image Processing

• Image segmentation: Group connected pixels
• Component labeling: Label connected regions
• Blob detection: Find connected blobs in images

Equivalence Relations

• Equivalence classes: Group equivalent elements
• Partition problems: Divide elements into groups
• Constraint satisfaction: Track variable equivalences

Physical Systems

• Percolation theory: Model phase transitions
• Particle systems: Track particle clusters
• Crystal growth: Model crystal formation

Complexity Analysis

Operation	Naive	Optimized
make_set	O(1)	O(1)
find	O(n)	O(α(n))
union	O(n)	O(α(n))

Space: O(n) - one entry per element

Amortized complexity: O(α(n)) per operation, where α(n) is the inverse Ackermann function. For all practical values of n, α(n) ≤ 5, making it effectively constant time!

Example: Kruskal's Algorithm

Union-Find is essential for Kruskal's MST algorithm:

1. Sort edges by weight
2. For each edge (u, v):
   if find(u) != find(v):  // Not in same component
     add edge to MST
     union(u, v)            // Merge components

Usage Example

Fixed_Relation uf(10);
 
uf.join(0, 1);
uf.join(2, 3);
uf.join(1, 2);
 
if (uf.are_connected(0, 3))
  cout << "0 and 3 are connected!\n";

Usage

./union_find_example

This example has no command-line options; it runs all demos.

See also

tpl_union.H Union-Find implementation

percolation_example.C Application: Percolation simulation

mst_example.C Application: Kruskal's MST algorithm

Author

Leandro Rabindranath León

Definition in file union_find_example.C.

Function Documentation

demo_basic_operations()

void demo_basic_operations

(

)

Definition at line 196 of file union_find_example.C.

References Fixed_Relation::are_connected(), Fixed_Relation::get_num_blocks(), Fixed_Relation::join(), and Aleph::maps().

Referenced by main().

demo_kruskal_simulation()

void demo_kruskal_simulation

(

)

Definition at line 339 of file union_find_example.C.

References Fixed_Relation::are_connected(), StlAlephIterator< SetName >::begin(), StlAlephIterator< SetName >::end(), Fixed_Relation::join(), Aleph::maps(), Aleph::HTList::size(), and Aleph::sort().

Referenced by main().

demo_network_connectivity()

void demo_network_connectivity

(

)

Definition at line 266 of file union_find_example.C.

References Aleph::maps(), and Aleph::HTList::size().

Referenced by main().

demo_path_compression()

void demo_path_compression

(

)

Definition at line 406 of file union_find_example.C.

References Fixed_Relation::are_connected(), Fixed_Relation::get_num_blocks(), Fixed_Relation::join(), and Aleph::maps().

Referenced by main().

main()

int main

(

)

Definition at line 445 of file union_find_example.C.

References demo_basic_operations(), demo_kruskal_simulation(), demo_network_connectivity(), demo_path_compression(), and Aleph::maps().