Index: src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java (revision 18) +++ src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java (revision 20) @@ -81,6 +81,6 @@ */ static public Set> metisMqi(UndirectedGraph g, int numberOfCluster, int sizeFinerGraph) { - System.out.println("VERTEX: " + g.getVertexCount()); - System.out.println("EDGE: " + g.getEdgeCount()); + System.out.println("Vertex count: " + g.getVertexCount()); + System.out.println("Edges count: " + g.getEdgeCount()); Iterator iNodes = g.getVertices().iterator(); int degreeCounter = 0; @@ -95,7 +95,10 @@ // Util.viewGraph(g); for (int i = 0; i < numberOfCluster; i++) { - Bisection partition = metis(g,sizeFinerGraph); - System.out.println("Partizione iniziale (Metis)"); -// System.out.println("Edge-cut: " + partition.edgeCut() / 2); +// Bisection partition = metis(g,sizeFinerGraph); + Bisection partition = new Bisection(g); + System.out.print("Partizione iniziale: "); + System.out.print("V1: " + partition.getSubgraph().getVertexCount()); + System.out.print(" V2: " + partition.getComplement().getVertexCount()); + System.out.println(" EC: " + partition.edgeCut() * 0.5); System.out.println("Conductance: " + ((double)partition.edgeCut() / 2) / Math.min(partition.getSubgraph().totalDegree(),partition.getComplement().totalDegree())); @@ -107,5 +110,4 @@ Bisection mqiBisection = new Bisection(new Subgraph(g,cluster)); System.out.println("Partizione raffinata (MQI)"); -// System.out.println("Edge-cut: " + mqiBisection.edgeCut() / 2); double newConductance = ((double)mqiBisection.edgeCut() / 2) / Math.min(mqiBisection.getSubgraph().totalDegree(),mqiBisection.getComplement().totalDegree()); System.out.println("Conductance: " + newConductance); @@ -117,4 +119,5 @@ } + System.out.println(); Iterator clustersNode = cluster.iterator(); while(clustersNode.hasNext()){ Index: src/main/java/weka/clusterers/forMetisMQI/MQI.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/MQI.java (revision 18) +++ src/main/java/weka/clusterers/forMetisMQI/MQI.java (revision 20) @@ -81,15 +81,7 @@ static private DirectedGraph prepareDirectedGraph( - Bisection partition, Node source, Node sink, boolean forConductance) { - Subgraph A = null; - Subgraph B = null; - if (partition.getSubgraph().getVertexCount() < partition - .getComplement().getVertexCount()) { - A = partition.getSubgraph(); - B = partition.getComplement(); - } else { - A = partition.getComplement(); - B = partition.getSubgraph(); - } + Bisection bisection, Node source, Node sink, boolean forConductance) { + Subgraph A = bisection.getLargerSubgraph(); + Subgraph B = bisection.getSmallerSubgraph(); int a = 0; if (!forConductance) @@ -98,8 +90,8 @@ Iterator aIterator = A.iterator(); while(aIterator.hasNext()) { - a += partition.getGraph().degree(aIterator.next()); - } - } - int c = partition.edgeCut() / 2; + a += bisection.getGraph().degree(aIterator.next()); + } + } + int c = bisection.edgeCut() / 2; DirectedGraph g = new DirectedSparseGraph(); @@ -109,5 +101,4 @@ g.addVertex(u); } - nodes = A.iterator(); int id = 0; @@ -153,5 +144,5 @@ if(forConductance) //FIXME: CONTROLLAMI - g.addEdge(new Edge(Integer.toString(id), 1, c * partition.getGraph().degree(u)), u, sink); + g.addEdge(new Edge(Integer.toString(id), 1, c * bisection.getGraph().degree(u)), u, sink); else g.addEdge(new Edge(Integer.toString(id), 1, c), u, sink); @@ -173,5 +164,5 @@ boolean finished = false; Bisection bisection = partition; - Set cluster = new HashSet(partition.getSmallerNotEmptySubgraph() + Set cluster = new HashSet(partition.getLargerSubgraph() .createInducedSubgraph().getVertices()); int maxFlowThreshold = Integer.MAX_VALUE; @@ -200,9 +191,9 @@ if (!forConductance) - maxFlowThreshold = bisection.getSmallerNotEmptySubgraph() + maxFlowThreshold = bisection.getLargerSubgraph() .getVertexCount() * bisection.edgeCut() / 2; else { - Iterator aIterator = bisection.getSmallerNotEmptySubgraph().iterator(); + Iterator aIterator = bisection.getLargerSubgraph().iterator(); maxFlowThreshold = 0; while(aIterator.hasNext()) @@ -212,19 +203,14 @@ } alg.evaluate(); -// Util.viewFlowGraph(directedGraph, edgeFlowMap); -// System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: " -// + maxFlowThreshold); +// Util.viewFlowGraph(directedGraph, edgeFlowMap); + System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: " + + maxFlowThreshold); if (alg.getMaxFlow() < maxFlowThreshold) { Set dfsResult = DFSReversed(sink, directedGraph, edgeFlowMap, new HashSet()); dfsResult.remove(sink); -// if (dfsResult.size() > 0) { - cluster = dfsResult; - bisection = new Bisection(new Subgraph( - bisection.getGraph(), cluster)); -// System.out -// .println("NEW BISECTION: " + bisection.toString()); -// } else -// finished = true; + cluster = dfsResult; + bisection = new Bisection(new Subgraph( + bisection.getGraph(), cluster)); } else finished = true; Index: src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java (revision 18) +++ src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java (revision 20) @@ -139,13 +139,16 @@ } + public Subgraph getLargerSubgraph() { + if(a.getVertexCount() < b.getVertexCount()) + return b; + else + return a; + } + /** - * Returns the smaller not empty subgraph of this bisection, null otherwise. + * Returns the smaller subgraph of this bisection, null otherwise. * @return */ - public Subgraph getSmallerNotEmptySubgraph() { - if(a.getVertexCount() > 0 && b.getVertexCount() == 0) - return a; - if(b.getVertexCount() > 0 && a.getVertexCount() == 0) - return b; + public Subgraph getSmallerSubgraph() { if(a.getVertexCount() < b.getVertexCount()) return a; Index: src/main/java/weka/clusterers/forMetisMQI/graph/UndirectedGraph.java =================================================================== --- src/main/java/weka/clusterers/forMetisMQI/graph/UndirectedGraph.java (revision 18) +++ src/main/java/weka/clusterers/forMetisMQI/graph/UndirectedGraph.java (revision 20) @@ -1,8 +1,11 @@ package weka.clusterers.forMetisMQI.graph; +import java.io.PrintStream; import java.util.ArrayList; import java.util.Collection; +import java.util.HashMap; import java.util.Iterator; import java.util.List; +import java.util.TreeMap; import weka.clusterers.forMetisMQI.Random; @@ -109,4 +112,28 @@ } + public void printForMetis(PrintStream output) { + TreeMap map = new TreeMap(); + HashMap reverseMap = new HashMap(); + Iterator nodesIterator = getVertices().iterator(); + int id = 1; + while(nodesIterator.hasNext()) { + Node node = nodesIterator.next(); + map.put(id, node); + reverseMap.put(node,id); + id++; + } + output.println(getVertexCount() + " "+ getEdgeCount()); + Iterator mappedIterator = map.keySet().iterator(); + while(mappedIterator.hasNext()) { + id = mappedIterator.next(); + Iterator neighbors = getNeighbors(map.get(id)).iterator(); + while(neighbors.hasNext()){ + output.print(reverseMap.get(neighbors.next())); + if(neighbors.hasNext()) output.print(" "); + } + output.println(); + } + } + public String toString() { StringBuffer sb = new StringBuffer("Vertices:");