Changeset 36 for branches/localSpectral/src

Timestamp:

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

Author:

toshi

Message:

ultimo commit

Location:

branches/localSpectral/src

Files:

• clustering/GraphClusterer.java (modified) (5 diffs)
• clustering/LocalSpectral.java (modified) (6 diffs)
• clustering/VertexScore.java (modified) (2 diffs)
• data/GraphBuilder.java (modified) (3 diffs)
• jung/Main.java (modified) (2 diffs)
• view/VertexPaintRankTransformer.java (modified) (2 diffs)
• view/Viewer.java (modified) (3 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;
     }

branches/localSpectral/src/data/GraphBuilder.java

@@ -2 +2 @@
 package data;
 
+import GraphType.DirectedDenseGraph;
 import clustering.Edge;
-import clustering.VertexString;
 import edu.uci.ics.jung.graph.DirectedSparseGraph;
 import edu.uci.ics.jung.graph.Graph;
 import edu.uci.ics.jung.graph.SparseGraph;
-import java.io.BufferedInputStream;
 import java.io.BufferedReader;
 import java.io.DataInputStream;
@@ -21 +20 @@
 public class GraphBuilder {
 
-    Graph<String,Edge<String>> graph;
+    Graph<String,Integer> graph;
 
     public GraphBuilder(boolean directed){
         if (directed)
-           graph = new DirectedSparseGraph<String, Edge<String>>();
+            graph = new DirectedDenseGraph<String, Integer>();
+           //graph = new DirectedSparseGraph<String, Integer>();
 
         else
-            graph = new SparseGraph<String, Edge<String>>();
+            graph = new SparseGraph<String, Integer>();
     }
 
-    public Graph<String, Edge<String>> getGraph() {
+    public Graph<String, Integer> getGraph() {
         return graph;
     }
 
-    public void buildGraphFromARFF(String path, int maxreadline){
+    public void buildGraphFromCVS(String path, int maxreadline){
         try {
             FileInputStream fstream = new FileInputStream(path);
@@ -41 +41 @@
             BufferedReader br = new BufferedReader(new InputStreamReader(in));
 
-            Set<String> vertex = new HashSet<String>();
-
             String read;
             int edge=0;
-            int count=0;
-            while(((read = br.readLine()) != null) && (count < maxreadline)){
-                count++;
-                if(!(read.contains("@DATA") || read.contains("@RELATION") || read.contains("@ATTRIBUTE") || read.trim().isEmpty())){
-                    String[] splitted = read.trim().split(",");
-                    vertex.addAll(Arrays.asList(splitted));
-                    graph.addEdge(new Edge<String>(splitted[0], splitted[1]), splitted[0], splitted[1]);
+            String[] splitted;
+            while((read = br.readLine()) != null){
+                if(!read.trim().isEmpty()){
+                    splitted = read.trim().split(",");
+                    graph.addEdge(edge, splitted[0], splitted[1]);
                     edge++;
                 }

branches/localSpectral/src/jung/Main.java

@@ -3 +3 @@
 
 import clustering.GraphClusterer;
+import data.GraphBuilder;
+import view.GraphToGraphviz;
 
 
@@ -10 +12 @@
     public static void main(String[] args) {
 
-        String path_simply_net = "/home/luke/Desktop/reteSemplice.txt";
-        String path_mike_hiddent = "/home/luke/Desktop/reteUtentiMikeHidden.arff";
-        String karate_club = "/home/luke/Desktop/karate.csv";
-        String les_miserables = "/home/luke/Desktop/lesmis.csv";
-        String power_grids = "/home/luke/Desktop/power.csv";
-        String pol_blogs = "/home/luke/Desktop/polblogs.csv";
-        String dolphins = "/home/luke/Desktop/dolphins.csv";
-        String erdos_co_authors = "/home/luke/Desktop/erdos.csv";
-        GraphClusterer cl = new GraphClusterer(dolphins,false,60);
-        cl.clusterize(true);
+        String maindir = "/home/luke/Desktop/nets/";
+        String path_simply_net = maindir+"reteSemplice.txt";
+        String path_mike_hidden = maindir+"reteUtentiMikeHidden.arff";
+        String path_mike = maindir+"reteUtentiMike.arff";
+        String karate_club = maindir+"karate.csv";
+        String les_miserables = maindir+"lesmis.csv";
+        String power_grids = maindir+"power.csv";
+        String pol_blogs = maindir+"polblogs.csv";
+        String dolphins = maindir+"dolphins.csv";
+        String erdos_co_authors = maindir+"erdos.csv";
+        String net_science = maindir+"netscience.csv";
+        String epinions = maindir + "soc-Epinions1.csv";
+        String friend_feed = maindir + "ffeed.csv";
+        boolean isDirected = true;
+        boolean mainGraphOutput = false;
+        boolean clusterGraphOutput = false;
+        GraphClusterer cl = new GraphClusterer(friend_feed,isDirected,600000, mainGraphOutput);
+        cl.clusterize(mainGraphOutput,clusterGraphOutput);
 
     }

branches/localSpectral/src/view/VertexPaintRankTransformer.java

@@ -14 +14 @@
     List<VertexScore<V>> pagerank;
     V seed_node;
+    List<V> cluster;
 
     public VertexPaintRankTransformer(List<VertexScore<V>> ranking, V seed_node){
         this.pagerank = ranking;
         this.seed_node = seed_node;
+        this.cluster = null;
     }
 
+    public VertexPaintRankTransformer(List<VertexScore<V>> ranking, V seed_node, List<V> cluster){
+        this.pagerank = ranking;
+        this.seed_node = seed_node;
+        this.cluster = cluster;
+    }
+    
     public Paint transform(V node) {
 
@@ -25 +33 @@
             if (seed_node.equals(node)){
                 return (Paint) Color.GREEN;
+            }
+        }
+        if(cluster != null){
+            if (!cluster.contains(node)){
+                return (Paint) Color.WHITE;
             }
         }

branches/localSpectral/src/view/Viewer.java

@@ -24 +24 @@
 import javax.swing.JPanel;
 import javax.swing.JTextArea;
-import javax.xml.bind.JAXB;
 import org.apache.commons.collections15.Transformer;
 
@@ -83 +82 @@
     }
 
+    public void viewClusterRankedInGraph(List<VertexScore<V>> pagerank, V seed_node, List<V> cluster){
+         VertexPaintRankTransformer vertexPaint = new VertexPaintRankTransformer(pagerank,seed_node, cluster);
+         vv.getRenderContext().setVertexFillPaintTransformer((Transformer<V, Paint>) vertexPaint);
+
+         frame.getContentPane().add(vv);
+         frame.pack();
+         frame.repaint();
+         frame.setVisible(true);
+    }
+
 
     public void viewGraph(List<V> cut){
@@ -98 +107 @@
      }
 
+
 }