package weka.clusterers.forMetisMQI;

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);
		Bisection partition = null;
		Coarse.setFinerSize(8);
		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());
		}
		System.out.println("AAAAAA");
		System.out.println(MQI.mqi(partition).toString());
		
	}

}