Cluster algorithms were proposed by Swendsen and Wang [#!SW!#] in
1987, for Potts spin models. They have since been generalized to other
models, and other algorithms. In the Swendsen-Wang algorithm, clusters
of spins are created by introducing bonds between neighboring spins
A slightly different cluster algorithm has been proposed by Wolff [#!WOLFF!#]. In the Swendsen-Wang algorithm, we generated many clusters and then flip these clusters. In Wolff algorithm, a spin is chosen at random and a single cluster constructed around it, using same bond probabilities as for the Swendsen-Wang algorithm. All the spins in this cluster are then flipped, i.e, changed to a random new spin different from the old one. These parallel Wolff cluster algorithms were developed in several different languages including C code for the CM-5 using CMMD [#!CMMD!#] which was presented in [#!BAE!#].
Cluster algorithms have in common the problem of identifying and labeling the connected clusters of spins. This is very similar to an important problem in image processing, that of identifying and labeling the connected components in a binary or multi-colored image composed of an array of pixels. The only real difference is that in the spin model case, neighboring sites of the same spin have a certain probability of being in the same cluster, while for neighboring pixels of the same color that probability is one. Unfortunately this is a large enough difference so that some algorithms which work in image analysis will not work, or require substantial changes, for spin models. In our implementation of the Swendsen-Wang cluster algorithm for the Ising model, we have used a commonly used cluster identification algorithm invented by Hoshen and Kopelman.