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

Timestamp:

Oct 9, 2010, 12:24:38 PM (14 years ago)

Author:

gnappo

Message:

Aggiunto output in formato XML dei dati; modificato MQI (adesso cerca nella partizione piu` grande).

Location:

src/main/java/weka/clusterers/forMetisMQI

Files:

• GraphAlgorithms.java (modified) (7 diffs)
• MQI.java (modified) (6 diffs)
• graph/Bisection.java (modified) (2 diffs)
• graph/UndirectedGraph.java (modified) (1 diff)
• util/Configuration.java (modified) (1 diff)
• util/Random.java (moved) (moved from src/main/java/weka/clusterers/forMetisMQI/Random.java) (2 diffs)
• util/Util.java (modified) (2 diffs)

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

@@ -1 +1 @@
 package weka.clusterers.forMetisMQI;
 
+import java.io.File;
+import java.io.FileOutputStream;
+import java.io.IOException;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.Set;
 import java.util.Stack;
+
+import org.jdom.Document;
+import org.jdom.Element;
+import org.jdom.output.Format;
+import org.jdom.output.XMLOutputter;
 
 import weka.clusterers.forMetisMQI.graph.Bisection;
@@ -13 +21 @@
 import weka.clusterers.forMetisMQI.util.Configuration;
 import weka.clusterers.forMetisMQI.util.GraphsFrame;
+import weka.clusterers.forMetisMQI.util.Random;
 import weka.clusterers.forMetisMQI.util.Util;
 
@@ -92 +101 @@
                 int verboseLevel = Configuration.instance().getVerboseLevel();
                 GraphsFrame gf = GraphsFrame.instance();
+                
+                Element rootXML = new Element("run");
+                Document logXML = new Document(rootXML);
+                rootXML.setAttribute("seed", Long.toString(Random.instance().getSeed()));
+                Element graphXML = new Element("graph");
+                graphXML.addContent(new Element("vertex").setText(Integer.toString(g.getVertexCount())));
+                graphXML.addContent(new Element("edge").setText(Integer.toString(g.getEdgeCount())));
+                rootXML.addContent(graphXML);
+                Element clustersXML = new Element("clusters");
+                rootXML.addContent(clustersXML);
+                
                 System.out.println("Seed: " + Random.instance().getSeed());
                 System.out.println("Vertex count: " + g.getVertexCount());
@@ -97 +117 @@
                 Set<Set<Node>> clusters = new HashSet<Set<Node>>();
                 UndirectedGraph gclone = g.clone();
+                
                 for (int i = 0; i < numberOfCluster; i++) {
                         Bisection bisection = null;
@@ -109 +130 @@
                                 gf.addPanel(Util.panelCluster(g.clone(),bisection.getSmallerSubgraph().createInducedSubgraph().getVertices()));
                         
-                        System.out.print("Partizione iniziale: ");
+                        System.out.print("Initial partition: ");
                         System.out.print("V1: " + bisection.getSubgraph().getVertexCount());
                         System.out.print(" V2: " + bisection.getComplement().getVertexCount());
@@ -121 +142 @@
 //                      System.out.println(cluster);
                         Bisection mqiBisection = new Bisection(new Subgraph(g,cluster));
-                        System.out.println("Partizione raffinata (MQI)");
+                        System.out.println("Refined partition (MQI)");
                         double newConductance = ((double)mqiBisection.edgeCut() / 2) / Math.min(mqiBisection.getSubgraph().totalDegree(),mqiBisection.getComplement().totalDegree());
-                        System.out.println("Cluster "+ i + ":  V=" + clusterGraph.getVertexCount() + ", E=" + clusterGraph.getEdgeCount()+".");
+                        System.out.print("Cluster "+ i + ":  V=" + clusterGraph.getVertexCount() + ", E=" + clusterGraph.getEdgeCount()+", ");
+                        System.out.println("Cond: " + newConductance);
+                        
+                        
+                        mqiBisection = new Bisection(new Subgraph(gclone,cluster));
+                        newConductance = ((double)mqiBisection.edgeCut() / 2) / Math.min(mqiBisection.getSubgraph().totalDegree(),mqiBisection.getComplement().totalDegree());
                         System.out.println("Cluster conductance: " + newConductance);
+                        
+                        
+                        Element clusterXML = new Element("cluster");
+                        clusterXML.setAttribute("id", Integer.toString(i));
+                        clusterXML.addContent(new Element("vertex").setText(Integer.toString(clusterGraph.getVertexCount())));
+                        clusterXML.addContent(new Element("edge").setText(Integer.toString(clusterGraph.getEdgeCount())));
+                        clusterXML.addContent(new Element("conductance").setText(Double.toString(newConductance)));
+                        clustersXML.addContent(clusterXML);
                         
                         clusters.add(cluster);
@@ -134 +168 @@
                         }
                 }
+                
+                
+                XMLOutputter xmlOutputter = new XMLOutputter();
+                xmlOutputter.setFormat(Format.getPrettyFormat());
+                try {
+                        xmlOutputter.output(logXML, new FileOutputStream(new File(Configuration.instance().getOutputFile())));
+                } catch (IOException e) {
+                        e.printStackTrace();
+                }
+                
                 if(verboseLevel > 0) {
                         gf.addPanel(Util.panelClusters(gclone, clusters));

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

@@ -16 +16 @@
 import weka.clusterers.forMetisMQI.graph.Node;
 import weka.clusterers.forMetisMQI.graph.Subgraph;
+import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
 import edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow;
 import edu.uci.ics.jung.graph.DirectedGraph;
@@ -83 +84 @@
 
         static private DirectedGraph<Node, Edge> prepareDirectedGraph(
-                        Bisection bisection, Node source, Node sink, boolean forConductance) {
-                Subgraph B = bisection.getLargerSubgraph();
-                Subgraph A = bisection.getSmallerSubgraph();
+                        Subgraph A, Node source, Node sink, boolean forConductance) {
+                Bisection bisection = new Bisection(A);
+                Subgraph B = bisection.getComplement();
                 int a = 0;
                 if (!forConductance)
@@ -161 +162 @@
         static public Set<Node> mqi(Bisection partition, boolean forConductance) {
 //              System.out.println("INITIAL BISECTION: " + partition.toString());
+                UndirectedGraph startingGraph = partition.getGraph();
                 boolean finished = false;
                 Bisection bisection = partition;
-                Set<Node> cluster = new HashSet<Node>(partition.getSmallerSubgraph()
+                Set<Node> cluster = new HashSet<Node>(partition.getLargerSubgraph()
                                 .createInducedSubgraph().getVertices());
 //              System.out.println("IMPROVING SUBGRAPH: " + cluster);
@@ -170 +172 @@
                         Node source = new Node("$$$$S");
                         Node sink = new Node("$$$$T");
-                        DirectedGraph<Node, Edge> directedGraph = prepareDirectedGraph(
-                                        bisection, source, sink, true);
+                        Subgraph A = new Subgraph(startingGraph,cluster);
+                        DirectedGraph<Node, Edge> directedGraph = prepareDirectedGraph(A, source, sink, true);
                         Transformer<Edge, Number> capTransformer = new Transformer<Edge, Number>() {
                                 public Double transform(Edge e) {
@@ -191 +193 @@
 
                         if (!forConductance)
-                                maxFlowThreshold = bisection.getLargerSubgraph()
-                                                .getVertexCount()
+                                maxFlowThreshold = A.getVertexCount()
                                                 * bisection.edgeCut() / 2;
                         else {
 //                              maxFlowThreshold = Math.min(bisection.getLargerSubgraph().totalDegree(), bisection.getSmallerSubgraph().totalDegree());
-                                maxFlowThreshold = bisection.getSmallerSubgraph().totalDegree();
+                                maxFlowThreshold = A.totalDegree();
                                 maxFlowThreshold = maxFlowThreshold
                                                 * (bisection.edgeCut() / 2);
@@ -216 +217 @@
 //                              System.out.println("REFINED BISECTION: " + bisection.toString());
                                 if(Configuration.instance().getVerboseLevel() > 1)
-                                        GraphsFrame.instance().addPanel(Util.panelCluster(bisection.getGraph(), cluster));
+                                        GraphsFrame.instance().addPanel(Util.panelCluster(bisection.getGraph().clone(), cluster));
                         } else
                                 finished = true;

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

@@ -4 +4 @@
 import java.util.Iterator;
 import java.util.Set;
+
+import weka.clusterers.forMetisMQI.util.Random;
 
 
@@ -42 +44 @@
          */
         public Bisection(UndirectedGraph g){
+                double limitingProbabilities = 0.1;
                 this.g = g;
                 a = new Subgraph(g);
                 b = new Subgraph(g);
                 Iterator<Node> graph = g.vtxsPermutation().iterator();
-                int i = 0;
                 while(graph.hasNext()) {
                         Node u = graph.next();
-                        if((i%2)==0)
+                        if(Random.instance().nextDouble() < limitingProbabilities)
                                 a.addVertex(u);
                         else
                                 b.addVertex(u);
-                        i++;
                 }
                 marked = new HashSet<Node>();

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

@@ -9 +9 @@
 import java.util.TreeMap;
 
-import weka.clusterers.forMetisMQI.Random;
+import weka.clusterers.forMetisMQI.util.Random;
 import weka.core.Attribute;
 import weka.core.Instance;

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

@@ -11 +11 @@
         private int numberOfClusters = 2;
         
+        private String outputFile = null;
+        
+        public String getOutputFile() {
+                return outputFile;
+        }
+
+        public void setOutputFile(String outputFile) {
+                this.outputFile = outputFile;
+        }
+
         private static Configuration instance = null;
         

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

@@ -1 @@
-package weka.clusterers.forMetisMQI;
+package weka.clusterers.forMetisMQI.util;
 
 public class Random extends java.util.Random {
@@ -15 +15 @@
         public static Random instance() {
                 if(instance == null) {
-                        instance = new Random(/*new java.util.Random().nextLong()*/1234567890);
+                        instance = new Random(new java.util.Random().nextLong()/*1234567890*/);
                 }
                 return instance;

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

@@ -16 +16 @@
 import org.apache.commons.collections15.Transformer;
 
-import weka.clusterers.forMetisMQI.Random;
 import weka.clusterers.forMetisMQI.graph.Edge;
 import weka.clusterers.forMetisMQI.graph.Node;
@@ -93 +92 @@
         
         public static JPanel panelGraph(Graph<Node, Edge> g){
-                Layout<Node, Edge> layout = new KKLayout<Node, Edge>(g);
+                Layout<Node, Edge> layout = new FRLayout<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