Hoshen–Kopelman algorithm: Difference between revisions

Revision as of 05:20, 11 September 2016

Revision as of 05:29, 11 September 2016

Line 5:

== Percolation Theory ==

<div style="text-align:justify">

Percolation theory is the study of the behavior and statistics of clusters on lattices. Suppose we have a large square lattice where each cell can be occupied with the probability p and empty with probability 1 – p.

Percolation theory is the study of the behavior and statistics of clusters on lattices. Suppose we have a large square lattice where each cell can be occupied with the probability p and empty with probability 1 – p. Each group of neighboring occupied cells forms a cluster. Neighbors are defined as cells having a common side but not those sharing only a corner i.e. we consider 4x4 neighborhood. (top, bottom, left, right). Each occupied cell is occupied independently of the status of its neighborhood. The number of clusters, size of each cluster and their distribution are important topics in percolation theory.

</div>

Each group of neighboring occupied cells forms a cluster. Neighbors are defined as cells having a common side but not those sharing only a corner i.e. we consider 4x4 neighborhood. (top, bottom, left, right). Each occupied cell is occupied independently of the status of its neighborhood. The number of clusters, size of each cluster and their distribution are important topics in percolation theory.

== Union-Find Algorithm ==

Line 21:

largest_label = 0;

for x in 0 to n_columns {

for y in 0 to n_rows {

if occupied[x,y] then

{

left = occupied[x-1,y];

above = occupied[x,y-1];

for y in 0 to n_rows

else if (left !== 0) and (above == 0) then /* OneNeither a label above neighbor,nor to the left. */

largest_label = largest_label + 1; /* Make a new, as-yet-unused cluster label. */

{

label[x,y] = largest_label;

else if (left =!= 0) and (above !== 0) then /* One neighbor, aboveto the left. */

if occupied[x,y] then

label[x,y] = find(left);

else if (left == 0) and (above != 0) then /* One neighbor, above. */

left = occupied[x-1,y];

label[x,y] = find(above);

else /* Neighbors BOTH to the left and above. */

above = occupied[x,y-1];

union(left,above); /* Link the left and above clusters. */

if (left == 0) and (above == 0) then /* Neither a label[x,y] above nor to the= find(left. */);

}

largest_label = largest_label + 1; /* Make a new, as-yet-unused cluster label. */

label[x,y] = largest_label;

else if (left != 0) and (above == 0) then /* One neighbor, to the left. */

label[x,y] = find(left);

else if (left == 0) and (above != 0) then /* One neighbor, above. */

label[x,y] = find(above);

else /* Neighbors BOTH to the left and above. */

union(left,above); /* Link the left and above clusters. */

label[x,y] = find(left);

}

void union(int x, int y) {

labels[find(x)] = find(y);

}

voidint unionfind(int x,) int y){

int y = x;

while (labels[y] != y)

{

y = labels[y];

while (labels[find(x)] != find(yx); {

int z = labels[x];

while ( labels[x] != x)y;

}

x = z;

}

int find(int x)

return y;

{

int y = x;

while (labels[y] != y)

y = labels[y];

while (labels[x] != x)

{

int z = labels[x];

labels[x] = y;

x = z;

}

return y;

}

</div>