Hoshen–Kopelman algorithm: Difference between revisions

Revision as of 05:00, 13 September 2016

Revision as of 05:04, 13 September 2016

Line 5:

[[Percolation_theory|Percolation Theory]] is the study of the behavior and statistics of clusters on [[Lattice_graph | lattices]]. Suppose we have a large square lattice where each cell can be occupied with the [[Probability | probability]] <code>p</code> and empty with probability <code>1 – 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 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 style="width:40%;float:left;">

<gallery>

Occupied_Grids_P_%3D_0.24.png|Figure (a)

Occupied_Grids_P_%3D_0.64.png|Figure (b)

</gallery>

</div>

<div style="width:60%;float:left;">

{| class="wikitable"

Consider <code>5x5</code> grids in figure (a) and figure (b). In figure (a), the probability of occupied cells is equal to <code>p = 6/25 = 0.24</code> while in figure (b), the probability of occupancy is equal to <code>p = 16/25 = 0.64</code>

|-

</div>

| <gallery>

Occupied_Grids_P_%3D_0.24.png |Figure (a)

</gallery> || <gallery>

Occupied_Grids_P_%3D_0.6424.png |Figure (ba)

</gallery> || Example

|}

== Hoshen - Kopelman Algorithm for cluster finding ==