Numerical simulation of the probability of two adjacent vertices being connected in edge percolation on the two-dimensional square lattice; see http://math.stackexchange.com/questions/395809.

Question395809.java

package math.se;

import java.util.HashSet;
import java.util.Random;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

public class Question395809 {
  static Random random = new Random ();
	
	static class Edge implements Comparable<Edge> {
		double p;
		int i1;
		int i2;
		
		public int compareTo (Edge e) {
			double diff = p - e.p;
			return diff > 0 ? 1 : diff < 0 ? -1 : 0;
		}
	}
	
	public static void main (String [] args) {
		int n = Integer.parseInt (args [0]);
		int nbins = Integer.parseInt (args [1]);
		int ntrials = Integer.parseInt (args [2]);

		int [] bins = new int [nbins];
		
		SortedSet<Edge> edges = new TreeSet<Edge> ();
	
		Set [] clusters = new Set [n * n];
		for (int i = 0;i < clusters.length;i++)
			clusters [i] = new HashSet ();

		int [] indices = new int [n * n];

		int [] [] neighbours = new int [n * n] [4];
		
		for (int i = 0;i < n;i++)
			for (int j = 0;j < n;j++)
				for (int k = 0;k < 2;k++) {
					int i1 = j * n + i;
					int i2 = ((j + k) % n) * n + (i + 1 - k) % n;
					neighbours [i1] [k] = i2;
					neighbours [i2] [k + 2] = i1;
				}
		
		for (int m = 0;m < ntrials;m++) {
			for (int i = 0;i < n * n;i++) {
				indices [i] = i;
				clusters [i].clear ();
				clusters [i].add (i);
			}
			
			edges.clear ();
			for (int i = 0;i < n;i++)
				for (int j = 0;j < n;j++)
					for (int k = 0;k < 2;k++) {
						Edge e = new Edge ();
						e.i1 = j * n + i;
						e.i2 = ((j + k) % n) * n + (i + 1 - k) % n;
						e.p = random.nextDouble ();
						edges.add (e);
					}
			
			for (Edge e : edges) {
				int i1 = indices [e.i1];
				int i2 = indices [e.i2];
				
				if (i1 != i2) {
					
					if (clusters [i1].size () < clusters [i2].size ()) {
						int i = i1;
						i1 = i2;
						i2 = i;
					}

					Set<Integer> c1 = clusters [i1];
					Set<Integer> c2 = clusters [i2];
					
					int count = 0;
					for (Integer i : (Set<Integer>) c2)
						for (int j : neighbours [i])
							if (indices [j] == i1)
								count++;
					bins [(int) (nbins * e.p)] += count;
					
					for (Integer i : (Set<Integer>) c2)
						indices [i] = i1;
					c1.addAll (c2);
				}
			}
		}
		
		double norm = 1 / (2. * n * n * ntrials);
		int sum = 0;
		for (int i = 0;i < bins.length;i++) {
			System.out.println (i / ((double) bins.length) + " " + norm * sum);
			sum += bins [i];
		}
		System.out.println ("1 1");
	}
}