Hoshen–Kopelman algorithm: Difference between revisions

Revision as of 06:14, 12 March 2022

Revision as of 15:09, 5 July 2022

Line 5:

== Percolation theory ==

[[Percolation theory]] is the study of the behavior and [[statistics]] of [[cluster analysis|clusters]] on [[Lattice graph|lattices]]. Suppose we have a large square lattice where each cell can be occupied with the [[probability]] <code>p</code> and can be empty with the probability <code>1&nbsp;–&nbsp;''p''</code>. 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 the [[Pixel connectivity|4-connected neighborhood]] that is top, bottom, left and right. Each occupied cell is independent of the status of its neighborhood. The number of clusters, the size of each cluster and their distribution are important topics in percolation theory.

<center>

{| style="margin: auto;"

{|

|-

| <gallery>

Occupied_Grids_P_%3D_0.24.png | <{{center>|'''Figure (a)'''</center>}}

</gallery>||<gallery>

Occupied_Grids_P_%3D_0.64.png | <{{center>|'''Figure (b)'''</center>}}

</gallery>|| Consider <code>5x5</code> grids in figure (a) and (b).<br /> In figure (a), the probability of occupancy is <code>p = 6/25 = 0.24</code>.<br /> In figure (b), the probability of occupancy is <code>p = 16/25 = 0.64</code>.

|}

</center>

== Hoshen–Kopelman algorithm for cluster finding ==

Line 96 ⟶ 95:

* <code>grid[5][4]</code> is occupied so check cell to the left and above, both the cells are unoccupied so assign a new label <code>8</code>.

* <code>grid[5][5]</code> is occupied so check cell to the left and above, both, cell to the left and above are occupied so merge the two clusters and assign the cluster label of the cell above to the cell on the left and to this cell i.e. <code>7</code>. (Merging using union algorithm will label all the cells with label <code>8</code> to <code>7</code>).

<center>

{| style="margin: auto;"

{|

|-

| <gallery>

H-K algorithm Input.png | <{{center>|'''Figure (a)'''</center>}}

</gallery>||<gallery>

H-K algorithm output.png | <{{center>|'''Figure (b)'''</center>}}

</gallery>|| Consider <code>6x6</code> grids in figure (a) and (b).<br /> Figure (a), This is the input to the Hoshen–Kopelman algorithm.<br /> Figure (b), This is the output of the algorithm with all the clusters labeled.

|}

</center>

== Applications ==