Changeset 11 for src/main/java/weka/clusterers/forMetisMQI/MQI.java

Timestamp:

Sep 16, 2010, 10:44:40 AM (14 years ago)

Author:

gnappo

Message:

Un po' di refactoring e implementazione dell'algoritmo di raffinamento.

File:

• src/main/java/weka/clusterers/forMetisMQI/MQI.java (modified) (6 diffs)

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

@@ -2 +2 @@
 
 import java.awt.Dimension;
+import java.util.HashMap;
 import java.util.Iterator;
+import java.util.Map;
+import java.util.Set;
 
 import javax.swing.JFrame;
 
+import org.apache.commons.collections15.Factory;
+import org.apache.commons.collections15.Transformer;
+
+import weka.clusterers.forMetisMQI.graph.Bisection;
+import weka.clusterers.forMetisMQI.graph.Edge;
+import weka.clusterers.forMetisMQI.graph.Node;
+import weka.clusterers.forMetisMQI.graph.Subgraph;
+import weka.clusterers.forMetisMQI.graph.UndirectedGraph;
+import edu.uci.ics.jung.algorithms.flows.EdmondsKarpMaxFlow;
 import edu.uci.ics.jung.algorithms.layout.KKLayout;
 import edu.uci.ics.jung.algorithms.layout.Layout;
+import edu.uci.ics.jung.graph.DirectedGraph;
 import edu.uci.ics.jung.graph.DirectedSparseGraph;
 import edu.uci.ics.jung.graph.Graph;
@@ -15 +28 @@
 public class MQI {
         
+        static int i = -1;
+        
         public static void viewGraph(Graph<Node, Edge> g){
                 Layout<Node, Edge> layout = new KKLayout<Node, Edge>(g);
-                layout.setSize(new Dimension(300,300)); // sets the initial size of the space
+                layout.setSize(new Dimension(800,600)); // sets the initial size of the space
                 // The BasicVisualizationServer<V,E> is parameterized by the edge types
                 BasicVisualizationServer<Node,Edge> vv =
                 new BasicVisualizationServer<Node,Edge>(layout);
-                vv.setPreferredSize(new Dimension(350,350)); //Sets the viewing area size
+                vv.setPreferredSize(new Dimension(800,600)); //Sets the viewing area size
                 vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<Node>());
                 vv.getRenderContext().setEdgeLabelTransformer(new ToStringLabeller<Edge>());
@@ -31 +46 @@
                 frame.setVisible(true);
         }
+
+        /**
+         * Given a bisection, returns the cardinality of the larger subgraph.
+         * @param b
+         * @return
+         */
+        static private int getMaxCardinality(Bisection b) {
+                Subgraph A = null;
+                if(b.getSubgraph().getVertexCount() > b.getComplement().getVertexCount()) {
+                        A = b.getSubgraph();
+                }
+                else {
+                        A = b.getComplement();
+                }
+                return A.getVertexCount();
+        }
         
-        static public void start(KLPartition partition) {
+        static private DirectedGraph<Node,       Edge> prepareDirectedGraph(Bisection partition, Node source, Node sink) {
                 Subgraph A = null;
                 Subgraph B = null;
@@ -44 +75 @@
                 }
                 int a = A.getVertexCount();
-                int c = partition.edgeCut();
+                int c = partition.edgeCut() / 2;
                 
                 
-                Graph<Node,Edge> g = new DirectedSparseGraph<Node, Edge>();
+                DirectedGraph<Node,Edge> g = new DirectedSparseGraph<Node, Edge>();
                 Iterator<Node> nodes =  A.iterator();
                 while(nodes.hasNext()) {
@@ -66 +97 @@
                 }
                 
-                Node source = new Node("S");
-                Node sink = new Node("T");
                 g.addVertex(source);
                 g.addVertex(sink);
@@ -91 +120 @@
                         id++;
                 }
-                
-//              viewGraph(g);
-                System.out.println(g.toString());
-                
+                return g;
+        }
+        
+        static public Bisection mqi(Bisection partition) {
+                boolean finished = false;
+                Bisection bisection = partition;
+                int maxFlowThreshold = Integer.MAX_VALUE;
+                while (!finished) {
+                        UndirectedGraph startingGraph = partition.getGraph();
+                        Node source = new Node("S");
+                        Node sink = new Node("T");
+                        DirectedGraph<Node, Edge> g = prepareDirectedGraph(bisection, source, sink);
+                        Transformer<Edge, Number> capTransformer = new Transformer<Edge, Number>() {
+                                public Double transform(Edge e) {
+                                        return (double) e.getCapacity();
+                                }
+                        };
+                        Map<Edge, Number> edgeFlowMap = new HashMap<Edge, Number>();
+                        // This Factory produces new edges for use by the algorithm
+                        i=-1;
+                        Factory<Edge> edgeFactory = new Factory<Edge>() {
+                                public Edge create() {
+                                        i++;
+                                        return new Edge(Integer.toString(i), 1, 1);
+                                }
+                        };
+                        EdmondsKarpMaxFlow<Node, Edge> alg = new EdmondsKarpMaxFlow<Node, Edge>(
+                                        g, source, sink, capTransformer, edgeFlowMap, edgeFactory);
+                        
+                        maxFlowThreshold = getMaxCardinality(bisection) * bisection.edgeCut() / 2; 
+                        alg.evaluate();
+                        if(alg.getMaxFlow() < maxFlowThreshold) {
+                                Set<Node> sinkPartition = alg.getNodesInSinkPartition();
+                                Set<Node> sourcePartition = alg.getNodesInSourcePartition();
+                                bisection = prepareBisection(startingGraph, sourcePartition, sinkPartition);
+                        } else
+                                finished = true;
+                }
+                return bisection;
+        }
+        
+        private static Bisection prepareBisection(UndirectedGraph g, Set<Node> sourcePartition, Set<Node> sinkPartition) {
+                Bisection b = null;
+                Subgraph sourceSubgraph = new Subgraph(g, sourcePartition);
+                Subgraph sinkSubgraph = new Subgraph(g, sinkPartition);
+                Subgraph subgraph = null;
+                if(sourceSubgraph.getVertexCount() > sinkSubgraph.getVertexCount())
+                        subgraph =sourceSubgraph;
+                else
+                        subgraph = sinkSubgraph;
+                b = new Bisection(subgraph);
+                return b;
         }