Changeset 36 for branches/localSpectral/src/clustering

Timestamp:

Jan 6, 2011, 9:41:42 AM (14 years ago)

Author:

toshi

Message:

ultimo commit

Location:

branches/localSpectral/src/clustering

Files:

• GraphClusterer.java (modified) (5 diffs)
• LocalSpectral.java (modified) (6 diffs)
• VertexScore.java (modified) (2 diffs)

branches/localSpectral/src/clustering/GraphClusterer.java

@@ -6 +6 @@
 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;
 
@@ -17 +20 @@
     private int currentElement;
     private Viewer viewGraph;
-    private Graph<String, Edge<String>> graph;
-    private boolean graph_output;
+    private Graph<String, Integer> graph;
+    private boolean main_graph_output;
+    private boolean cluster_graph_output;
     private boolean isGraphDirected;
     private int minvolume;
-    LocalSpectral<String,Edge<String>> clusterer;
+    LocalSpectral<String,String> clusterer;
 
-    public GraphClusterer(String path, boolean isGraphDirected,int min_volume) {
+    public GraphClusterer(String path, boolean isGraphDirected,int min_volume, boolean graph_output) {
         global_ranking = null;
         this.currentElement = 0;
         GraphBuilder builder = new GraphBuilder(isGraphDirected);
-        builder.buildGraphFromARFF(path, 1000000);
+        builder.buildGraphFromCVS(path, 1);
         graph = builder.getGraph();
-        viewGraph = new Viewer(graph, this);
-        graph_output = true;
+        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) {
-        System.out.println("Clicked!");
         this.visualNextCluster();
     }
 
-    public void clusterize(boolean graph_output){
+    public void clusterize(boolean main_graph_output, boolean cluster_graph_output){
 
        global_ranking = clusterer.getGlobalRank();
-       this.graph_output = graph_output;
+       this.main_graph_output = main_graph_output;
+       this.cluster_graph_output = cluster_graph_output;
 
        System.out.println("GLOBAL RANKING");
@@ -50 +63 @@
            System.out.println(v.toString());
        
-       if (graph_output)
-            viewGraph.viewGraphRank(global_ranking,null);
+       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;
+
     }
 
@@ -57 +101 @@
        if(this.currentElement > global_ranking.size()-1)
            return;
-       
-       List<String> cut = clusterer.clusterPageRankPriors(global_ranking.get(currentElement).getVertex(),this.minvolume);
+
+       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)
@@ -65 +111 @@
             cut_graph = new SparseGraph<String, Edge<String>>();
        for(String vertex : cut){
-           Collection<Edge<String>> out_edges = graph.getOutEdges(vertex);
-           for(Edge<String> edge : out_edges){
+           Collection<Integer> out_edges = graph.getOutEdges(vertex);
+           for(Integer edge : out_edges){
                String out_node = graph.getOpposite(vertex, edge);
                if (cut.contains(out_node)){
-                   cut_graph.addEdge(edge, edge.getVertex1(),edge.getVertex2());
+                   Pair<String> edge_nodes = graph.getEndpoints(edge);
+                   cut_graph.addEdge(edge,edge_nodes.getFirst() ,edge_nodes.getSecond());
                }
            }
        }
-       viewGraph.setGraph(cut_graph);
-       float vertex_rank = (float) global_ranking.get(this.currentElement).getScore();
-       viewGraph.setText("Page Rank Value: "+vertex_rank);
-       if (graph_output)
-            viewGraph.viewGraphRank(global_ranking, global_ranking.get(this.currentElement).getVertex());
+       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++;

branches/localSpectral/src/clustering/LocalSpectral.java

@@ -49 +49 @@
         rank.evaluate();
         Collection<V> vertexs = graph.getVertices();
-        Iterator<?> vertexsIterator = vertexs.iterator();
+        Iterator<V> vertexsIterator = vertexs.iterator();
         ArrayList<VertexScore<V>> vertexsScore = new ArrayList<VertexScore<V>>();
         while(vertexsIterator.hasNext()){
-            V vertex = (V) vertexsIterator.next();
+            V vertex =  vertexsIterator.next();
             Double score = (Double) rank.getVertexScore(vertex);
-            VertexScore<V> vertexscore = new VertexScore<V>(vertex,score);
+            VertexScore<V> vertexscore = new VertexScore<V>(vertex,score.floatValue());
             vertexsScore.add(vertexscore);
         }
@@ -62 +62 @@
     }
     
-    public List<V> clusterPageRankPriors(V seed, double min_volume){
+    public List<V> clusterPageRankPriors(List<V> seed, double min_volume){
         PageRankWithPriors rank;
         if(seed != null){
-            Transformer transf = new SeedTransformer(seed);
-            rank = new PageRankWithPriors(graph, transf, alpha);
+            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{
@@ -79 +86 @@
             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);
+            int degree = graph.inDegree(vertex);
+            VertexScore<V> vertexscore = new VertexScore<V>(vertex,score.floatValue()/degree);
             vertexsScore.add(vertexscore);
         }
@@ -103 +110 @@
             int edge_boundary = 0;
             for(int j=0; j<i; j++){
-                volume_subset += graph.getIncidentEdges(vertexsScore.get(j).getVertex()).size();
+                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);
@@ -117 +124 @@
 
                 if ((volume_subset > min_volume) && (volume_subset < max_volume)){
-                //if (volume_subset < min_volume){
                     if (conductance < min_conductance_subset){
                         min_conductance_subset = conductance;
@@ -143 +149 @@
     }
 
+
 }

branches/localSpectral/src/clustering/VertexScore.java

@@ -5 +5 @@
 
     private V vertex;
-    private double score;
+    private float score;
 
-    public VertexScore(V vertex, double score) {
+    public VertexScore(V vertex, float score) {
         this.vertex = vertex;
         this.score = score;
@@ -16 +16 @@
     }
 
-    public void setScore(double score) {
+    public void setScore(float score) {
         this.score = score;
     }