package weka.clusterers.forMetisMQI;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.Stack;

import weka.clusterers.forMetisMQI.graph.Bisection;
import weka.clusterers.forMetisMQI.graph.Node;
import weka.clusterers.forMetisMQI.graph.Subgraph;
import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
import weka.clusterers.forMetisMQI.util.CoarserGraphElement;
import weka.clusterers.forMetisMQI.util.Configuration;
import weka.clusterers.forMetisMQI.util.GraphsFrame;
import weka.clusterers.forMetisMQI.util.Util;

public class GraphAlgorithms {

	
	static public Bisection KLRefinement(Bisection b) {
		int remainingNumberOfSwap = 50;
		Bisection partition = b;
		Bisection result = partition;
		int bestEdgeCut = partition.edgeCut();
		Node u = partition.getCandidate();
		while (u != null && remainingNumberOfSwap > 0) {
			partition.swap(u);
			if (partition.edgeCut() <= bestEdgeCut) {
				bestEdgeCut = partition.edgeCut();
				result = partition.clone();
				remainingNumberOfSwap = 50;
			} else
				remainingNumberOfSwap--;
			u = partition.getCandidate();
		}
		return result;
	}
	
	
	/**
	 * Given an undirected graph, performs the Kernighan-Li algorithm to find a bisection and
	 * then returns it.
	 * @param g
	 * @return
	 */
	static public Bisection KL(UndirectedGraph g) {
		int remainingNumberOfSwap = 50;
		Bisection partition = new Bisection(g);
		Bisection result = partition;
		int bestEdgeCut = partition.edgeCut();
		Node u = partition.getCandidate();
		while (u != null && remainingNumberOfSwap > 0) {
			partition.swap(u);
			if (partition.edgeCut() <= bestEdgeCut) {
				bestEdgeCut = partition.edgeCut();
				result = partition.clone();
				remainingNumberOfSwap = 50;
			} else
				remainingNumberOfSwap--;
			u = partition.getCandidate();
		}
		return result;
	}
	
	static public Bisection metis(UndirectedGraph g, int sizeFinerGraph) {
		Coarse.setFinerSize(sizeFinerGraph);
		Stack<CoarserGraphElement> stack = Coarse.coarse(g);
		Bisection partition = null;
		if (stack.size() > 0) {
			partition = KL(stack.peek().getContracted());
			if(Configuration.instance().getVerboseLevel() > 1) {
				GraphsFrame.instance().addPanel(Util.panelContractedGraph(stack.peek()));
				GraphsFrame.instance().addPanel(Util.panelContractedGraph(stack.peek(),partition.getSmallerSubgraph().createInducedSubgraph().getVertices()));
			}
			partition = Uncoarse.uncoarse(stack, partition);
		}
		return partition;
	}

	/**
	 * Given an UndirectedGraph, runs metis+mqi for <code>numberOfCluster</code> times and
	 * returns a set of clusters. With the third parameter you can control the maximum size of the finer
	 * graph during the coarsening phase.  
	 * @param g
	 * @param numberOfCluster
	 * @param sizeFinerGraph
	 */
	static public Set<Set<Node>> metisMqi(UndirectedGraph g) {
		int numberOfCluster = Configuration.instance().getNumberOfClusters();
		boolean randomBisection = Configuration.instance().isRandomBisection();
		int sizeFinerGraph = Configuration.instance().getSizeFinerGraph();
		int verboseLevel = Configuration.instance().getVerboseLevel();
		GraphsFrame gf = GraphsFrame.instance();
		System.out.println("Vertex count: " + g.getVertexCount());
		System.out.println("Edges count: " + g.getEdgeCount());
		Set<Set<Node>> clusters = new HashSet<Set<Node>>();
		UndirectedGraph gclone = g.clone();
		for (int i = 0; i < numberOfCluster; i++) {
			Bisection bisection = null;
			if(verboseLevel > 1)
				gf.addPanel(Util.panelGraph(g.clone()));
			if(!randomBisection)
				bisection = metis(g,sizeFinerGraph);
			else
				bisection = new Bisection(g);
			
			if(verboseLevel > 1)
				gf.addPanel(Util.panelCluster(g.clone(),bisection.getSmallerSubgraph().createInducedSubgraph().getVertices()));
			
			System.out.print("Partizione iniziale: ");
			System.out.print("V1: " + bisection.getSubgraph().getVertexCount());
			System.out.print(" V2: " + bisection.getComplement().getVertexCount());
			System.out.println(" EC: " + bisection.edgeCut() * 0.5);
			System.out.println("Conductance: " + 
					((double)bisection.edgeCut() / 2) / Math.min(bisection.getSubgraph().totalDegree(),bisection.getComplement().totalDegree()));
			Set<Node> cluster = MQI.mqi(bisection,true);
			
			UndirectedGraph clusterGraph = new Subgraph(gclone,cluster).createInducedSubgraph();
			
//			System.out.println(cluster);
			Bisection mqiBisection = new Bisection(new Subgraph(g,cluster));
			System.out.println("Partizione raffinata (MQI)");
			double newConductance = ((double)mqiBisection.edgeCut() / 2) / Math.min(mqiBisection.getSubgraph().totalDegree(),mqiBisection.getComplement().totalDegree());
			System.out.println("Conductance: " + newConductance);
			
			System.out.println("CLUSTER "+ i + ":  V=" + clusterGraph.getVertexCount() + ", E=" + clusterGraph.getEdgeCount()+".");
			clusters.add(cluster);
			
			System.out.println();
			Iterator<Node> clustersNode = cluster.iterator();
			while(clustersNode.hasNext()){
				g.removeVertex(clustersNode.next());
			}
		}
		if(verboseLevel > 0)
			gf.addPanel(Util.panelClusters(gclone, clusters));
		gf.setVisible(true);
		return clusters;
	}

}