code for : Percolation using Weighted Quick Union Find Algorithm.

this is a homework assignment. iv made the code do what its supposed to do, and it works perfectly.
The only problem im facing now is to model the code structure according to the given API. when i try to do so, i go into null pointer exceptions. i have somewhat understanding of why that happens, but still, cant figure out a solution.

so here is about the assignment:

Percolation: calculate how many sites are needed for a connection between top row n bottom row to take place

algorithm:

  1. open an NxN array, such that initially all 'sites' ie, elements of the array are blocked, ie their state is 'b' connect all top row elements to a 'virtual' TOP site, and all bottom row elements to a virtual 'bottom' site. sites connected to the TOP site directly(as with first row elememts) or indirectly are called 'full'

  2. iterate, opening one site in each process, assign the state of this site 'o' (for open)
    once opened, check the neighbors (up,down,left,right) for other open or 'full' members
    connect open/full neighbors,
    if connected to a 'full' site, change state of the newly opened site to 'f' (full)
    else state remains as 'o'

  3. check if TOP n BOTTOM are connected,
    if yes > system percolates, display num of open sites
    else go back to loop

following this algorithm, we have to make a code that that performs computational experiments with percolation.
the api is:

public class PercolationStats {
   public PercolationStats(int N, int T)    // perform T independent computational experiments on an N-by-N grid
   public double mean()                     // sample mean of percolation threshold
   public double stddev()                   // sample standard deviation of percolation threshold
   public double confidenceLo()             // returns lower bound of the 95% confidence interval
   public double confidenceHi()             // returns upper bound of the 95% confidence interval
   public static void main(String[] args)   // test client, described below
}

im running into problems with creating separate methods for stddev(),confidenceLo(),confidenceHi().
my code below shows the program running WITHOUT creating separate methods for these
my code :

public class PercolationStats{

    private int arrDim;
    private char[][] state;
    private WeightedQuickUnionUF qu;
    private int top = 0;
    private int bottom;
    private double count;


    public PercolationStats(int N){
        arrDim = N;
        qu = new WeightedQuickUnionUF((N*N)+2); // +2 is for the virtual top n bottom site
        state = new char[N][N];

        for(int i = 0; i< N; i++){
            for(int j = 0; j < N ; j++){
//              'b' = blocked
//              'o' = open
//              'f' = full
                state[i][j]='b';

            }
        }
        bottom = N*N + 1; // (N*N + 2) - 1;
        for(int i = 1; i<= N; i++){
            qu.union(top, i); // creating virtual connection of top row to Top site
            qu.union(bottom,bottom - i); // connecting bottom row sites to Bottom
        }

    }

    public int convertTo1D(int row, int col){
        // the conversion is needed as union find has 1D array, and return value will give the index of that array
        // but, since the initial(0) and final(N*N+1) positions of the (N*N + 2) array are reserved for TOP n BOTTOM virtual sites
        // the array index range for use is from 1 to N*N
        return ((row*arrDim + col) + 1); 
    }
    public void open(int row,int col){

        if (row < 1 || row > arrDim || col < 1 || col > arrDim)  
            throw new IndexOutOfBoundsException("Illegal parameter value.");  

        // passed values are in 1:N convention , here, since 2D to 1D conversion is used, row convention changed to 0:(N-1)
        row = row - 1;
        col = col - 1;

        if(calledBefore(row,col)){
            // if the site is already  opened, do nothing
        }
        else{
            count++;

            int myIndex = convertTo1D(row,col);



            if(row == 0){
                state[row][col] = 'f';

            }
            else if(row == (arrDim - 1)){
                state[row][col] = 'o';

            }
            else{
                // if neither in top or bottom row just mark state as open n check for open neighbors, and connect them.
                state[row][col] = 'o';

            }
            // opening a site means connecting the newly opened site with its neighboring sites
            if(row < (arrDim - 1)){
                // do row + 1
                int neighborIndex = convertTo1D(row+1,col);
                if(isOpen(row+1,col)){ // || 
                    qu.union(myIndex, neighborIndex);

                    // isOpen returns true, so state[row + 1][col] is open. thus it can only change to full if state[row][col] = 'f'
                    // state[row][col] is either full or open, so state[row + 1][col] has nothing to lose, only it can gain.
                    state[row + 1][col] = state[row][col]; 

                }else if(isFull(row+1,col)){
                    qu.union(myIndex, neighborIndex);

                    state[row][col] = 'f';
                }
            }
            if(row > 0){

                // do row - 1               
                int neighborIndex = convertTo1D(row-1,col);
                if(isOpen(row-1,col)){// || 
                    qu.union(myIndex, neighborIndex);

                    state[row - 1][col] = state[row][col]; 

                }else if(isFull(row-1,col)){
                    qu.union(myIndex, neighborIndex);

                    state[row][col] = 'f';                  
                }
            }
            if(col < (arrDim - 1)){
                // do col + 1

                int neighborIndex = convertTo1D(row,col+1);
                if(isOpen(row,col + 1)){ // || 
                    qu.union(myIndex, neighborIndex);

                    state[row][col + 1] = state[row][col];

                }else if(isFull(row,col + 1)){
                    qu.union(myIndex, neighborIndex);

                    state[row][col] = 'f';
                }
            }
            if(col > 0){
                // do col - 1

                int neighborIndex = convertTo1D(row,col-1);
                if(isOpen(row,col - 1)){ // 
                    qu.union(myIndex, neighborIndex);

                    state[row][col - 1] = state[row][col];

                }else if(isFull(row,col - 1)){
                    qu.union(myIndex, neighborIndex);

                    state[row][col] = 'f';
                }
            }
        }


    }
    public boolean isOpen(int row, int col){
        return (state[row][col] == 'o');
    }
    public boolean isFull(int row, int col){
        return (state[row][col] == 'f');

    }
    public boolean calledBefore(int row, int col){
        return (state[row][col] == 'o' || state[row][col] == 'f');
    }
    public boolean percolates(){

        if(qu.connected(top, bottom)){
            System.out.println("\n\n percolates: true");
            return true;
        }
        else{

            return false;
        }
    }

//  public double mean(double[] fraction){
//      return(StdStats.mean(fraction));
//  }
//  public double stddev(double[] fraction){
//      return(StdStats.stddev(fraction));
//  }
//  public double confidenceHi(double mu, double sigma, double T){
//      return(mu + (1.96*sigma/Math.sqrt((double)T)));
//  }
//  public double confidenceLo(double mu, double sigma, double T){
//      return(mu - (1.96*sigma/Math.sqrt((double)T)));
//  }

    public static void main(String[] args){
        final long startTime = System.nanoTime();

        int size = Integer.parseInt(args[0]);
        int numOfRuns = Integer.parseInt(args[1]);
        PercolationStats perC;
        double[] fraction = new double[numOfRuns];

        for(int runCount = 0; runCount < numOfRuns ; runCount++){
//          
//          System.out.println("enter size: ");
//          int size = StdIn.readInt() ;
//          int size=200;
            int arraySize= size*size;
            perC = new PercolationStats(size);
//          System.out.println("enter number of iterations: ");
//          int numOfRuns = StdIn.readInt();

            for(;;){
                int row = StdRandom.uniform(size) + 1;
                int column = StdRandom.uniform(size) + 1;
//              System.out.format("\n row n column: %d %d",row,column);
//              int row = StdIn.readInt();
//              int column = StdIn.readInt();
                if((row<1 || row>size) || (column < 1 || column > size )) throw new java.lang.IndexOutOfBoundsException("entered value is not valid \n");

                perC.open(row,column);
                if(perC.percolates()){
                    System.out.println("percolates with: " + perC.count + "counts");
                    fraction[runCount] = perC.count/arraySize;
                    break;
                }

            }
        }
//      double mu = perC.mean(fraction);
//      double sigma = perC.stddev(fraction);
//      double confHi = perC.confidenceHi(mu, sigma, numOfRuns);
//      double confLow = perC.confidenceLo(mu, sigma, numOfRuns);

        double mu = StdStats.mean(fraction);
        double sigma = StdStats.stddev(fraction);
        double confHi = mu + (1.96*sigma/Math.sqrt((double)numOfRuns));
        double confLow = mu - (1.96*sigma/Math.sqrt((double)numOfRuns));

        System.out.println("\n mean: " + mu);
        System.out.println(" stddev: " + sigma);
        System.out.println(" confHi: " + confHi);
        System.out.println(" confLow: " + confLow);
        final long duration = System.nanoTime() - startTime;
        System.out.println("duration: " + duration);
    }


}

iv kept my attempts at creating the separate methods within comments.
all the supporting codes like StdRandom and StdIn can be found here

im really working hard on this, any suggestion will be of great help!

regards
somjit.

Edited 3 Years Ago by somjit{}

so ....

this is a homework assignment. iv made the code do what its supposed to do, and it works perfectly.
The only problem im facing now is to model the code structure according to the given API. when i try to do so, i go into null pointer exceptions.

is it working perfectly, or is it throwing nullpointerexceptions? those two are not exactly the same.
what is the full error message?

this is a homework assignment. iv made the code do what its supposed to do, and it works perfectly.
The only problem im facing now is to model the code structure according to the given API. when i try > to do so, i go into null pointer exceptions.

the posted code works perfectly. as i said, i face problems only when modelling it according to the given API, which makes it mandatory to have separate methods to calculate the mean, standard deviation, and the 95% confidence levels.

the problem is that to calculate standard deviation, (as well as the other three statistical measures) i need to have access to the fraction[] array which stores the (perC.count/arraySize) values for each iteration.
However, as the reference perC is initialized inside the for() loop of main(), it brings in issues related to scope, and (i assume) null pointer exceptions(it hasnt been mentioned in the error report). This is because calculating the stats measures through the API methods means calling perC.<method_name> from outside the for loop, but perC itself is initialized inside the for loop.
so this would give errors, as it does:

The local variable perC may not have been initialized

^ the error showing up.

Edited 3 Years Ago by somjit{}

I don't see what you mean by "issues relating to scope." At least there is no problem with the scope of perC. It looks like you haven't decided which perC you want, since it is given many values, one for each run. If you really haven't decided which run's perC value you want, then you have the very serious problem of unclear requirements.

On the other hand, if you just want the perC of the last run only, then just initialize perC to null where you declare it and then check for perC == null before using it after the loop. If perC == null that will mean numOfRuns is zero or less and you can handle that case specially.

It looks like you haven't decided which perC you want,

mean = (sum of elements)/num_of_elements
which is the 1st thing i want to calculate, and it requires the count/arraySize value of each iteration( or run ).

thus mean becomes : (sum of count/arraySize of each run)/numOfRuns
so want every new perC, in a loop.

Edited 3 Years Ago by somjit{}

On the other hand, if you just want the perC of the last run only, then just initialize perC to null where you declare it and then check for perC == null before using it after the loop. If perC == null that will mean numOfRuns is zero or less and you can handle that case specially.

this can give a solution, but if you look at my code again, the value is calculated in main() , but your answer points to getting the value from the class itself. if i can return the same value to main, instead of calculating it there, the way ur suggesting to solve the problem can be done. thanks for the idea :)

Actually, looking at your code again, you don't need perC at all after the loop. The methods that you are calling in the commented lines 207-210 don't use perC; they could just as well be static methods, and you prove that by calculating the same values without perC in lines 212-215. So I had to look again to figure out why you thought you needed perC after the loop at all.

It looks like you've misunderstood your instructions and implemented mean, stddev, confidenceHi, confidenceLo so that they don't use the value of the PercolationStats object by passing in every value that they need as an argument to each method. Unfortunately for that plan, it does not count as implementing the API if you change the parameters of the methods, including adding parameters to methods that aren't supposed to have parameters. You need to rethink your design and implement the API as given, not some alternate version of the API.

Edited 3 Years Ago by bguild

You need to rethink your design and implement the API as given, not some alternate version of the API.

yes, i had a feeling parameterized versions wont count, and rightly so.

i made a few modifications

  1. created a static fraction[] array inside the class, it keeps all the individual (count/arrSize) data in it, to be used by the mean() and stddev() methods.
    (lines 173 onwards in the code below.)

  2. created a static classRunCount variable, that keeps track of how many times the class has been called/instantiated. this helps in the way, that when last call is made, that classRunCount is used in the mean and stddev methods.

thus calculations are now done inside the class itself, so no need to call perC outside the for() loops as before.
however, the results arent correct, ie
before, in the 1st code, the mean was coming at around .59 , but here, its coming at around .0058
thats another new problem now...

public class PercolationStats{

    private int arrDim;
    private int arrSize;
    private char[][] state;
    private WeightedQuickUnionUF qu;
    private int top = 0;
    private int bottom;
    private double count;
    private static double[] fraction;

    private static int classRunCount = 0; // keeps track of the num of runs from within the class


    public PercolationStats(int N){
        classRunCount++;
        arrDim = N;
        arrSize = N*N;
        qu = new WeightedQuickUnionUF((N*N)+2); // +2 is for the virtual top n bottom site
        state = new char[N][N];

        for(int i = 0; i< N; i++){
            for(int j = 0; j < N ; j++){
//              'b' = blocked
//              'o' = open
//              'f' = full
                state[i][j]='b';

            }
        }
        bottom = N*N + 1; // (N*N + 2) - 1;
        for(int i = 1; i<= N; i++){
            qu.union(top, i); // creating virtual connection of top row to Top site
            qu.union(bottom,bottom - i); // connecting bottom row sites to Bottom
        }

    }

    private void setFraction(int size){
        fraction = new double[size];
    }

    private int convertTo1D(int row, int col){
        // the conversion is needed as union find has 1D array, and return value will give the index of that array
        // but, since the initial(0) and final(N*N+1) positions of the (N*N + 2) array are reserved for TOP n BOTTOM virtual sites
        // the array index range for use is from 1 to N*N
        return ((row*arrDim + col) + 1); 
    }
    public void open(int row,int col){

        if (row < 1 || row > arrDim || col < 1 || col > arrDim)  
            throw new IndexOutOfBoundsException("Illegal parameter value.");  

        // passed values are in 1:N convention , here, since 2D to 1D conversion is used, row convention changed to 0:(N-1)
        row = row - 1;
        col = col - 1;

        if(calledBefore(row,col)){
            // if the site is already  opened, do nothing
        }
        else{
            count++;

            int myIndex = convertTo1D(row,col);



            if(row == 0){
                state[row][col] = 'f';

            }
            else if(row == (arrDim - 1)){
                state[row][col] = 'o';

            }
            else{
                // if neither in top or bottom row just mark state as open n check for open neighbors, and connect them.
                state[row][col] = 'o';

            }
            // opening a site means connecting the newly opened site with its neighboring sites
            if(row < (arrDim - 1)){
                // do row + 1
                int neighborIndex = convertTo1D(row+1,col);
                if(isOpen(row+1,col)){ // || 
                    qu.union(myIndex, neighborIndex);

                    // isOpen returns true, so state[row + 1][col] is open. thus it can only change to full if state[row][col] = 'f'
                    // state[row][col] is either full or open, so state[row + 1][col] has nothing to lose, only it can gain.
                    state[row + 1][col] = state[row][col]; 

                }else if(isFull(row+1,col)){
                    qu.union(myIndex, neighborIndex);

                    state[row][col] = 'f';
                }
            }
            if(row > 0){

                // do row - 1               
                int neighborIndex = convertTo1D(row-1,col);
                if(isOpen(row-1,col)){// || 
                    qu.union(myIndex, neighborIndex);

                    state[row - 1][col] = state[row][col]; 

                }else if(isFull(row-1,col)){
                    qu.union(myIndex, neighborIndex);

                    state[row][col] = 'f';                  
                }
            }
            if(col < (arrDim - 1)){
                // do col + 1

                int neighborIndex = convertTo1D(row,col+1);
                if(isOpen(row,col + 1)){ // || 
                    qu.union(myIndex, neighborIndex);

                    state[row][col + 1] = state[row][col];

                }else if(isFull(row,col + 1)){
                    qu.union(myIndex, neighborIndex);

                    state[row][col] = 'f';
                }
            }
            if(col > 0){
                // do col - 1

                int neighborIndex = convertTo1D(row,col-1);
                if(isOpen(row,col - 1)){ // 
                    qu.union(myIndex, neighborIndex);

                    state[row][col - 1] = state[row][col];

                }else if(isFull(row,col - 1)){
                    qu.union(myIndex, neighborIndex);

                    state[row][col] = 'f';
                }
            }
        }


    }
    public boolean isOpen(int row, int col){
        return (state[row][col] == 'o');
    }
    public boolean isFull(int row, int col){
        return (state[row][col] == 'f');

    }
    public boolean calledBefore(int row, int col){
        return (state[row][col] == 'o' || state[row][col] == 'f');
    }
    public boolean percolates(){

        if(qu.connected(top, bottom)){
            fraction[classRunCount] = count/arrSize;
            System.out.println("\n\n percolates: true");
            return true;
        }
        else{

            return false;
        }
    }

    private double mu = 0;
    private double sigma = 0;

    public double mean(){
        mu = StdStats.mean(fraction);
        return mu;
    }
    public double stddev(){
        sigma = StdStats.stddev(fraction);
        return sigma;
    }
    public double confidenceHi(){
        return(mu + (1.96*sigma/Math.sqrt((double)classRunCount)));
    }
    public double confidenceLo(){
        return(mu - (1.96*sigma/Math.sqrt((double)classRunCount)));
    }

    public static void main(String[] args){
        final long startTime = System.nanoTime();

        int size = Integer.parseInt(args[0]);
        int numOfRuns = Integer.parseInt(args[1]);

//      double[] fraction = new double[numOfRuns];

        for(int runCount = 0; runCount < numOfRuns; runCount++){
//          
//          System.out.println("enter size: ");
//          int size = StdIn.readInt() ;
//          int size=200;
//          int arraySize= size*size;

            PercolationStats perC = new PercolationStats(size);

            if(runCount == 0)  // setup the fraction array in the perC instance on the 1st iteration
                perC.setFraction(size);


//          System.out.println("enter number of iterations: ");
//          int numOfRuns = StdIn.readInt();

            for(;;){
                int row = StdRandom.uniform(size) + 1;
                int column = StdRandom.uniform(size) + 1;
//              System.out.format("\n row n column: %d %d",row,column);
//              int row = StdIn.readInt();
//              int column = StdIn.readInt();
                if((row<1 || row>size) || (column < 1 || column > size )) throw new java.lang.IndexOutOfBoundsException("entered value is not valid \n");

                perC.open(row,column);
                if(perC.percolates()){
                    System.out.println("percolates with: " + perC.count + "counts");

                    if(runCount == (numOfRuns - 1)){ // signifies that this was the last run to be made, and now we have to calculate the stats measures
                        double mu = perC.mean();
                        double sigma = perC.stddev();
                        double confHi = perC.confidenceHi();
                        double confLow = perC.confidenceLo();

                        System.out.println("\n mean: " + mu);
                        System.out.println(" stddev: " + sigma);
                        System.out.println(" confHi: " + confHi);
                        System.out.println(" confLow: " + confLow);
                    }


                    break;
                }

            }
        }


//      double mu = StdStats.mean(fraction);
//      double sigma = StdStats.stddev(fraction);
//      double confHi = mu + (1.96*sigma/Math.sqrt((double)numOfRuns));
//      double confLow = mu - (1.96*sigma/Math.sqrt((double)numOfRuns));


        final long duration = System.nanoTime() - startTime;
        System.out.println("duration: " + duration);
    }


}

Edited 3 Years Ago by somjit{}

the problem is solved, i was doing two things wrong:

  1. initialized the fraction array with the wrong value. it needs to be initialized with numOfRuns, i was doing it with arraySize

  2. classRunCount needs to be initialized with -1 instead of 0. in this way, in each new Percolation class construction, classRunCount++ will increment it, starting from 0 to N-1. previously, it was starting from 1, and giving an outOfBounds error on the last run.( this happens after fixing the fraction[] initialization with proper set up values.)

Your constructor still has the wrong parameters.

I notice that your API methods won't work correctly if confidenceHi or confidenceLo is called before mean and stddev. Unless the definition of the API you were given guarantees that they will always be called in a certain order, you shouldn't trust that they will be called in a certain order. Remember those methods aren't there just so they can be called in your main method. If they were, they would be private. They are there so someone can use your PercolationStats class somewhere else. Are you sure that it will do what that person expects if that person has only read the API description and hasn't looked at your code?

Remember those methods aren't there just so they can be called in your main method

i found that out the hard way.. the assignment , after being checked, i was given the report that all the stats measures was 0. then i learned, that the main method wasnt even run by the checking software... it required all the heavy lifting to be done by the constructor itself... they wouldnt even touch the main. i had to modify it quite a bit based on these factors.

I notice that your API methods won't work correctly if confidenceHi or confidenceLo is called before mean and stddev.

thats true... i have to put in a call to mean() and stddev() inside the confidenceHi() n confidenceLow() methods for it to be independent of the order. so far, it seems that its being called only after mean() n stddev() , so i didnt want it to spend time calculating what it already did..

thanks for keeping up with me :)

Edited 3 Years Ago by somjit{}

This question has already been answered. Start a new discussion instead.