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

(6.10) |

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.