Extension of Hoshen-Kopelman algorithm to non-lattice environments

Ahmed Al-Futaisi, Tadeusz W. Patzek*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

78 Scopus citations


We extend the Hoshen-Kopelman (HK) algorithm for cluster labeling to non-lattice environments, where sites are placed at random at non-lattice points. This extension is useful for continuum systems and disordered networks. Our extension of the HK algorithm relies on several data structures that describe network connectivity regardless of its dimensionality. Just as for the classic HK algorithm on lattices, our extension is completed in a single pass through the sites of the network and cluster relabeling operates on a vector whose size is much smaller than the size of the network. Our extension of the HK algorithm works for any environment (lattice or non-lattice) of any dimensionality, type (sites, bonds or both), and with arbitrary connectivity between the sites. The proposed extension is illustrated through a simple network consisting of 16 sites and 24 bonds, and applied to a complex network extracted from a 3D micro-focused X-ray CT image of Bentheimer sandstone consisting of 3677 sites and 8952 bonds.

Original languageEnglish (US)
Pages (from-to)665-678
Number of pages14
JournalPhysica A: Statistical Mechanics and its Applications
Issue number3-4
StatePublished - Apr 15 2003
Externally publishedYes


  • Cluster labeling
  • Continuum systems
  • Disordered networks
  • Hoshen-Kopelman algorithm
  • Non-lattice

ASJC Scopus subject areas

  • Statistics and Probability
  • Condensed Matter Physics


Dive into the research topics of 'Extension of Hoshen-Kopelman algorithm to non-lattice environments'. Together they form a unique fingerprint.

Cite this