package weka.clusterers.forMetisMQI;

import java.util.Stack;

public class GraphAlgorithms {
	
	public KLPartition KL(Graph g) {
		KLPartition partition = new KLPartition(g);
		KLPartition result = partition;
		int bestEdgeCut = Integer.MAX_VALUE;
		int u = partition.getCandidate();
		while(u != -1) {
			partition.swap(u);
			if(partition.edgeCut() <=  bestEdgeCut) {
				bestEdgeCut = partition.edgeCut();
				result = partition.clone();
			}
			u = partition.getCandidate();
		}
		return result;
	}
	
	public void METIS(Graph g) {
		KLPartition partition = null;
		Stack<CoarserGraphElement> stack = Coarse.coarse(g);
		
		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());
		}
		
	}

}