I need to implement the percolation algorithm Project 1, Percolation Description
ID: 3872961 • Letter: I
Question
I need to implement the percolation algorithm
Project 1, Percolation Description Percolation is a scientific model thats used to analyze the connectivity of systems. For example, it can be used to analyze if u porous landscape with water on the surface will eventually allow the wuter to drain through to the bottom. It can be us to analyze if oil would be able to reach the sur acc n a similar manner. The idea of the mo cl is o anal ze what conditions arc necessary or the system to per o ate ' e let the water or oil throu h of 3 states: blocked (black), open (white) or full The current assignment will allow students to apply the union-find data structure to solve this problem. The system will be represented as a Vby-V grid where cach cel can be in on (blue). A grid where percolation has been achieved will have a path of full cells livm the surface toe butou percolates does not percolate blocked site ful emmpty site open site connected to top no open site connected to top As can be observed in the cxamples, the flow of the matcrial gocs from top to bottom and cach ce routs that flow through the top, lcft, right and bottom ncighbors. A system whcre at least oue bottom-row ccll is full (thanks to thc flow route) is said to percolate Tasks e current project w e divided nto 3 pru raunining tus s and an analysLs phase 1 t wil require cou e sunulation experum en a evaluation and discussion o the results t is expectedat students will use the all ar rary provided by the authors of the course textbook, along with the suggested implementations for union-find data structures in Algorith 1.5 (Chapter I). The standard library JAR file can be dircctly seccssed here and basic instructions on how to execure programs using it a here Percolation API Develop a·lava class called Percolation that complies with the following interface: public Percolatian int n: Create a new n hy n grid where all cells are inially blocked public vold open( int x 1nt y): Open he sile al cuor unte x.y), where x represents the horizon al axis and y the vertical one. For cuns! Ieny purposes. 0,0 will be he button-le cell of the grid and n-1 -l) will be on the top-right. The graphical capabilitics discussed later assumc a similar convcntion.Explanation / Answer
PercolationVisualizer.java
public class PercolationVisualizer {
private int n; // n x n matrix
private boolean[][] matrix; // the matrix
private UF uf; // union find data structure
private int squares = 0; // number of spots opened
/**
* creates a new n by n grid where all cells are initially blocked
*
* @param n determines the size of the grid
*/
public PercolationVisualizer (int n) {
// creates boolean 2d array
this.n = n;
matrix = new boolean[n][n];
uf = new UF (n*n);
// initializes 2d array by filling all spots (false = blocked)
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
matrix[x][y] = false;
}
}
}
public void open (int x, int y, double scale) {
// opens a spot in the matrix (true = open)
matrix[x][y] = true;
int row = x;
int col = y;
// checks cells to the left, right, above, and under
// the newly opened cell; if checked cells are opened,
// they are unioned
if (isOpen(x+1,y))
uf.weightedUnion((y*n+x),(y*n+(x+1)));
if (isOpen(x-1,y))
uf.weightedUnion((y*n+x),(y*n+(x-1)));
if (isOpen(x,y+1))
uf.weightedUnion((y*n+x),((y+1)*n+x));
if (isOpen(x,y-1))
uf.weightedUnion((y*n+x),((y-1)*n+x));
// if it percolates to point (x,y), represent that
// component in light blue
if (isFull(x,y)) {
StdDraw.setPenColor(StdDraw.BOOK_LIGHT_BLUE);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (uf.weightedConnected((y*n+x), (j*n+i)))
StdDraw.filledSquare(scale + (2*scale*i),scale + (2*scale*j), scale);
}
}
}
// if doesn't percolate to point (x,y), just draw
// a white square
else {
StdDraw.setPenColor(StdDraw.WHITE);
StdDraw.filledSquare(scale + (2*scale*row),scale + (2*scale*col), scale);
}
// clears the previous text, and writes new text
// displaying how many open sites are currently
// open on the board
StdDraw.setPenColor(StdDraw.BLACK);
StdDraw.filledRectangle(.47, -.03, .2, .024);
squares++;
StdDraw.setPenColor(StdDraw.GREEN);
StdDraw.text(.47, -.03, squares + " open sites");
}
/**
* Returns true if cell (x,y) is open due to a previous call to
* open(int x, int y)
*
* @param x horizontal axis
* @param y vertical axis
* @return boolean if it's open
*/
public boolean isOpen (int x, int y) {
// checks for out of range values
if (x < 0 || x >= n) return false;
if (y < 0 || y >= n) return false;
// true is open, false is closed
return matrix[x][y];
}
/**
* Returns true if there is a path from cell (x,y) to the surface
* (i.e. there is percolation up to this cell)
*
* @param x horizontal axis
* @param y vertical axis
* @return boolean if it percolates
*/
public boolean isFull (int x, int y) {
// n == column
for (int row = 0; row < n; row++) {
if (uf.weightedConnected((((n-1)*n)+(row)), ((y*n)+x)))
return true;
}
return false;
}
/**
* Analyzes the entire grid and returns true if the whole
* system percolates
*
* @boolean true or false
*/
public boolean percolates() {
// checks each cell in the first row to see if there is
// a path to the surface, aka if the whole thing percolates
for (int i = 0; i < n-1; i++) {
if (isFull(i, 0)) {
System.out.println("Yes");
return true;
}
}
System.out.println("No");
return false;
}
/**
* Waits in seconds
*
* @param n time in seconds to wait
*/
public static void waiting (double n){
long t0, t1;
t0 = System.currentTimeMillis();
do{
t1 = System.currentTimeMillis();
}
while ((t1 - t0) < (n * 1000));
}
/**
* Reads a description of a grid from standard input
* (using StdIn.java) and draws it
*/
public static void main (String[] args) {
int size = StdIn.readInt();
PercolationVisualizer percolater = new PercolationVisualizer (size);
double scale = ((1.00 / size) / 2.00);
// sets the background as white, with a black square on top
StdDraw.setCanvasSize(600,600);
// StdDraw.frame.setTitle("Percolation Visualizer");
StdDraw.clear(StdDraw.BLACK);
// prototype: first parameter is for column, second parameter is for row
// int row = 3;
// int column = 1;
// StdDraw.filledSquare(scale + (2*scale*column),scale + (2*scale*row), scale);
while (!StdIn.isEmpty()) {
int x = StdIn.readInt();
int y = StdIn.readInt();
percolater.open(x,y,scale);
//waiting(.3);
}
}
}
UF.java
/**
* CS 251 - Project 1 - Union-Find
* This class stores the data structure
* of union find used for percolation. Has both
* quick-find and weighted-union implementations.
*
* @author Joseph Martella
*
* @professor Neville
*
* @date January 24, 2011
*/
public class UF {
private int[] id; // access to component id (site indexed)
private int[] sz; // size of component for roots (site indexed)
private int count; // number of components
public UF (int N) {
// initialize component id array
count = N;
id = new int[N];
for (int i = 0; i < N; i++)
id[i] = i;
sz = new int[N];
for (int i = 0; i < N; i++)
sz[i] = 1;
}
public int count() {
return count;
}
// checks if p and q are in the same component
public boolean connected (int p, int q) {
return (find(p) == find(q));
}
// weight union connected method
public boolean weightedConnected (int p, int q) {
return (findIt(p) == findIt(q));
}
// quick find
public int find (int p) {
return id[p];
}
// weight quick union
private int findIt (int p) {
// follow links to find a root
while (p != id[p])
p = id[p];
return p;
}
public void union (int p, int q) {
// put p and q into the same component
int pID = find(p);
int qID = find(q);
// nothing to do if p and q are already in the same component
if (pID == qID) return;
// rename p's component to q's name
for (int i = 0; i < id.length; i++)
if (id[i] == pID) id[i] = qID;
count--;
}
// union for the weightedUnion
public void weightedUnion (int p, int q) {
int i = findIt(p);
int j = findIt(q);
if (i == j) return;
// Make smaller root point to larger one.
if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i];}
else { id[j] = i; sz[i] += sz[j];}
count--;
}
}
PercolationStats.java
public class PercolationStats {
/**
* Main method takes three arguments, n,t, and speed;
* n is the size of the matrix; t is the repetitions,
* speed determines which implementation of union-find
* to use.
*/
public static void main (String[] args) {
int n = Integer.parseInt(args[0]); // the size of the square grid
int t = Integer.parseInt(args[1]); // repetitions of process
String speed = args[2]; // slow = quick find; fast = weighted union find
double[] sitesOpen = new double[t]; // how many open sites
double[] thresholds = new double[t]; // stores threshold values (p* = sitesOpen / n^2)
double[] time = new double[t]; // stores time of each repition
// stats to calculate
double avgThreshold = 0; // average threshold value
double standardDev = 0; // standard deviation of threshold values
double totalTime = 0; // total time
double averageTime = 0; // average time
double standardDevTime = 0; // standard deviation of time
int extra = n+2; // to use ghost rows
Percolation percolater = new Percolation (extra, speed);
int[] xA = new int[n*n];
// performs test t amount of times, each
// time with a new system and a different
// set of open spaces.
for (int reps = 0; reps < t; reps++) {
// System.out.println(reps);
// creates new, blocked grid to test
percolater = new Percolation (extra, speed);
boolean go = false;
for (int i = 0; i < n*n; i++) {
xA[i] = i;
}
StdRandom.shuffle(xA);
for (int i = 0; i < n; i++) {
percolater.open(i,0);
percolater.open(i,extra-1);
}
// y*n + x
// 4x4
// 12 13 14 15
// 8 9 10 11
// 4 5 6 7
// 0 1 2 3
// modNum = 6 mod 4 = 2
// divNum = 6 div 4 = 1
// (x,y) = (modNum, divNum)
// 15 mod 4 = 3
// 15 div 4 = 3
int modNum = 0;
int divNum = 0;
int x = 0;
int y = 0;
int i = 0;
Stopwatch timer = new Stopwatch();
// keeps opening random boxes until system percolates
while (!go) {
// generates random row and column to open
modNum = xA[i] % n;
divNum = xA[i] / n;
i++;
x = modNum+1;
y = divNum+1;
// makes sure random spot is closed before
// trying to open and increment value
percolater.open(x,y);
sitesOpen[reps]++;
time[reps] = timer.elapsedTime();
// if system percolates, calculates p* value
//if (sitesOpen[reps] > n) {
if (percolater.percolatesX()) {
thresholds[reps] = (sitesOpen[reps] / (double)(n*n));
go = true;
}
//}
}
}
//////////////////////////////
//// Calculation of Stats ////
//////////////////////////////
// calculates the average threshold
avgThreshold = StdStats.mean(thresholds);
// calculates the standard deviation
standardDev = StdStats.stddev(thresholds);
// calculates total time
for (int i = 0; i < t; i++) {
totalTime += time[i];
}
// calculates average time of experiment
averageTime = StdStats.mean(time);
// calculates standard deviation of time
standardDevTime = StdStats.stddev(time);
//////////////////////
//// Prints Stats ////
//////////////////////
System.out.println("mean threshold = " + avgThreshold);
System.out.println("std dev = " + standardDev);
System.out.println("time = " + totalTime);
System.out.println("mean time = " + averageTime);
System.out.println("stddev time = " + standardDevTime);
}
}
Percolation.java
public class Percolation {
private int n; // n x n matrix
private boolean[][] matrix; // the matrix
private UF uf; // union find data structure
private String speed; // fast = weight union find; slow = quick find
/**
* creates a new n by n grid where all cells are initially blocked
*
* @param n determines the size of the grid
*/
public Percolation (int n, String speed) {
// creates boolean 2d array
this.n = n;
matrix = new boolean[n][n];
uf = new UF (n*n);
// initializes 2d array by filling all spots (false = blocked)
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
matrix[x][y] = false;
}
}
this.speed = speed;
}
/**
* Open the site at coordinate (x,y), where x represents the horizontal
* axis and y the vertical one. For consistency purposes, (0,0) will be
* the bottom-left cell of the grid and (n-1,n-1) will be on the
* top-right.
*
* @param x horizontal axis
* @param y vertical axis
* @return void
*/
public void open (int x, int y) {
// opens a spot in the matrix (true = open)
matrix[x][y] = true;
// checks cells to the left, right, above, and under
// the newly opened cell; if checked cells are opened,
// they are unioned
if (speed.equals("slow")) {
if (isOpen(x+1,y))
uf.union((y*n+x),(y*n+(x+1)));
if (isOpen(x-1,y))
uf.union((y*n+x),(y*n+(x-1)));
if (isOpen(x,y+1))
uf.union((y*n+x),((y+1)*n+x));
if (isOpen(x,y-1))
uf.union((y*n+x),((y-1)*n+x));
}
if (speed.equals("fast")) {
if (isOpen(x+1,y))
uf.weightedUnion((y*n+x),(y*n+(x+1)));
if (isOpen(x-1,y))
uf.weightedUnion((y*n+x),(y*n+(x-1)));
if (isOpen(x,y+1))
uf.weightedUnion((y*n+x),((y+1)*n+x));
if (isOpen(x,y-1))
uf.weightedUnion((y*n+x),((y-1)*n+x));
}
}
/**
* Returns true if cell (x,y) is open due to a previous call to
* open(int x, int y)
*
* @param x horizontal axis
* @param y vertical axis
* @return boolean if it's open
*/
public boolean isOpen (int x, int y) {
// checks for out of range values
if (x < 0 || x >= n) return false;
if (y < 0 || y >= n) return false;
// true is open, false is closed
return matrix[x][y];
}
/**
* Returns true if there is a path from cell (x,y) to the surface
* (i.e. there is percolation up to this cell)
*
* @param x horizontal axis
* @param y vertical axis
* @return boolean if it percolates
*/
public boolean isFull (int x, int y) {
for (int row = 0; row < n; row++) {
if (speed.equals("slow")) {
if (uf.connected(((y*n)+x), (((n-1)*n)+(row))))
return true;
}
if (speed.equals("fast")) {
if (uf.weightedConnected(((y*n)+x), (((n-1)*n)+(row))))
return true;
}
}
return false;
}
/**
* Analyzes the entire grid and returns true if the whole
* system percolates
*
* @return boolean true or false
*/
public boolean percolates() {
// checks each cell in the first row to see if there is
// a path to the surface, aka if the whole thing percolates
for (int i = 0; i < n; i++) {
if (isFull(i, 0)) {
return true;
}
}
return false;
}
/**
* Analyzes the entire grid and returns true if the whole
* system percolates
*
* @return boolean true or false
*/
public boolean percolatesX() {
// checks each cell in the first row to see if there is
// a path to the surface, aka if the whole thing percolates
if (isFull(0,0))
return true;
return false;
}
/**
* Reads a description of a grid
* from standard input (using StdIn.java) and validates if
* the system described percolates or not, printing to
* standard output a simple "Yes" or "No" answer
* (using StdOut.java).
*/
public static void main (String[] args) {
// hard coded to use weighted union find
String speed = "fast";
int size = StdIn.readInt();
Percolation percolater = new Percolation (size, speed);
// reads values until file is empty
while (!StdIn.isEmpty()) {
int x = StdIn.readInt();
int y = StdIn.readInt();
percolater.open(x,y);
}
if (percolater.percolates())
System.out.println("Yes");
else
System.out.println("No");
}
}