next up previous
Next: Temporary Label Determination Up: Hoshen-Kopelman Algorithm Previous: Implementing the Hoshen-Kopelman

1.5 Finite State Machine Implementation

The objective of the Hoshen-Kopelman finite state machine (FSM) implementation is to reduce the number of integer comparison operations thus reducing the overall cluster identification time for a particular map. Particular emphasis is given to the integer comparison operations found in the temporary label determination and the cluster-merge functions of the algorithm. The objective is reached by encapsulating the label value and cluster membership status of the west neighbor in a state of the FSM and by compressing the recursive pointer path in the csize array formed during the merge-cluster function of the algorithm implementation. Table 2 details the information encapsulated in each state of the Hoshen-Kopelman finite state machine.

Table 2: Cluster information encapsulated by each state of the FSM.

Michael W. Berry (
Sat Mar 30 23:40:13 EST 1996