Abstract

In this paper we extend the Hoshen-Kopelman (HK) cluster labeling algorithm to non-lattice environments, where sites are placed at  random locations and have random connectivities. This extension is useful for continuum systems and complex networks used in pore-level studies of natural rocks. Our extension of the algorithm relies on specific data structures that describe network connectivity regardless of its complexity. Similarly to the HK algorithm on lattices, our extension is performed in a single pass through the network. The label recycling scheme is identical to the one implemented for lattices. The proposed extension of the HK algorithm works identically for any environment (lattices or non-lattices), any network dimensionality, any network element (sites, bonds, or both), and finally for any possible connectivity between the sites and bonds (spatially heterogeneous number of bonds connecting a site). Our extension of the HK algorithm is illustrated through a simple network consisting of 16 sites and 24 bonds, and applied to a complex network extracted from a 3-D micro-focused X-ray CT images of a Bentheimer sandstone consisting of 3677 sites and 8952 bonds.