Index: /src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java =================================================================== --- /src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java (revision 17) +++ /src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java (revision 18) @@ -8,4 +8,5 @@ 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; @@ -14,4 +15,24 @@ public class GraphAlgorithms { + + static public Bisection KLRefinement(Bisection b) { + int remainingNumberOfSwap = 50; + Bisection partition = b; + Bisection result = partition; + int bestEdgeCut = partition.edgeCut(); + Node u = partition.getCandidate(); + while (u != null && remainingNumberOfSwap > 0) { + partition.swap(u); + if (partition.edgeCut() <= bestEdgeCut) { + bestEdgeCut = partition.edgeCut(); + result = partition.clone(); + remainingNumberOfSwap = 50; + } else + remainingNumberOfSwap--; + u = partition.getCandidate(); + } + return result; + } + /** @@ -22,14 +43,17 @@ */ static public Bisection KL(UndirectedGraph g) { + int remainingNumberOfSwap = 50; Bisection partition = new Bisection(g); Bisection result = partition; - int bestEdgeCut = Integer.MAX_VALUE; + int bestEdgeCut = partition.edgeCut(); Node u = partition.getCandidate(); - while (u != null) { + while (u != null && remainingNumberOfSwap > 0) { partition.swap(u); if (partition.edgeCut() <= bestEdgeCut) { bestEdgeCut = partition.edgeCut(); - result = partition.copy(); - } + result = partition.clone(); + remainingNumberOfSwap = 50; + } else + remainingNumberOfSwap--; u = partition.getCandidate(); } @@ -57,4 +81,14 @@ */ static public Set> metisMqi(UndirectedGraph g, int numberOfCluster, int sizeFinerGraph) { + System.out.println("VERTEX: " + g.getVertexCount()); + System.out.println("EDGE: " + g.getEdgeCount()); + Iterator iNodes = g.getVertices().iterator(); + int degreeCounter = 0; + while(iNodes.hasNext()) { + Node node = iNodes.next(); + if(g.degree(node) == 1) { + degreeCounter++; + } + } Set> clusters = new HashSet>(); UndirectedGraph gclone = g.clone(); @@ -62,15 +96,29 @@ for (int i = 0; i < numberOfCluster; i++) { Bisection partition = metis(g,sizeFinerGraph); - Set cluster = MQI.mqi(partition); + System.out.println("Partizione iniziale (Metis)"); +// System.out.println("Edge-cut: " + partition.edgeCut() / 2); + System.out.println("Conductance: " + + ((double)partition.edgeCut() / 2) / Math.min(partition.getSubgraph().totalDegree(),partition.getComplement().totalDegree())); + Set cluster = MQI.mqi(partition,true); + + UndirectedGraph clusterGraph = new Subgraph(gclone,cluster).createInducedSubgraph(); + +// System.out.println(cluster); + 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); + + + if(newConductance < 1) { + System.out.println("CLUSTER "+ i + ": V=" + clusterGraph.getVertexCount() + ", E=" + clusterGraph.getEdgeCount()+"."); + clusters.add(cluster); + } + Iterator clustersNode = cluster.iterator(); while(clustersNode.hasNext()){ g.removeVertex(clustersNode.next()); } - - - if(cluster.size()>10) { - clusters.add(cluster); - } - System.out.println("CLUSTER "+ i + ": " + cluster); } Util.viewClusters(gclone, clusters); Index: /src/main/java/weka/clusterers/forMetisMQI/MQI.java =================================================================== --- /src/main/java/weka/clusterers/forMetisMQI/MQI.java (revision 17) +++ /src/main/java/weka/clusterers/forMetisMQI/MQI.java (revision 18) @@ -16,5 +16,4 @@ import weka.clusterers.forMetisMQI.graph.Node; import weka.clusterers.forMetisMQI.graph.Subgraph; -import weka.clusterers.forMetisMQI.graph.UndirectedGraph; import weka.clusterers.forMetisMQI.util.Util; import edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow; @@ -27,5 +26,6 @@ static private Set DFSReversed(Node currentNode, - DirectedGraph g, Map edgeFlowMap, Set marked) { + DirectedGraph g, Map edgeFlowMap, + Set marked) { Collection inEdges = g.getInEdges(currentNode); Set result = new HashSet(); @@ -47,6 +47,4 @@ return result; } - - static private Set BFSReversed(Node sink, @@ -83,5 +81,5 @@ static private DirectedGraph prepareDirectedGraph( - Bisection partition, Node source, Node sink) { + Bisection partition, Node source, Node sink, boolean forConductance) { Subgraph A = null; Subgraph B = null; @@ -94,5 +92,13 @@ B = partition.getSubgraph(); } - int a = A.getVertexCount(); + int a = 0; + if (!forConductance) + a = A.getVertexCount(); + else { + Iterator aIterator = A.iterator(); + while(aIterator.hasNext()) { + a += partition.getGraph().degree(aIterator.next()); + } + } int c = partition.edgeCut() / 2; @@ -120,7 +126,7 @@ g.addVertex(sink); - - //build the edges from source to each node of A which previously was connected - //with a node of B. + // build the edges from source to each node of A which previously was + // connected + // with a node of B. nodes = B.iterator(); while (nodes.hasNext()) { @@ -131,8 +137,9 @@ if (A.contains(v)) { Edge e = g.findEdge(source, v); - if(e != null) { + if (e != null) { e.setCapacity(e.getCapacity() + a); } else { - g.addEdge(new Edge(Integer.toString(id), 1, a), source, v); + g.addEdge(new Edge(Integer.toString(id), 1, a), source, + v); id++; } @@ -144,5 +151,9 @@ while (nodes.hasNext()) { Node u = nodes.next(); - g.addEdge(new Edge(Integer.toString(id), 1, c), u, sink); + if(forConductance) + //FIXME: CONTROLLAMI + g.addEdge(new Edge(Integer.toString(id), 1, c * partition.getGraph().degree(u)), u, sink); + else + g.addEdge(new Edge(Integer.toString(id), 1, c), u, sink); id++; } @@ -158,11 +169,10 @@ * @return */ - static public Set mqi(Bisection partition) { + static public Set mqi(Bisection partition, boolean forConductance) { // System.out.println("INITIAL BISECTION: " + partition.toString()); boolean finished = false; Bisection bisection = partition; - Set cluster = new HashSet(partition - .getSmallerNotEmptySubgraph().createInducedSubgraph() - .getVertices()); + Set cluster = new HashSet(partition.getSmallerNotEmptySubgraph() + .createInducedSubgraph().getVertices()); int maxFlowThreshold = Integer.MAX_VALUE; while (!finished) { @@ -170,5 +180,5 @@ Node sink = new Node("$$$$T"); DirectedGraph directedGraph = prepareDirectedGraph( - bisection, source, sink); + bisection, source, sink, true); Transformer capTransformer = new Transformer() { public Double transform(Edge e) { @@ -189,17 +199,32 @@ edgeFactory); - maxFlowThreshold = bisection.getSmallerNotEmptySubgraph() - .getVertexCount() - * bisection.edgeCut() / 2; + if (!forConductance) + maxFlowThreshold = bisection.getSmallerNotEmptySubgraph() + .getVertexCount() + * bisection.edgeCut() / 2; + else { + Iterator aIterator = bisection.getSmallerNotEmptySubgraph().iterator(); + maxFlowThreshold = 0; + while(aIterator.hasNext()) + maxFlowThreshold += partition.getGraph().degree(aIterator.next()); + maxFlowThreshold = maxFlowThreshold + * (bisection.edgeCut() / 2); + } alg.evaluate(); -// Util.viewFlowGraph(directedGraph, edgeFlowMap); +// Util.viewFlowGraph(directedGraph, edgeFlowMap); // System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: " // + maxFlowThreshold); if (alg.getMaxFlow() < maxFlowThreshold) { - cluster = DFSReversed(sink, directedGraph, edgeFlowMap, new HashSet()); - cluster.remove(sink); - bisection = new Bisection(new Subgraph(bisection.getGraph(), - cluster)); -// System.out.println("NEW BISECTION: " + bisection.toString()); + 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; } else finished = true; Index: /src/main/java/weka/clusterers/forMetisMQI/Uncoarse.java =================================================================== --- /src/main/java/weka/clusterers/forMetisMQI/Uncoarse.java (revision 17) +++ /src/main/java/weka/clusterers/forMetisMQI/Uncoarse.java (revision 18) @@ -38,5 +38,5 @@ /** * 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. + * it returns the bisection projected into the coarser graph. * @param stack * @param partition @@ -47,4 +47,5 @@ CoarserGraphElement element = stack.pop(); partition = uncoarseOneStep(partition,element); + partition = GraphAlgorithms.KLRefinement(partition); } return partition; Index: /src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java =================================================================== --- /src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java (revision 17) +++ /src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java (revision 18) @@ -122,8 +122,9 @@ } - public Bisection copy(){ + public Bisection clone(){ Bisection clone = new Bisection(); clone.a = (Subgraph) a.clone(); clone.b = (Subgraph) b.clone(); + clone.g = g.clone(); clone.marked = new HashSet(); return clone; Index: /src/main/java/weka/clusterers/forMetisMQI/graph/Subgraph.java =================================================================== --- /src/main/java/weka/clusterers/forMetisMQI/graph/Subgraph.java (revision 17) +++ /src/main/java/weka/clusterers/forMetisMQI/graph/Subgraph.java (revision 18) @@ -260,3 +260,13 @@ return FilterUtils.createInducedSubgraph(nodes,g); } + + public int totalDegree() { + int result = 0; + Iterator nodeIterator = iterator(); + while(nodeIterator.hasNext()) { + int degree = g.degree(nodeIterator.next()); + result += degree; + } + return result; + } } Index: /src/main/java/weka/clusterers/forMetisMQI/util/Util.java =================================================================== --- /src/main/java/weka/clusterers/forMetisMQI/util/Util.java (revision 17) +++ /src/main/java/weka/clusterers/forMetisMQI/util/Util.java (revision 18) @@ -5,4 +5,5 @@ import java.awt.Paint; import java.util.HashMap; +import java.util.HashSet; import java.util.Iterator; import java.util.Map; @@ -18,4 +19,5 @@ import weka.clusterers.forMetisMQI.graph.UndirectedGraph; import edu.uci.ics.jung.algorithms.layout.FRLayout; +import edu.uci.ics.jung.algorithms.layout.ISOMLayout; import edu.uci.ics.jung.algorithms.layout.Layout; import edu.uci.ics.jung.graph.Graph; @@ -24,4 +26,12 @@ public class Util { + + public static void viewCluster(Graph g, Set cluster) { + Set> clusters = new HashSet>(); + clusters.add(cluster); + viewClusters(g, clusters); + } + + public static void viewClusters(Graph g, Set> clusters) { Layout layout = new FRLayout(g);