source: src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java @ 12

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);
        }

}