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

class smallWorldGraph extends myGenericListGraph<Integer>{

	private static BufferedReader stdin = new BufferedReader( new InputStreamReader( System.in ) );

	public smallWorldGraph(int n, int d, double p)
	{

		// Make space for names array and Edges array
                names = new Integer[n];
                Edges = (GenericLinkList<Integer>[]) new GenericLinkList[n];
                for (int i = 0 ; i < n; i ++) 
                        Edges[i] = new GenericLinkList<Integer>();

		// Make space for the point array
		Point[] pointArray = new Point[n];	
		
		// Generate points and add these as vertices to the smallworldGraph
		for(int i = 0; i < n; i++)
		{
			// Generate a point uniformly in the d by d square
			Point aPoint = new Point(d);
			pointArray[i] = aPoint;
			addVertex(i);
		}

		Random rand = new Random();

		// Generate the edges. Consider each vertex i
		for(int i = 0; i < n; i++)
		{
			Point thisPoint = pointArray[i];

			// Put all non-neighbors in an array
			int[] nonNeighbors = new int[n];
			int numNonNeighbors = 0;
			for(int j = 0; j < i; j++)
				if(!isEdge(i, j))
					nonNeighbors[numNonNeighbors++] = j;

			for(int j = i+1; j < n; j++)
				if(thisPoint.distance(pointArray[j]) > 1)
					nonNeighbors[numNonNeighbors++] = j;

			// For each vertex i, only  consider vertices  with higher indices
			for(int j = i+1; j < n; j++)
			{
				// Check if j is within unit distance of i
				if(thisPoint.distance(pointArray[j]) <= 1)
				{
					// Now flip a coin.  Heads, with probability p, Tails with probability 1-p
					// If Heads, then connect i to a randomly picked non-neighbor
					if (rand.nextFloat() <=  p)
                                        {
                                                int index = rand.nextInt(numNonNeighbors);
                                                int newNeighbor = nonNeighbors[index];

                                                //  Connect i to randomly picked neighbor
                                                addEdge(i, newNeighbor);

                                                // Replace newNeighbor by j in the list of non-neighbors
                                                nonNeighbors[index] = j;
					}
					// If tails, pick a non-neighbor uniformly at random and connect i to that
					// vertex
					else
						addEdge(i, j);
				} // end of if distance <= 1
			} // end of the j-loop, considering all vertices with higher index 
		} // end of i-loop
	} // end of constructor


        // Finds the location at which a vertex is stored in Vertices.
        // Returns -1 if vertex not found
        public int getIndex(Integer vertex)
        {
		int index = vertex.intValue();
		if((0 <= index)&&(index < numVertices))
			return index;
		
                return -1;
        }


	public static void main (String [] args) {
		int n = 0;
		int d = 0;

		try{
			// Prompt the user
            		System.out.println( "Type number of vertices in the graph (should be a positive integer). " );
            		// Read a line of text from the user.
            		String input = stdin.readLine();

			// converts a String into an int value
			n = Integer.parseInt( input ); 

			// Prompt the user again
            		System.out.println( "Type dimensions of the square you want the points in (should be a positive int.)" );
            		// Read a line of text from the user.
            		input = stdin.readLine();

			// converts a String into an int value
			d = Integer.parseInt( input ); 
		}
               	catch(java.io.IOException e)
               	{
               		System.out.println(e);
                }

		// Generate a bunch of smallWorldGraphs for d = 50 and different values of p
		for(int i = 0; i < 100; i=i+5)
		{
			// A function that takes n, d, and p and creates a small world network with these
			// parameters in a way that is specified in the Project 1 handout
			double p = i/100.0;
			smallWorldGraph g = new smallWorldGraph(n, d, p);

			System.out.print(p+" "+g.averageDegree()+" "+g.clusteringCoefficient());
			if(g.isConnected())
				System.out.println(" "+g.averagePathLength());
			else
				System.out.println(" "+0);

		}	
			
	}
}