Index: branches/localSpectral/nbproject/project.properties =================================================================== --- branches/localSpectral/nbproject/project.properties (revision 35) +++ branches/localSpectral/nbproject/project.properties (revision 36) @@ -41,7 +41,7 @@ ${file.reference.jung-api-2.0.1.jar}:\ ${file.reference.jung-visualization-2.0.1.jar}:\ - ${file.reference.jung-graph-impl-2.0.1.jar}:\ ${file.reference.jung-io-2.0.1.jar}:\ - ${file.reference.jung-jai-2.0.1.jar} + ${file.reference.jung-jai-2.0.1.jar}:\ + ${file.reference.jung-graph-impl-2.0.1.jar} # Space-separated list of extra javac options javac.compilerargs= @@ -76,4 +76,5 @@ ${javac.classpath}:\ ${build.classes.dir} +run.jvmargs=-Xms1500M -Xmx1500M run.test.classpath=\ ${javac.test.classpath}:\ Index: branches/localSpectral/src/clustering/GraphClusterer.java =================================================================== --- branches/localSpectral/src/clustering/GraphClusterer.java (revision 35) +++ branches/localSpectral/src/clustering/GraphClusterer.java (revision 36) @@ -6,8 +6,11 @@ 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,32 +20,42 @@ private int currentElement; private Viewer viewGraph; - private Graph> graph; - private boolean graph_output; + private Graph graph; + private boolean main_graph_output; + private boolean cluster_graph_output; private boolean isGraphDirected; private int minvolume; - LocalSpectral> clusterer; + LocalSpectral 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,6 +63,37 @@ 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 graph, List 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,6 +101,8 @@ if(this.currentElement > global_ranking.size()-1) return; - - List cut = clusterer.clusterPageRankPriors(global_ranking.get(currentElement).getVertex(),this.minvolume); + + List seed = new ArrayList(); + seed.add(global_ranking.get(currentElement).getVertex()); + List cut = clusterer.clusterPageRankPriors(seed,this.minvolume); Graph cut_graph; if (isGraphDirected) @@ -65,17 +111,21 @@ cut_graph = new SparseGraph>(); for(String vertex : cut){ - Collection> out_edges = graph.getOutEdges(vertex); - for(Edge edge : out_edges){ + Collection 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 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++; Index: branches/localSpectral/src/clustering/LocalSpectral.java =================================================================== --- branches/localSpectral/src/clustering/LocalSpectral.java (revision 35) +++ branches/localSpectral/src/clustering/LocalSpectral.java (revision 36) @@ -49,10 +49,10 @@ rank.evaluate(); Collection vertexs = graph.getVertices(); - Iterator vertexsIterator = vertexs.iterator(); + Iterator vertexsIterator = vertexs.iterator(); ArrayList> vertexsScore = new ArrayList>(); while(vertexsIterator.hasNext()){ - V vertex = (V) vertexsIterator.next(); + V vertex = vertexsIterator.next(); Double score = (Double) rank.getVertexScore(vertex); - VertexScore vertexscore = new VertexScore(vertex,score); + VertexScore vertexscore = new VertexScore(vertex,score.floatValue()); vertexsScore.add(vertexscore); } @@ -62,9 +62,16 @@ } - public List clusterPageRankPriors(V seed, double min_volume){ + public List clusterPageRankPriors(List 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,6 +86,6 @@ V vertex = (V) vertexsIterator.next(); Double score = (Double) rank.getVertexScore(vertex); - int degree = graph.getIncidentEdges(vertex).size(); - VertexScore vertexscore = new VertexScore(vertex,score/degree); + int degree = graph.inDegree(vertex); + VertexScore vertexscore = new VertexScore(vertex,score.floatValue()/degree); vertexsScore.add(vertexscore); } @@ -103,5 +110,5 @@ int edge_boundary = 0; for(int j=0; j min_volume) && (volume_subset < max_volume)){ - //if (volume_subset < min_volume){ if (conductance < min_conductance_subset){ min_conductance_subset = conductance; @@ -143,3 +149,4 @@ } + } Index: branches/localSpectral/src/clustering/VertexScore.java =================================================================== --- branches/localSpectral/src/clustering/VertexScore.java (revision 35) +++ branches/localSpectral/src/clustering/VertexScore.java (revision 36) @@ -5,7 +5,7 @@ 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,5 +16,5 @@ } - public void setScore(double score) { + public void setScore(float score) { this.score = score; } Index: branches/localSpectral/src/data/GraphBuilder.java =================================================================== --- branches/localSpectral/src/data/GraphBuilder.java (revision 35) +++ branches/localSpectral/src/data/GraphBuilder.java (revision 36) @@ -2,10 +2,9 @@ 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,19 +20,20 @@ public class GraphBuilder { - Graph> graph; + Graph graph; public GraphBuilder(boolean directed){ if (directed) - graph = new DirectedSparseGraph>(); + graph = new DirectedDenseGraph(); + //graph = new DirectedSparseGraph(); else - graph = new SparseGraph>(); + graph = new SparseGraph(); } - public Graph> getGraph() { + public Graph getGraph() { return graph; } - public void buildGraphFromARFF(String path, int maxreadline){ + public void buildGraphFromCVS(String path, int maxreadline){ try { FileInputStream fstream = new FileInputStream(path); @@ -41,15 +41,11 @@ BufferedReader br = new BufferedReader(new InputStreamReader(in)); - Set vertex = new HashSet(); - 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(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++; } Index: branches/localSpectral/src/jung/Main.java =================================================================== --- branches/localSpectral/src/jung/Main.java (revision 35) +++ branches/localSpectral/src/jung/Main.java (revision 36) @@ -3,4 +3,6 @@ import clustering.GraphClusterer; +import data.GraphBuilder; +import view.GraphToGraphviz; @@ -10,14 +12,22 @@ 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); } Index: branches/localSpectral/src/view/VertexPaintRankTransformer.java =================================================================== --- branches/localSpectral/src/view/VertexPaintRankTransformer.java (revision 35) +++ branches/localSpectral/src/view/VertexPaintRankTransformer.java (revision 36) @@ -14,10 +14,18 @@ List> pagerank; V seed_node; + List cluster; public VertexPaintRankTransformer(List> ranking, V seed_node){ this.pagerank = ranking; this.seed_node = seed_node; + this.cluster = null; } + public VertexPaintRankTransformer(List> ranking, V seed_node, List cluster){ + this.pagerank = ranking; + this.seed_node = seed_node; + this.cluster = cluster; + } + public Paint transform(V node) { @@ -25,4 +33,9 @@ if (seed_node.equals(node)){ return (Paint) Color.GREEN; + } + } + if(cluster != null){ + if (!cluster.contains(node)){ + return (Paint) Color.WHITE; } } Index: branches/localSpectral/src/view/Viewer.java =================================================================== --- branches/localSpectral/src/view/Viewer.java (revision 35) +++ branches/localSpectral/src/view/Viewer.java (revision 36) @@ -24,5 +24,4 @@ import javax.swing.JPanel; import javax.swing.JTextArea; -import javax.xml.bind.JAXB; import org.apache.commons.collections15.Transformer; @@ -83,4 +82,14 @@ } + public void viewClusterRankedInGraph(List> pagerank, V seed_node, List cluster){ + VertexPaintRankTransformer vertexPaint = new VertexPaintRankTransformer(pagerank,seed_node, cluster); + vv.getRenderContext().setVertexFillPaintTransformer((Transformer) vertexPaint); + + frame.getContentPane().add(vv); + frame.pack(); + frame.repaint(); + frame.setVisible(true); + } + public void viewGraph(List cut){ @@ -98,3 +107,4 @@ } + }