1 Problem setting and motivation
1.1 Connected components in discrete lattices
In many computational physics models, the basic object is a discrete grid (a lattice) whose sites may be “active” (for example, occupied) or “inactive.” A central task is to partition the active sites into maximal groups such that sites in the same group are mutually reachable through allowed adjacency steps. These groups are called connected components, and each component is often interpreted as a physical cluster.
1.2 Percolation and cluster labeling use cases
Percolation theory studies how connectivity emerges as the fraction of active sites or bonds changes. Cluster labeling is the computational primitive that converts a random occupancy configuration into a set of identifiable clusters. Once labels are assigned, one can compute cluster sizes, track whether a cluster spans the system, and estimate thresholds for large-scale connectivity.
1.3 Efficiency goals: single-pass labeling and equivalence resolution
A naïve approach might repeatedly search for clusters using graph traversal methods (such as breadth-first search or depth-first search), which can revisit or scan sites many times. The Hoshen–Kopelman algorithm is designed to avoid this by scanning the lattice in a prescribed order and assigning provisional labels on the fly. When later sites indicate that two provisional labels actually belong to the same connected component, the algorithm records this through label equivalences and resolves the final labeling after the scan.
2 Core idea of the algorithm
2.1 Scanning order and local neighborhood checks
The algorithm traverses the lattice sites in a fixed order (for example, row by row). For each active site, it inspects only a limited set of neighbors that have already been processed under the chosen scan order. This locality makes it possible to decide provisional connectivity without revisiting future sites.
2.2 Assigning provisional labels during the pass
When an active site is encountered, its neighbors’ labels (if any) determine the provisional label assignment:
- If no inspected active neighbors exist, the site starts a new cluster and receives a fresh label.
- If exactly one inspected neighbor belongs to an existing cluster, the site inherits that neighbor’s label.
- If multiple inspected neighbors correspond to different provisional labels, the site is labeled consistently (often using one of them) while noting that the different provisional labels should be merged.
2.3 Handling label conflicts via equivalence tracking
The key mechanism is the treatment of label “conflicts.” If different previously assigned labels are discovered to represent the same connected component, the algorithm does not immediately relabel the entire lattice. Instead, it stores an equivalence relationship between those labels using a disjoint-set (union–find) structure. This defers costly global updates until all sites have been processed.
2.4 Final relabeling and cluster normalization
After the scan completes, each provisional label corresponds to a set of labels that are equivalent (belong to the same true cluster). The algorithm then resolves each label to a canonical representative (typically the disjoint-set root) and produces a normalized cluster map. Optionally, labels can be compressed to a contiguous range to simplify later analysis.
3 Equivalence management (union–find)
3.1 Disjoint-set representation of label equivalences
Union–find maintains a partition of provisional labels into equivalence classes. Each label is associated with a node in the disjoint-set structure. Two provisional labels that are found to describe the same cluster are placed into the same set, meaning they share a common representative for the final output.
3.2 Union operations when clusters merge
When the scan detects that an active site connects multiple provisional labels, the algorithm performs union operations between their corresponding disjoint-set nodes. Over time, these unions build the equivalence relations needed to merge clusters consistently.
3.3 Find operations and path compression
To decide whether two labels are already known to be equivalent (and to obtain the canonical representative), the algorithm uses the find operation. Path compression is a technique where, during find, nodes traversed along the way are rewired to point closer to the representative. This reduces future lookup time.
3.4 Complexity considerations for union–find integration
Union–find with path compression (and often union by rank or size) yields near-constant amortized time per operation. As a result, the overhead of equivalence management remains small compared with the full lattice scan, supporting the algorithm’s efficiency goals.
4 Lattice formulation details
4.1 Choice of lattice type and adjacency rule
The algorithm’s behavior depends on how adjacency is defined. In grid-based models, adjacency usually follows a neighborhood rule such as:
- Von Neumann adjacency (orthogonal neighbors)
- Moore adjacency (including diagonals)
The neighborhood rule determines which sites count as connected and therefore affects both the equivalence merges and the final cluster geometry.
4.2 Two-dimensional site percolation conventions
In a typical two-dimensional site-percolation setting, the lattice is treated as a square grid and sites are considered connected if they are both active and adjacent according to the chosen neighborhood rule. The scan order and neighbor inspection set are often selected so that only a subset of neighbors (those “behind” the scan) are checked, which is sufficient for correct labeling under the equivalence tracking strategy.
4.3 Boundary conditions (open vs. periodic) in implementations
Boundary conditions influence neighbor availability at the edges:
- Open boundaries treat missing neighbors as absent.
- Periodic boundaries wrap around edges, effectively connecting opposite sides.
Implementations must encode these rules consistently both in neighbor checks during the pass and in any spanning criteria evaluated afterward.
4.4 Generalization to higher dimensions
The same methodology extends to higher-dimensional lattices. The neighborhood inspection set grows with dimension, but the logic remains: each site’s provisional label depends on already-visited neighbors, and any discovered connectivity among different provisional labels is captured through union operations. The final relabeling step remains conceptually identical.
5 Step-by-step algorithm workflow
5.1 Initialization of data structures
Before scanning begins, the algorithm prepares:
- A label array (or equivalent structure) matching the lattice footprint to store provisional labels for active sites.
- A disjoint-set structure sized to the maximum possible number of provisional labels (often bounded by the number of active sites or by the total lattice size).
- A counter for the next new label to assign.
5.2 First pass: provisional labeling rules
For each lattice site in scan order:
- If the site is inactive, it receives no label.
- If active, the algorithm examines the inspected neighbors that have already been processed.
- Based on how many distinct neighbor clusters are found, it assigns:
- a new label if none exist,
- an inherited label if one exists,
- an inherited label plus recorded equivalences if multiple exist.
This completes the “single pass” portion, with merges tracked indirectly.
5.3 Updating equivalence classes on conflicts
When multiple inspected neighbors indicate connectivity between distinct provisional labels, the algorithm unions their disjoint-set nodes. It may also maintain the chosen label for the current site while ensuring that all involved labels share the same final representative after resolution.
5.4 Second pass: resolving to canonical labels
After the scan, the algorithm iterates over the lattice again:
- Each active site’s stored provisional label is mapped to its disjoint-set representative via find.
- The representative labels are then optionally remapped to a compact numbering scheme.
The result is a final cluster labeling map suitable for statistical measurements.
6 Mathematical and computational interpretation
6.1 Mapping clusters to labeled connected components
Mathematically, the algorithm produces an explicit labeling of connected components in a graph induced by active sites and adjacency relations. Each label corresponds to a component, and the label equivalence structure guarantees that the labeling respects transitive connectivity discovered through the scan order.
6.2 Relationship to graph algorithms (contrast with BFS/DFS)
While cluster identification is a standard graph problem, Hoshen–Kopelman differs from BFS/DFS approaches in execution pattern. BFS/DFS starts from an unvisited node and explores the full component before moving on, potentially requiring many dynamic queue or stack operations. Hoshen–Kopelman instead processes nodes in a predetermined sweep, using local neighborhood information and deferred merges. This makes it particularly convenient for regular lattices and repeated simulations.
6.3 Data structure perspective on computational graph connectivity
From a computational viewpoint, the lattice scan constructs connectivity information incrementally. Union–find acts as a compressed representation of partial connectivity knowledge. The final component structure emerges when all unions induced by local adjacency constraints are applied and representatives are queried.
6.4 Notes on reproducibility and deterministic label outcomes
Given a fixed scan order, neighborhood definition, and union–find tie-breaking behavior (when present), the algorithm’s output can be deterministic in the sense that it produces consistent cluster maps for the same input. However, the specific numeric label values may differ across implementations if representative selection or relabel compression differs, even though the partition into clusters remains the same.
7 Performance and complexity
7.1 Time complexity analysis
The algorithm performs a constant amount of work per lattice site during the first pass (including neighbor checks) and a similar traversal during the second pass (for representative resolution). With union–find operations contributing near-constant amortized overhead, the overall time scales roughly linearly with the number of sites.
7.2 Space complexity and memory footprint
Space usage includes the label array and the disjoint-set structure. Both are proportional to lattice size or, more precisely, to the number of provisional labels that can be created. For typical percolation simulations, this is manageable relative to the costs of repeated traversal using explicit graph search structures.
7.3 Practical optimization tips for large lattices
Efficient implementations often:
- Use compact integer arrays for labels.
- Limit inspected neighbors to the minimal set required by scan order.
- Apply path compression so find operations remain fast.
- Perform label resolution in a streaming manner to reduce cache misses.
These details can significantly affect runtime in large-scale Monte Carlo studies.
7.4 Scaling behavior in typical simulation regimes
In Monte Carlo workflows, the algorithm’s near-linear scaling supports running many independent configurations. The effective cost per sample depends on occupancy density: at very low densities, few labels are created; at high densities, labels are abundant but union operations remain efficient. In either regime, the dominant factor is typically the number of lattice sites processed.
8 Applications in statistical physics and simulations
8.1 Cluster statistics from labeled components
Once clusters are labeled, physical quantities can be computed directly from the labeled map. Counting the number of clusters of each size, tracking their shapes, and computing aggregate measures become straightforward because membership queries reduce to scanning label identifiers.
8.2 Measuring observables: cluster size distributions
Cluster size distributions are central in many percolation and critical phenomena investigations. The labeled output allows the algorithm to tally how many connected components have each cardinality. These distributions can then be compared with theoretical scaling forms or used to estimate critical exponents.
8.3 Detecting percolation and spanning clusters
Percolation is often identified by the emergence of a cluster that connects across the system. Spanning detection can use boundary flags: during or after labeling, one checks whether any component touches multiple boundaries (depending on boundary conditions). The labeled map makes this check efficient because it requires only component-level metadata rather than repeated searches.
8.4 Use in Monte Carlo workflows
In Monte Carlo simulations, many independent configurations are generated, and connectivity must be recomputed each time. Hoshen–Kopelman’s single-sweep structure and union–find efficiency make it well-suited for repeated application across large ensembles, reducing total computational cost.
9 Extensions and variants
9.1 Bond percolation vs. site percolation labeling
In site percolation, sites are either active or inactive; connectivity depends on active sites and adjacency. In bond percolation, sites are always present but edges between neighboring sites may be active. Labeling can be adapted by changing the “neighbor check” so that provisional connectivity exists only when the connecting bond is present (and, in some formulations, both endpoint sites are considered “available”).
9.2 Continuum-to-lattice approximations and discretization effects
In some simulations, continuum geometries are discretized into grids, after which connectivity is computed on the lattice. Labeling provides a practical way to approximate connectivity in complex media. Accuracy depends on how discretization translates geometric proximity into adjacency, and results may require finite-size or resolution studies.
9.3 Higher-order neighborhood connectivity (e.g., extended adjacency)
Connectivity rules can be extended beyond immediate neighbors, for instance by allowing steps within a larger stencil. Incorporating such rules changes which neighbors are inspected during the scan and how unions are triggered, but the equivalence-based structure remains applicable as long as connectivity can be expressed through local adjacency checks.
9.4 Incremental updates for dynamic lattice changes (conceptual approaches)
For systems where occupancy changes gradually over time, rerunning the full labeling pass may be expensive. Conceptual incremental strategies can reuse prior connectivity information, but correctness becomes more complex when removals occur (unions handle additions naturally, while deletions may require recomputation). In practice, many dynamic models still recompute labeling periodically or use hybrid approaches.
10 Illustrative example
10.1 Constructing an input occupancy pattern
Consider a small two-dimensional grid where some sites are marked occupied and others empty. For clarity, assume the adjacency rule is nearest-neighbor in orthogonal directions, and scan order proceeds left to right, top to bottom.
10.2 Walking through provisional labeling on a small grid
As the scan progresses, the algorithm assigns new labels when it encounters an occupied site with no occupied neighbors already inspected. If an occupied site has exactly one labeled occupied neighbor among those already processed, it copies that neighbor’s label. This produces a provisional label field where nearby connected regions initially share labels but may still be split due to the one-pass constraint.
10.3 Demonstrating equivalence merges and final label resolution
Suppose a later occupied site bridges two previously labeled regions. When the site is processed, it finds multiple occupied neighbors with different provisional labels. The algorithm assigns one label for the current site and performs unions between the other labels’ disjoint-set nodes. In the second pass, both provisional labels map to a single representative, and the provisional split is eliminated.
10.4 Interpreting the resulting cluster map
After canonical relabeling, all sites belonging to the same connected component share the same final label. The cluster map can then be read as a segmentation of the occupied set into connected clusters, enabling direct counting, size distribution generation, or spanning checks.