Changeset 36 for branches/localSpectral/src/clustering/GraphClusterer.java

Timestamp:

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

Author:

toshi

Message:

ultimo commit

File:

• branches/localSpectral/src/clustering/GraphClusterer.java (modified) (5 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++;