Changeset 22

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.

Location:

src/main/java/weka/clusterers

Files:

• MetisMQIClusterer.java (modified) (4 diffs)
• forMetisMQI/GraphAlgorithms.java (modified) (3 diffs)
• forMetisMQI/MQI.java (modified) (5 diffs)

src/main/java/weka/clusterers/MetisMQIClusterer.java

@@ -36 +36 @@
          */
         private Map<Node, Integer> nodeMap = null;
+        
+        /**
+         * True if a random bisection must be used.
+         */
+        private boolean randomBisection = false;
 
         /**
@@ -48 +53 @@
                 g.loadFromInstance(data);
                 Set<Set<Node>> clusters = GraphAlgorithms.metisMqi(g, numberOfClusters,
-                                sizeFinerGraph);
+                                sizeFinerGraph, randomBisection);
                 setNumClusters(clusters.size());
                 int i = 0;
@@ -118 +123 @@
                         setSizeFinerGraph(Integer.parseInt(optionString));
                 }
+                optionString = Utils.getOption('R', options);
+                setRandomBisection(Boolean.parseBoolean(optionString));
+        }
+
+        private void setRandomBisection(boolean b) {
+                this.randomBisection = b;
         }
 
@@ -134 +145 @@
                 result.add("-S");
                 result.add("" + getSizeFinerGraph());
+                result.add("-R");
                 return (String[]) result.toArray(new String[result.size()]);
         }

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();

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

@@ -82 +82 @@
         static private DirectedGraph<Node, Edge> prepareDirectedGraph(
                         Bisection bisection, Node source, Node sink, boolean forConductance) {
-                Subgraph A = bisection.getLargerSubgraph();
-                Subgraph B = bisection.getSmallerSubgraph();
+                Subgraph B = bisection.getLargerSubgraph();
+                Subgraph A = bisection.getSmallerSubgraph();
                 int a = 0;
                 if (!forConductance)
                         a = A.getVertexCount();
                 else {
-                        a = Math.min(B.totalDegree(),A.totalDegree());
+//                      a = Math.min(B.totalDegree(),A.totalDegree());
+                        a = A.totalDegree();
                 }
                 int c = bisection.edgeCut() / 2;
@@ -140 +141 @@
                         Node u = nodes.next();
                         if(forConductance)
-                                //FIXME: CONTROLLAMI
                                 g.addEdge(new Edge(Integer.toString(id), 1, c * bisection.getGraph().degree(u)), u, sink);
                         else
@@ -161 +161 @@
                 boolean finished = false;
                 Bisection bisection = partition;
-                Set<Node> cluster = new HashSet<Node>(partition.getLargerSubgraph()
+                Set<Node> cluster = new HashSet<Node>(partition.getSmallerSubgraph()
                                 .createInducedSubgraph().getVertices());
+//              System.out.println("IMPROVING SUBGRAPH: " + cluster);
                 int maxFlowThreshold = Integer.MAX_VALUE;
                 while (!finished) {
@@ -192 +193 @@
                                                 * bisection.edgeCut() / 2;
                         else {
-                                maxFlowThreshold = Math.min(bisection.getLargerSubgraph().totalDegree(), bisection.getSmallerSubgraph().totalDegree());
+//                              maxFlowThreshold = Math.min(bisection.getLargerSubgraph().totalDegree(), bisection.getSmallerSubgraph().totalDegree());
+                                maxFlowThreshold = bisection.getSmallerSubgraph().totalDegree();
                                 maxFlowThreshold = maxFlowThreshold
                                                 * (bisection.edgeCut() / 2);
                         }
                         alg.evaluate();
-                        Util.viewFlowGraph(directedGraph, edgeFlowMap);
+//                      Util.viewFlowGraph(directedGraph, edgeFlowMap);
                         System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: "
                                         + maxFlowThreshold);
@@ -207 +209 @@
                                 bisection = new Bisection(new Subgraph(
                                         bisection.getGraph(), cluster));
+//                              System.out.println("REFINED BISECTION: " + bisection.toString());
                         } else
                                 finished = true;