Hoshen and Kopelman

Hoshen and Kopelman [#!Hoshen!#] developed a sequential cluster identification algorithm which gives each cluster a unique label and counts the number of sites it contains. Each site belonging to cluster $\alpha$ is assigned a cluster label $m^\alpha_i$. The sites in cluster $\alpha$ may initially be assigned several different cluster labels. This is chosen to be the smallest number in the set. These are given as a set of natural numbers { $m^\alpha_1,m^\alpha_2,\ldots,m^\alpha_s,\ldots,m^\alpha_t,\ldots$}. In this set only one number is regarded as the proper cluster label which we designate as $m^\alpha_s$. This is the smallest number in the set.

A connection between the label $m^\alpha_t$ at any site, and the proper cluster cluster label $m^\alpha_s$, is provided by an array as { $N(m^\alpha_1),N(m^\alpha_2),\ldots,N(m^\alpha_s),\ldots,N(m^\alpha_t),\ldots$}. This is constructed so that $N(m^\alpha_s)$ is the only positive integer member of the set and denotes the number of sites in the cluster, while the remaining $N(m^\alpha_t)$ provide the links between the $N(m^\alpha_t)$ and the proper cluster label $N(m^\alpha_s)$. To be specific, if a site with label $m^\alpha_t$ is bonded to a site which has the proper cluster label $m^\alpha_s$ then

$$N(m^\alpha_t) = -m^\alpha_s$$ (6.11)

However, if a site with label $m^\alpha_p$ is not directly bonded to a site with the proper cluster label, but is connected to a site with label $m^\alpha_t$ then

$$N(m^\alpha_p) = -m^\alpha_t$$ (6.12)

Therefore to get the proper cluster label for this site we have to go through $m^\alpha_t$ using 6.12 then 6.11. Similarly for higher-order indirections, we just need to iterate $-m \leftarrow N(m)$ until we reach a positive value of $N(m)$, which means that $m$ is the proper cluster label and $N(m)$ the current number of sites in the cluster. Fortunately in most cases this hierarchy consists to one or two levels (one or two equations) only [#!Hoshen!#].

In practice the algorithm works as follows. We sweep through the sites of the lattice looking at neighbors in the negative directions (there are $d$ of them for a $d$-dimensional lattice). If site has no connected neighbors (or none of its neighbors have been labeled) then it is assigned a new label $S_i = m^\alpha_t$, and $N(m^\alpha_t) = 1$. If there is only one connected neighbor, at site with label $S_n = m^\alpha_r$, say, then gets the same label as $n:$ $S_i = m^\alpha_r$, and $N(m^\alpha_t) = N(m^\alpha_t) + 1$. The good feature of this cluster labeling technique becomes apparent when site links two or more previously labeled cluster fragments into a single cluster, that is, when it is bonded to two or more of its neighbors. No site belonging to any of these cluster fragments is relabeled (so that once a site is labeled it retains this label throughout the labeling process)--instead the readjustments occur within the $N(m^\alpha_t)$. The number of readjusted $N(m^\alpha_t)$'s for a site is equal to the number of coalescing cluster fragments at that site. Let us assume that the connected sites belong to clusters $\alpha,\beta,\gamma,\ldots$ which have proper cluster labels $m^\alpha_s,m^\beta_s,m^\gamma_s,\ldots$ with $m^\alpha_s$ being the smallest. These clusters coalesce at to form a single larger cluster so we set label $S_i = m^\alpha_s$ and readjust

$$N(m^\alpha_s) = N(m^\alpha_s)+N(m^\beta_s)+N(m^\gamma_s)+\ldots+1$$

$$N(m^\beta_s) = -m^\alpha_s$$ (6.13)

$$N(m^\gamma_s) = -m^\alpha_s$$

$$\ldots$$

It is this continual readjustment which keeps the hierarchy of indirections small. As a final stage in the algorithm we can pass through the lattice a second time setting the label at each site to be the proper cluster label $m^\alpha_s$. This makes it easier to pick out the clusters for updating.