Changeset 14 for src/main/java/weka/clusterers/forMetisMQI

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/forMetisMQI

Files:

• Coarse.java (copied) (copied from src/main/java/weka/clusterers/forMetisMQI/coarse/Coarse.java) (2 diffs)
• GraphAlgorithms.java (modified) (2 diffs)
• MQI.java (modified) (2 diffs)
• Uncoarse.java (modified) (4 diffs)
• coarse (deleted)
• graph/UndirectedGraph.java (modified) (1 diff)
• util (added)
• util/CoarserGraphElement.java (copied) (copied from src/main/java/weka/clusterers/forMetisMQI/coarse/CoarserGraphElement.java) (1 diff)
• util/Util.java (added)

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

@@ -1 @@
-package weka.clusterers.forMetisMQI.coarse;
+package weka.clusterers.forMetisMQI;
 
 import java.io.PrintStream;
@@ -12 +12 @@
 import weka.clusterers.forMetisMQI.graph.Node;
 import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
+import weka.clusterers.forMetisMQI.util.CoarserGraphElement;
 
 import edu.uci.ics.jung.graph.util.Pair;

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

@@ -5 +5 @@
 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;
+import weka.clusterers.forMetisMQI.util.CoarserGraphElement;
+import weka.clusterers.forMetisMQI.util.Util;
 
 public class GraphAlgorithms {
 
-        public Bisection KL(UndirectedGraph g) {
+        
+        /**
+         * 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;
@@ -28 +35 @@
                 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;
+        }
 
-        public void METIS(UndirectedGraph g) {
-//              MQI.viewGraph(g);
+        /**
+         * 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 < 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);
-                        }
+                for (int i = 0; i < numberOfCluster; i++) {
+                        Bisection partition = metis(g,sizeFinerGraph);
+                        Set<Node> cluster = MQI.mqi(partition);
+                        clusters.add(cluster);
                 }
-                MQI.viewClusters(g, clusters);
+                return clusters;
         }
 

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

@@ -23 +23 @@
 import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
 import edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow;
+import edu.uci.ics.jung.algorithms.layout.FRLayout;
 import edu.uci.ics.jung.algorithms.layout.KKLayout;
 import edu.uci.ics.jung.algorithms.layout.Layout;
@@ -35 +36 @@
         static int i = -1;
         
-        public static void viewClusters(Graph<Node, Edge> g, Set<Set<Node>> clusters) {
-                Layout<Node, Edge> layout = new KKLayout<Node, Edge>(g);
-                layout.setSize(new Dimension(800, 600)); // sets the initial size of the space
-                // The BasicVisualizationServer<V,E> is parameterized by the edge types
-                BasicVisualizationServer<Node, Edge> vv = new BasicVisualizationServer<Node, Edge>(
-                                layout);
-
-                class VertexPaintTransformer implements Transformer<Node, Paint> {
-                        Set<Set<Node>> clusters = null;
-                        Map<Set<Node>, Color> clustersColor = null;
-
-                        public Set<Node> getCluster(Node node) {
-                                Iterator<Set<Node>> clusterIterator = clusters.iterator();
-                                while (clusterIterator.hasNext()) {
-                                        Set<Node> cluster = clusterIterator.next();
-                                        if (cluster.contains(node))
-                                                return cluster;
-                                }
-                                return null;
-                        }
-
-                        public VertexPaintTransformer(Set<Set<Node>> clusters) {
-                                this.clusters = clusters;
-                                clustersColor = new HashMap<Set<Node>, Color>(clusters.size());
-                                Iterator<Set<Node>> clusterIterator = clusters.iterator();
-                                while (clusterIterator.hasNext()) {
-                                        Set<Node> cluster = clusterIterator.next();
-                                        clustersColor.put(cluster, new Color(Random.instance()
-                                                        .nextInt(256), Random.instance().nextInt(256),
-                                                        Random.instance().nextInt(256)));
-                                }
-                        }
-
-                        public Paint transform(Node i) {
-                                Set<Node> cluster = getCluster(i);
-                                if (cluster == null)
-                                        return Color.RED;
-                                else
-                                        return clustersColor.get(getCluster(i));
-                        }
-                }
-
-                Transformer<Node, Paint> vertexPaint = new VertexPaintTransformer(
-                                clusters);
-                vv.setPreferredSize(new Dimension(800, 600)); // Sets the viewing area
-                                                                                                                // size
-                vv.getRenderContext().setVertexLabelTransformer(
-                                new ToStringLabeller<Node>());
-                vv.getRenderContext().setEdgeLabelTransformer(
-                                new ToStringLabeller<Edge>());
-                vv.getRenderContext().setVertexFillPaintTransformer(vertexPaint);
-                JFrame frame = new JFrame("Graph View");
-                frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
-                frame.getContentPane().add(vv);
-                frame.pack();
-                frame.setVisible(true);
-        }
-        
-        public static void viewGraph(Graph<Node, Edge> g){
-                Layout<Node, Edge> layout = new KKLayout<Node, Edge>(g);
-                layout.setSize(new Dimension(800,600)); // sets the initial size of the space
-                // The BasicVisualizationServer<V,E> is parameterized by the edge types
-                BasicVisualizationServer<Node,Edge> vv =
-                new BasicVisualizationServer<Node,Edge>(layout);
-                vv.setPreferredSize(new Dimension(800,600)); //Sets the viewing area size
-                vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<Node>());
-                vv.getRenderContext().setEdgeLabelTransformer(new ToStringLabeller<Edge>());
-
-                JFrame frame = new JFrame("Simple Graph View");
-                frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
-                frame.getContentPane().add(vv);
-                frame.pack();
-                frame.setVisible(true);
-        }
-
         static private Set<Node> BFSReversed(Node sink, DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) {
                 Set<Node> result = new HashSet<Node>();

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

@@ -4 +4 @@
 import java.util.Stack;
 
-import weka.clusterers.forMetisMQI.coarse.CoarserGraphElement;
 import weka.clusterers.forMetisMQI.graph.Bisection;
 import weka.clusterers.forMetisMQI.graph.Node;
 import weka.clusterers.forMetisMQI.graph.Subgraph;
 import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
+import weka.clusterers.forMetisMQI.util.CoarserGraphElement;
 
 public class Uncoarse {
         
-        private boolean projectedBelongs(Node u, Bisection partition, CoarserGraphElement cge) {
+        private static boolean projectedBelongs(Node u, Bisection partition, CoarserGraphElement cge) {
                 Subgraph s = partition.getSubgraph();
                 Node mappedNode = cge.getMap().get(u);
@@ -24 +24 @@
          * @param cge
          */
-        public Bisection uncoarseOneStep(Bisection partition, CoarserGraphElement cge) {
+        private static Bisection uncoarseOneStep(Bisection partition, CoarserGraphElement cge) {
                 UndirectedGraph projected = cge.getProjected();
                 Subgraph part = new Subgraph(projected);
@@ -36 +36 @@
         }
         
-        public Bisection uncoarse(Stack<CoarserGraphElement> stack, Bisection partition) {
+        /**
+         * Given a bisection of the finer graph and the stack of graphs which yielded the finer graph,
+         * it returns the bisection projected into the coarser graph. 
+         * @param stack
+         * @param partition
+         * @return
+         */
+        public static Bisection uncoarse(Stack<CoarserGraphElement> stack, Bisection partition) {
                 while(stack.size() > 0) {
                         CoarserGraphElement element = stack.pop();
@@ -43 +50 @@
                 return partition;
         }
-        
-        public Uncoarse() {
-        }
-
 }

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

@@ -122 +122 @@
         return sb.toString();
         }
-
 }

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

@@ -1 @@
-package weka.clusterers.forMetisMQI.coarse;
+package weka.clusterers.forMetisMQI.util;
 
 import java.util.Map;