CS 190C, Spring 2009: Project 2

Percolation in Grids

Posted: Thursday, February 26, 2009

Due dates:

  • Part 1: Friday, March 6, 10pm
  • Part 2: Friday, March 13, 10pm

Introduction

  • Imagine a landscape filled with patches of dry grass. A fire has started at one end and it jumps from one patch to another. What is the probability that the fire manages to cross the entire area?
  • Imagine a system composed of randomly distributed insulating and metallic materials. What is the probability that the system is an electric conductor?
  • Imagine a porous landscape with water on the surface. What is the probability that the water will be able to drain to the bottom?

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).

Does percolate Does not percolate
Does percolate Does not percolate

The question scientists ask is “What is the smallest probability q at which a grid generated with probability q will percolate?”

Objectives

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.

Getting Started

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:

  • printgrid(grid): prints the grid represented by the nested list, one row per line (this module may be helpful in testing and debugging your code)
  • readgrid(filename): opens the file filename and returns the contents as a list of list (also helpful in testing and debugging your code)
  • grid(size,fill=0): returns a grid of dimensions size × size in which every grid location is initialized to fill. The default fill value is 0.
  • visualize(flow_grid, input_grid): visualizes the flow through a grid using VPython

The 2-dimensional grid will be represented as a list of lists with [0][0] 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:

  • Generate a uniformly distributed random number between 0 and 1.
  • If the random number is less than p, set input_grid[i][j] to 0, otherwise it is set to 1.

Function random_grid(size, p) written in Lab 6 generates such a grid (it is also included in the provided file).

Detecting Percolation

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]]
Example of percolation
input_gridflow_grid

Wave Exploration of the Grid

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.

Example of wavefront percolation

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 generate_nextwave are

  1. input_grid: input_grid[i][j] is 1 if position [i][j] is blocked.
  2. flow_grid: 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.
  3. last_wave: a list of (row, col) pairs indicating the grid positions that were in the last wave.

Function generate_nextwave returns the next wave that contains all positions that

  • are adjacent to at least one position in last_wave
  • are not blocked
  • and have not been visited.

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).

Recursive Exploration of the Grid

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 percolation_recursive and 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.

General comments about the functions

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: Using the Wave Percolation Function for Determining the Percolation Probability

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:

  • How many trials are needed to make a prediction on whether a grid generated with probability p percolates?
  • How many different values of p should be considered to determine the percolation probability q?

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: Comparing the Performance of two Percolation Functions

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:

  • set n=75
  • consider values of p from 0 to 1 in increments of 0.05 (or smaller)
  • for each value of p, generate 10 random grids and record for each algorithm the average running time on the ten grids

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.

Note:

  • We encourage you to use your wave propagation function in the performance comparison. If your code did not work correctly or some other problems arise, you can use the posted wave solution.
  • While real applications have significantly larger grid sizes, generating the plot for n=75 may exceed default values Python uses. To increase the setrecursionlimit from the default value use:
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?

Reminder

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.

 
cs190c/project2_09.txt · Last modified: 2009/03/13 11:36 by lstuart
 
Recent changes RSS feed Creative Commons License Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki