Percolation/Site percolation
Given an rectangular array of cells numbered assume is horizontal and is downwards.
Assume that the probability of any cell being filled is a constant where
- The task
Simulate creating the array of cells with probability and then testing if there is a route through adjacent filled cells from any on row to any on row cell, i.e. testing for site percolation.
Given repeat the percolation times to estimate the proportion of times that the fluid can percolate to the bottom for any given .
Show how the probability of percolating through the random grid changes with going from to in increments and with the number of repetitions to estimate the fraction at any given as .
Use an grid of cells for all cases.
Optionally depict a successfull percolation path through a cell grid graphically.
Show all output on this page.
- See
Python
<lang python>from random import random import string from pprint import pprint as pp
M, N, t = 15, 15, 100
cell2char = ' #' + string.ascii_letters NOT_VISITED = 1 # filled cell not walked
class PercolatedException(Exception): pass
def newgrid(p):
return [[int(random() < p) for m in range(M)] for n in range(N)] # cell
def pgrid(cell, percolated=None):
for n in range(N): print( '%i) ' % (n % 10) + ' '.join(cell2char[cell[n][m]] for m in range(M))) if percolated: where = percolated.args[0][0] print('!) ' + ' ' * where + cell2char[cell[n][where]])
def check_from_top(cell):
n, walk_index = 0, 1 try: for m in range(M): if cell[n][m] == NOT_VISITED: walk_index += 1 walk_maze(m, n, cell, walk_index) except PercolatedException as ex: return ex return None
def walk_maze(m, n, cell, indx):
# fill cell cell[n][m] = indx # down if n < N - 1 and cell[n+1][m] == NOT_VISITED: walk_maze(m, n+1, cell, indx) # THE bottom elif n == N - 1: raise PercolatedException((m, indx)) # left if m and cell[n][m - 1] == NOT_VISITED: walk_maze(m-1, n, cell, indx) # right if m < M - 1 and cell[n][m + 1] == NOT_VISITED: walk_maze(m+1, n, cell, indx) # up if n and cell[n-1][m] == NOT_VISITED: walk_maze(m, n-1, cell, indx)
if __name__ == '__main__':
sample_printed = False pcount = {} for p10 in range(11): p = p10 / 10.0 pcount[p] = 0 for tries in range(t): cell = newgrid(p) percolated = check_from_top(cell) if percolated: pcount[p] += 1 if not sample_printed: print('\nSample percolating %i x %i, p = %5.2f grid\n' % (M, N, p)) pgrid(cell, percolated) sample_printed = True print('\n p: Fraction of %i tries that percolate through\n' % t ) pp({p:c/float(t) for p, c in pcount.items()})</lang>
- Output:
The Ascii art grid of cells has blanks for cells that were not filled. Filled cells start off as the '#', hash character and are changed to a succession of printable characters by successive tries to navigate from the top, (top - left actually), filled cell to the bottom.
The '!)' row shows where the percolation finished and you can follow the letter backwards from that row, (letter 'c' in this case), to get the route. The program stops after finding its first route through.
Sample percolating 15 x 15, p = 0.40 grid 0) a a a b c # 1) a a # c c # # 2) # # # # c # # # 3) # # # # # c 4) # # c c c c c c 5) # # # # # # c c c 6) # # # c c c 7) # # # # # # # c 8) # # # # # c c c 9) # # # c 0) # # # # # # c c # # 1) # # # # c 2) # # # # # # c c c c 3) # # # # c c c c 4) # # c # !) c p: Fraction of 100 tries that percolate through {0.0: 0.0, 0.1: 0.0, 0.2: 0.0, 0.3: 0.0, 0.4: 0.01, 0.5: 0.11, 0.6: 0.59, 0.7: 0.94, 0.8: 1.0, 0.9: 1.0, 1.0: 1.0}
Note the abrupt change in percolation at around p = 0.6. These abrupt changes are expected.