Hoshen–Kopelman algorithm: Difference between revisions

Revision as of 09:09, 23 February 2019

Revision as of 03:53, 16 July 2019

Line 1:

{{short description|Algorithm for labeling clusters on a grid}}

{{Machine learning bar}}

The '''Hoshen–Kopelman algorithm''' is a simple and efficient [[algorithm]] for labeling [[Cluster analysis|clusters]] on a grid, where the grid is a regular [[Artificial neural network|network]] of cells, with the cells being either occupied or unoccupied. This algorithm is based on a well-known [[Disjoint-set data structure|union-finding algorithm]].<ref>https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf</ref> The algorithm was originally described by J. Hoshen and R.[[Raoul Kopelman]] in their 1976 paper "Percolation and Cluster Distribution. I. Cluster Multiple Labeling Technique and Critical Concentration Algorithm".<ref>{{cite journal|url=http://link.aps.org/doi/10.1103/PhysRevB.14.3438|title=Percolation and cluster distribution. I. Cluster multiple labeling technique and critical concentration algorithm|first1=J.|last1=Hoshen|first2=R.|last2=Kopelman|date=15 October 1976|publisher=|journal=Phys. Rev. B|volume=14|issue=8|pages=3438–3445|via=APS|doi=10.1103/PhysRevB.14.3438}}</ref>

== Percolation theory ==

Line 10:

| <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>

Line 99:

| <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>