source: branches/localSpectral/src/clustering/GraphClusterer.java

package clustering;

import data.GraphBuilder;
import edu.uci.ics.jung.graph.DirectedSparseGraph;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.graph.SparseGraph;
import edu.uci.ics.jung.graph.util.Pair;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.ArrayList;
import java.util.Collection;
import java.util.List;
import java.util.Scanner;
import view.Viewer;

public class GraphClusterer implements ActionListener{

    private List<VertexScore<String>> global_ranking;
    private int currentElement;
    private Viewer viewGraph;
    private Graph<String, Integer> graph;
    private boolean main_graph_output;
    private boolean cluster_graph_output;
    private boolean isGraphDirected;
    private int minvolume;
    LocalSpectral<String,String> clusterer;

    public GraphClusterer(String path, boolean isGraphDirected,int min_volume, boolean graph_output) {
        global_ranking = null;
        this.currentElement = 0;
        GraphBuilder builder = new GraphBuilder(isGraphDirected);
        builder.buildGraphFromCVS(path, 1);
        graph = builder.getGraph();
        if(graph_output){
            viewGraph = new Viewer(graph, this);
            this.main_graph_output = true;
        }
        else
            this.main_graph_output = false;
        this.isGraphDirected = isGraphDirected;
        this.minvolume = min_volume;
        System.out.println("Graph data: nodes "+graph.getVertexCount()+" edges "+graph.getEdgeCount());
        System.out.flush();
        //System.out.println("What is the min cluster volume? ");
        //Scanner in = new Scanner(System.in);
        //this.minvolume = in.nextInt();
        this.clusterer = new LocalSpectral(graph);
    }

    public void actionPerformed(ActionEvent ae) {
        this.visualNextCluster();
    }

    public void clusterize(boolean main_graph_output, boolean cluster_graph_output){

       global_ranking = clusterer.getGlobalRank();
       this.main_graph_output = main_graph_output;
       this.cluster_graph_output = cluster_graph_output;

       System.out.println("GLOBAL RANKING");
       for(VertexScore<String> v : global_ranking)
           System.out.println(v.toString());
       
       if (main_graph_output){
           viewGraph.setText("Nodes: "+graph.getVertexCount() + "\nEdges: "+graph.getEdgeCount());
           viewGraph.viewGraphRank(global_ranking,null);
       }
       else{
           for(int i=0; i< this.global_ranking.size(); i++)
               visualNextCluster();
       }
    }

    public float getConductance(Graph<String,Integer> graph, List<String> cluster){
        int volume_graph = 2 * graph.getEdgeCount();
        int volume_cluster = 0;
        int edge_boundary = 0;
        for(String vertex : cluster){
            volume_cluster += graph.getInEdges(vertex).size();
            for(Integer e : graph.getOutEdges(vertex)){
                String opposite = graph.getOpposite(vertex, e);
                if(!cluster.contains(opposite))
                    edge_boundary++;
            }

        }
        if(volume_cluster > 0){
           double volume = volume_cluster;
           if (volume_cluster > (volume_graph - volume_cluster))
                volume = volume_graph - volume_cluster;
           double conductance = edge_boundary / volume;
           return (float) conductance;
        }
        else
            return 0;

    }

    public void visualNextCluster(){
       if(this.currentElement > global_ranking.size()-1)
           return;

       List<String> seed = new ArrayList<String>();
       seed.add(global_ranking.get(currentElement).getVertex());
       List<String> cut = clusterer.clusterPageRankPriors(seed,this.minvolume);
       Graph cut_graph;
       if (isGraphDirected)
            cut_graph = new DirectedSparseGraph<String, Edge<String>>();
        else
            cut_graph = new SparseGraph<String, Edge<String>>();
       for(String vertex : cut){
           Collection<Integer> out_edges = graph.getOutEdges(vertex);
           for(Integer edge : out_edges){
               String out_node = graph.getOpposite(vertex, edge);
               if (cut.contains(out_node)){
                   Pair<String> edge_nodes = graph.getEndpoints(edge);
                   cut_graph.addEdge(edge,edge_nodes.getFirst() ,edge_nodes.getSecond());
               }
           }
       }
       if (cluster_graph_output){
           viewGraph.setGraph(cut_graph);
           float vertex_rank = (float) global_ranking.get(this.currentElement).getScore();
           viewGraph.setText("Nodes: "+cut_graph.getVertexCount() + "\nEdges: "+cut_graph.getEdgeCount()
                   + "\nPage Rank Value: "+vertex_rank + "\nConductance: "+this.getConductance(graph, cut) + "\nSeed Element: "+global_ranking.get(this.currentElement).getVertex());
           //viewGraph.viewClusterRankedInGraph(global_ranking, global_ranking.get(this.currentElement).getVertex(),cut);
           viewGraph.viewGraphRank(global_ranking, global_ranking.get(this.currentElement).getVertex());
       }

       this.currentElement++;

     }
}