Changeset 14 for src/main/java
- Timestamp:
- Sep 17, 2010, 1:09:06 PM (14 years ago)
- 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 1 1 package weka.clusterers; 2 2 3 import java.util.Enumeration; 4 import java.util.HashMap; 5 import java.util.Iterator; 6 import java.util.Map; 7 import java.util.Set; 8 import java.util.Vector; 3 9 4 10 import weka.clusterers.forMetisMQI.GraphAlgorithms; 11 import weka.clusterers.forMetisMQI.graph.Node; 5 12 import weka.clusterers.forMetisMQI.graph.UndirectedGraph; 13 import weka.core.Attribute; 6 14 import weka.core.Capabilities; 7 15 import weka.core.Instance; 8 16 import weka.core.Instances; 17 import weka.core.Option; 18 import weka.core.OptionHandler; 19 import weka.core.Utils; 9 20 import weka.core.Capabilities.Capability; 10 21 11 public class SimpleClusterer extends AbstractClusterer { 12 13 private int numberOfClusters = 0; 22 public 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; 14 38 15 39 /** … … 21 45 public void buildClusterer(Instances data) throws Exception { 22 46 getCapabilities().testWithFail(data); 23 24 47 UndirectedGraph g = new UndirectedGraph(); 25 48 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 } 29 68 } 30 69 31 70 @Override 32 71 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 <num> 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 { 39 173 double[] d = new double[numberOfClusters()]; 40 174 d[clusterInstance(instance)] = 1.0; … … 62 196 */ 63 197 public static void main(String[] args) { 64 AbstractClusterer.runClusterer(new SimpleClusterer(), args);198 AbstractClusterer.runClusterer(new MetisMQIClusterer(), args); 65 199 } 66 200 -
src/main/java/weka/clusterers/forMetisMQI/Coarse.java
r11 r14 1 package weka.clusterers.forMetisMQI .coarse;1 package weka.clusterers.forMetisMQI; 2 2 3 3 import java.io.PrintStream; … … 12 12 import weka.clusterers.forMetisMQI.graph.Node; 13 13 import weka.clusterers.forMetisMQI.graph.UndirectedGraph; 14 import weka.clusterers.forMetisMQI.util.CoarserGraphElement; 14 15 15 16 import edu.uci.ics.jung.graph.util.Pair; -
src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java
r12 r14 5 5 import java.util.Stack; 6 6 7 import weka.clusterers.forMetisMQI.coarse.Coarse;8 import weka.clusterers.forMetisMQI.coarse.CoarserGraphElement;9 7 import weka.clusterers.forMetisMQI.graph.Bisection; 10 8 import weka.clusterers.forMetisMQI.graph.Node; 11 9 import weka.clusterers.forMetisMQI.graph.UndirectedGraph; 10 import weka.clusterers.forMetisMQI.util.CoarserGraphElement; 11 import weka.clusterers.forMetisMQI.util.Util; 12 12 13 13 public class GraphAlgorithms { 14 14 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) { 16 23 Bisection partition = new Bisection(g); 17 24 Bisection result = partition; … … 28 35 return result; 29 36 } 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 } 30 48 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) { 33 58 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); 49 63 } 50 MQI.viewClusters(g, clusters);64 return clusters; 51 65 } 52 66 -
src/main/java/weka/clusterers/forMetisMQI/MQI.java
r12 r14 23 23 import weka.clusterers.forMetisMQI.graph.UndirectedGraph; 24 24 import edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow; 25 import edu.uci.ics.jung.algorithms.layout.FRLayout; 25 26 import edu.uci.ics.jung.algorithms.layout.KKLayout; 26 27 import edu.uci.ics.jung.algorithms.layout.Layout; … … 35 36 static int i = -1; 36 37 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 space40 // The BasicVisualizationServer<V,E> is parameterized by the edge types41 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 else75 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 area82 // size83 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 space98 // The BasicVisualizationServer<V,E> is parameterized by the edge types99 BasicVisualizationServer<Node,Edge> vv =100 new BasicVisualizationServer<Node,Edge>(layout);101 vv.setPreferredSize(new Dimension(800,600)); //Sets the viewing area size102 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 112 38 static private Set<Node> BFSReversed(Node sink, DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) { 113 39 Set<Node> result = new HashSet<Node>(); -
src/main/java/weka/clusterers/forMetisMQI/Uncoarse.java
r11 r14 4 4 import java.util.Stack; 5 5 6 import weka.clusterers.forMetisMQI.coarse.CoarserGraphElement;7 6 import weka.clusterers.forMetisMQI.graph.Bisection; 8 7 import weka.clusterers.forMetisMQI.graph.Node; 9 8 import weka.clusterers.forMetisMQI.graph.Subgraph; 10 9 import weka.clusterers.forMetisMQI.graph.UndirectedGraph; 10 import weka.clusterers.forMetisMQI.util.CoarserGraphElement; 11 11 12 12 public class Uncoarse { 13 13 14 private boolean projectedBelongs(Node u, Bisection partition, CoarserGraphElement cge) {14 private static boolean projectedBelongs(Node u, Bisection partition, CoarserGraphElement cge) { 15 15 Subgraph s = partition.getSubgraph(); 16 16 Node mappedNode = cge.getMap().get(u); … … 24 24 * @param cge 25 25 */ 26 p ublic Bisection uncoarseOneStep(Bisection partition, CoarserGraphElement cge) {26 private static Bisection uncoarseOneStep(Bisection partition, CoarserGraphElement cge) { 27 27 UndirectedGraph projected = cge.getProjected(); 28 28 Subgraph part = new Subgraph(projected); … … 36 36 } 37 37 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) { 39 46 while(stack.size() > 0) { 40 47 CoarserGraphElement element = stack.pop(); … … 43 50 return partition; 44 51 } 45 46 public Uncoarse() {47 }48 49 52 } -
src/main/java/weka/clusterers/forMetisMQI/graph/UndirectedGraph.java
r11 r14 122 122 return sb.toString(); 123 123 } 124 125 124 } -
src/main/java/weka/clusterers/forMetisMQI/util/CoarserGraphElement.java
r11 r14 1 package weka.clusterers.forMetisMQI. coarse;1 package weka.clusterers.forMetisMQI.util; 2 2 3 3 import java.util.Map;
Note: See TracChangeset
for help on using the changeset viewer.