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

Timestamp:

Oct 5, 2010, 5:14:37 PM (14 years ago)

Author:

gnappo

Message:

Implementata ricorsione corretta di MQI. Aggiunto parametro a linea di comando per la bisezione casuale.

File:

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

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

@@ -80 +80 @@
          * @param sizeFinerGraph
          */
-        static public Set<Set<Node>> metisMqi(UndirectedGraph g, int numberOfCluster, int sizeFinerGraph) {
+        static public Set<Set<Node>> metisMqi(UndirectedGraph g, int numberOfCluster, int sizeFinerGraph, boolean randomBisection) {
                 System.out.println("Vertex count: " + g.getVertexCount());
                 System.out.println("Edges count: " + g.getEdgeCount());
@@ -95 +95 @@
 //              Util.viewGraph(g);
                 for (int i = 0; i < numberOfCluster; i++) {
-                        Bisection partition = metis(g,sizeFinerGraph);
-//                      Bisection partition = new Bisection(g);
+                        Bisection bisection = null;
+                        if(!randomBisection)
+                                bisection = metis(g,sizeFinerGraph);
+                        else
+                                bisection = 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.print("V1: " + bisection.getSubgraph().getVertexCount());
+                        System.out.print(" V2: " + bisection.getComplement().getVertexCount());
+                        System.out.println(" EC: " + bisection.edgeCut() * 0.5);
                         System.out.println("Conductance: " + 
-                                        ((double)partition.edgeCut() / 2) / Math.min(partition.getSubgraph().totalDegree(),partition.getComplement().totalDegree()));
-                        Set<Node> cluster = MQI.mqi(partition,true);
+                                        ((double)bisection.edgeCut() / 2) / Math.min(bisection.getSubgraph().totalDegree(),bisection.getComplement().totalDegree()));
+                        Set<Node> cluster = MQI.mqi(bisection,true);
                         
                         UndirectedGraph clusterGraph = new Subgraph(gclone,cluster).createInducedSubgraph();
@@ -113 +116 @@
                         System.out.println("Conductance: " + newConductance);
                         
-                        
-                        if(newConductance < 1) {
-                                System.out.println("CLUSTER "+ i + ":  V=" + clusterGraph.getVertexCount() + ", E=" + clusterGraph.getEdgeCount()+".");
-                                clusters.add(cluster);
-                        }
+                        System.out.println("CLUSTER "+ i + ":  V=" + clusterGraph.getVertexCount() + ", E=" + clusterGraph.getEdgeCount()+".");
+                        clusters.add(cluster);
                         
                         System.out.println();