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.

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

 

I hope you enjoy it!