Cluster counting: The Hoshen-Kopelman algorithm vs. spanning tree approaches

Abstract

Two basic approaches to the cluster counting task in the percolation and related models are discussed. The Hoshen-Kopelman multiple labeling technique for cluster statistics is redescribed. Modifications for random and aperiodic lattices are sketched as well as some parallelised versions of the algorithm are mentioned. The graph-theoretical basis for the spanning tree approaches is given by describing the "breadth-first search" and "depth-first search" procedures. Examples are given for extracting the elastic and geometric "backbone" of a percolation cluster. An implementation of the "pebble game" algorithm using a depth-first search method is also described.

LaTeX, uses ijmpc1.sty(included), 18 pages, 3 figures, submitted to Intern. J. of Modern Physics C

References in corpus (1)

• Stressed backbone and elasticity of random central-force systems

Cited by in corpus (3)

• An Introduction to Monte Carlo Simulation of Statistical physics Problem
• Random nanowire networks: Identification of a current-carrying subset of wires using a modified wall follower algorithm
• Identification of a current-carrying subset of a percolation cluster using a modified wall follower algorithm