source: src/main/java/weka/clusterers/forMetisMQI/MQI.java @ 11

package weka.clusterers.forMetisMQI;

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;
import edu.uci.ics.jung.visualization.BasicVisualizationServer;
import edu.uci.ics.jung.visualization.decorators.ToStringLabeller;

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(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(800,600)); //Sets the viewing area size
                vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<Node>());
                vv.getRenderContext().setEdgeLabelTransformer(new ToStringLabeller<Edge>());

                JFrame frame = new JFrame("Simple Graph View");
                frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
                frame.getContentPane().add(vv);
                frame.pack();
                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 private DirectedGraph<Node,       Edge> prepareDirectedGraph(Bisection partition, Node source, Node sink) {
                Subgraph A = null;
                Subgraph B = null;
                if(partition.getSubgraph().getVertexCount() > partition.getComplement().getVertexCount()) {
                        A = partition.getSubgraph();
                        B = partition.getComplement();
                }
                else {
                        A = partition.getComplement();
                        B = partition.getSubgraph();
                }
                int a = A.getVertexCount();
                int c = partition.edgeCut() / 2;
                
                
                DirectedGraph<Node,Edge> g = new DirectedSparseGraph<Node, Edge>();
                Iterator<Node> nodes =  A.iterator();
                while(nodes.hasNext()) {
                        Node u = nodes.next();
                        g.addVertex(u);
                }
                
                nodes =  A.iterator();
                int id = 0;
                while(nodes.hasNext()) {
                        Node u = nodes.next();
                        Iterator<Node> neighbors = A.getNeighbors(u).iterator();
                        while(neighbors.hasNext()) {
                                Node v = neighbors.next();
                                g.addEdge(new Edge(Integer.toString(id),A.getWeight(u, v),a),u,v);
                                id++;
                        }
                }
                
                g.addVertex(source);
                g.addVertex(sink);
                
                
                nodes =  B.iterator();
                while(nodes.hasNext()) {
                        Node u = nodes.next();
                        Iterator<Node> neighbors = B.getGraph().getNeighbors(u).iterator();
                        while(neighbors.hasNext()) {
                                Node v = neighbors.next();
                                if(A.contains(v)) {
                                        g.addEdge(new Edge(Integer.toString(id),1,a),source,v);
                                        id++;
                                }
                        }
                }
                
                nodes =  A.iterator();
                while(nodes.hasNext()) {
                        Node u = nodes.next();
                        g.addEdge(new Edge(Integer.toString(id),1,c),u,sink);
                        id++;
                }
                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;
        }
        
}