next up previous
Next: Breadth-First Search (FGHK) Up: Parallel Cluster Algorithms Previous: Labeling or Growing

Depth-First Search (``Ants-in-the-Labyrinth'')

A Wolff cluster is grown in the same way as the ant colony analogy. Placing a baby ant on a new site corresponds to putting a bond between the two sites (with probability p), and an ant colony corresponds to a cluster.

This is straightforward to program --- just need to keep track of which sites are in the cluster, and which are the newly labeled sites (latest generation of ants) to be looped over in the next iteration.

This algorithm can also be used to do the connected component labeling for all sites in the Swendsen-Wang algorithm, given the configuration of bonds, by just adding an extra loop over all sites. If a site has already been labeled (assigned to a cluster), go to the next site. If not, increment the cluster label counter and give it to a new parent ant on that site, which then propagates the label through the labyrinth of bonds connecting sites in the cluster.



Paul Coddington, Northeast Parallel Architectures Center at Syracuse University, paulc@npac.syr.edu