package weka.clusterers.forMetisMQI;

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;

public class GraphAlgorithms {
	
	boolean debug = true;
	PrintStream debugStream = System.err;
	
	/**
	 * Return true if the vertex v is matched
	 * 
	 * @param v
	 *            the index of the vertex
	 * @return true if the vertex v is matched, false o.w.
	 */
	private boolean isMatched(List<Integer> match, int v) {
		return match.get(v) != v;
	}

	private void RMMatch(Graph g, List<Integer> match, List<Integer> map) {
		int labelCounter = 0;
		for (int i = 0; i < g.size(); i++) {
			match.add(i);
			map.add(i);
		}
		g.adjncyPermutation();
		Iterator<Integer> nodeIterator = g.vtxsPermutation().iterator();
		while (nodeIterator.hasNext()) {
			int u = nodeIterator.next();
			if (debug)
				debugStream.println("Visiting node " + u + " Matched = " + isMatched(match,u));
			if (!isMatched(match,u)) {
				boolean foundMatch = false;
				int matchedNode = -1;
				Iterator<Integer> iterator = g.getNeighbors(u).iterator();
				while(iterator.hasNext() && !foundMatch){
					int v = iterator.next();
					if (!isMatched(match,v)) {
						matchedNode = v;
						foundMatch = true;
						if (debug)
							debugStream.println("Found a match with node "
									+ matchedNode);
					}
				}
				if (debug && !foundMatch)
					debugStream.println("There aren't unmatched neighbors.");
				if(foundMatch) {
					match.set(u, matchedNode);
					match.set(matchedNode, u);
					map.set(u, labelCounter);
					map.set(matchedNode, labelCounter);
					if(debug) debugStream.println("Contracting node " + u + " with " + matchedNode + ". Node id: " + map.get(u));
				} else
					map.set(u, labelCounter);
				labelCounter++;
			}
		}
	}
	
	/**
	 * Return a new contracted graph.
	 */
	private Graph contract(Graph g, List<Integer> match, List<Integer> map) {
		Graph output = new Graph();
		Iterator<Integer> iterator = g.iterator();
		while(iterator.hasNext()) {
			int u = iterator.next();
			output.addNode(map.get(u));
			Iterator<Integer> it = g.getNeighbors(u).iterator();
			Set<Integer> neighbors = new HashSet<Integer>();
			while(it.hasNext()) {
				int v = it.next();
				neighbors.add(map.get(v));
			}
			it = g.getNeighbors(match.get(u)).iterator();
			while(it.hasNext()) {
				int v = it.next();
				neighbors.add(map.get(v));
			}
			neighbors.remove(map.get(u));
			it = neighbors.iterator();
			while(it.hasNext()) {
				int v = it.next();
				output.addNode(v);
				output.addEdgeUndirected(map.get(u), v, 0);
			}
		}	
		//calcolo dei pesi del nuovo grafo: per ogni arco (u,v) && u < v.
		//w(map(u),map(v)) += w(u,v). 
		for(int u=0; u < g.size(); u++) {
			Iterator<Integer> it = g.getNeighbors(u).iterator();
			while(it.hasNext()) {
				int v = it.next();
				if(map.get(u) != map.get(v) && output.isEdge(map.get(u), map.get(v)) && u < v) {
					output.setWeight(map.get(u), map.get(v), output.getWeight(map.get(u), map.get(v)) + g.getWeight(u, v));
				}
			}
		}
		for(int u = 0; u < g.size(); u++) {
			if(isMatched(match,u)) {
				int v = match.get(u);
				if(u < v) {
					output.getNode(map.get(u)).vwgt = g.getNode(u).vwgt + g.getNode(v).vwgt;
					output.getNode(map.get(u)).cewgt = g.getNode(u).cewgt + g.getNode(v).cewgt +
					g.getWeight(u, v);
					output.getNode(map.get(u)).adjwgt = g.getNode(u).adjwgt + g.getNode(v).adjwgt - 2 *
					g.getWeight(u, v);
				}
			} else {
				output.getNode(map.get(u)).vwgt = g.getNode(u).vwgt;
				output.getNode(map.get(u)).cewgt = g.getNode(u).cewgt;
				output.getNode(map.get(u)).adjwgt = g.getNode(u).adjwgt;
			}
		}
		return output;
	}

	/**
	 * Performs the first stage of the METIS algorithm, using RM.
	 */
	private CoarserGraphElement coarseOneStep(Graph g) {
		List<Integer> match = new ArrayList<Integer>();
		List<Integer> map = new ArrayList<Integer>();
		RMMatch(g,match,map);
		g = contract(g,match,map);
		return new CoarserGraphElement(g, match, map);
	}
	
	public void coarse(Graph g) {
		int n = 1;
		Graph prev = g;
		CoarserGraphElement e;
		g.printGraph(System.out);
	    do {
	    	e = coarseOneStep(g);
	    	prev = g;
	    	g = e.getGraph();
	    	g.printGraph(System.out);
	    } while(prev.size() > g.size() && g.size() > n);
	}

}