Percolation theory
p
and can be empty with the probability 1 – ''p''
. Each group of neighboring occupied cells forms a cluster. Neighbors are defined as cells having a common side but not those sharing only a corner i.e. we consider the Hoshen–Kopelman algorithm for cluster finding
In this algorithm, we scan through a grid looking for occupied cells and labeling them with cluster labels. The scanning process is called aUnion-find algorithm
This algorithm is a simple method for computing equivalence classes. Calling the functionunion(x,y)
returns whether items x
and y
are members of the same equivalence class. Because equivalence relations are transitive, all the items equivalent to x
are equivalent to all the items equivalent to y
. Thus for any item x
, there is a set of items which are all equivalent to x
(called the equivalence class). A second function find(x)
returns a representative member of the equivalence class to which x
belongs.
Pseudocode
During theunion
operation is performed, to specify that these neighboring cells are in fact members of the same equivalence class. Then thefind
operation is performed to find a representative member of that equivalence class with which the current cell will be labeled.
On the other hand, if the current cell has no neighbors, it is assigned a new, previously unused, label. The entire grid is processed in this way.
Following pseudocode is referred froExample
Consider the following example. The dark cells in the grid infigure (a)
represent that they are occupied and the white ones are empty. So by running H–K algorithm on this input we would get the output as shown in figure (b)
with all the clusters labeled.
The algorithm processes the input grid, cell by cell, as follows: Let's say that grid is a two-dimensional array.
* Starting from cell grid 0]
i.e. the first cell. The cell is occupied and it doesn't have cells to the left or above so we will label this cell with a new label say 1
.
* grid 1]
and grid 2]
both are unoccupied so they are not labeled.
* grid 3]
is occupied so check cell to the left which is unoccupied so we increment the current label value and assign the label to the cell as 2
.
* grid 4]
, grid 5]
and grid 0]
are unoccupied so they are not labeled.
* grid 1]
is occupied so check cell to the left and above, both the cells are unoccupied so assign a new label 3
.
* grid 2]
is occupied so check cell to the left and above, only the cell to the left is occupied so assign the label of a cell on the left to this cell 3
.
* grid 3]
is occupied so check cell to the left and above, both the cells are occupied, so merge the two clusters and assign the cluster label of the cell above to the cell on the left and to this cell i.e. 2
. (Merging using union algorithm will label all the cells with label 3
to 2
)
* grid 4]
is occupied so check cell to the left and above, only the cell to the left is occupied so assign the label of a cell on the left to this cell 2
.
* grid 5]
, grid 0]
and grid 1]
are unoccupied so they are not labeled.
* grid 2]
is occupied so check cell to the left and above, only cell above is occupied so assign the label of the cell above to this cell 2
.
* grid 3]
, grid 4]
and grid 5]
are unoccupied so they are not labeled.
* grid 0]
is occupied so check cell above which is unoccupied so we increment the current label value and assign the label to the cell as 4
.
* grid 1]
is occupied so check cell to the left and above, only the cell to the left is occupied so assign the label of the cell on the left to this cell 4
.
* grid 2]
is unoccupied so it is not labeled.
* grid 3]
is occupied so check cell to the left and above, both the cells are unoccupied so assign a new label 5
.
* grid 4]
is occupied so check cell to the left and above, only the cell to the left is occupied so assign the label of the cell on the left to this cell 5
.
* grid 5]
, grid 0]
and grid 1]
are unoccupied so they are not labeled.
* grid 2]
is occupied so check cell to the left and above, both the cells are unoccupied so assign a new label 6
.
* grid 3]
is occupied so check cell to the left and above, both, cell to the left and above are occupied so merge the two clusters and assign the cluster label of the cell above to the cell on the left and to this cell i.e. 5
. (Merging using union algorithm will label all the cells with label 6
to 5
).
* grid 4]
is unoccupied so it is not labeled.
* grid 5]
is occupied so check cell to the left and above, both the cells are unoccupied so assign a new label 7
.
* grid 0]
, grid 1]
, grid 2]
and grid 3]
are unoccupied so they are not labeled.
* grid 4]
is occupied so check cell to the left and above, both the cells are unoccupied so assign a new label 8
.
* grid 5]
is occupied so check cell to the left and above, both, cell to the left and above are occupied so merge the two clusters and assign the cluster label of the cell above to the cell on the left and to this cell i.e. 7
. (Merging using union algorithm will label all the cells with label 8
to 7
).
Applications
* Determination of Nodal Domain Area and Nodal Line Lengths * Connectivity (graph theory), Nodal Connectivity Information * Modeling ofSee also
* K-means clustering algorithm * Fuzzy clustering algorithm * Gaussian (References
{{DEFAULTSORT:Hoshen-Kopelman algorithm Cluster analysis algorithms