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

package weka.clusterers.forMetisMQI;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

import weka.clusterers.forMetisMQI.graph.Bisection;
import weka.clusterers.forMetisMQI.graph.Node;
import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
import weka.clusterers.forMetisMQI.util.CoarserGraphElement;
import weka.clusterers.forMetisMQI.util.Util;

public class GraphAlgorithms {

        
        /**
         * Given an undirected graph, performs the Kernighan-Li algorithm to find a bisection and
         * then returns it.
         * @param g
         * @return
         */
        static 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;
        }
        
        static public Bisection metis(UndirectedGraph g, int sizeFinerGraph) {
                Coarse.setFinerSize(sizeFinerGraph);
                Stack<CoarserGraphElement> stack = Coarse.coarse(g);
                Bisection partition = null;
                if (stack.size() > 0) {
                        partition = KL(stack.peek().getContracted());
                        partition = Uncoarse.uncoarse(stack, partition);
                }
                return partition;
        }

        /**
         * Given an UndirectedGraph, runs metis+mqi for <code>numberOfCluster</code> times and
         * returns a set of clusters. With the third parameter you can control the maximum size of the finer
         * graph during the coarsening phase.  
         * @param g
         * @param numberOfCluster
         * @param sizeFinerGraph
         */
        static public Set<Set<Node>> metisMqi(UndirectedGraph g, int numberOfCluster, int sizeFinerGraph) {
                Set<Set<Node>> clusters = new HashSet<Set<Node>>();
                for (int i = 0; i < numberOfCluster; i++) {
                        Bisection partition = metis(g,sizeFinerGraph);
                        Set<Node> cluster = MQI.mqi(partition);
                        clusters.add(cluster);
                }
                return clusters;
        }

}