//Patrick Cullom
//4/23/10
//Algorithms

import java.util.ArrayList;
import java.util.Random;


public class SmallWorldNetwork {

	ArrayList<Integer> path = new ArrayList();
	int counter123 = 0;
	public SmallWorldNetwork(){
		int nodes = 256;
		int k = 8;
		int[][] graph = new int[nodes][nodes];
		graph = createGraph(nodes, k);
		graph = randomizeNeighbors(graph);
		System.out.println("C: " + 1 / (findC(graph, 0) / nodes));
		if(isConnected(graph))
			System.out.println("L: " + (findL(graph) / nodes));
		else
			System.out.println("Graph is unconnected. L not calculated.");
//		for(int i = 0; i < graph.length; i++){
//			for(int j = 0; j < graph.length; j++){
//				System.out.print(graph[i][j]);
//			}
//			System.out.println();
//		}
	}

	public int[][] createGraph(int nodes, int k){
		int[][] graph = new int[nodes][nodes];

		for(int i = 0; i < nodes; i++){
			for(int j = 1; j < k / 2 + 1; j++){
				if((i + j) >= nodes){
					graph[i][i + j - nodes] = 1;
					graph[i + j - nodes][i] = 1;
				} else {
					graph[i][i + j] = 1;
					graph[i + j][i] = 1;
				}
			}
		}
		return graph;
	}

	public int[][] randomizeNeighbors(int[][] graph){
		Random random = new Random();
		int temp = 0;
		boolean noChange = true;
		for(int i = 0; i < graph.length; i++){
			for(int j = 0; j < graph.length; j++){
				if(random.nextDouble() < 1 && graph[i][j] == 1 && i != j){
					graph[i][j] = 0;
					graph[j][i] = 0;
					temp = random.nextInt(graph.length);
					noChange = true;
					while(noChange){
						temp = random.nextInt(graph.length);
						if(temp != i && graph[i][temp] != 1){
							graph[i][temp] = 1;
							graph[temp][i] = 1;
							noChange = false;
						}
					}
				}
			}
		}
		return graph;
	}

	public int findL(int[][] graph){
		int count = 0;
		for(int i = 0; i < graph.length; i++){
			for(int j = 0; j < graph.length; j++){
				if(i != j)
					count += findShortestPath(graph, i, j);
				path.clear();
			}
		}

		return count / graph.length;
	}
	public int findShortestPath(int graph[][], int node1, int node2){
		int shortest = 0;
		ArrayList<Integer> pathCount = new ArrayList();

		if(graph[node1][node2] == 1){
			return 1;
		}

		path.add(node1);

		for(int i = 0; i < graph.length; i++){
			if(graph[node1][i] == 1 && !path.contains(i) && node1 != i){
				path.add(i);
				pathCount.add(findShortestPath(graph, i, node2));
			}
		}
		for(int i = 0; i < pathCount.size(); i++){
			if(i == 0){
				shortest = pathCount.get(i);
			} else if(pathCount.get(i) < shortest){
				shortest = pathCount.get(i);
			}
		}
		return 1 + shortest;
	}

	public double findC(int[][] graph, int start){
		double total = 0;
		ArrayList<Integer> nodesToCheck = new ArrayList();
		if(start == graph.length)
			return 0;
		for(int i = 0; i < graph.length; i++){
			if(graph[start][i] == 1){
				nodesToCheck.add(i);
			}
		}
		for(int j = 0; j < nodesToCheck.size(); j++){
			for(int k = j + 1; k < nodesToCheck.size(); k++){
				if(graph[nodesToCheck.get(j)][nodesToCheck.get(k)] == 1){
					total++;
				}
			}
		}
		return (double) (nodesToCheck.size()*(nodesToCheck.size()-1) / 2 ) - total + findC(graph, ++start);
	}

	public boolean isConnected(int[][] graph){
		ArrayList<Integer> visited = new ArrayList();
		ArrayList<Integer> neighbors = new ArrayList();
		visited.add(0);
		for(int i = 0; i < visited.size(); i++){
			neighbors = findNeighbors(graph, visited.get(i));
			for(int j = 0; j < neighbors.size(); j++){
				if(!visited.contains(neighbors.get(j))){
					visited.add(neighbors.get(j));
				}
			}
		}
		if(visited.size() == graph.length){
			return true;
		}
		return false;
	}

	public ArrayList<Integer> findNeighbors(int[][] graph, int node){
		ArrayList<Integer> neighbors = new ArrayList();

		for(int i = 0; i < graph.length; i++){
			if(graph[node][i] == 1){
				neighbors.add(i);
			}
		}
		return neighbors;
	}

	public static void main(String[] args){
		new SmallWorldNetwork();
	}
}