Graph generator

Main.java

import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Random;

public class Main {

	static class Graph {

		HashSet<Integer>[] g;
		Random rnd = new Random();
		int k;

		public Graph(int n, int k) {
			this.k = k;
			g = new HashSet[n];
			for (int i = 0; i < g.length; i++) {
				g[i] = new HashSet<Integer>();
			}
		}

		void rec(int count, int first) {
			if (count != 1) {
				int a = count >> 1;
				rec(a, first);
				rec(a, first + a);
				for (int i = 0; i < k; ++i) {
					int v = rnd.nextInt(a);
					int u = rnd.nextInt(a);
					if (rnd.nextBoolean()) {
						g[first + v].add(first + u + a);
					} else
						g[first + v + a].add(first + u);
				}
			} else {
				if (rnd.nextBoolean())
					g[first].add(first);
			}
		}

		boolean check(int count, int first) {
			if (count != 1) {
				int a = count >> 1;
				if (!check(a, first))
					return false;
				if (!check(a, first + a))
					return false;
				int v = first;
				int cnt = 0;
				for (int j = 0; j < a; ++j, ++v)
					for (int u : g[v])
						if (u >= first + a && u < first + count)
							cnt++;
				for (int j = 0; j < a; ++j, ++v)
					for (int u : g[v])
						if (u < first + a && u >= first)
							cnt++;
				return cnt <= k;
			}
			return true;
		}

		int edgesCount() {
			int ret = 0;
			for (int i = 0; i < g.length; i++) {
				ret += g[i].size();
			}
			return ret;
		}

		void print() throws FileNotFoundException {
			PrintWriter out = new PrintWriter("test.txt");
			out.println(g.length + " " + edgesCount() + " " + k);
			for (int i = 0; i < g.length; i++)
				for (int u : g[i])
					out.println(i + " " + u);
			out.close();
		}
	}

	public static void main(String[] args) throws FileNotFoundException {
		Graph g = new Graph(131072, 100);
		g.rec(131072, 0);
		if (!g.check(131072, 0))
			throw new RuntimeException();
		g.print();
	}
}