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; }