Index: src/main/java/weka/clusterers/MetisMQIClusterer.java =================================================================== --- src/main/java/weka/clusterers/MetisMQIClusterer.java (revision 25) +++ src/main/java/weka/clusterers/MetisMQIClusterer.java (revision 26) @@ -35,5 +35,4 @@ - private Configuration conf = null; /** * @@ -122,4 +121,16 @@ setVerboseLevel(Integer.parseInt(optionString)); } + optionString = Utils.getOption('o', options); + if (optionString.length() != 0) { + setOutputFile(optionString); + } + } + + private void setOutputFile(String outputFile) { + Configuration.instance().setOutputFile(outputFile); + } + + private String getOutputFile() { + return Configuration.instance().getOutputFile(); } @@ -150,4 +161,6 @@ result.add("-V"); result.add("" + getVerboseLevel()); + result.add("-o"); + result.add("" + getOutputFile()); return (String[]) result.toArray(new String[result.size()]); } @@ -186,4 +199,6 @@ result.addElement(new Option("\tverbosity of graphical output.\n" + "\t(default 1).", "V", 1, "-V ")); + result.addElement(new Option("\tpath of the output file.\n" + , "o", 1, "-o ")); return result.elements(); } Index: src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java (revision 25) +++ src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java (revision 26) @@ -1,8 +1,16 @@ 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,4 +21,5 @@ 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,4 +101,15 @@ 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,4 +117,5 @@ Set> clusters = new HashSet>(); UndirectedGraph gclone = g.clone(); + for (int i = 0; i < numberOfCluster; i++) { Bisection bisection = null; @@ -109,5 +130,5 @@ 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,8 +142,21 @@ // 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,4 +168,14 @@ } } + + + 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)); Index: src/main/java/weka/clusterers/forMetisMQI/MQI.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/MQI.java (revision 25) +++ src/main/java/weka/clusterers/forMetisMQI/MQI.java (revision 26) @@ -16,4 +16,5 @@ 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,7 +84,7 @@ static private DirectedGraph 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,7 +162,8 @@ static public Set mqi(Bisection partition, boolean forConductance) { // System.out.println("INITIAL BISECTION: " + partition.toString()); + UndirectedGraph startingGraph = partition.getGraph(); boolean finished = false; Bisection bisection = partition; - Set cluster = new HashSet(partition.getSmallerSubgraph() + Set cluster = new HashSet(partition.getLargerSubgraph() .createInducedSubgraph().getVertices()); // System.out.println("IMPROVING SUBGRAPH: " + cluster); @@ -170,6 +172,6 @@ Node source = new Node("$$$$S"); Node sink = new Node("$$$$T"); - DirectedGraph directedGraph = prepareDirectedGraph( - bisection, source, sink, true); + Subgraph A = new Subgraph(startingGraph,cluster); + DirectedGraph directedGraph = prepareDirectedGraph(A, source, sink, true); Transformer capTransformer = new Transformer() { public Double transform(Edge e) { @@ -191,10 +193,9 @@ 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,5 +217,5 @@ // 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; Index: src/main/java/weka/clusterers/forMetisMQI/Random.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/Random.java (revision 25) +++ (revision ) @@ -1,31 +1,0 @@ -package weka.clusterers.forMetisMQI; - -public class Random extends java.util.Random { - - private static final long serialVersionUID = 1L; - - private static Random instance = null; - - private long seed = 1234567890; - - /** - * Return an instance of a random generator with a random seed. - * @return - */ - public static Random instance() { - if(instance == null) { - instance = new Random(/*new java.util.Random().nextLong()*/1234567890); - } - return instance; - } - - public long getSeed() { - return seed; - } - - private Random(long seed) { - super(seed); - this.seed = seed; - } - -} Index: src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java (revision 25) +++ src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java (revision 26) @@ -4,4 +4,6 @@ import java.util.Iterator; import java.util.Set; + +import weka.clusterers.forMetisMQI.util.Random; @@ -42,16 +44,15 @@ */ public Bisection(UndirectedGraph g){ + double limitingProbabilities = 0.1; this.g = g; a = new Subgraph(g); b = new Subgraph(g); Iterator 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(); Index: src/main/java/weka/clusterers/forMetisMQI/graph/UndirectedGraph.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/graph/UndirectedGraph.java (revision 25) +++ src/main/java/weka/clusterers/forMetisMQI/graph/UndirectedGraph.java (revision 26) @@ -9,5 +9,5 @@ import java.util.TreeMap; -import weka.clusterers.forMetisMQI.Random; +import weka.clusterers.forMetisMQI.util.Random; import weka.core.Attribute; import weka.core.Instance; Index: src/main/java/weka/clusterers/forMetisMQI/util/Configuration.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/util/Configuration.java (revision 25) +++ src/main/java/weka/clusterers/forMetisMQI/util/Configuration.java (revision 26) @@ -11,4 +11,14 @@ 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; Index: src/main/java/weka/clusterers/forMetisMQI/util/Random.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/util/Random.java (revision 26) +++ src/main/java/weka/clusterers/forMetisMQI/util/Random.java (revision 26) @@ -0,0 +1,31 @@ +package weka.clusterers.forMetisMQI.util; + +public class Random extends java.util.Random { + + private static final long serialVersionUID = 1L; + + private static Random instance = null; + + private long seed = 1234567890; + + /** + * Return an instance of a random generator with a random seed. + * @return + */ + public static Random instance() { + if(instance == null) { + instance = new Random(new java.util.Random().nextLong()/*1234567890*/); + } + return instance; + } + + public long getSeed() { + return seed; + } + + private Random(long seed) { + super(seed); + this.seed = seed; + } + +} Index: src/main/java/weka/clusterers/forMetisMQI/util/Util.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/util/Util.java (revision 25) +++ src/main/java/weka/clusterers/forMetisMQI/util/Util.java (revision 26) @@ -16,5 +16,4 @@ import org.apache.commons.collections15.Transformer; -import weka.clusterers.forMetisMQI.Random; import weka.clusterers.forMetisMQI.graph.Edge; import weka.clusterers.forMetisMQI.graph.Node; @@ -93,5 +92,5 @@ public static JPanel panelGraph(Graph g){ - Layout layout = new KKLayout(g); + Layout layout = new FRLayout(g); layout.setSize(new Dimension(800,600)); // sets the initial size of the space // The BasicVisualizationServer is parameterized by the edge types