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

public class Graph {
    ArrayList nodes;
    ArrayList degreeList;
    ArrayList levelList;
    Node root;
	int edges;
	int[] edgeHistogram;
	int[] levelHistogram;
    ArrayList pathSamples;

    Graph () {
		nodes = new ArrayList();
    }
    public void sortByDegree(boolean connectSubgraphs) {
		if (connectSubgraphs) {
			ArrayList graphs = getSubgraphs(); // Start w/ random nodes list?
			if(graphs.size()>1)
				System.out.println("!Multiple SubGraphs: "+graphs.size());
			connectSubgraphs(graphs);
		}

		// Sample the nodes
		ArrayList samples = new ArrayList(nodes);
		randShuffle(samples);
		int imax = Math.min(samples.size(),100);
		pathSamples = new ArrayList(imax);
		for (int i=0; i<imax; i++) {
			Node node = (Node)samples.get(i);
			node.traverse();
			pathSamples.add(node);
		}

		// Build degree list for nodes
		degreeList = new ArrayList(nodes);
		Collections.sort(degreeList, new Comparator() {
				public int compare(Object o1, Object o2) {
					int size1 = ((Node)o1).edges();
					int size2 = ((Node)o2).edges();
					return size1<size2?1:(size1>size2?-1:0);
				}
			});

		// Use max node for "root"
		root = (Node)degreeList.get(0);
		//		System.out.print("Root: "); root.print();
		root.traverse();

		// Collect root stats
		this.edges = 0;
		edgeHistogram = new int[nodes.size()];
		levelHistogram = new int[nodes.size()];
		for (Iterator it = nodes.iterator(); it.hasNext();) {
			Node node = (Node)it.next();
			assert(node.root()!=null,"Non connected graph");
			int edges = node.edges(), level = node.level();
			edgeHistogram[edges]++;
			this.edges += edges;
			levelHistogram[level]++;
		}
		this.edges /= 2;
		assert(root.nodeSum()==nodes.size(),"Traversal miss-count");
		assert(root.edgeSum()==edges,"Edge miss-count");

		// Root levels & median level
		levelList = new ArrayList(nodes);
		Collections.sort(levelList, new Comparator() {
				public int compare(Object o1, Object o2) {
					int size1 = size((Node)o1);
					int size2 = size((Node)o2);
					return size1<size2?-1:(size1>size2?1:0);
				}
				int size(Node n) {
					Node p = n.parent();
					return n.level()*nodes.size()+(p==null?0:p.ID());
				}
			});
    }
    public ArrayList getSubgraphs() {
		ArrayList graphs = new ArrayList();
		if (nodes.size()==0)
			return graphs;
		for (Iterator it=nodes.iterator(); it.hasNext();)
			((Node)it.next()).resetPath();
		for (Iterator it=nodes.iterator(); it.hasNext();) {
			Node n = (Node)it.next();
			if (n.root()==null) {
				n.traverse();
				graphs.add(n);
			}
		}
		return graphs;
	}
    public void connectSubgraphs(ArrayList graphs) {
		for (int i=0; i<(graphs.size()-1); i++) {
			Node n1 = (Node)graphs.get(i);
			Node n2 = (Node)graphs.get((i+1));
			n1.addEdge(n2);
			n2.addEdge(n1);
		}
	}
	static private Random RanGen = new Random(12345678);
	static public int randInt(int to) { // return int in [0, to)
		return RanGen.nextInt(to);
    }
	static public double randDouble() { // return double in [0, 1.0)
		return RanGen.nextDouble();
    }
    static String arg (String args[], int i, String s) {
		return (args.length<=i||args[i].equals("-"))?s:args[i];
    }
	static public void randShuffle(List list) {
		Collections.shuffle(list, RanGen);
    }
    public int size() {
		return nodes.size();
    }
    static public void assert(boolean test, String msg) {
		if ( !test ) {
			System.out.println("!!Assert Failure: "+msg+"; Sorry!");
			System.exit(1);
		}
    }
    public void printGrid() {
		System.out.print("   ");
		for (int i=0; i<nodes.size(); i++)
			System.out.print((i<10?" ":"")+i+" ");
		System.out.println();
		System.out.print("   ");
		for (int i=0; i<nodes.size(); i++)
			System.out.print("---");
		System.out.println();

		for (int i=0; i<nodes.size(); i++) {
			System.out.print((i<10?" ":"")+i+"|");
			int[] ii = new int[nodes.size()];
			Node n = (Node)nodes.get(i);
			for (Iterator it = n.edgeList().iterator(); it.hasNext();) {
				int id = ((Node)it.next()).ID();
				ii[id] = 1;
			}
			for (int j=0; j<nodes.size(); j++)
				System.out.print(" "+(ii[j]==0?" ":"x")+" ");
			System.out.println();
		}
	}
    public void print() {
		print(nodes);
    }
    public void printByDegree() {
		print(degreeList);
    }
    public void printByLevel() {
		print(levelList);
    }
    public void print(ArrayList nodes) {
		System.out.println("Nodes size="+nodes.size());
		for (Iterator it = nodes.iterator(); it.hasNext();)
			((Node)it.next()).print();
    }
    public void printHist(String title) { //REMIND: Rename! printEdgeHistogram
    	System.out.println(title);
		int[] hist = getEdgeHistogram();
		int edgeSum = 0;
		for (int i=0; i<hist.length; i++)
			if (hist[i] != 0) {
				System.out.print(i+":"+hist[i]+"\t");
				edgeSum += i*hist[i];
			}
    	System.out.println("\nTotals: Nodes="+nodes.size()
						   +", Edges="+(edgeSum/2));
    }
    public int[] getEdgeHistogram() {
		int[] hist = new int[nodes.size()];
		for (Iterator it = nodes.iterator(); it.hasNext();)
			hist[((Node)it.next()).edges()]++;
		return hist;
    }
    public int[] getLevelsHistogram() {
		int[] hist = new int[nodes.size()];
		for (Iterator it = nodes.iterator(); it.hasNext();)
			hist[((Node)it.next()).level()]++;
		return hist;
    }
    public void printLevels(String title) {
    	System.out.println(title);
		for (int i=0; i<levelHistogram.length; i++)
			if (levelHistogram[i] != 0)
				System.out.print(i+":"+levelHistogram[i]+"\t");
		System.out.println();
		System.out.println("Level Totals: Max/Avg/Med="+root.pathMax()
						   +"/"+root.pathAvg()
						   +"/"+root.pathMed()
						   +"; Nodes="+nodes.size()
						   +", Edges="+edges);
		printPathSamples("Path Samples");
    }
    public double clusterCoeff() {
		double G = 0.0;
		for (Iterator it = pathSamples.iterator(); it.hasNext();)
			G += ((Node)it.next()).clusterCoeff();
		return Node.lop(G/pathSamples.size());
	}
    public void printPathSamples(String title) {
    	System.out.println(title+" [pathMax:pathAvg:pathMed|edges:cCoef] root="
						   +root.pathMax()
						   +":"+root.pathAvg()
						   +":"+root.pathMed()
						   +"|"+root.edges()
						   +":"+root.clusterCoeff());
		for (Iterator it = pathSamples.iterator(); it.hasNext();) {
			Node node = (Node)it.next();
			System.out.print(node.pathMax()
							 +":"+node.pathAvg()
							 +":"+node.pathMed()
							 +"|"+node.edges()
							 +":"+node.clusterCoeff()+"  ");
		}
		System.out.println();
		printSearchSamples("Searches:");
    }
    public void printSearchSamples(String title) {
    	System.out.println(title+"id->id:PowerLaw/DepthFst/BreadthFst/Shortest"
						   +":Path-Max/Avg/Med");
		int pathSum=0, path0Sum=0, path1Sum=0, path2Sum=0, 
			maxSum=0, medSum=0, diameter=0;
		double avgSum=0.0;
		for (Iterator it = pathSamples.iterator(); it.hasNext();) {
			Node node = (Node)it.next();
			int id = randInt(nodes.size());
			//NOTE: Use 1+searchpath .. so log scale plots work.
			//..i.e. origin 1 rather than origin 0
			int pathLen0 = 1+node.searchPowerLaw(id);
			int pathLen1 = 1+node.searchDepthFirst(id);
			int pathLen2 = 1+node.searchBreadthFirst(id);
			int pathLen  = node.pathLength(id);
			System.out.print(node.ID()+"->"+id
							 +":"+pathLen0
							 +"/"+pathLen1
							 +"/"+pathLen2
							 +"/"+pathLen
							 +":"+node.pathMax()
							 +"/"+node.pathAvg()
							 +"/"+node.pathMed()
							 +"     ");
			pathSum  += pathLen;
			path0Sum += pathLen0;
			path1Sum += pathLen1;
			path2Sum += pathLen2;
			maxSum += node.pathMax();
			avgSum += node.pathAvg();
			medSum += node.pathMed();
			diameter = Math.max(diameter, node.pathMax());
		}
		System.out.println("\nAverages["+pathSamples.size()
						   +"]: PL/DFst/BFst/Min="
						   +dAvg(path0Sum, pathSamples.size())
						   +"/"+dAvg(path1Sum, pathSamples.size())
						   +"/"+dAvg(path2Sum, pathSamples.size())
						   +"/"+dAvg(pathSum, pathSamples.size())
						   +"; Path-Max/Avg/Med="
						   +dAvg(maxSum, pathSamples.size())
						   +"/"+dAvg(avgSum, pathSamples.size())
						   +"/"+dAvg(medSum, pathSamples.size())
						   );
		System.out.println("Small World Averages["+pathSamples.size()
						   +"]: cCoef/charPath/Diam="+clusterCoeff()
						   +"/"+dAvg(medSum, pathSamples.size())
						   +"/"+diameter
						   );
    }
	static public double dAvg(int i, int n) {
		return dAvg((double)i, n);
    }
	static public double dAvg(double d, int n) {
		return Node.lop(d/n);
    }
}