Percolation Programming Project

Experimenting With Percolation

Nathan Sprague
Kalamazoo College

 


Motivation

Our graphical percolation program is great for visualizing the percolation process. However in its current form it is not ideal for running experiments. Imagine we want to answer the following question:

"What is the probability that a gas will percolate from the top row to the bottom row in a 100x100 grid, given that each cell has a 30% chance of being blocked?"
Your first instinct might be to start the program, create an appropriate grid, and click run. What would you be able to conclude from the result? Not much. The fact that the material reached the bottom (or didn't) tells us very little about what will happen the next time we run the experiment. In order to obtain a meaningful answer, we need to run the experiment many times and average the results. If we run this experiment 1,000 times, and the material percolates 234 times, we can be confident that the probability of percolation for these conditions is somewhere around 23%.

Clicking the run button 1,000 times is not an attractive option. Running these experiments by hand will be even less attractive if we want to systematically explore the effects of changing the probability that cells are blocked. Generating a figure like this:



involves running 100 experiments for 21 different conditions. That's 2,100 clicks of the run button. If we want to run 1,000 experiments for each condition we end up with 21,000 clicks.

The purpose of this project is to modify the Percolation program to automate the process of obtaining results like those described above, and then to use the updated program to obtain some experimental results.

Updating the GUI

Up until now, we have placed the initial percolators by hand using the "Manually Populate Grid" button. For the purposes of experimentation we want this process to be automated. At the beginning of each experiment the entire grid should be randomly populated with solid cells, and each empty cell in the top row should be populated with the appropriate type of percolator. There is code in place to handle this.

The first step is to uncomment several lines in PercolationApp. Somewhere around line 87 you should see the following statement:

        Class[] percTypes = {
//                              VerticalPercolator.class,
//                              GravitationalPercolator.class,
//                              AllDirectionPercolator.class
                            };
Remove the comments and, if necessary, update the names to match the names you used for your percolator classes. The percTypes array will be used by the program to generate a pull-down menu of percolator types. Compile and run your updated program. Experiment with selecting a percolator type and clicking on the "Automatically Populate Grid" button. You should find that the top row is automatically populated with the appropriate percolator type. You will also observe that two additional buttons have been added to the GUI: "Run N Times" and "Run Density Experiments". Try clicking these buttons. You will be prompted for the appropriate experimental parameters, but the experiments will not run. The next step in the project is to write the code that executes the requested experiments and prints the results.

Implementing Experiments

The "Run N Times" and "Run Density Experiments" buttons each result in a call to corresponding methods in the PercolationController class, runNTimes and runExperiments.

runNTimes

The basic logic for the runNTimes method should be as follows:
repeat N times:
   Randomly fill in the grid using the appropriate density.
   Fill in the top row of the grid with percolators.
   Run the percolation simulation (without involving the GUI).
   If any material percolated to the bottom, increment a counter. 

After all N runs have completed, use System.out.println to print a summary
of the results including: 
    The size of the grid.
    The density.
    The number of runs.
    The number of runs that resulted in percolation.
There are several existing methods in the PercolationController class that will be useful for implementing runNTimes. These include randomlyFillGrid, fillTopRow, invisibleRun and percolatedToBottom. Read each of these methods, along with their comments, to make sure that you understand what they do and how to use them.

Notice that we want to avoid updating the GUI while these experiments are running. While it might be entertaining to watch thousands of percolation experiments, (it might make a good screensaver) the experiments can be run much more quickly if the GUI is not involved. This is one of the motivations for maintaining a separation between the code that handles the GUI and the code that handles the simulation logic.

Implement and test the runNTimes method.

runExperiments

Once you have completed the runNTimes method, implementing runExperiments should be straightforward. It will consist of a loop that repeatedly calls runNTimes with an appropriate series of density values. Implement and test the runExperiments method. (Note that there are two stub methods in the PercolationController class named runExperiments. You will be modifying the version that takes three arguments. Disregard the version that takes zero arguments.)

Improving Efficiency

So far in this class we haven't worried very much about writing efficient code. Computers can execute many millions of instructions per second, so a slightly more efficient implementation of code that moves a fish or fills a grid row are unlikely to make a noticeable difference to the user. The situation here is different. The code you wrote above allows you to easily run tens of thousands of percolation experiments with just a few mouse clicks. Even if each of those experiments only takes a fraction of a second, the entire process could take minutes or hours. For example, assume that for a given grid size it takes .1 seconds to complete a single percolation experiment. If we want to complete 1,000 runs at 20 different densities, the total time will be: 1,000 * 20 = 20,000 runs * .1 seconds/run = 2,000 seconds = 33 minutes.

Testing SlowPercolationController

The next step in the project is to run some experiments to get a feel for the performance of the current version of the code. Fill in the following table by using a stopwatch to time the program. Each entry in the table should contain the time, in seconds, that it took the program to complete under the given conditions. Use the AllDirectionPercolator for these experiments. Save these results to be submitted along with your finished programming project.

 25x25 grid 50x50 grid 100x100 grid
50 runs     
100 runs     
200 runs     

Is it possible to do better than this? Take a few minutes to read over the step method of the SlowPercolationController. This method works by iterating through the entire grid, placing every object it finds into an ArrayList, and calling act on each of those objects. This is inefficient in at least two different ways. First it is possible that the grid is mostly empty. In that case the code may loop through many hundreds of grid positions just to find a small number of objects. Second, it is likely that most of the objects being asked to act will not do anything. The act method will have no effect on solid material or on percolating material that has no place to go.

Take another look at the results of your timing experiments and write answers to the following questions:

Implementing ListPercolationController

A more efficient approach is to explicitly keep track of the set of items that needs to be processed. Any individual item in the grid needs to have its act method called at most once. Once an object has percolated to the appropriate neighbors, its work is done and it no longer needs to be considered.

The source code provided to you includes the skeleton of a ListPercolationController class that will take advantage of this. The basic idea is to maintain two lists of grid objects. One list (processThisStep) will represent the set of items that needs to be processed in the current step, and the other (processNextStep) will contain the list of objects that needs to be processed in the next step. Every time a new object is added to the grid as a result of percolation, it is also added to the list of items that will be processed on the next step. The process completes whenever there is a step that adds no items to the processNextStep list.

Complete and test the ListPercolationController by following the comments in the method stubs. You can test the controller by selecting it in the pull-down menu of the GUI. Once you are sure that your code is working correctly, re-run the timing experiments above using the new controller. Record the results to be submitted with the completed project. Type answers to the following questions for your new set of results:

Estimating Percolation Thresholds

For large grids, percolation systems like the one we are looking at experience a threshold effect: if we gradually increase the percentage of blocked grid squares, at some point the probability that the material will percolate drops from 100% to 0% almost immediately. The goal of this exercise is to estimate where that drop-off occurs. Pick either the gravity percolator or the all directions percolator and estimate the value of the threshold. The threshold will be the place where there is a 50/50 chance that the material will percolate. For these experiments you should use grids of size at least 100x100, with at least 1,000 runs per density. You will get better results with larger grids.

You can start out by running experiments across a wide range of densities, say from 0%-100% in 10% intervals. Those results should allow you to narrow your experiments down to a smaller region where you can run experiments using smaller intervals. Since we have implemented our probabilities as integer values, you won't be able to narrow down your estimate much beyond the closest percentage point. That's OK. Type up a paragraph describing your results and presenting your estimate. You should also include a copy of the raw data that you used to reach your conclusion. You will submit these results along with your completed project.

If you are interested, there are many other experiments you could run using this system: how exactly does the size of the grid change the sharpness of the threshold? Does the shape of the grid matter? In other words, would the probability of percolation be the same for a 100x100 grid as for a 20x500 grid (both have 10,000 entries)?

Submitting Results

Submit your answers to the questions above, along with your four completed percolator classes, the completed PercolationController class and the ListPercolationController class.