Changeset 18

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.

Location:

src/main/java/weka/clusterers/forMetisMQI

Files:

• GraphAlgorithms.java (modified) (5 diffs)
• MQI.java (modified) (11 diffs)
• Uncoarse.java (modified) (2 diffs)
• graph/Bisection.java (modified) (1 diff)
• graph/Subgraph.java (modified) (1 diff)
• util/Util.java (modified) (3 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);

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

@@ -16 +16 @@
 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 +26 @@
 
         static private Set<Node> DFSReversed(Node currentNode,
-                        DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap, Set<Node> marked) {
+                        DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap,
+                        Set<Node> marked) {
                 Collection<Edge> inEdges = g.getInEdges(currentNode);
                 Set<Node> result = new HashSet<Node>();
@@ -47 +47 @@
                 return result;
         }
-
-
 
         static private Set<Node> BFSReversed(Node sink,
@@ -83 +81 @@
 
         static private DirectedGraph<Node, Edge> prepareDirectedGraph(
-                        Bisection partition, Node source, Node sink) {
+                        Bisection partition, Node source, Node sink, boolean forConductance) {
                 Subgraph A = null;
                 Subgraph B = null;
@@ -94 +92 @@
                         B = partition.getSubgraph();
                 }
-                int a = A.getVertexCount();
+                int a = 0;
+                if (!forConductance)
+                        a = A.getVertexCount();
+                else {
+                        Iterator<Node> aIterator = A.iterator();
+                        while(aIterator.hasNext()) {
+                                a += partition.getGraph().degree(aIterator.next());
+                        }
+                }
                 int c = partition.edgeCut() / 2;
 
@@ -120 +126 @@
                 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 +137 @@
                                 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 +151 @@
                 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 +169 @@
          * @return
          */
-        static public Set<Node> mqi(Bisection partition) {
+        static public Set<Node> mqi(Bisection partition, boolean forConductance) {
 //              System.out.println("INITIAL BISECTION: " + partition.toString());
                 boolean finished = false;
                 Bisection bisection = partition;
-                Set<Node> cluster = new HashSet<Node>(partition
-                                .getSmallerNotEmptySubgraph().createInducedSubgraph()
-                                .getVertices());
+                Set<Node> cluster = new HashSet<Node>(partition.getSmallerNotEmptySubgraph()
+                                .createInducedSubgraph().getVertices());
                 int maxFlowThreshold = Integer.MAX_VALUE;
                 while (!finished) {
@@ -170 +180 @@
                         Node sink = new Node("$$$$T");
                         DirectedGraph<Node, Edge> directedGraph = prepareDirectedGraph(
-                                        bisection, source, sink);
+                                        bisection, source, sink, true);
                         Transformer<Edge, Number> capTransformer = new Transformer<Edge, Number>() {
                                 public Double transform(Edge e) {
@@ -189 +199 @@
                                         edgeFactory);
 
-                        maxFlowThreshold = bisection.getSmallerNotEmptySubgraph()
-                                        .getVertexCount()
-                                        * bisection.edgeCut() / 2;
+                        if (!forConductance)
+                                maxFlowThreshold = bisection.getSmallerNotEmptySubgraph()
+                                                .getVertexCount()
+                                                * bisection.edgeCut() / 2;
+                        else {
+                                Iterator<Node> 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<Node>());
-                                cluster.remove(sink);
-                                 bisection = new Bisection(new Subgraph(bisection.getGraph(),
-                                 cluster));
-//                              System.out.println("NEW BISECTION: " + bisection.toString());
+                                Set<Node> dfsResult = DFSReversed(sink, directedGraph,
+                                                edgeFlowMap, new HashSet<Node>());
+                                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;

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

@@ -38 +38 @@
         /**
          * 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 +47 @@
                         CoarserGraphElement element = stack.pop();
                         partition = uncoarseOneStep(partition,element);
+                        partition = GraphAlgorithms.KLRefinement(partition);
                 }
                 return partition;

src/main/java/weka/clusterers/forMetisMQI/graph/Bisection.java

@@ -122 +122 @@
         }
         
-        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<Node>();
                 return clone;

src/main/java/weka/clusterers/forMetisMQI/graph/Subgraph.java

@@ -260 +260 @@
                 return FilterUtils.createInducedSubgraph(nodes,g);
         }
+        
+        public int totalDegree() {
+                int result = 0;
+                Iterator<Node> nodeIterator = iterator();
+                while(nodeIterator.hasNext()) {
+                        int degree = g.degree(nodeIterator.next());
+                        result += degree;
+                }
+                return result;
+        }
 }

src/main/java/weka/clusterers/forMetisMQI/util/Util.java

@@ -5 +5 @@
 import java.awt.Paint;
 import java.util.HashMap;
+import java.util.HashSet;
 import java.util.Iterator;
 import java.util.Map;
@@ -18 +19 @@
 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 +26 @@
 
 public class Util {
+        
+        public static void viewCluster(Graph<Node, Edge> g, Set<Node> cluster) {
+                Set<Set<Node>> clusters = new HashSet<Set<Node>>();
+                clusters.add(cluster);
+                viewClusters(g, clusters);
+        }
+        
+        
         public static void viewClusters(Graph<Node, Edge> g, Set<Set<Node>> clusters) {
                 Layout<Node, Edge> layout = new FRLayout<Node, Edge>(g);