source: branches/MetisMQI/src/main/java/weka/clusterers/forMetisMQI/GraphAlgorithms.java

package weka.clusterers.forMetisMQI;

import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.Stack;

import org.jdom.Document;
import org.jdom.Element;
import org.jdom.output.Format;
import org.jdom.output.XMLOutputter;

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;
import weka.clusterers.forMetisMQI.util.Configuration;
import weka.clusterers.forMetisMQI.util.GraphsFrame;
import weka.clusterers.forMetisMQI.util.Random;
import weka.clusterers.forMetisMQI.util.Util;

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;
        }
        
        
        /**
         * Given an undirected graph, performs the Kernighan-Li algorithm to find a bisection and
         * then returns it.
         * @param g
         * @return
         */
        static public Bisection KL(UndirectedGraph g) {
                int remainingNumberOfSwap = 50;
                Bisection partition = new Bisection(g);
                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;
        }
        
        static public Bisection metis(UndirectedGraph g, int sizeFinerGraph) {
                Coarse.setFinerSize(sizeFinerGraph);
                Stack<CoarserGraphElement> stack = Coarse.coarse(g);
                Bisection partition = null;
                if (stack.size() > 0) {
                        partition = KL(stack.peek().getContracted());
                        if(Configuration.instance().getVerboseLevel() > 1) {
                                GraphsFrame.instance().addPanel(Util.panelContractedGraph(stack.peek()));
                                GraphsFrame.instance().addPanel(Util.panelContractedGraph(stack.peek(),partition.getSmallerSubgraph().createInducedSubgraph().getVertices()));
                        }
                        partition = Uncoarse.uncoarse(stack, partition);
                }
                return partition;
        }

        /**
         * Given an UndirectedGraph, runs metis+mqi for <code>numberOfCluster</code> times and
         * returns a set of clusters. With the third parameter you can control the maximum size of the finer
         * graph during the coarsening phase.  
         * @param g
         * @param numberOfCluster
         * @param sizeFinerGraph
         */
        static public Set<Set<Node>> metisMqi(UndirectedGraph g) {
                int numberOfCluster = Configuration.instance().getNumberOfClusters();
                boolean randomBisection = Configuration.instance().isRandomBisection();
                int sizeFinerGraph = Configuration.instance().getSizeFinerGraph();
                int verboseLevel = Configuration.instance().getVerboseLevel();
                GraphsFrame gf = GraphsFrame.instance();
                
                Element rootXML = new Element("run");
                Document logXML = new Document(rootXML);
                rootXML.setAttribute("seed", Long.toString(Random.instance().getSeed()));
                Element graphXML = new Element("graph");
                graphXML.addContent(new Element("vertex").setText(Integer.toString(g.getVertexCount())));
                graphXML.addContent(new Element("edge").setText(Integer.toString(g.getEdgeCount())));
                rootXML.addContent(graphXML);
                Element clustersXML = new Element("clusters");
                rootXML.addContent(clustersXML);
                
                System.out.println("Seed: " + Random.instance().getSeed());
                System.out.println("Vertex count: " + g.getVertexCount());
                System.out.println("Edges count: " + g.getEdgeCount());
                Set<Set<Node>> clusters = new HashSet<Set<Node>>();
                UndirectedGraph gclone = g.clone();
                
                for (int i = 0; i < numberOfCluster; i++) {
                        Bisection bisection = null;
                        if(verboseLevel > 1)
                                gf.addPanel(Util.panelGraph(g.clone()));
                        if(!randomBisection)
                                bisection = metis(g,sizeFinerGraph);
                        else
                                bisection = new Bisection(g);
                        
                        if(verboseLevel > 1)
                                gf.addPanel(Util.panelCluster(g.clone(),bisection.getSmallerSubgraph().createInducedSubgraph().getVertices()));
                        
                        System.out.print("Initial partition: ");
                        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)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();
                        
//                      System.out.println(cluster);
                        Bisection mqiBisection = new Bisection(new Subgraph(g,cluster));
                        System.out.println("Refined partition (MQI)");
                        double newConductance = ((double)mqiBisection.edgeCut() / 2) / Math.min(mqiBisection.getSubgraph().totalDegree(),mqiBisection.getComplement().totalDegree());
                        System.out.print("Cluster "+ i + ":  V=" + clusterGraph.getVertexCount() + ", E=" + clusterGraph.getEdgeCount()+", ");
                        System.out.println("Cond: " + newConductance);
                        
                        
                        mqiBisection = new Bisection(new Subgraph(gclone,cluster));
                        newConductance = ((double)mqiBisection.edgeCut() / 2) / Math.min(mqiBisection.getSubgraph().totalDegree(),mqiBisection.getComplement().totalDegree());
                        System.out.println("Cluster conductance: " + newConductance);
                        
                        
                        Element clusterXML = new Element("cluster");
                        clusterXML.setAttribute("id", Integer.toString(i));
                        clusterXML.addContent(new Element("vertex").setText(Integer.toString(clusterGraph.getVertexCount())));
                        clusterXML.addContent(new Element("edge").setText(Integer.toString(clusterGraph.getEdgeCount())));
                        clusterXML.addContent(new Element("conductance").setText(Double.toString(newConductance)));
                        clustersXML.addContent(clusterXML);
                        
                        clusters.add(cluster);
                        
                        System.out.println();
                        Iterator<Node> clustersNode = cluster.iterator();
                        while(clustersNode.hasNext()){
                                g.removeVertex(clustersNode.next());
                        }
                }
                
                
                XMLOutputter xmlOutputter = new XMLOutputter();
                xmlOutputter.setFormat(Format.getPrettyFormat());
                try {
                        xmlOutputter.output(logXML, new FileOutputStream(new File(Configuration.instance().getOutputFile())));
                } catch (IOException e) {
                        e.printStackTrace();
                }
                
                if(verboseLevel > 0) {
                        gf.addPanel(Util.panelClusters(gclone, clusters));
                        gf.setVisible(true);
                }
                return clusters;
        }

}