Percolation/Bond percolation

Percolation/Bond percolation is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Percolation Simulation
This is a simulation of aspects of mathematical percolation theory.

For other percolation simulations, see Category:Percolation Simulations, or:
1D finite grid simulation
Mean run density
2D finite grid simulations
Site percolation | Bond percolation | Mean cluster density

Given an $M\times N$ rectangular array of cells numbered $\mathrm {cell} [0..M-1,0..N-1]$assume $M$ is horizontal and $N$ is downwards. Each $\mathrm {cell} [m,n]$ is bounded by (horizontal) walls $\mathrm {hwall} [m,n]$ and $\mathrm {hwall} [m+1,n]$; (vertical) walls $\mathrm {vwall} [m,n]$ and $\mathrm {vwall} [m,n+1]$

Assume that the probability of any wall being present is a constant $p$ where

$0.0\leq p\leq 1.0$

Except for the outer horizontal walls at $m=0$ and $m=M$ which are always present.

The task

Simulate pouring a fluid onto the top surface ($n=0$) where the fluid will enter any empty cell it is adjacent to if there is no wall between where it currently is and the cell on the other side of the (missing) wall.

The fluid does not move beyond the horizontal constraints of the grid.

The fluid may move “up” within the confines of the grid of cells. If the fluid reaches a bottom cell that has a missing bottom wall then the fluid can be said to 'drip' out the bottom at that point.

Given $p$ repeat the percolation $t$ times to estimate the proportion of times that the fluid can percolate to the bottom for any given $p$.

Show how the probability of percolating through the random grid changes with $p$ going from $0.0$ to $1.0$ in $0.1$ increments and with the number of repetitions to estimate the fraction at any given $p$ as $t=100$.

Use an $M=10,N=10$ grid of cells for all cases.

Optionally depict fluid successfully percolating through a grid graphically.

Show all output on this page.

See

• Percolation theory
• Percolation/Site percolation

Python

<lang python>from collections import namedtuple from random import random from pprint import pprint as pp

Grid = namedtuple('Grid', 'cell, hwall, vwall')

M, N, t = 10, 10, 100

class PercolatedException(Exception): pass

HVF = [(' .', ' _'), (':', '|'), (' ', '#')] # Horiz, vert, fill chars

def newgrid(p):

   hwall = [[int(random() < p) for m in range(M)] 
            for n in range(N+1)]
   vwall = [[(1 if m in (0, M) else int(random() < p)) for m in range(M+1)] 
            for n in range(N)]
   cell = [[0 for m in range(M)] 
            for n in range(N)]
   return Grid(cell, hwall, vwall)

def pgrid(grid, percolated=None):

   cell, hwall, vwall = grid
   h, v, f = HVF
   for n in range(N):
       print('    ' + .join(h[hwall[n][m]] for m in range(M)))
       print('%i)  ' % (n % 10) + .join(v[vwall[n][m]] + f[cell[n][m] if m < M else 0]
                                         for m in range(M+1))[:-1])
   n = N
   print('    ' + .join(h[hwall[n][m]] for m in range(M)))
   if percolated: 
       where = percolated.args[0][0]
       print('!)  ' + '  ' * where + ' ' + f[1])
   

def pour_on_top(grid):

   cell, hwall, vwall = grid
   n = 0
   try:
       for m in range(M):
           if not hwall[n][m]:
               flood_fill(m, n, cell, hwall, vwall)
   except PercolatedException as ex:
       return ex
   return None
       

def flood_fill(m, n, cell, hwall, vwall):

   # fill cell 
   cell[n][m] = 1
   # bottom
   if n < N - 1 and not hwall[n + 1][m] and not cell[n+1][m]:
       flood_fill(m, n+1, cell, hwall, vwall)
   # THE bottom
   elif n == N - 1 and not hwall[n + 1][m]:
       raise PercolatedException((m, n+1))
   # left
   if m and not vwall[n][m] and not cell[n][m - 1]:
       flood_fill(m-1, n, cell, hwall, vwall)
   # right
   if m < M - 1 and not vwall[n][m + 1] and not cell[n][m + 1]:
       flood_fill(m+1, n, cell, hwall, vwall)
   # top
   if n and not hwall[n][m] and not cell[n-1][m]:
       flood_fill(m, n-1, cell, hwall, vwall)

if __name__ == '__main__':

   sample_printed = False
   pcount = {}
   for p10 in range(11):
       p = (10 - p10) / 10.0    # count down so sample print is interesting
       pcount[p] = 0
       for tries in range(t):
           grid = newgrid(p)
           percolated = pour_on_top(grid)
           if percolated:
               pcount[p] += 1
               if not sample_printed:
                   print('\nSample percolating %i x %i grid' % (M, N))
                   pgrid(grid, percolated)
                   sample_printed = True
   print('\n p: Fraction of %i tries that percolate through' % t )
   
   pp({p:c/float(t) for p, c in pcount.items()})</lang>

Output:

In the Ascii art, cells are either a space of a hash and are surrounded by either '_', '|' for intact walls and '.' and ':' for missing (leaky) walls.

The bottom-most line starting '!)' shows where the fluid can drip out from. (The percolation stops when one route through the bottom is found).

Sample percolating 10 x 10 grid
     _ _ . _ . _ _ . _ _
0)  | |#:#:#|#| | :#| | |
     _ _ . _ _ _ . . _ _
1)  | | |#:#| | | |#| : |
     _ _ _ . _ . . . . _
2)  | | |#:#| : | |#: | |
     _ _ _ _ . . _ . . .
3)  | : : | | | : |#: | |
     _ _ . _ . . _ . _ _
4)  | : : : | | | |#: : |
     _ _ _ . _ _ _ . . _
5)  | : | | : | | :#| | |
     _ _ . . _ _ _ . _ .
6)  | : | | : | |#:#:#| |
     _ . _ _ . _ _ _ . .
7)  | : | : | : | | |#: |
     _ _ _ . . _ _ . . _
8)  | | : | | | |#:#:#: |
     _ _ _ . . . . _ _ .
9)  | : : | : : :#: | : |
     . _ . _ . . . . _ _
!)               #

 p: Fraction of 100 tries that percolate through
{0.0: 1.0,
 0.1: 1.0,
 0.2: 1.0,
 0.3: 1.0,
 0.4: 0.9,
 0.5: 0.47,
 0.6: 0.06,
 0.7: 0.0,
 0.8: 0.0,
 0.9: 0.0,
 1.0: 0.0}

Note the abrupt cut-off in percolation at around p = 0.5 which is to be expected.