/** Generate a random DAG using preferential attachment. First an independent set of <code>n0</code> nodes is generated.
 *  Then <code>n-n0</code> more nodes are generated: for each node, the outdegree is determined using <code>outdegreeDistribution.nextInt()</code>
 *  minimized with the number of existing nodes. For each arc, the target is the existing node <code>i</code> with probability proportional to
 *  <code>k+1</code> where <code>k</code> is <code>i</code>'s current outdegree.
 *
 * @param n number of nodes.
 * @param n0 number of initial nodes.
 * @param outdegreeDistribution distribution from which outdegrees are sampled.
 * @param random generator used to produce the arcs.
 * @return the generated DAG.
 */
public static ArrayListMutableGraph preferentialAttachmentDAG(final int n, final int n0, final IntegerDistribution outdegreeDistribution, final RandomGenerator random) {
	final ArrayListMutableGraph g = new ArrayListMutableGraph(n);
	final FenwickTree ft = new FenwickTree(n);
	// Initial independent set
	for (int source = 0; source < n0; source++) ft.incrementCount(source + 1);
	// Rest of the graph
	final IntOpenHashSet s = new IntOpenHashSet();
	for (int source = n0; source < n; source++) {
		final int m = Math.min(outdegreeDistribution.sample(), source - 1); // Outdegree
		s.clear();
		while(s.size() < m) {
			final int t = ft.sample(random);
			if (s.add(t)) {
				ft.incrementCount(t);
				g.addArc(source, t - 1);
			}
		}
		ft.incrementCount(source + 1);
	}
	return g;
}
 

@Test(expected=IllegalArgumentException.class)
public void testWrongBound() throws IOException, JSAPException {
	// (0,1) (0,2) (0,3) (1,7)
	ImmutableGraph graph1 = new XImmutableGraph(ImmutableGraph.wrap(new ArrayListMutableGraph(8, new int[][] { { 0, 1 }, { 0, 2 }, { 0, 3 }, { 1, 7 } }).immutableView()), 4);
	// (4,2) (4,3) (7,4) (7,6)
	ImmutableGraph graph2 = new XImmutableGraph(ImmutableGraph.wrap(new ArrayListMutableGraph(8, new int[][] { { 0, 2 }, { 0, 3 }, { 3, 4 }, { 3, 6 } }).immutableView()), 4);
	File ef1 = new File(dir, "graph1.ef");
	EFGraph.store(graph1, 10, ef1.getAbsolutePath(), null);
	File ef2 = new File(dir, "graph2.ef");
	EFGraph.store(graph2, 8, ef2.getAbsolutePath(), null);
	File result = new File(dir, "result-ef"); result.delete();
	CatEFGraphs.main(new String[] { "-m", result.getAbsolutePath(), ef1.getAbsolutePath(), ef2.getAbsolutePath() });
}
 

/** Generates <code>np</code> call graphs. Each call graph is obtained using {@link #preferentialAttachmentDAG(int, int, IntegerDistribution, RandomGenerator)} (with
 *  specified initial graph size (<code>initialGraphSizeDistribution</code>), graph size (<code>graphSizeDistribution</code>), outdegree distribution (<code>outdegreeDistribution</code>).
 *  Then a dependency DAG is generated between the call graphs, once more using {@link #preferentialAttachmentDAG(int, int, IntegerDistribution, RandomGenerator)} (this
 *  time the initial graph size is 1, whereas the outdegree distribution is <code>outdegreeDistribution</code>).
 *  Then to each node of each call graph a new set of outgoing arcs is generated (their number is chosen using <code>externalOutdegreeDistribution</code>): the target
 *  call graph is generated using the indegree distribution of the dependency DAG; the target node is chosen according to the reverse indegree distribution within the revision call graph.
 *
 * @param np number of revision call graphs to be generated.
 * @param graphSizeDistribution the distribution of the graph sizes (number of functions per call graph).
 * @param initialGraphSizeDistribution the distribution of the initial graph sizes (the initial independent set from which the preferential attachment starts).
 * @param outdegreeDistribution the distribution of internal outdegrees (number of internal calls per function).
 * @param externalOutdegreeDistribution the distribution of external outdegrees (number of external calls per function).
 * @param depExponent exponent of the Zipf distribution used to establish the dependencies between call graphs.
 * @param random the random object used for the generation.
 */
public void generate(final int np, final IntegerDistribution graphSizeDistribution, final IntegerDistribution initialGraphSizeDistribution,
		final IntegerDistribution outdegreeDistribution, final IntegerDistribution externalOutdegreeDistribution, final IntegerDistribution dependencyOutdegreeDistribution, final RandomGenerator random) {
	rcgs = new ArrayListMutableGraph[np];
	nodePermutation = new int[np][];
	final FenwickTree[] td = new FenwickTree[np];
	deps = new IntOpenHashSet[np];
	source2Targets = new ObjectOpenCustomHashSet[np];

	// Generate rcg of the np revisions, and the corresponding reverse preferential distribution; cumsize[i] is the sum of all nodes in packages <i
	for ( int i = 0; i < np; i++) {
		deps[i] = new IntOpenHashSet();
		final int n = graphSizeDistribution.sample();
		final int n0 = Math.min(initialGraphSizeDistribution.sample(), n);
		rcgs[i] = preferentialAttachmentDAG(n, n0, outdegreeDistribution, random);
		td[i] = getPreferentialDistribution(rcgs[i].immutableView(), true);
		nodePermutation[i] = Util.identity(n);
		Collections.shuffle(IntArrayList.wrap(nodePermutation[i]), new Random(random.nextLong()));
	}

	// Generate the dependency DAG between revisions using preferential attachment starting from 1 node
	final ArrayListMutableGraph depDAG = preferentialAttachmentDAG(np, 1, dependencyOutdegreeDistribution, random);

	// For each source package, generate function calls so to cover all dependencies
	for (int sourcePackage = 0; sourcePackage < np; sourcePackage++) {
		source2Targets[sourcePackage] = new ObjectOpenCustomHashSet<>(IntArrays.HASH_STRATEGY);
		final int outdegree = depDAG.outdegree(sourcePackage);
		if (outdegree == 0) continue; // No calls needed (I'm kinda busy)

		final int numFuncs = rcgs[sourcePackage].numNodes();
		final int[] externalArcs = new int[numFuncs];
		int allExternalArcs = 0;
		// We decide how many calls to dispatch from each function
		for (int sourceNode = 0; sourceNode < numFuncs; sourceNode++) allExternalArcs += (externalArcs[sourceNode] = externalOutdegreeDistribution.sample());
		// We create a global list of external successors by shuffling
		final int[] targetPackage = new int[allExternalArcs];
		final int[] succ = depDAG.successorArray(sourcePackage);
		for(int i = 0; i < outdegree; i++) deps[sourcePackage].add(succ[i]);
		for(int i = 0; i < allExternalArcs; i++) targetPackage[i] = succ[i % outdegree];
		MathArrays.shuffle(targetPackage, random);

		for (int sourceNode = allExternalArcs = 0; sourceNode < numFuncs; sourceNode++) {
			final int externalOutdegree = externalArcs[sourceNode];
			for (int t = 0; t < externalOutdegree; t++) {
				final int targetNode = td[targetPackage[allExternalArcs + t]].sample(random) - 1;
				source2Targets[sourcePackage].add(new int[] { sourceNode, targetPackage[allExternalArcs + t], targetNode });
			}
			allExternalArcs += externalOutdegree;
		}
	}
}
 

private static String graph2String(final CallGraphGenerator callGraphGenerator, final int i, final RandomGenerator randomGenerator) {
	final ArrayListMutableGraph g = callGraphGenerator.rcgs[i];
	final StringBuilder sb = new StringBuilder();
	sb.append("{\n");
	sb.append("\t\"product\": \"graph-" + i + "\",\n");
	sb.append("\t\"forge\": \"f\",\n");
	sb.append("\t\"generator\": \"OPAL\",\n");
	sb.append("\t\"version\": \"1.0\",\n");
	sb.append("\t\"timestamp\": \"0\",\n");
	sb.append("\t\"depset\": [\n\t\t");
	// All generated DNFs are singletons
	for(final IntIterator d = callGraphGenerator.deps[i].iterator(); d.hasNext(); ) {
		sb.append( "[{ \"forge\": \"f\", \"product\": \"graph-" + d.nextInt() + "\", \"constraints\": [\"[1.0]\"] }]");
		if (d.hasNext()) sb.append(", ");
	}
	sb.append("\n\t],\n");
	sb.append("\t\"cha\": {\n");
	for (int jj = 0; jj < g.numNodes() / 3; jj++) {			
		sb.append("\t\t\"/p" + i + "/A" + jj + "\": {\n");
		sb.append("\t\t\t\"methods\": {\n");
		for (int j = 3 * jj; j < 3 * jj + 3 && j < g.numNodes(); j++) {
			sb.append("\t\t\t\t\"" + j + "\": \"/p" + i + "/A" + jj + ".f" + j + "()v\"");
			if (j < 3 * jj + 2 && j < g.numNodes() + 1) sb.append(",");
			sb.append("\n");
		}
		sb.append("\t\t\t},\n");
		sb.append("\t\t\t\"superInterfaces\": [],\n");
		sb.append("\t\t\t\"sourceFile\": \"A" + jj + ".java\",\n");
		sb.append("\t\t\t\"superClasses\": [\"/java.lang/Object\"]\n");
		sb.append("\t\t}");
		if (jj < g.numNodes() / 3 - 1) sb.append(",");
		sb.append("\n");
	}
	sb.append("\t},\n");
	sb.append("\t\"graph\": {\n");
	
	// Internal calls
	sb.append("\t\t\"internalCalls\": [\n");
	final ObjectArrayList<String> lines = new ObjectArrayList<>(); // Graph lines
	for(int j = 0; j < g.numNodes(); j++) {
		for(final IntIterator s = g.successors(j); s.hasNext();)
			lines.add("\t\t\t[\n\t\t\t\t" + callGraphGenerator.nodePermutation[i][j] + ",\n\t\t\t\t" + callGraphGenerator.nodePermutation[i][s.nextInt()] + "\n\t\t\t]");
	}
	Collections.shuffle(lines, new Random(randomGenerator.nextLong())); // Permute graph lines
	for (int j = 0; j < lines.size(); j++) {
		sb.append(lines.get(j));
		if (j < lines.size() - 1) sb.append(",");
		sb.append("\n");
	}
	sb.append("\t\t],\n");
	
	// External calls
	sb.append("\t\t\"externalCalls\": [\n");
	lines.clear();
	for(final int[] t: callGraphGenerator.source2Targets[i]) {
		lines.add("\t\t\t[\n\t\t\t\t\"" + callGraphGenerator.nodePermutation[i][t[0]] + "\",\n\t\t\t\t\"/p" + t[1] + "/A"+ callGraphGenerator.nodePermutation[t[1]][t[2]] / 3 + ".f" + callGraphGenerator.nodePermutation[t[1]][t[2]] +"()v\",\n"
				+ "\t\t\t\t{\"invokevirtual\": \"1\"}\n"
				+ "\t\t\t]");
	}
	Collections.shuffle(lines, new Random(randomGenerator.nextLong())); // Permute graph lines
	for (int j = 0; j < lines.size(); j++) {
		sb.append(lines.get(j));
		if (j < lines.size() - 1) sb.append(",");
		sb.append("\n");
	}
	sb.append("\t\t]\n");
	sb.append("\t}\n");
	sb.append("}");
	
	return sb.toString();
}