Changeset 18 for src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java

Timestamp:

Sep 29, 2010, 9:13:19 AM (14 years ago)

Author:

gnappo

Message:

Implementato raffinamento KL in metis; implementata ottimizzazione di mqi sulla conduttanza.

File:

• src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java (modified) (5 diffs)

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

@@ -8 +8 @@
 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 +15 @@
 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 +43 @@
          */
         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 +81 @@
          */
         static public Set<Set<Node>> metisMqi(UndirectedGraph g, int numberOfCluster, int sizeFinerGraph) {
+                System.out.println("VERTEX: " + g.getVertexCount());
+                System.out.println("EDGE: " + g.getEdgeCount());
+                Iterator<Node> iNodes = g.getVertices().iterator();
+                int degreeCounter = 0;
+                while(iNodes.hasNext()) {
+                        Node node = iNodes.next();
+                        if(g.degree(node) == 1) {
+                                degreeCounter++;
+                        }
+                }
                 Set<Set<Node>> clusters = new HashSet<Set<Node>>();
                 UndirectedGraph gclone = g.clone();
@@ -62 +96 @@
                 for (int i = 0; i < numberOfCluster; i++) {
                         Bisection partition = metis(g,sizeFinerGraph);
-                        Set<Node> 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<Node> 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<Node> 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);