Cluster counting: The Hoshen-Kopelman algorithm versus spanning tree approaches

摘要

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 parallelized 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. [References: 36]