Union-find applications: Percolation
Percolation data type. To model a percolation system, create a data type Percolation with the following API:
public class Percolation {
public Percolation(int n); // create n-by-n grid, with all sites blocked
public void open(int row, int col); // open site (row, col) if it is not open already
public boolean isOpen(int row, int col); // is site (row, col) open?
public boolean isFull(int row, int col); // is site (row, col) full?
public int numberOfOpenSites(); // number of open sites
public boolean percolates(); // does the system percolate?
}
Monte Carlo simulation. To estimate the percolation threshold, consider the following computational experiment:
- Initialize all sites to be blocked.
- Repeat the following until the system percolates:
- Choose a site uniformly at random among all blocked sites.
- Open the site.
- The fraction of sites that are opened when the system percolates provides an estimate of the percolation threshold.
Codes available at algs4/Percolation/src/
The back wash issue
My solution inspired from this post https://www.sigmainfy.com/blog/avoid-backwash-in-percolation.html, with some improvements:
- Using one
WeightedQuickUnionUF(n * n)
objects to track each site’s parent. - Use a
byte[n * n]
to store the each site’s state.- There are four possible states, represented as
BLOCKED: 0b000
OPEN: 0b001
CONNECT_TO_BOTTOM: 0b010
CONNECT_TO_TOP: 0b100
- With byte operation
|
, we enable sites to have mixture of states.
- There are four possible states, represented as
open(row, col)
: to open the current sitecur
, we need to- find out its four possible neibourghs (
up
,down
,left
,right
, if exist); - use
find()
to return the neibourghs’ parents (upParent
, etc..), useunion()
to connectcur
and its neibourghs; - Fianally, update
cur
’s new parentnewParent
’s state with the combination ofcur
’s parent state and the neibourghs’ parents states. - in totalm, there involves 4
union()
and 5find()
API calls at most but the time complexity is still $\Theta(\lg N)$
- find out its four possible neibourghs (
isOpen()
: $\in \Theta(1)$ by checking thebyte[n * n]
.isFull()
: $\in \Theta(1)$, use one callfind()
API and thus is $\in \Theta (\lg N)$percolates()
: use aboolean isPercolates
as mark, for any new open site that becomes bothCONNECT_TO_BOTTOM
andCONNECT_TO_TOP
, we could mark the model as percolates.
Estimated student memory = 9.00 n^2 + 0.00 n + 160.00 (R^2 = 1.000)
Test 2 (bonus): check that total memory <= 11 n^2 + 128 n + 1024 bytes
==> passed