Changeset 12

Timestamp:

Sep 16, 2010, 7:01:57 PM (14 years ago)

Author:

gnappo

Message:

Visualizzazione dei cluster. (da spostare)

Location:

src/main/java/weka/clusterers/forMetisMQI

Files:

• GraphAlgorithms.java (modified) (4 diffs)
• MQI.java (modified) (6 diffs)
• graph/Bisection.java (modified) (1 diff)

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

@@ -1 +1 @@
 package weka.clusterers.forMetisMQI;
 
+import java.util.HashSet;
+import java.util.Set;
 import java.util.Stack;
 
@@ -10 +12 @@
 
 public class GraphAlgorithms {
-        
+
         public Bisection KL(UndirectedGraph g) {
                 Bisection partition = new Bisection(g);
@@ -16 +18 @@
                 int bestEdgeCut = Integer.MAX_VALUE;
                 Node u = partition.getCandidate();
-                while(u != null) {
+                while (u != null) {
                         partition.swap(u);
-                        if(partition.edgeCut() <=  bestEdgeCut) {
+                        if (partition.edgeCut() <= bestEdgeCut) {
                                 bestEdgeCut = partition.edgeCut();
                                 result = partition.copy();
@@ -26 +28 @@
                 return result;
         }
-        
+
         public void METIS(UndirectedGraph g) {
-                MQI.viewGraph(g);
-                Bisection partition = null;
-                Coarse.setFinerSize(8);
-                Stack<CoarserGraphElement> stack = Coarse.coarse(g);
-                if(stack.size() > 0) {
-                        partition = KL(stack.peek().getContracted());
-                        System.out.println(partition.toString());
-                        partition = new Uncoarse().uncoarse(stack, partition);
-                        System.out.println(partition.toString());
+//              MQI.viewGraph(g);
+                Set<Set<Node>> clusters = new HashSet<Set<Node>>();
+                for (int i = 0; i < 8; i++) {
+                        Coarse.setFinerSize(8);
+                        Stack<CoarserGraphElement> stack = Coarse.coarse(g);
+                        Bisection partition = null;
+                        if (stack.size() > 0) {
+                                partition = KL(stack.peek().getContracted());
+//                              System.out.println(partition.toString());
+                                partition = new Uncoarse().uncoarse(stack, partition);
+//                              System.out.println(partition.toString());
+                                Set<Node> cluster = MQI.mqi(partition);
+                                clusters.add(cluster);
+//                              Set<Set<Node>> foundCluster = new HashSet<Set<Node>>();
+//                              foundCluster.add(cluster);
+//                              MQI.viewClusters(g, foundCluster);
+                        }
                 }
-                System.out.println("AAAAAA");
-                System.out.println(MQI.mqi(partition).toString());
-                
+                MQI.viewClusters(g, clusters);
         }
 

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

@@ -1 +1 @@
 package weka.clusterers.forMetisMQI;
 
+import java.awt.Color;
 import java.awt.Dimension;
+import java.awt.Paint;
+import java.util.Collection;
 import java.util.HashMap;
+import java.util.HashSet;
 import java.util.Iterator;
 import java.util.Map;
 import java.util.Set;
+import java.util.Stack;
 
 import javax.swing.JFrame;
@@ -30 +35 @@
         static int i = -1;
         
+        public static void viewClusters(Graph<Node, Edge> g, Set<Set<Node>> clusters) {
+                Layout<Node, Edge> layout = new KKLayout<Node, Edge>(g);
+                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);
+
+                class VertexPaintTransformer implements Transformer<Node, Paint> {
+                        Set<Set<Node>> clusters = null;
+                        Map<Set<Node>, Color> clustersColor = null;
+
+                        public Set<Node> getCluster(Node node) {
+                                Iterator<Set<Node>> clusterIterator = clusters.iterator();
+                                while (clusterIterator.hasNext()) {
+                                        Set<Node> cluster = clusterIterator.next();
+                                        if (cluster.contains(node))
+                                                return cluster;
+                                }
+                                return null;
+                        }
+
+                        public VertexPaintTransformer(Set<Set<Node>> clusters) {
+                                this.clusters = clusters;
+                                clustersColor = new HashMap<Set<Node>, Color>(clusters.size());
+                                Iterator<Set<Node>> clusterIterator = clusters.iterator();
+                                while (clusterIterator.hasNext()) {
+                                        Set<Node> cluster = clusterIterator.next();
+                                        clustersColor.put(cluster, new Color(Random.instance()
+                                                        .nextInt(256), Random.instance().nextInt(256),
+                                                        Random.instance().nextInt(256)));
+                                }
+                        }
+
+                        public Paint transform(Node i) {
+                                Set<Node> cluster = getCluster(i);
+                                if (cluster == null)
+                                        return Color.RED;
+                                else
+                                        return clustersColor.get(getCluster(i));
+                        }
+                }
+
+                Transformer<Node, Paint> vertexPaint = new VertexPaintTransformer(
+                                clusters);
+                vv.setPreferredSize(new Dimension(800, 600)); // Sets the viewing area
+                                                                                                                // size
+                vv.getRenderContext().setVertexLabelTransformer(
+                                new ToStringLabeller<Node>());
+                vv.getRenderContext().setEdgeLabelTransformer(
+                                new ToStringLabeller<Edge>());
+                vv.getRenderContext().setVertexFillPaintTransformer(vertexPaint);
+                JFrame frame = new JFrame("Graph View");
+                frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
+                frame.getContentPane().add(vv);
+                frame.pack();
+                frame.setVisible(true);
+        }
+        
         public static void viewGraph(Graph<Node, Edge> g){
                 Layout<Node, Edge> layout = new KKLayout<Node, Edge>(g);
@@ -47 +110 @@
         }
 
-        /**
-         * 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 private Set<Node> BFSReversed(Node sink, DirectedGraph<Node, Edge> g, Map<Edge, Number> edgeFlowMap) {
+                Set<Node> result = new HashSet<Node>();
+                Set<Node> visitedNodes = new HashSet<Node>();
+                Stack<Node> nodesToVisit = new Stack<Node>();
+                result.add(sink);
+                nodesToVisit.push(sink);
+                while(!nodesToVisit.empty()) {
+                        Node currentNode = nodesToVisit.pop();
+                        visitedNodes.add(currentNode);
+                        Collection<Edge> inEdges = g.getInEdges(currentNode);
+                        Iterator<Edge> inEdgesIterator = inEdges.iterator();
+                        while(inEdgesIterator.hasNext()) {
+                                Edge edge = inEdgesIterator.next();
+                                Node src = g.getSource(edge);
+                                Edge reverseEdge = g.findEdge(src, currentNode);
+                                if((reverseEdge != null) && ((Integer)edgeFlowMap.get(reverseEdge) < reverseEdge.getCapacity())) {
+                                        if(!nodesToVisit.contains(src) && !visitedNodes.contains(src)) {
+                                                nodesToVisit.push(src);
+                                        }
+                                        result.add(src);
+                                }
+                        }
+                }
+                return result;
         }
         
@@ -66 +139 @@
                 Subgraph A = null;
                 Subgraph B = null;
-                if(partition.getSubgraph().getVertexCount() > partition.getComplement().getVertexCount()) {
+                if(partition.getSubgraph().getVertexCount() < partition.getComplement().getVertexCount()) {
                         A = partition.getSubgraph();
                         B = partition.getComplement();
@@ -123 +196 @@
         }
         
-        static public Bisection mqi(Bisection partition) {
+        /**
+         * Given a partion of a graph, execute the Max-Flow Quotient-cut Improvement algorithm,
+         * to find an improved cut and then returns the cluster which yields the best quotient cut.
+         * @param partition
+         * @return
+         */
+        static public Set<Node> mqi(Bisection partition) {
+                System.out.println("INITIAL BISECTION: " + partition.toString());
                 boolean finished = false;
                 Bisection bisection = partition;
+                Set<Node> cluster = new HashSet<Node>(partition.getSubgraph().createInducedSubgraph().getVertices());
                 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);
+                        DirectedGraph<Node, Edge> directedGraph = prepareDirectedGraph(bisection, source, sink);
                         Transformer<Edge, Number> capTransformer = new Transformer<Edge, Number>() {
                                 public Double transform(Edge e) {
@@ -147 +227 @@
                         };
                         EdmondsKarpMaxFlow<Node, Edge> alg = new EdmondsKarpMaxFlow<Node, Edge>(
-                                        g, source, sink, capTransformer, edgeFlowMap, edgeFactory);
+                                        directedGraph, source, sink, capTransformer, edgeFlowMap, edgeFactory);
                         
-                        maxFlowThreshold = getMaxCardinality(bisection) * bisection.edgeCut() / 2; 
+                        maxFlowThreshold = bisection.getSmallerSubgraph().getVertexCount() * bisection.edgeCut() / 2; 
                         alg.evaluate();
+                        System.out.println("MAX FLOW: " + alg.getMaxFlow() + " THRESHOLD: " + maxFlowThreshold);
                         if(alg.getMaxFlow() < maxFlowThreshold) {
                                 Set<Node> sinkPartition = alg.getNodesInSinkPartition();
+                                System.out.println(sinkPartition);
                                 Set<Node> sourcePartition = alg.getNodesInSourcePartition();
-                                bisection = prepareBisection(startingGraph, sourcePartition, sinkPartition);
+                                System.out.println(sourcePartition);
+                                bisection = prepareBisection(bisection.getSmallerSubgraph().createInducedSubgraph(), sourcePartition, sinkPartition);
+//                              bisection = new Bisection(new Subgraph(bisection.getSmallerSubgraph().createInducedSubgraph(), BFSReversed(sink, directedGraph, edgeFlowMap)));
+                                System.out.println("NEW BISECTION: " + bisection.toString());
+                                cluster = sinkPartition;
                         } else
                                 finished = true;
                 }
-                return bisection;
+                return cluster;
         }
         

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

@@ -137 +137 @@
                 return out;
         }
+        
+        /**
+         * Returns the smaller subgraph of this bisection.
+         * @return
+         */
+        public Subgraph getSmallerSubgraph() {
+                if(a.getVertexCount() < b.getVertexCount())
+                        return a;
+                else
+                        return b;
+        }
 }