/******************************************************************************
* 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);
}
}