import java.io.*;
import java.util.*;

public class SWGraph extends Graph {
    int N;
    double RewireProb;
    int K;
    boolean increaseEdges;
    SWGraph (int N, double P, int K, boolean increaseEdges) {
		super();
		this.N = N;
		this.RewireProb = P;
		this.K = K;
		this.increaseEdges = increaseEdges;
		initGraph();
    }
    public void initGraph() { // preferential & dynamic version
		ArrayList P = new ArrayList();
		for (int i=0; i<N; i++)
			nodes.add(new Node(i));
		for (int i=0; i<N; i++) {
			Node n = (Node)nodes.get(i);
			for (int j=0; j<K/2; j++) {
				Node n1 = (Node)nodes.get((i+j+1)%N);
				Node n2 = n;
				if (i>K/2 && randDouble()<RewireProb) {
					do {
						n2 = (Node)P.get(randInt(P.size()));
					} while (n2.ID()>=i-K/2 || n2==n || n2==n1);
					n2.addEdge(n);
					n.addEdge(n2);
					P.add(n);
					P.add(n2);
				}
				if (increaseEdges || n2 == n) {
					n1.addEdge(n);
					n.addEdge(n1);
					P.add(n);
					P.add(n1);
				}
			}
		}
		sortByDegree(true);
    }
	// ---------------- Test Program
    public static void main (String args[]) {
		boolean print = false;
		int N=Integer.parseInt(arg(args, 0, "100"));
		if (N<=100) { // if < 100 or neg
			N=Math.abs(N);
			print=true;
		}
		int K=Integer.parseInt(arg(args, 1, "4"));
		double P=Double.parseDouble(arg(args, 2, "0.05"));
		boolean increase=Boolean.valueOf(arg(args, 3, "true")).booleanValue();
		String name="SmW"+(increase?"+":"-")+N+"-"+K+"-"+P;
		System.out.println(name+": SmWorld N="+N+" K="+K+" P="+P
						   +(increase?" Add":" Remove"));
		assert(N > K, "N <= K: N="+N+" K="+K);
		assert((N*K/2)*2==N*K, "N*K not even: N="+N+" K="+K);
		assert((K/2)*2==K, "K not even: K="+K);
		assert(P <= 1.0, "P>1: P="+P);

		SWGraph g = new SWGraph(N, P, K, increase);
		if (print)
			g.printByLevel();
		g.printHist("Edge Histogram");
		g.printLevels("Levels Histogram");
    }
}