Posted: Thursday, February 26, 2009
All three problems can be modeled by a process called percolation. In its simplest form, percolation is modeled by an n×n grid containing blocked and open sites and the probability that a site is open is p. We say the grid percolates if there exists a sequence of open sites connecting an open site on the top row of the grid with an open site on the bottom row of the grid. The figure below shows two 2-dimensional grids generated with probability p=0.42. The left one percolates and the right one does not (light gray indicates a blocked site, blue/darkest shade indicates open sites that can be reached from the top row).
The question scientists ask is “What is the smallest probability q at which a grid generated with probability q will percolate?”
The majority of percolation problems have no mathematical solution and thus percolation is a natural problem for computational experimentation. The objective of this project is to write two function implementing two conceptually different algorithms for flow through a 2-d grid and to experimentally determine the probability at which a grid percolates. You will also compare the running time of the two functions.
The project uses a significant portion of the material covered already as described in the next section. You will (i) use nested lists to represent and manipulate 2-dimensional grids, (ii) write a recursive and a non-recursive function for exploring the grid to detect percolation, and (iii) experience the benefit of writing small and reusable modules and developing code incrementally.
You have already written a number of functions useful for this project. Note that you can use your solutions or the ones we provide (in file (percolation_provided.py). You will be making use of the following:
The 2-dimensional grid will be represented as a list of lists with  representing the upper left-most position of the grid. Assume input_grid is the grid to be checked for percolation. A location represented in grid input_grid is set to 0 if the corresponding site is open, permitting flow, and it is set to 1 if the site is blocked. For a given probability p, the grid is generated by performing the following for each location [i][j], where i is the row and j is the column:
Function random_grid(size, p) written in Lab 6 generates such a grid (it is also included in the provided file).
A grid percolates if there is a flow from a grid cell in the first row of the grid to a grid cell in the last row of the grid and all cells on the path created by the flow are either horizontally or vertically adjacent. For a grid cell at [i][j], the four adjacent cells are [i-1][j], [i+1][j], [i][j-1], [i][j+1], assuming they exist. Note that different definition of percolation exist in the literature, many motivated by specific applications.
You will write two functions, percolation_wave(input_grid, trace=False) and percolation_recursive(input_grid, trace=False). Each function returns a grid flow_grid and a boolean does_percolate. If trace is True, you should call visualize(flow_grid, input_grid) each time the flow_grid changes.
The percolation functions should not change grid input_grid; input_grid should always represent the initial grid generated with probability p. Use a second grid, grid flow_grid, to represent the flow. The values grid flow_grid contains will vary depending on the percolation function. For both, flow_grid[i][j] = -1 if no flow has yet reached location [i][j]. Hence, grid flow_grid is initialized to -1 and its final state will record locations that can be reached by a flow starting in the first row. The figure below shows a grid input_grid, the corresponding grid flow_grid (where flow is indicated by the symbol “*”) , and a visualization using three colors (blue/darkest shade represents the flow).
[[0 1 1 1 0 1 1 0 1 0] [0 0 1 0 1 1 0 1 0 1] [0 0 0 0 0 0 0 0 0 0] [1 0 0 0 0 1 0 0 1 0] [0 1 0 1 0 0 0 0 0 0] [1 0 0 0 0 0 0 1 1 0] [0 1 1 0 0 0 1 0 0 0] [1 1 1 0 0 0 0 0 0 0] [0 0 0 1 1 0 0 0 1 1] [0 0 0 0 0 1 1 0 0 1]]
[[ * -1 -1 -1 * -1 -1 * -1 *] [ * * -1 * -1 -1 * -1 * -1] [ * * * * * * * * * *] [-1 * * * * -1 * * -1 *] [-1 -1 * -1 * * * * * *] [-1 * * * * * * -1 -1 *] [-1 -1 -1 * * * -1 * * *] [-1 -1 -1 * * * * * * *] [-1 -1 -1 -1 -1 * * * -1 -1] [-1 -1 -1 -1 -1 -1 -1 * * -1]]
Function percolation_wave(input_grid, trace=False) detects percolation using the idea of expanding wavefronts. This process is illustrated in the figure below. The first wave consists of all the open positions in the top row of the grid. For the shown example, the first wave contains the three open grid locations labeled '0'. The second wave consists of all positions not in the first wave and that can be reached in one step from a position in the first wave. In general, the k-th wave is generated using the (k-1)-st wave and it contains positions not reached earlier. Waves are numbered starting from zero. Note that if a position appears in wave k, there is a path of length k to this position from a location in the top row. (Actually, the path contains k+1 grid locations.) Hence, the wave algorithm can be used to not only detect whether the grid percolates, but it also finds a shortest percolation path.
In your implementation, let function
percolation_wave use the grid
flow_grid to record the positions reached by the waves (its entries are initialized to -1) and use a list
last_wave to record the last wave generated. Note that once a new wave has been determined, the positions reached by last_wave are recorded in the grid visualized. Use a function
generate_nextwave to generate the next wave. The parameters of function
input_grid[i][j]is 1 if position [i][j] is blocked.
flow_grid[i][j]is -1 if position [i][j] has not been visited by a wave; it contains the value k if the k-th wave reached it.
last_wave: a list of (row, col) pairs indicating the grid positions that were in the last wave.
generate_nextwave returns the next wave that contains all positions that
The function terminates when an open position in the last row is reached by a wave (the grid percolates) or no more grid locations can be explored (the grid does not percolate).
Note: In your implementation, the lists representing waves should not contain duplicate entries. Allowing duplicate entries can result in very slow code (too slow for an effective experimental part).
The recursive exploration of a grid uses the following idea: a path through the grid is followed exploring new locations and following the most recently discovered location, as long as there still exists the possibility of detecting percolation. Once it is detected that the path pursued leads to a dead end, it backtracks and pursues the most recent branch it did not yet take. This is in some sense, this approach is the opposite of the wave exploration approach which works its way through the entire grid, wave by wave. Recursion will handle the concept of backtracking for you.
To implement percolation_recursive, use a function
explore which has as parameters a row i and column j, as well as grids input_grid and flow_grid. Assume a cell adjacent to [i][j] can be reached by flow (or that i is the first row), input_grid[i][j]=0 and flow_grid[i][j]=-1. This means no flow has reached location [i][j], the location is not blocked, and flow from the adjacent location can reach it. We record that the flow reaches location [i][j] by setting flow_grid[i][j]=*. Then, function
explore considers the neighbors of [i][j] it can flow to, one at a time. For each such neighbor,
explore makes a recursive call with the position of the neighbor as the row and column index. Realize that after this recursive call is made, the initial conditions of explore stated above hold.
The recursive nature of function
explore explores paths in the grid allowing flow until it reaches a “dead end” or until it reaches the last row. Once a flow reaches the last row, a flow resulting in percolation has been found and the computation stops. When a dead end is reached, no more recursive calls are made and the recursion returns to where it was called from (recursion handles the backtracking for you).
The initial call to function
explore will be made by
explore will make future recursive calls. Function
percolation_recursive will make more calls to
explore if there are free locations in the first row
explore cannot reach. Function
percolation_recursive will return the correct parameters when
explore has completed its work.
When designing the percolation functions, consider how to reuse code and what code segments should be placed into a function. Test each function carefully and make sure to visualize the detected flow using function visualize provided. Here is an example of how the functions should be called in a possible testing function.
if __name__ == "__main__": # a format you may want to use for testing input_grid = random_grid(50, 0.5) # Run percolation using wave algorithm flow_grid, percolates_wave = percolation_wave(input_grid) visualize(flow_grid, input_grid) # Run percolation using recursive algorithm flow_grid, percolates_rec = percolation_recursive(input_grid) visualize(flow_grid, input_grid) # the flow_grids generated may look different, # but correct functions will produce the same Boolean value
Part 1 of the project consists of writing the function
percolation_wave and running experiments to computationally determine the smallest probability q at which a grid generated with probability q percolates. We call this the percolation probability q.
First write and test function
percolation_wave. To computationally determine the percolation probability, use the following setup.
One trial consist of determining whether one grid percolates. Consider the following questions:
For p=1, the grid will always percolate (there are no blocked locations) and for p=0 the grid will never percolate (all locations are blocked). Intuitively, for values of p close to 1, one expects that the majority of the trials will report percolation and for values of p close to 0 one expects very few percolations.
The goal is to generate a plot whose x-coordinate represents values of p (from 0 to 1) and whose y-coordinate represents q (also from 0 to 1). From the shape of the plot, you will make a prediction of the percolation probability.
Every point in the plot is obtained by running a number of trials. For a certain probability p, assume we are making t trials and s of the t randomly generated grids allow percolation. We set q = s/t and (p,q) is a point in the plot. It would be helpful if there were a formula allowing us to plot this function. However, such a formula does not exist.
Experimentally determine the percolation probability for a grid of size n=25. Remember that you need to decide how many values of p to consider and how many experiments to run for each value of p (you should set this quantity t to at leats 10). Plot the graph using Matplotlib or VPython. Place all code generating the plot into a file experiment_n_fixed.py (this file needs to import all files and libraries you use). In addition to the graph, discuss how you decided on the number of trials used and the probabilities p considered. State the observed percolation probability.
Next, consider grid sizes n = 10, 25, 50, and 75 and determine the percolation probabilities (you already know it for n=25). One way to visualize the performance for the different values of n is to make the same curve as above and show all three in one plot. Discuss how the size of the grid seems to impact the percolation probability and the shape of the curves. Place all code generating the curves into file experiment_n_varies.py.
Submit a folder containing percolation_wave.py, experiment_n_fixed.py, experiment_n_varies.py, percolation_provided.py, and a text file discussing your results.
Part 2 of the project consists of writing function
percolation_recursive and comparing the running times of the two percolation functions. Before starting to write
percolation_recursive, read the description given earlier carefully. Realize that the recursion happens in function
explore and that
percolation_recursive makes the initial call to
explore (it may make more than one call to explore).
Use the following framework to compare the running times of one execution of the two functions.
import time n = ... p = ... input_grid = random_grid(n, p): t = time.clock() flow_grid, percolates_wave = percolation_wave(input_grid, trace=False) time_wave = time.clock()-t t = time.clock() flow_grid, percolates_wave = percolation_recursive(input_grid, trace=False). time_recur = time.clock()-t
Make sure both functions are operating the same way (both terminate when percolation is first detected, or both detect all percolation paths). Your comparison should report performance on the following scenario:
This experimental setup produces two lists (or arrays), each containing 20 values (or more for smaller increments). Plot the performance results in an interesting and effectve way and give a brief discussion of your interpretation.
from sys import setrecursionlimit setrecursionlimit(30000)
Place the recursive function detecting percolation into file my_percolation_recursive.py. Your performance comparisons should be in a file named my_performace_results.py. Your submission for Part 2 needs to contain these two programs, the wave propagation function, the provided functions file, and a discussion of your performance results. Can you make a conclusion on which approach is more efficient?
When you submit your code, always submit all files used by your solutions. This means that if you are using code we provide to the class, you need to submit this code whether you changed it or not. Your project will be run and tested only with the code submitted. Instruction on files names are given above. We will grade both the quality of your code as well as the quality of your experimental study, including the associated write-up answering the given questions.