package weka.clusterers.forMetisMQI;

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

import weka.clusterers.forMetisMQI.coarse.Coarse;
import weka.clusterers.forMetisMQI.coarse.CoarserGraphElement;
import weka.clusterers.forMetisMQI.graph.Bisection;
import weka.clusterers.forMetisMQI.graph.Node;
import weka.clusterers.forMetisMQI.graph.UndirectedGraph;

public class GraphAlgorithms {

	public Bisection KL(UndirectedGraph g) {
		Bisection partition = new Bisection(g);
		Bisection result = partition;
		int bestEdgeCut = Integer.MAX_VALUE;
		Node u = partition.getCandidate();
		while (u != null) {
			partition.swap(u);
			if (partition.edgeCut() <= bestEdgeCut) {
				bestEdgeCut = partition.edgeCut();
				result = partition.copy();
			}
			u = partition.getCandidate();
		}
		return result;
	}

	public void METIS(UndirectedGraph g) {
//		MQI.viewGraph(g);
		Set<Set<Node>> clusters = new HashSet<Set<Node>>();
		for (int i = 0; i < 8; i++) {
			Coarse.setFinerSize(8);
			Stack<CoarserGraphElement> stack = Coarse.coarse(g);
			Bisection partition = null;
			if (stack.size() > 0) {
				partition = KL(stack.peek().getContracted());
//				System.out.println(partition.toString());
				partition = new Uncoarse().uncoarse(stack, partition);
//				System.out.println(partition.toString());
				Set<Node> cluster = MQI.mqi(partition);
				clusters.add(cluster);
//				Set<Set<Node>> foundCluster = new HashSet<Set<Node>>();
//				foundCluster.add(cluster);
//				MQI.viewClusters(g, foundCluster);
			}
		}
		MQI.viewClusters(g, clusters);
	}

}