package weka.clusterers.forMetisMQI;

import java.util.Iterator;
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;

public class Uncoarse {
	
	private static boolean projectedBelongs(Node u, Bisection partition, CoarserGraphElement cge) {
		Subgraph s = partition.getSubgraph();
		Node mappedNode = cge.getMap().get(u);
		return s.contains(mappedNode);
	}
	
	/**
	 * Given the projected graph and the partition of the coarser graph, it builds
	 * the projected partition.
	 * @param partition
	 * @param cge
	 */
	private static Bisection uncoarseOneStep(Bisection partition, CoarserGraphElement cge) {
		UndirectedGraph projected = cge.getProjected();
		Subgraph part = new Subgraph(projected);
		Iterator<Node> projectedIterator = projected.getVertices().iterator();
		while(projectedIterator.hasNext()) {
			Node u = projectedIterator.next();
			if(projectedBelongs(u,partition,cge))
				part.addVertex(u);
		}
		return new Bisection(part);
	}
	
	/**
	 * Given a bisection of the finer graph and the stack of graphs which yielded the finer graph,
	 * it returns the bisection projected into the coarser graph. 
	 * @param stack
	 * @param partition
	 * @return
	 */
	public static Bisection uncoarse(Stack<CoarserGraphElement> stack, Bisection partition) {
		while(stack.size() > 0) {
			CoarserGraphElement element = stack.pop();
			partition = uncoarseOneStep(partition,element);
		}
		return partition;
	}
}