package weka.clusterers.forMetisMQI;

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;

import weka.core.Attribute;
import weka.core.Instance;
import weka.core.Instances;

public class Graph {
	
	protected static class NodeInfo {
		/** The weight of the node */
		protected int vwgt;
		/** The size of the adjacency list of the node */
		protected int nedges;
		/**
		 * The index into the adjacency list that is the beginning of the
		 * adjacency list of v
		 */
		protected int iedges;
		/** The weight of the edges that have been contracted to create the node */
		protected int cewgt;
		/** The sum of the weight of the edges adjacent to v */
		protected int adjwgt;

		public NodeInfo() {
			this.vwgt = 1;
			this.cewgt = 0;
			this.iedges = 0;
			this.nedges = 0;
			this.adjwgt = 0;

		}

		@Override
		public String toString() {
			return "Vwgt: " + vwgt + " Cewgt: " + cewgt + " Iedges: " + iedges
					+ " Nedges: " + nedges + " Adjwgt: " + adjwgt;
		}
	}

	/**
	 * Additional node info for all vertices..
	 */
	private List<NodeInfo> vtxs;
	/**
	 * Adjacency vector.
	 */
	private List<Integer> adjncy;
	/**
	 * Weights vector
	 */
	private List<Integer> weights;
	
	private HashMap<Integer,Integer> label;
	private HashMap<Integer,Integer> index;

	/**
	 * Build a new graph given a set of instances.
	 * 
	 * @param data
	 */
	public Graph(Instances data) {
		vtxs = new ArrayList<NodeInfo>();
		adjncy = new ArrayList<Integer>();
		weights = new ArrayList<Integer>();
		label = new HashMap<Integer,Integer>();
		index = new HashMap<Integer,Integer>();
		Iterator<Instance> dataIterator = data.iterator();
		Attribute from = data.attribute("from");
		Attribute to = data.attribute("to");
		if (from == null || to == null)
			throw new RuntimeException(
					"Unsupported data: check the list of attributes (from and to are needed).");
		while (dataIterator.hasNext()) {
			Instance edge = dataIterator.next();
			int node1 = (int) Math.round(edge.value(from));
			int node2 = (int) Math.round(edge.value(to));
			addNode(node1); addNode(node2);
			addEdgeUndirected(node1, node2, 1);
		}
	}

	public Graph() {
		vtxs = new ArrayList<NodeInfo>();
		adjncy = new ArrayList<Integer>();
		weights = new ArrayList<Integer>();
		label = new HashMap<Integer,Integer>();
		index = new HashMap<Integer,Integer>();
	}
	
	/**
	 * Returns an iterator over the nodes of the graph.
	 * @return
	 */
	public Iterator<Integer> iterator() {
		return label.keySet().iterator();
	}
	
	/**
	 * Returns the label associated with a given index.
	 * @param index
	 * @return
	 */
	private int getLabel(int index) {
		return this.index.get(index);
	}
	
	/**
	 * Returns the index associated with a given label.
	 * @param index
	 * @return
	 */
	private int getIndex(int label) {
		return this.label.get(label);
	}
	
	private void updateAssociation(int index, int label) {
		this.index.put(index,label);
		this.label.put(label,index);
	}
	
	/**
	 * Returns the weight of the edge (u,v).
	 * @param u
	 * @param v
	 * @return
	 */
	public int getWeight(int u, int v) {
		int i = getIndex(u);
		int istart = vtxs.get(i).iedges;
		int iend = vtxs.get(i).iedges + vtxs.get(i).nedges;
		int weight = -1; boolean found = false;
		for(int k = istart; k < iend && !found; k++) {
			if(adjncy.get(k) == v) {
				weight = weights.get(k);
				found = true;
		    }
		}
		return weight;
	}
	
	public void setWeight(int u, int v, int weight) {
		int i = getIndex(u);
		int j = getIndex(v);
		int istart = vtxs.get(i).iedges;
		int iend = istart + vtxs.get(i).nedges;
		for(int k = istart; k < iend; k++){
			if(adjncy.get(k) == v) {
				weights.set(k, weight);
			}
		}
		int jstart = vtxs.get(j).iedges;
		int jend = jstart + vtxs.get(j).nedges;
		for(int k = jstart; k < jend; k++){
			if(adjncy.get(k) == u)
				weights.set(k, weight);
		}
	}
	
	public NodeInfo getNode(int u) {
		int i = getIndex(u);
		return vtxs.get(i);
	}
	
	public int nedge() {
		return adjncy.size();
	}
	
	public boolean isNode(int u) {
		return label.containsKey(u);
	}
	
	public void addNode(int u) {
		if(!isNode(u)) {
			int index = size();
			updateAssociation(index, u);
			NodeInfo node = new NodeInfo();
			node.iedges = nedge();
			node.nedges = 0;
			node.vwgt = 1;
			node.adjwgt = 0;
			node.cewgt = 0;
			vtxs.add(index, node);
		}
	}
	
	public int size() {
		return vtxs.size();
	}
	
	public List<Integer> getNeighbors(int u) {
		int i = getIndex(u);
		List<Integer> neighbors = new ArrayList<Integer>();
		int istart = vtxs.get(i).iedges;
		int iend = vtxs.get(i).iedges + vtxs.get(i).nedges;
		for(int k = istart; k < iend; k++) {
			neighbors.add(adjncy.get(k));
		}
		return neighbors;
	}
	
	/**
	 * Return true if u is neighbor of v.
	 * @param u
	 * @param v
	 * @return
	 */
	public boolean isNeighbor(int u, int v){
		return getNeighbors(u).contains(v);
	}
	
	public void addEdgeUndirected(int i, int j, int w) {
		addEdgeDirectedl(i, j, w);
		addEdgeDirectedl(j, i, w);
	}
	
	/**
	 * Add an edge from i to j of weight w if previously it doesn't exists, otherwise
	 * simply update the weight of the edge.
	 * @param i
	 * @param j
	 * @param w
	 */
	public void addEdgeDirectedl(int u, int v, int w) {
		int i = getIndex(u);
		if(!isNeighbor(u,v)) {
			int istart = getNode(u).iedges;
			adjncy.add(istart,v);
			for(int k = i + 1; k < size(); k++) {
				vtxs.get(k).iedges++;
			}
			vtxs.get(i).nedges++;
			vtxs.get(i).adjwgt += w;
			weights.add(istart, w);
		} else
			setWeight(u, v, w);
	}
	
	public boolean isEdge(int u, int v) {
		int i = getIndex(u);
		int istart = vtxs.get(i).iedges;
		int iend = vtxs.get(i).iedges + vtxs.get(i).nedges;
		boolean found = false;
		for(int k = istart; k < iend && !found; k++) {
			found = (adjncy.get(k) == v);
		}
		return found;
	}

	/**
	 * Print the graph structure.
	 */
	public void printGraph(PrintStream io) {
		for(int i = 0; i < vtxs.size(); i++) {
			int u = getLabel(i);
			io.print("Node: " + u + " Neighbors: ");
			Iterator<Integer> neighbors = getNeighbors(u).iterator();
			while(neighbors.hasNext()) {
				int v = neighbors.next();
				io.print(v + " [w: " + getWeight(u, v) + "] ");
			}
			io.println(getNode(u).toString());
		}
	}
	
	/**
	 * Return a list containing a random permutation of the vertices.
	 * 
	 * @return a random permutation of vertices
	 */
	public List<Integer> vtxsPermutation() {
		Random r = Random.instance(); 
		List<Integer> perm = new ArrayList<Integer>();
		for (int i = 0; i < vtxs.size(); i++) {
			perm.add(getLabel(i));
		}
		for (int i = 0; i < perm.size(); i++) {
			int k = r.nextInt(perm.size());
			int swap = perm.get(k);
			perm.set(k, perm.get(i));
			perm.set(i, swap);
		}
		return perm;
	}
	
	/**
	 * Randomize the adjacency list.
	 */
	public void adjncyPermutation() {
		Random r = Random.instance();
		for (int i = 0; i < vtxs.size(); i++) {
			NodeInfo n = vtxs.get(i);
			for (int j = n.iedges; j < n.nedges + n.iedges; j++) {
				int k = r.nextInt(n.nedges) + n.iedges;
				int swap = adjncy.get(k);
				adjncy.set(k, adjncy.get(j));
				adjncy.set(j, swap);
				swap = weights.get(k);
				weights.set(k, weights.get(j));
				weights.set(j, swap);
			}
		}
	}
}