import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

/**
 * This is the RandomGraph class. It can build a random graph in one of several ways
 * and keep track of the vertices and connected components. 
 *
 */
public class RandomGraph {
	private List<Vertex> vertexList;
	private Random rand;
	private LinkedList<Component> componentList;
	private int edges;
	private int verts;

	/**
	 * Builds a RandomGraph with n vertices and m edges using a multigraph process.
	 */
	public RandomGraph(int n, int m) {
		rand = new Random();
		edges = m;
		verts = n;
		populateVertices(n);
		multigraphProcess(m);
	}

	/**
	 * Builds a random graph with n vertices and places an edge between two vertices with
	 * probability lambda/n.
	 */
	public RandomGraph(int n, double lambda) {
		rand = new Random();
		verts = n;
		populateVertices(n);
		edges = rvProcess(lambda);
		componentList = new LinkedList<Component>();
		generateComponents();
	}

	/**
	 * Creates the set of vertices in this random graph.
	 */
	public void populateVertices(int n) {
		vertexList = new LinkedList<Vertex>();
		for (int i = 0; i < n; i++) {
			Vertex v = new Vertex(i);
			vertexList.add(v);
		}
	}

	/**
	 * Generates the components using a depth-first recursive approach through the list of
	 * vertices, marking ones that have already been visited.
	 */
	public void generateComponents() {
		boolean[] vertTouchedList = new boolean[verts];

		for (int i = 0; i < verts; i++) {
			if (!vertTouchedList[i]) {
				Vertex v = vertexList.get(i);
				Component c = new Component();
				buildComponent(c, v, vertTouchedList);
				c.countEdges();
				componentList.add(c);
			}
		}
	}

	public void buildComponent(Component c, Vertex root, boolean[] touchedList) {
		c.addVertex(root);
		touchedList[root.getId()] = true;
		for (Vertex v : root.getLocalVertices()) {
			if (!touchedList[v.getId()]) {
				buildComponent(c, v, touchedList);
			}
		}
	}

	/**
	 * Builds the random graph with n vertices by adding a edge between two vertices
	 * with probability lambda/n.
	 */
	public int rvProcess(double lambda) {
		double val;
		Vertex v1;
		Vertex v2;
		int totalEdges = 0;
		double param = lambda / vertexList.size();
		for (int i = 0; i < vertexList.size(); i++) {
			for (int j = i + 1; j < vertexList.size(); j++) {
				val = rand.nextDouble();
				if (val < param) {
					v1 = vertexList.get(i);
					v2 = vertexList.get(j);
					Edge.addEdge(v1, v2);
					totalEdges++;
				}
			}
		}
		return totalEdges;
	}

	/**
	 * Builds a random multigraph with n vertices and m edges. The edges are chosen by
	 * uniformly choosing two random vertices m different times. Two vertices can
	 * be chosen more than once or an edge can be placed connecting the same vertex to itself.
	 */
	public void multigraphProcess(int m) {
		edges = m;
		componentList = new LinkedList<Component>();
		for (int i = 0; i < m; i++) {
			addRandomEdge();
		}
		for (Vertex v : vertexList) {
			if (!componentList.contains(v.getComponent())) {
				componentList.add(v.getComponent());
			}
		}
	}

	// Adds an edge randomly between two vertices, not allowing for multigraphs.
	public boolean addRandomEdge() {
		int index1 = rand.nextInt(vertexList.size());
		int index2 = rand.nextInt(vertexList.size());
		Vertex v1 = vertexList.get(index1);
		Vertex v2 = vertexList.get(index2);
		return v1.addEdge(v2);
	}

	/**
	 * Determines and returns the largest component of this random graph.
	 * @return
	 */
	public Component getLargestComponent() {
		int size = 0;
		Component largest = null;
		if (componentList.size() == 0) {
			return null;
		}
		largest = componentList.getFirst();
		size = largest.getNumVerts();
		for (Component c : componentList) {
			if (c.getNumVerts() > size) {
				largest = c;
				size = largest.getNumVerts();
			}
		}
		return largest;
	}

	@SuppressWarnings("unchecked")
	public Component getComponent(int rank) {
		Collections.sort(componentList);
		return componentList.get(componentList.size() - rank);
	}

	@Override
	public String toString() {
		String list = "[";
		for (int i = 1; i < edges; i++) {
			int count = 0;
			boolean more = false;
			for (Component c : componentList) {
				if (c.excess() == i) {
					count++;
				} else if (c.excess() > i) {
					more = true;
				}
			}
			if (i + 1 == edges || !more) {
				list += count + "]";
				i = edges;
			} else {
				list += count + ",";
			}
		}
		list += " Largest: " + getLargestComponent();
		return list;
	}

	/**
	 * Gets the number of components of this RandomGraph of a certain size and excess.
	 */
	public int getNumComponents(int size, int excess) {
		int count = 0;
		for (Component c : componentList) {
			if (c.getNumVerts() == size && c.excess() == excess) {
				count++;
			}
		}
		return count;
	}
}
