percolation_example.C File Reference

Percolation Simulation using Union-Find. More...

#include <iostream>
#include <iomanip>
#include <vector>
#include <random>
#include <chrono>
#include <tpl_union.H>
#include <tclap/CmdLine.h>

Include dependency graph for percolation_example.C:

Go to the source code of this file.

Classes
class	PercolationSystem
	Percolation system using Union-Find. More...

Functions
double	run_experiment (size_t n, mt19937 &rng)
	Run a single percolation experiment.
void	monte_carlo_simulation (size_t n, size_t trials, unsigned seed, bool verbose)
	Monte Carlo estimation of percolation threshold.
void	visual_demonstration (size_t n, unsigned seed)
	Interactive demonstration with visualization.
void	explain_union_find ()
	Explain Union-Find operations.
int	main (int argc, char *argv[])

Detailed Description

Percolation Simulation using Union-Find.

This example demonstrates the Union-Find (Disjoint Set Union) data structure through a classic application: percolation simulation. Percolation theory studies the behavior of connected clusters in random graphs and has applications in physics, materials science, and network analysis.

The Percolation Problem

Problem Statement

Given an n×n grid of sites:

• Each site is either open (can flow through) or blocked
• Sites are opened randomly with probability p
• System percolates if there's a path from top to bottom through open sites

Visual Example

Grid (n=5):
  Top:  O O X O O  (O=open, X=blocked)
        O X O O O
        O O O X O
        X O O O O
  Bottom: O O O O X
 
Does it percolate? Check if top row connects to bottom row.

Physical Phenomena Modeled

Materials Science

• Porous materials: Water flowing through rock
• Composite materials: Electricity conducting through materials
• Fracture mechanics: Cracks propagating through materials

Network Science

• Disease spread: Infection spreading through social networks
• Information diffusion: News spreading through networks
• Cascade failures: Failures propagating through systems

Ecology

• Forest fires: Fire spreading through forest
• Species migration: Species spreading through habitat

Union-Find Application

How Union-Find Helps

Problem: Need to check if top connects to bottom efficiently

Solution with Union-Find:

1. Each open site is an element in Union-Find
2. When site opens, union with adjacent open sites
3. Use virtual nodes:
   • Virtual "top" node connected to all open sites in the top row
   • Virtual "bottom" node connected to all open sites in the bottom row
4. System percolates if find(top) == find(bottom)

Algorithm

Initialize:
  - Create n×n grid
  - Create Union-Find with n² + 2 elements (sites + top + bottom)
  - Virtual nodes are connected when a site is opened in the top/bottom row
 
For each site (random order):
  Open site
  For each adjacent open site:
    Union(current, adjacent)
  If find(top) == find(bottom):
    System percolates!

Efficiency

• Without Union-Find: O(n²) per check (BFS/DFS)
• With Union-Find: O(α(n²)) ≈ O(1) per check
• Total: O(n² × α(n²)) ≈ O(n²) for entire simulation

Percolation Threshold

Critical Probability

The percolation threshold p* is the critical probability at which the system transitions from non-percolating to percolating.

Properties:

• For p < p*: System almost never percolates
• For p > p*: System almost always percolates
• At p = p*: Phase transition occurs

Known Thresholds

Lattice Type	Dimension	Threshold p*
Square	2D	≈ 0.593
Square	3D	≈ 0.312
Triangular	2D	0.5 (exact)
Hexagonal	2D	1 - 0.5 = 0.5 (exact)

Estimating Threshold

Through Monte Carlo simulation:

1. Run many simulations for different p values
2. Measure fraction that percolate
3. Find p where fraction ≈ 0.5
4. This estimates p*

Applications

Materials Science

• Porous materials: Understand flow through materials
• Composite design: Design materials with desired properties
• Fracture analysis: Predict material failure

Network Analysis

• Robustness: Understand network resilience
• Cascade failures: Model failure propagation
• Information spread: Model information diffusion

Ecology

• Habitat connectivity: Understand species movement
• Conservation: Design protected areas

Complexity

Operation	Complexity	Notes
Open site	O(α(n²))	Union-Find union
Check percolation	O(α(n²))	Union-Find find
Full simulation	O(n² × α(n²))	Open all sites

With path compression and union by rank: α(n²) ≈ constant!

Usage

# Run all demos (default if no specific demo flags are given)
./percolation_example
 
# Visual demonstration (small grid)
./percolation_example --visual
 
# Monte Carlo simulation (estimate percolation threshold)
./percolation_example --monte-carlo
 
# Explain Union-Find and percolation model
./percolation_example --explain
 
# Run all demos (default if no specific demo flags are given)
./percolation_example --all
 
# Configure parameters
./percolation_example --size 50 --trials 200 --seed 123
 
# Verbose Monte Carlo output
./percolation_example --monte-carlo --verbose

See also

tpl_union.H Union-Find implementation

union_find_example.C Union-Find basics

Author

Leandro Rabindranath León

Definition in file percolation_example.C.

Function Documentation

explain_union_find()

void explain_union_find

(

)

Explain Union-Find operations.

Definition at line 504 of file percolation_example.C.

References Aleph::maps().

Referenced by main().

main()

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 529 of file percolation_example.C.

References Aleph::all(), explain_union_find(), Aleph::maps(), min(), monte_carlo_simulation(), Aleph::verbose, and visual_demonstration().

monte_carlo_simulation()

void monte_carlo_simulation	(	size_t	n,
		size_t	trials,
		unsigned	seed,
		bool	verbose
	)

Monte Carlo estimation of percolation threshold.

Definition at line 388 of file percolation_example.C.

References abs(), Aleph::maps(), Aleph::mean(), rng, run_experiment(), sqrt(), Aleph::stddev(), Aleph::sum(), Aleph::variance(), and Aleph::verbose.

Referenced by main().

run_experiment()

double run_experiment	(	size_t	n,
		mt19937 &	rng
	)

Run a single percolation experiment.

Opens random sites until system percolates, returns threshold

Definition at line 362 of file percolation_example.C.

References StlAlephIterator< SetName >::begin(), StlAlephIterator< SetName >::end(), Aleph::maps(), rng, and Aleph::shuffle().

Referenced by monte_carlo_simulation().

visual_demonstration()

void visual_demonstration	(	size_t	n,
		unsigned	seed
	)

Interactive demonstration with visualization.

Definition at line 436 of file percolation_example.C.

References StlAlephIterator< SetName >::begin(), StlAlephIterator< SetName >::end(), Aleph::maps(), rng, Aleph::shuffle(), and Aleph::HTList::size().

Referenced by main().