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

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<?> 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);
            VertexScore<V> vertexscore = new VertexScore<V>(vertex,score);
            vertexsScore.add(vertexscore);
        }

        Collections.sort(vertexsScore,new VertexScoreComparator());
        return vertexsScore;
    }
    
    public List<V> clusterPageRankPriors(V seed, double min_volume){
        PageRankWithPriors rank;
        if(seed != null){
            Transformer transf = new SeedTransformer(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.getIncidentEdges(vertex).size();
            VertexScore<V> vertexscore = new VertexScore<V>(vertex,score/degree);
            vertexsScore.add(vertexscore);
        }

        Collections.sort(vertexsScore,new VertexScoreComparator());
        
        double sum=0;
        for(VertexScore<V> v : vertexsScore){
            System.out.println(v.getVertex().toString()+ " " + v.getScore());
            sum+=v.getScore();
        }
        System.out.println("SUM SCORES: "+sum);
        
        int volume_graph = 2 * graph.getEdgeCount();
        System.out.println("GRAPH VOLUME: " + volume_graph);
        double max_volume = (volume_graph / 3) * 2;
        double min_conductance_subset=100;
        int min_conductance_index = -1;

        int subsets_count = vertexsScore.size();
        for(int i=0; i<subsets_count; i++){
            System.out.println("i="+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.getIncidentEdges(vertexsScore.get(j).getVertex()).size();
                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;
                    }
                }
                System.out.println("CONDUCTANCE: "+conductance + " minvolume: "+minvolume + " edge_boundary: "+edge_boundary);
            }

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

        List<V> cluster = new ArrayList<V>();
        for(int i=0; i< min_conductance_index; i++)
            cluster.add(vertexsScore.get(i).getVertex());
       
        return cluster;

    }

}