Changeset 14


Ignore:
Timestamp:
Sep 17, 2010, 1:09:06 PM (14 years ago)
Author:
gnappo
Message:

Ulteriori refactoring. Creato il clusterer metisMqi, con opzioni.

Location:
src/main/java/weka/clusterers
Files:
2 added
1 deleted
4 edited
2 copied
1 moved

Legend:

Unmodified
Added
Removed

  • src/main/java/weka/clusterers/MetisMQIClusterer.java

    r11 r14  
    11package weka.clusterers;
    22
     3import java.util.Enumeration;
     4import java.util.HashMap;
     5import java.util.Iterator;
     6import java.util.Map;
     7import java.util.Set;
     8import java.util.Vector;
    39
    410import weka.clusterers.forMetisMQI.GraphAlgorithms;
     11import weka.clusterers.forMetisMQI.graph.Node;
    512import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
     13import weka.core.Attribute;
    614import weka.core.Capabilities;
    715import weka.core.Instance;
    816import weka.core.Instances;
     17import weka.core.Option;
     18import weka.core.OptionHandler;
     19import weka.core.Utils;
    920import weka.core.Capabilities.Capability;
    1021
    11 public class SimpleClusterer extends AbstractClusterer {
    12 
    13         private int numberOfClusters = 0;
     22public class MetisMQIClusterer extends AbstractClusterer implements
     23                OptionHandler {
     24
     25        private int numberOfClusters = 2;
     26
     27        private int sizeFinerGraph = 10;
     28
     29        /**
     30         * It maps each cluster with an integer id.
     31         */
     32        private Map<Set<Node>, Integer> clustersMap = null;
     33
     34        /**
     35         * Holds the cluster membership for each node.
     36         */
     37        private Map<Node, Integer> nodeMap = null;
    1438
    1539        /**
    … …  
    2145        public void buildClusterer(Instances data) throws Exception {
    2246                getCapabilities().testWithFail(data);
    23                
    2447                UndirectedGraph g = new UndirectedGraph();
    2548                g.loadFromInstance(data);
    26                 GraphAlgorithms ga = new GraphAlgorithms();
    27                 ga.METIS(g);
    28                 numberOfClusters = 1;
     49                Set<Set<Node>> clusters = GraphAlgorithms.metisMqi(g, numberOfClusters,
     50                                sizeFinerGraph);
     51                setNumClusters(clusters.size());
     52                int i = 0;
     53                Iterator<Set<Node>> clusterIterator = clusters.iterator();
     54                clustersMap = new HashMap<Set<Node>, Integer>();
     55                nodeMap = new HashMap<Node, Integer>();
     56                while (clusterIterator.hasNext()) {
     57                        Set<Node> cluster = clusterIterator.next();
     58                        clustersMap.put(cluster, i);
     59                        Iterator<Node> nodeIterator = cluster.iterator();
     60                        while (nodeIterator.hasNext()) {
     61                                Node n = nodeIterator.next();
     62                                if (nodeMap.get(n) == null) {
     63                                        nodeMap.put(n, i);
     64                                }
     65                        }
     66                        i++;
     67                }
    2968        }
    3069
    3170        @Override
    3271        public int clusterInstance(Instance instance) throws Exception {
    33                 return 0;
    34         }
    35 
    36         @Override
    37         public double[] distributionForInstance(Instance instance)
    38         throws Exception {
     72                Attribute from = instance.dataset().attribute("from");
     73                Attribute to = instance.dataset().attribute("to");
     74                Instance edge = instance;
     75                Node node1 = new Node(Integer.toString(((int) Math.round(edge
     76                                .value(from)))));
     77                Node node2 = new Node(Integer.toString(((int) Math
     78                                .round(edge.value(to)))));
     79                if (nodeMap.get(node1) == nodeMap.get(node2))
     80                        return nodeMap.get(node1);
     81                else
     82                        throw new Exception();
     83        }
     84
     85        /**
     86         * Parses a given list of options.
     87         * <p/>
     88         *
     89         * <!-- options-start --> Valid options are:
     90         * <p/>
     91         *
     92         * <pre>
     93         * -N &lt;num&gt;
     94         *  number of clusters.
     95         *  (default 2).
     96         * </pre>
     97         *
     98         * <pre>
     99         * -S
     100         *  Maximum size of the finer graph during the coarsening phase.
     101         * </pre>
     102         *
     103         * <!-- options-end -->
     104         *
     105         * @param options
     106         *            the list of options as an array of strings
     107         * @throws Exception
     108         *             if an option is not supported
     109         */
     110        @Override
     111        public void setOptions(String[] options) throws Exception {
     112                String optionString = Utils.getOption('N', options);
     113                if (optionString.length() != 0) {
     114                        setNumClusters(Integer.parseInt(optionString));
     115                }
     116                optionString = Utils.getOption('S', options);
     117                if (optionString.length() != 0) {
     118                        setSizeFinerGraph(Integer.parseInt(optionString));
     119                }
     120        }
     121
     122        /**
     123         * Gets the current settings of MetisMQIClusterer
     124         *
     125         * @return an array of strings suitable for passing to setOptions()
     126         */
     127        @SuppressWarnings("unchecked")
     128        @Override
     129        public String[] getOptions() {
     130                Vector result;
     131                result = new Vector();
     132                result.add("-N");
     133                result.add("" + getNumClusters());
     134                result.add("-S");
     135                result.add("" + getSizeFinerGraph());
     136                return (String[]) result.toArray(new String[result.size()]);
     137        }
     138
     139        private int getSizeFinerGraph() {
     140                return sizeFinerGraph;
     141        }
     142
     143        private int getNumClusters() {
     144                return numberOfClusters;
     145        }
     146
     147        /**
     148         * Returns an enumeration describing the available options.
     149         *
     150         * @return an enumeration of all the available options.
     151         */
     152        @SuppressWarnings("unchecked")
     153        @Override
     154        public Enumeration listOptions() {
     155                Vector result = new Vector();
     156                result.addElement(new Option("\tnumber of clusters.\n"
     157                                + "\t(default 2).", "N", 1, "-N <num>"));
     158                result.addElement(new Option("\tsize of finer graph.\n"
     159                                + "\t(default 10).", "S", 1, "-S <num>"));
     160                return result.elements();
     161        }
     162
     163        private void setSizeFinerGraph(int size) {
     164                this.sizeFinerGraph = size;
     165        }
     166
     167        private void setNumClusters(int n) {
     168                this.numberOfClusters = n;
     169        }
     170
     171        @Override
     172        public double[] distributionForInstance(Instance instance) throws Exception {
    39173                double[] d = new double[numberOfClusters()];
    40174                d[clusterInstance(instance)] = 1.0;
    … …  
    62196         */
    63197        public static void main(String[] args) {
    64                 AbstractClusterer.runClusterer(new SimpleClusterer(), args);
     198                AbstractClusterer.runClusterer(new MetisMQIClusterer(), args);
    65199        }
    66200

  • src/main/java/weka/clusterers/forMetisMQI/Coarse.java

    r11 r14  
    1 package weka.clusterers.forMetisMQI.coarse;
     1package weka.clusterers.forMetisMQI;
    22
    33import java.io.PrintStream;
    … …  
    1212import weka.clusterers.forMetisMQI.graph.Node;
    1313import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
     14import weka.clusterers.forMetisMQI.util.CoarserGraphElement;
    1415
    1516import edu.uci.ics.jung.graph.util.Pair;

  • src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java

    r12 r14  
    55import java.util.Stack;
    66
    7 import weka.clusterers.forMetisMQI.coarse.Coarse;
    8 import weka.clusterers.forMetisMQI.coarse.CoarserGraphElement;
    97import weka.clusterers.forMetisMQI.graph.Bisection;
    108import weka.clusterers.forMetisMQI.graph.Node;
    119import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
     10import weka.clusterers.forMetisMQI.util.CoarserGraphElement;
     11import weka.clusterers.forMetisMQI.util.Util;
    1212
    1313public class GraphAlgorithms {
    1414
    15         public Bisection KL(UndirectedGraph g) {
     15       
     16        /**
     17         * Given an undirected graph, performs the Kernighan-Li algorithm to find a bisection and
     18         * then returns it.
     19         * @param g
     20         * @return
     21         */
     22        static public Bisection KL(UndirectedGraph g) {
    1623                Bisection partition = new Bisection(g);
    1724                Bisection result = partition;
    … …  
    2835                return result;
    2936        }
     37       
     38        static public Bisection metis(UndirectedGraph g, int sizeFinerGraph) {
     39                Coarse.setFinerSize(sizeFinerGraph);
     40                Stack<CoarserGraphElement> stack = Coarse.coarse(g);
     41                Bisection partition = null;
     42                if (stack.size() > 0) {
     43                        partition = KL(stack.peek().getContracted());
     44                        partition = Uncoarse.uncoarse(stack, partition);
     45                }
     46                return partition;
     47        }
    3048
    31         public void METIS(UndirectedGraph g) {
    32 //              MQI.viewGraph(g);
     49        /**
     50         * Given an UndirectedGraph, runs metis+mqi for <code>numberOfCluster</code> times and
     51         * returns a set of clusters. With the third parameter you can control the maximum size of the finer
     52         * graph during the coarsening phase. 
     53         * @param g
     54         * @param numberOfCluster
     55         * @param sizeFinerGraph
     56         */
     57        static public Set<Set<Node>> metisMqi(UndirectedGraph g, int numberOfCluster, int sizeFinerGraph) {
    3358                Set<Set<Node>> clusters = new HashSet<Set<Node>>();
    34                 for (int i = 0; i < 8; i++) {
    35                         Coarse.setFinerSize(8);
    36                         Stack<CoarserGraphElement> stack = Coarse.coarse(g);
    37                         Bisection partition = null;
    38                         if (stack.size() > 0) {
    39                                 partition = KL(stack.peek().getContracted());
    40 //                              System.out.println(partition.toString());
    41                                 partition = new Uncoarse().uncoarse(stack, partition);
    42 //                              System.out.println(partition.toString());
    43                                 Set<Node> cluster = MQI.mqi(partition);
    44                                 clusters.add(cluster);
    45 //                              Set<Set<Node>> foundCluster = new HashSet<Set<Node>>();
    46 //                              foundCluster.add(cluster);
    47 //                              MQI.viewClusters(g, foundCluster);
    48                         }
     59                for (int i = 0; i < numberOfCluster; i++) {
     60                        Bisection partition = metis(g,sizeFinerGraph);
     61                        Set<Node> cluster = MQI.mqi(partition);
     62                        clusters.add(cluster);
    4963                }
    50                 MQI.viewClusters(g, clusters);
     64                return clusters;
    5165        }
    5266

  • src/main/java/weka/clusterers/forMetisMQI/MQI.java

    r12 r14  
    2323import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
    2424import edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow;
     25import edu.uci.ics.jung.algorithms.layout.FRLayout;
    2526import edu.uci.ics.jung.algorithms.layout.KKLayout;
    2627import edu.uci.ics.jung.algorithms.layout.Layout;
    … …  
    3536        static int i = -1;
    3637       
    37         public static void viewClusters(Graph<Node, Edge> g, Set<Set<Node>> clusters) {
    38                 Layout<Node, Edge> layout = new KKLayout<Node, Edge>(g);
    39                 layout.setSize(new Dimension(800, 600)); // sets the initial size of the space
    40                 // The BasicVisualizationServer<V,E> is parameterized by the edge types
    41                 BasicVisualizationServer<Node, Edge> vv = new BasicVisualizationServer<Node, Edge>(
    42                                 layout);
    43 
    44                 class VertexPaintTransformer implements Transformer<Node, Paint> {
    45                         Set<Set<Node>> clusters = null;
    46                         Map<Set<Node>, Color> clustersColor = null;
    47 
    48                         public Set<Node> getCluster(Node node) {
    49                                 Iterator<Set<Node>> clusterIterator = clusters.iterator();
    50                                 while (clusterIterator.hasNext()) {
    51                                         Set<Node> cluster = clusterIterator.next();
    52                                         if (cluster.contains(node))
    53                                                 return cluster;
    54                                 }
    55                                 return null;
    56                         }
    57 
    58                         public VertexPaintTransformer(Set<Set<Node>> clusters) {
    59                                 this.clusters = clusters;
    60                                 clustersColor = new HashMap<Set<Node>, Color>(clusters.size());
    61                                 Iterator<Set<Node>> clusterIterator = clusters.iterator();
    62                                 while (clusterIterator.hasNext()) {
    63                                         Set<Node> cluster = clusterIterator.next();
    64                                         clustersColor.put(cluster, new Color(Random.instance()
    65                                                         .nextInt(256), Random.instance().nextInt(256),
    66                                                         Random.instance().nextInt(256)));
    67                                 }
    68                         }
    69 
    70                         public Paint transform(Node i) {
    71                                 Set<Node> cluster = getCluster(i);
    72                                 if (cluster == null)
    73                                         return Color.RED;
    74                                 else
    75                                         return clustersColor.get(getCluster(i));
    76                         }
    77                 }
    78 
    79                 Transformer<Node, Paint> vertexPaint = new VertexPaintTransformer(
    80                                 clusters);
    81                 vv.setPreferredSize(new Dimension(800, 600)); // Sets the viewing area
    82                                                                                                                 // size
    83                 vv.getRenderContext().setVertexLabelTransformer(
    84                                 new ToStringLabeller<Node>());
    85                 vv.getRenderContext().setEdgeLabelTransformer(
    86                                 new ToStringLabeller<Edge>());
    87                 vv.getRenderContext().setVertexFillPaintTransformer(vertexPaint);
    88                 JFrame frame = new JFrame("Graph View");
    89                 frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    90                 frame.getContentPane().add(vv);
    91                 frame.pack();
    92                 frame.setVisible(true);
    93         }
    94        
    95         public static void viewGraph(Graph<Node, Edge> g){
    96                 Layout<Node, Edge> layout = new KKLayout<Node, Edge>(g);
    97                 layout.setSize(new Dimension(800,600)); // sets the initial size of the space
    98                 // The BasicVisualizationServer<V,E> is parameterized by the edge types
    99                 BasicVisualizationServer<Node,Edge> vv =
    100                 new BasicVisualizationServer<Node,Edge>(layout);
    101                 vv.setPreferredSize(new Dimension(800,600)); //Sets the viewing area size
    102                 vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<Node>());
    103                 vv.getRenderContext().setEdgeLabelTransformer(new ToStringLabeller<Edge>());
    104 
    105                 JFrame frame = new JFrame("Simple Graph View");
    106                 frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    107                 frame.getContentPane().add(vv);
    108                 frame.pack();
    109                 frame.setVisible(true);
    110         }
    111 
    11238        static private Set<Node> BFSReversed(Node sink, DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) {
    11339                Set<Node> result = new HashSet<Node>();

  • src/main/java/weka/clusterers/forMetisMQI/Uncoarse.java

    r11 r14  
    44import java.util.Stack;
    55
    6 import weka.clusterers.forMetisMQI.coarse.CoarserGraphElement;
    76import weka.clusterers.forMetisMQI.graph.Bisection;
    87import weka.clusterers.forMetisMQI.graph.Node;
    98import weka.clusterers.forMetisMQI.graph.Subgraph;
    109import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
     10import weka.clusterers.forMetisMQI.util.CoarserGraphElement;
    1111
    1212public class Uncoarse {
    1313       
    14         private boolean projectedBelongs(Node u, Bisection partition, CoarserGraphElement cge) {
     14        private static boolean projectedBelongs(Node u, Bisection partition, CoarserGraphElement cge) {
    1515                Subgraph s = partition.getSubgraph();
    1616                Node mappedNode = cge.getMap().get(u);
    … …  
    2424         * @param cge
    2525         */
    26         public Bisection uncoarseOneStep(Bisection partition, CoarserGraphElement cge) {
     26        private static Bisection uncoarseOneStep(Bisection partition, CoarserGraphElement cge) {
    2727                UndirectedGraph projected = cge.getProjected();
    2828                Subgraph part = new Subgraph(projected);
    … …  
    3636        }
    3737       
    38         public Bisection uncoarse(Stack<CoarserGraphElement> stack, Bisection partition) {
     38        /**
     39         * Given a bisection of the finer graph and the stack of graphs which yielded the finer graph,
     40         * it returns the bisection projected into the coarser graph.
     41         * @param stack
     42         * @param partition
     43         * @return
     44         */
     45        public static Bisection uncoarse(Stack<CoarserGraphElement> stack, Bisection partition) {
    3946                while(stack.size() > 0) {
    4047                        CoarserGraphElement element = stack.pop();
    … …  
    4350                return partition;
    4451        }
    45        
    46         public Uncoarse() {
    47         }
    48 
    4952}

  • src/main/java/weka/clusterers/forMetisMQI/graph/UndirectedGraph.java

    r11 r14  
    122122        return sb.toString();
    123123        }
    124 
    125124}

  • src/main/java/weka/clusterers/forMetisMQI/util/CoarserGraphElement.java

    r11 r14  
    1 package weka.clusterers.forMetisMQI.coarse;
     1package weka.clusterers.forMetisMQI.util;
    22
    33import java.util.Map;
Note: See TracChangeset for help on using the changeset viewer.