source: src/main/java/weka/clusterers/forMetisMQI/Uncoarse.java @ 20

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);
                        partition = GraphAlgorithms.KLRefinement(partition);
                }
                return partition;
        }
}