CS 190C, Spring 2008: Project 2

Computational Experiments on Percolation in Grids

Posted: February 15, 2008

Due dates:

  • Part 1: Friday, February 22, 10pm
  • Part 2: Friday, February 29, 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

Note that in the second and third example stated above, an n×n×n grid modeling the width, height, and depth would be used. Percolation now happens if there exists an open site on the top surface connected to an open site on the bottom surface.

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 design algorithms for three forms of flow through a 2-d grid and to experimentally determine for each type of flow the probability at which a grid percolates.

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 function for exploring the grid, 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 (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): returns a grid of dimensions size × size in which every grid location is initialized to fill
  • visualize(flow_grid, input_grid): visualizes the flow through a grid using VPython
  • Graphing the function f(p) = 1–(1-p^n)^n using MatPlotLib. Function f(p) represents the mathematical solution of vertical percolation.

The 2-dimensional grid will be represented as a list of lists with [0],[0] the upper left-most position of the grid (as done in Problem Set 2). 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.

Part 1: Detecting Percolation

You will design and implement three functions testing for different forms of percolation. In all three forms, the flow from one grid cell to the next cell can go only to cells that are either horizontally or vertically adjacent. The first two types of percolation place a limitation on the flow.

  • vertical_percolation(input_grid, trace=False): returns a grid flow_grid and a boolean does_percolate. Grid input_grid vertically percolates if there exists a column consisting of all 0's (i.e., not blocked) values.
  • monotone_percolation(input_grid, trace=False): returns a grid flow_grid and a boolean does_percolate. Grid input_grid monotonically percolates if there exists a path consisting of all 0's in which the row coordinate never decreases. Hence, from input_grid[i][j] the path can continue at [i+1][j], [i-1][j], or [i,j+1]. Monotone percolation models, for example, liquids that cannot flow up.
  • unrestricted_percolation(input_grid, trace=False): returns a grid flow_grid and a boolean does_percolate. Grid input_grid percolates if there exists a path of horizontally or vertically adjacent 0's from any location in the top row to any location in the bottom row.

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. To use the provided visualization modules, grid flow_grid needs to contain * and 1 values. More specifically, flow_grid[i][j] = 1 if no flow has yet reached location [i][j] and it is * if a flow has already filled location [i][j]. Hence, grid flow_grid is initialized to 1 and its final state will record all 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 with unrestricted percolation, 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

Vertical percolation is easier to detect than the other two types of percolation. You already wrote a function to detect vertical percolation, but you probably have to update it and add creating grid flow_grid. Monotone and unrestricted percolation should be detected using recursion. It is possible to write a non-recursive module for percolation by passing over the n x n grid n^2 times, but this quickly becomes untenable for even moderate n.

For the recursive exploration of grid input_grid, start with the following idea: a function, say explore, is called with row i and column j. You may want to make grids input_grid and flow_grid parameters of function explore. 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 needs to back up 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 could stop. Note that if you want to visualize all flows and not just the first one found, let all recursive calls terminate.

When designing the percolation functions, think how to reuse code and how to avoid writing functions having almost identical sections of code. Some of you will realize that all three forms of percolation can be handled in one explore function by making a list of allowable neighbors for each type of percolation a parameter. Test each form of percolation carefully and make sure to visualize the detected flow using function visualize provided.

Remember not to put a main function in your library. Here is an example of how the functions should be called in a possible testing function.

if __name__ == "__main__":
    input_grid = random_grid(50, 0.5)
 
    # Run vertical percolation
    flow_grid, vert_percolates = vertical_percolation(input_grid)
    visualize(flow_grid, input_grid)
 
    # Run monotone percolation
    flow_grid, mono_percolates = monotone_percolation(input_grid)
    visualize(flow_grid, input_grid)
 
    # Run unrestricted percolation
    flow_grid, unrest_percolates = unrestricted_percolation(input_grid)
    visualize(flow_grid, input_grid)

Part 1 of the project consists of writing the three functions. Place these functions into file my_percolation_functions.py. Provided functions you may use are in file percolation_provided.py. Your submission needs to consist of one folder containing both files you are using (including the functions provided by us).

Part 2: Running Experiments

Part 2 of the project focuses on 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. Each type of flow will have a different percolation probability and you should consider each one of the three forms of percolation.

Setup

A 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, for every type of percolation, 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. We point out that it would be helpful if there were a formula allowing us to plot this function. However, with the exception of vertical percolation, such formulas don’t exist.

Questions to be answered

For studying the three types of percolation, use a grid size of n=25. Then, experimentally determine the percolation probability for each of the three forms of percolation flow. Remember that you need to decide how many values of p to consider and how may experiments to run for each value of p. For each percolation, plot the graph. You can use Matplotlib or VPython and you should decide whether to show the three curves in one plot or in three separate ones. Place all code generating these plots into a file experiment_n_fixed.py (this file needs to import all files and libraries you use).

In addition to the graphs, you need to:

  • Discuss how you decided on the number of trials used and the probabilities p considered.
  • Discuss any differences or similarities of the graphs for the three forms of percolation.
  • For vertical percolation, compare results with known analytical bounds. Do the percolation probabilities differ?

Next, consider only unrestricted percolation and study the impact of the grid size on the percolation probability. Run the experiment for grid sizes n = 10, 25, and 50. One way to visualize the performance is to make the same curves as above and show them 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.

Note: While real applications have significantly larger grid sizes, generating the plot for n=50 may exceed default values Python uses. To increase the setrecursionlimit from the default value 1000 use:

from sys import setrecursionlimit
setrecursionlimit(2000)

Submission Instructions

When you submit your code, you must 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.

Extra Credit Options

After having completed both part 1 and part 2, you can consider one of the two extra credit options.

Extension 1: The flow models considered allow vertical and horizontal flow. Other types of flows arise in applications. A related flow model allows, in addition to horizontal and vertical flow, a flow to a diagonal neighbor. Hence, from position [i][j], flow can reach positions [i±1][j±1]. Write a function diagonal_unrestricted_percolation(input_grid, trace=False) and use it to create the percolation probability plot for diagonal flow for n=25. Discuss its similarities and differences to horizontal unrestricted flow.

Extension 2: Numerous applications require modeling flow in three dimensions. Consider 3-D percolation using monotone percolation (the z-coordinate cannot decrease) and not allowing diagonal flow.

  • Write a function 3D_restricted_percolation(input_grid) and use it to create the percolation probability plot for n=25.
  • Write a function visualize_3D to effectively visualize the resulting flow. The visualization requires some effort and you will have to make a number of decision on how to use VPython and the representation of the flow in VPython.
 
cs190c/project2.txt · Last modified: 2009/02/16 12:56 by seh
 
Recent changes RSS feed Creative Commons License Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki