COS226

• Download ErdosRenyi.java

/******************************************************************************
 *  Name:     Kevin Wayne
 *  NetID:    wayne
 *  Precept:  P99
 *
 *  Compilation:  javac ErdosRenyi.java
 *  Execution:    java ErdosRenyi n trials
 *
 *  Description: 
 *  Repeatedly add random edges (with replacement) to a graph on n
 *  vertices until the graph is connected. Report the mean and
 *  standard deviation of the number of edges added.
 *
 *  When n is large, Erdos and Renyi proved that after about 1/2 n ln n
 *  additions, the graph will have a 50/50 chance of being connected.
 *
 ******************************************************************************/

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdStats;
import edu.princeton.cs.algs4.Stopwatch;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class ErdosRenyi {

    public static int count(int n) {
        int edges = 0;
        WeightedQuickUnionUF uf = new WeightedQuickUnionUF(n);
        while (uf.count() > 1) {
            int i = StdRandom.uniform(n);
            int j = StdRandom.uniform(n);
            uf.union(i, j);
            edges++;
        }
        return edges;
    }

    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);          // number of vertices
        int trials = Integer.parseInt(args[1]);     // number of trials
        int[] edges = new int[trials];
        Stopwatch timer = new Stopwatch();

        // repeat the experiment trials times
        for (int t = 0; t < trials; t++) {
            edges[t] = count(n);
        }
        double timed = timer.elapsedTime();
        
        // report statistics
        StdOut.println("n                        = " + n);
        StdOut.println("mean of number of edges  = " + StdStats.mean(edges));
        StdOut.println("stddev of mean           = " + StdStats.stddev(edges));
        StdOut.println("elapsed time             = " + timed);
    }
}