Percolation using quick union connectivity algorithm

This is my attempt to solve the percolation problem for the Princeton Algorithm-I course, the problem is well-defined here. My implementation is in C++ not Java and the following procedure is followed:

-
Create an NxN grid using QuickUnion class and keep track of each grid site by labeling it (except the first row that is all labeled with zero, to make the percolates() and isFull() functions easier to implement).

-
Each site is a struct type that contains its id and the boolean open state.

-
The solving methodology is as follows: open a random site, check if system percolates and if not repeat.

-
My problem is with the open() function, specifically the part of the code where I try to get the neighbor sites in order to connect the current site with the open neighbor site, where I make multiple checks for the location of the current site and what to do in each case.

QuickUnion.h (the implementation is not attached because it's not the issue here)

#ifndef QUICKUNION_H
#define QUICKUNION_H

#include 

struct Site {
    bool open = false;
    std::size_t id;
};

typedef std::vector>   Matrix2D;
typedef std::pair              Location;

class QuickUnion {
public:
    QuickUnion(const int N);

    bool isConnected(int p, int q);
    void Union(int p, int q);
    int Root(int p);
    Location getLocation(int p);

    virtual ~QuickUnion(){ }

    Matrix2D grid;
    std::size_t count = 0;
};

#endif  /* QUICKUNION_H */

Percolation.h

```
#ifndef PERCOLATION_H
#define PERCOLATION_H

#include "QuickUnion.h"

inline std::size_t getRandom(std::size_t N);

class Percolation {
public:
Percolation(int N); // create n-by-n grid, with all sites blocked
void open(int row, int col); // open site (row, col) if it is not open already
bool isOpen(int row, int col); // is site (row, col) open?
bool isFull(int row, int col); // is site (row, col) full?
bool percolate

Because no details were provided regarding the implementation of the QuickUnion class, it's not possible to provide any meaningful comment on performance. However, here are a few things that many help you improve your code.

Consider using a better random number generator

You are currently using

inline std::size_t getRandom(std::size_t N) {
    return ( std::rand() % ( N ) );
}

The major problems with this approach is that the low order bits of the random number generator are not particularly random. On my machine, there's a slight but measurable bias toward 0 with that. A better solution, if your compiler and library supports it, would be to use the C++11 std::uniform_int_distribution. In this case, I'd instead add a std::uniform_int_distribution to the class as private data members like this:

std::uniform_int_distribution randomSquare;
static std::mt19937 gen;

Then in the implementation file, define gen:

std::mt19937 Percolation::gen([]()->std::random_device::result_type{std::random_device rd; return rd();}());

Now whenever you want a random square, use the member function randomSquare() like this:

randomSquare(0,size*size);

Or if you feel you must keep the x,y style the code is currently using, use this:

i = randomSquare(0, size);
j = randomSquare(0, size);

Save the constructor argument

The size N is the only constructor argument but it doesn't appear to be explicitly saved which would be convenient in a number of places. One could refer perhaps to qu->grid.size() each time, but that seems a little awkward. I'd suggest a private member variable that stores the size for convenience.

Fix the bug

Right now, the open function begins with this:

if (isOpen(row, col))
    return;

However, the threshold is incremented even if no new square is opened. That's a bug and will skew your calculation.

Make the object do the work

If I were writing this program, I'd prefer to write a main like this:

int main(int argc, char *argv[]) {
    if (argc < 2) {
        std::cout << "Too few arguments.\n";
        return -1;
    }
    auto size = std::atoi(argv[1]);

    Percolation p(size);
    std::cout << "System percolates at " << p.run() << " open sites propability.\n";
}

I'm sure you can figure out what would need to go into a run function.

Simplify your code

As you have already realized, the open function is waaaay too long and complex. Consider instead what's required. When a site is opened, you simply need to call qu->Union() with each of it neighbors. If the site is on the edge of the grid, the neighbor that would be outside the grid simply needs to be skipped. Also, it appears that id is simply an alias for row + col * size -- I'd recommend choosing the single id rather than the row,col approach or a messy mix of both. Anyway, a much simpler open might be this:

void Percolation::open(int row, int col) {
    if (isOpen(row, col))
        return;

    qu->grid[row][col].open = true;
    auto current_site_id = qu->grid[row][col].id;

    // process neighbor above
    if (row != 0 && qu->grid[row-1][col].open) {
        qu->Union(qu->grid[row-1][col].id, current_site_id);
    } 
    // process neighbor below
    if (row != size-1 && qu->grid[row+1][col].open) {
        qu->Union(qu->grid[row+1][col].id, current_site_id);
    }
    // process neighbor left
    if (col != 0 && qu->grid[row][col-1].open) {
        qu->Union(qu->grid[row][col-1].id, current_site_id);
    } 
    // process neighbor right
    if (col != size-1 && qu->grid[row][col+1].open) {
        qu->Union(qu->grid[row][col+1].id, current_site_id);
    } 
}

StackExchange Code Review Q#149546, answer score: 5