source: src/main/java/weka/clusterers/MetisMQIClusterer.java @ 22

package weka.clusterers;

import java.util.Enumeration;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.Vector;

import weka.clusterers.forMetisMQI.GraphAlgorithms;
import weka.clusterers.forMetisMQI.graph.Node;
import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
import weka.core.Attribute;
import weka.core.Capabilities;
import weka.core.Instance;
import weka.core.Instances;
import weka.core.Option;
import weka.core.OptionHandler;
import weka.core.Utils;
import weka.core.Capabilities.Capability;

public class MetisMQIClusterer extends AbstractClusterer implements
                OptionHandler {

        private int numberOfClusters = 2;

        private int sizeFinerGraph = 10;

        /**
         * It maps each cluster with an integer id.
         */
        private Map<Set<Node>, Integer> clustersMap = null;

        /**
         * Holds the cluster membership for each node.
         */
        private Map<Node, Integer> nodeMap = null;
        
        /**
         * True if a random bisection must be used.
         */
        private boolean randomBisection = false;

        /**
         * 
         */
        private static final long serialVersionUID = 1L;

        @Override
        public void buildClusterer(Instances data) throws Exception {
                getCapabilities().testWithFail(data);
                UndirectedGraph g = new UndirectedGraph();
                g.loadFromInstance(data);
                Set<Set<Node>> clusters = GraphAlgorithms.metisMqi(g, numberOfClusters,
                                sizeFinerGraph, randomBisection);
                setNumClusters(clusters.size());
                int i = 0;
                Iterator<Set<Node>> clusterIterator = clusters.iterator();
                clustersMap = new HashMap<Set<Node>, Integer>();
                nodeMap = new HashMap<Node, Integer>();
                while (clusterIterator.hasNext()) {
                        Set<Node> cluster = clusterIterator.next();
                        clustersMap.put(cluster, i);
                        Iterator<Node> nodeIterator = cluster.iterator();
                        while (nodeIterator.hasNext()) {
                                Node n = nodeIterator.next();
                                if (nodeMap.get(n) == null) {
                                        nodeMap.put(n, i);
                                }
                        }
                        i++;
                }
        }

        @Override
        public int clusterInstance(Instance instance) throws Exception {
                Attribute from = instance.dataset().attribute("from");
                Attribute to = instance.dataset().attribute("to");
                Instance edge = instance;
                Node node1 = new Node(Integer.toString(((int) Math.round(edge
                                .value(from)))));
                Node node2 = new Node(Integer.toString(((int) Math
                                .round(edge.value(to)))));
                if (nodeMap.get(node1) == nodeMap.get(node2))
                        return nodeMap.get(node1);
                else
                        throw new Exception();
        }

        /**
         * Parses a given list of options.
         * <p/>
         * 
         * <!-- options-start --> Valid options are:
         * <p/>
         * 
         * <pre>
         * -N &lt;num&gt;
         *  number of clusters.
         *  (default 2).
         * </pre>
         * 
         * <pre>
         * -S
         *  Maximum size of the finer graph during the coarsening phase.
         * </pre>
         * 
         * <!-- options-end -->
         * 
         * @param options
         *            the list of options as an array of strings
         * @throws Exception
         *             if an option is not supported
         */
        @Override
        public void setOptions(String[] options) throws Exception {
                String optionString = Utils.getOption('N', options);
                if (optionString.length() != 0) {
                        setNumClusters(Integer.parseInt(optionString));
                }
                optionString = Utils.getOption('S', options);
                if (optionString.length() != 0) {
                        setSizeFinerGraph(Integer.parseInt(optionString));
                }
                optionString = Utils.getOption('R', options);
                setRandomBisection(Boolean.parseBoolean(optionString));
        }

        private void setRandomBisection(boolean b) {
                this.randomBisection = b;
        }

        /**
         * Gets the current settings of MetisMQIClusterer
         * 
         * @return an array of strings suitable for passing to setOptions()
         */
        @SuppressWarnings("unchecked")
        @Override
        public String[] getOptions() {
                Vector result;
                result = new Vector();
                result.add("-N");
                result.add("" + getNumClusters());
                result.add("-S");
                result.add("" + getSizeFinerGraph());
                result.add("-R");
                return (String[]) result.toArray(new String[result.size()]);
        }

        private int getSizeFinerGraph() {
                return sizeFinerGraph;
        }

        private int getNumClusters() {
                return numberOfClusters;
        }

        /**
         * Returns an enumeration describing the available options.
         * 
         * @return an enumeration of all the available options.
         */
        @SuppressWarnings("unchecked")
        @Override
        public Enumeration listOptions() {
                Vector result = new Vector();
                result.addElement(new Option("\tnumber of clusters.\n"
                                + "\t(default 2).", "N", 1, "-N <num>"));
                result.addElement(new Option("\tsize of finer graph.\n"
                                + "\t(default 10).", "S", 1, "-S <num>"));
                return result.elements();
        }

        private void setSizeFinerGraph(int size) {
                this.sizeFinerGraph = size;
        }

        private void setNumClusters(int n) {
                this.numberOfClusters = n;
        }

        @Override
        public double[] distributionForInstance(Instance instance) throws Exception {
                double[] d = new double[numberOfClusters()];
                d[clusterInstance(instance)] = 1.0;
                return d;
        }

        @Override
        public Capabilities getCapabilities() {
                Capabilities result = super.getCapabilities();
                result.enable(Capability.NUMERIC_ATTRIBUTES);
                result.enable(Capability.NO_CLASS);
                return result;
        }

        @Override
        public int numberOfClusters() throws Exception {
                return numberOfClusters;
        }

        /**
         * Main method for executing this clusterer.
         * 
         * @param args
         *            the options, use "-h" to display options
         */
        public static void main(String[] args) {
                AbstractClusterer.runClusterer(new MetisMQIClusterer(), args);
        }

}