The percolation problem

The percolation problem deals with connected paths between nodes in a 2D grid. The grid nodes could be in either of two states: “open” or “closed”; “conducting” or “insulating” or any other two opposite physical properties. When open, a node will connect with all the open nodes surrounding it. The system percolates where there is a path of connected nodes from any node on the top row to any node at the bottom row.

The system can be used to model diffusion of a liquid through a porous surface or the electric conductivity of a dielectric.

In the case of liquid diffusion, the grid is said to percolate when there is a connected path from any of the sites at the top row to any of the sites at the bottom row. On that moment, there is a free path for the liquid to move through the grid.

For a given grid size and a given fraction of open sites, there is a certain probability that the grid will percolate. It depends, of course, of the distribution of open sites on the grid.

It turns out that there is a phase transition on the probability of percolation of a two dimensional grid. Below a certain fraction of open sites, the probability of percolation is almost null. Above that fraction, the probability of percolation is almost certain. The percent value that divides both phases is very hard, if not impossible, to find theoretically. A good algorithm to simulate percolation for random grids is in need, to experimentally find this value.

The fast O(N lgN) algorithm to check for connected paths used in Sedgewick‘s Algorithm book is Quick Find or some optimized version of it.

I decided to implement myself these algorithms on C++, using the OO Strategy Pattern.

When I finished coding these command line tests, I thought it would be fun to see it in action for some concrete instance of a grid. That’s why I programmed a simple GUI for OS X.

The MVC (Model-View-Controller) was of great help here. Since I had my strategy classes for Quick Union, Quick Find and Weighted Quick Find as separate classes, I already had my model part done.

I then coded an Objective-C wrapper for the grid. This will be the class aware of the 2D nature of the grid. The model only knows about nodes, but it’s not spatially aware.

I only needed a general controller class, the application delegate provided by Xcode, and a view class to display the grid.

Once all the connections were done, I only added some bells and whistles to the app, and it was done.

An OS X GUI for a Percolation example
An OS X GUI for a Percolation example

I leave here a link to download the app, and I will post the source code in another post.

 

I hope you enjoy it!

Advertisements
The percolation problem

A Null Geodesic Viewer

A few years ago, during my master years, I was studying the trajectory that a photon would take when passing by one of these space-time bending black holes (the null geodesics around a Kerr black hole, in technical terms.) I was then working under Dr. Richard Price and with another student, Travis Miller.

OutDirectionCalculator GUI
The GUI implemented to visualize null geodesics around a Kerr Black Hole

The idea was to study how one of these black holes would affect the electromagnetic jet from a pulsar that is orbiting the hole. By the end of the research, when all mathematical problems were sorted out, it became clear that I would need some kind of visualization tool to confirm that the geodesics were being calculated correctly.

That’s why I decided to start my first little project for a program in OS X. The result was a Geodesic Plotter, so to speak.

This app is basically a GUI wrapper to a set of C functions developed to calculate the final direction of a ray of light when it is far enough away from the black hole so that it’s not affected anymore by its gravitational field.

The input conditions are the pulsar position and the initial shooting direction of the photon from the pulsar. The pulsar is not restricted to the rotational plane of the black hole. It can be placed anywhere on space. The black hole parameters for mass and angular momentum can be varied independently too.

The program uses OpenGL for rendering, and it updates the screen automatically when parameters are changed using the text boxes or arrow buttons. This is especially useful to explore the effect that the initial direction has on the final direction of the photon trajectory. One can even try to find those special directions for which the photon revolves several times around the black hole before it can escape into infinity.

The GUI project was really fun to work with and it was done during a visit to Argentina during the (northern hemisphere’s) summer. After the first try, two more versions followed that improved responsiveness (mainly the automatic update of the view). There is still room for improvement and some bugs need to be fixed, but hopefully they will be resolved in the future versions of the program.

The program can be downloaded from Dropbox following this link.

A Null Geodesic Viewer