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

package clustering;

import edu.uci.ics.jung.algorithms.scoring.PageRank;
import edu.uci.ics.jung.algorithms.scoring.PageRankWithPriors;
import edu.uci.ics.jung.graph.Graph;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import org.apache.commons.collections15.Transformer;


public class LocalSpectral<V,E> {

    Graph<V,E> graph;

    double alpha = 0.15;

    public Graph<V, E> getGraph() {
        return graph;
    }

    public void setGraph(Graph<V, E> graph) {
        this.graph = graph;
    }

    public LocalSpectral(Graph<V,E> input){
        graph = input;
    }

    public void removeCutEdges(List<V> cut){
        for(V vertex : cut){
            Collection<E> out_edges = graph.getOutEdges(vertex);
            for(E edge : out_edges){
                V opposite_vertex = graph.getOpposite(vertex, edge);
                if (!cut.contains(opposite_vertex)){
                    graph.removeEdge(edge);
                }
            }
        }

    }

    public List<VertexScore<V>> getGlobalRank(){
        PageRankWithPriors rank;
        rank = new PageRank(graph, alpha);
        rank.evaluate();
        Collection<V> vertexs = graph.getVertices();
        Iterator<V> vertexsIterator = vertexs.iterator();
        ArrayList<VertexScore<V>> vertexsScore = new ArrayList<VertexScore<V>>();
        while(vertexsIterator.hasNext()){
            V vertex =  vertexsIterator.next();
            Double score = (Double) rank.getVertexScore(vertex);
            VertexScore<V> vertexscore = new VertexScore<V>(vertex,score.floatValue());
            vertexsScore.add(vertexscore);
        }

        Collections.sort(vertexsScore,new VertexScoreComparator());
        return vertexsScore;
    }
    
    public List<V> clusterPageRankPriors(List<V> seed, double min_volume){
        PageRankWithPriors rank;
        if(seed != null){
            if(seed.size() == 1){
                Transformer transf = new SeedTransformer(seed.get(0));
                rank = new PageRankWithPriors(graph, transf, alpha);
            }
            else{
                Transformer transf = new ListSeedTransformer(seed);
                rank = new PageRankWithPriors(graph, transf, alpha);
            }

        }
        else{
            rank = new PageRank(graph, alpha);
        }

        rank.evaluate();
        Collection<V> vertexs = graph.getVertices();
        Iterator<?> vertexsIterator = vertexs.iterator();
        ArrayList<VertexScore<V>> vertexsScore = new ArrayList<VertexScore<V>>();
        while(vertexsIterator.hasNext()){
            V vertex = (V) vertexsIterator.next();
            Double score = (Double) rank.getVertexScore(vertex);
            int degree = graph.inDegree(vertex);
            VertexScore<V> vertexscore = new VertexScore<V>(vertex,score.floatValue()/degree);
            vertexsScore.add(vertexscore);
        }

        Collections.sort(vertexsScore,new VertexScoreComparator());

        System.out.println("\n\nClustering with prior seed: "+seed.toString());
        
        int volume_graph = 2 * graph.getEdgeCount();
        double max_volume = (volume_graph / 3) * 2;
        double min_conductance_subset=100;
        int min_conductance_index = -1;
        int volume_cluster=0;

        int subsets_count = vertexsScore.size();
        for(int i=0; i<subsets_count; i++){
            int volume_subset = 0;
            ArrayList<V> subset = new ArrayList<V>();
            for(int j=0; j<i; j++){
                subset.add(vertexsScore.get(j).getVertex());
            }
            int edge_boundary = 0;
            for(int j=0; j<i; j++){
                volume_subset += graph.inDegree(vertexsScore.get(j).getVertex());
                for(E out_edge : graph.getOutEdges(vertexsScore.get(j).getVertex())){
                    V opposite = graph.getOpposite(vertexsScore.get(j).getVertex(), out_edge);
                    if(!subset.contains(opposite))
                        edge_boundary++;
                }
            }
            if(volume_subset > 0){
                double minvolume = volume_subset;
                if (volume_subset > (volume_graph - volume_subset))
                    minvolume = volume_graph - volume_subset;
                double conductance = edge_boundary / minvolume;

                if ((volume_subset > min_volume) && (volume_subset < max_volume)){
                    if (conductance < min_conductance_subset){
                        min_conductance_subset = conductance;
                        min_conductance_index = i;
                        volume_cluster = volume_subset;
                    }
                }
            }

        }
        System.out.println("MIN CONDUCTANCE: "+min_conductance_subset);

        System.out.println("CLUSTER: ("+min_conductance_index+" elements, volume "+ volume_cluster +", volume graph "+ 2 * this.graph.getEdgeCount()+")");
        List<V> cluster = new ArrayList<V>();
        for(int i=0; i< min_conductance_index; i++)
            cluster.add(vertexsScore.get(i).getVertex());

        String node_list = "";
        for(V node : cluster)
            node_list += node.toString() + ",";
        System.out.println(node_list);
       
        return cluster;

    }


}