Breadth-first Search Algorithm for Percolation Cluster Generation

0. Decide on a fixed local search order around a site. Initialize all variables.

1. Occupy the starting point and put this site on the stack. Set both the lower pointer m1 (for the site whose neighbors are being checked) and the upper pointer m2 (for the top site on the stack) to 1.

2. Search all neighbors of site m1 by first testing if the neighbor is already on the stack. • If yes, go to the next neighbor and continue searching.

• If not, check if any of the limits has been reached.

– If limits have been reached, then growth must be stopped. Exit.

– If not, check if this neighbor has been chosen empty already. ∗ If yes, go to the next neighbor.

∗ If not, get a random number to decide whether to occupy this site. Mark it as occupied, put it on the stack, and advance m2 ⟹ m2 + 1, if appropriate. Otherwise mark it empty and go to the next neighbor.

3. Test if the two stack pointers coincide (m1 = m2).

• If yes, the cluster is finished. Exit either with or without success depending on the success criteria.

• If no, increment m1 ⟹ m1 + 1 and repeat 2.