← Back to branch summary

~mathieu-jacomy/gephi/forceatlas2-multithread

« back to all changes in this revision

Viewing changes to StatisticsPlugin/src/org/gephi/statistics/plugin/PageRank.java

  • Committer: Mathieu Bastian
  • Date: 2010-01-20 20:37:57 UTC
  • Revision ID: mathieu.bastian@gmail.com-20100120203757-zl0qb0b37obd7vaf
Rename Statistics module, create spi package. Split Standard in Plugin and Plugin UI.

Show diffs side-by-side

added added

removed removed

Lines of Context:
StatisticsPlugin/src/org/gephi/statistics/plugin/PageRank.java
 
1
/*
 
2
Copyright 2008 WebAtlas
 
3
Authors : Patrick J. McSweeney (pjmcswee@syr.edu)
 
4
Website : http://www.gephi.org
 
5
 
 
6
This file is part of Gephi.
 
7
 
 
8
Gephi is free software: you can redistribute it and/or modify
 
9
it under the terms of the GNU General Public License as published by
 
10
the Free Software Foundation, either version 3 of the License, or
 
11
(at your option) any later version.
 
12
 
 
13
Gephi is distributed in the hope that it will be useful,
 
14
but WITHOUT ANY WARRANTY; without even the implied warranty of
 
15
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
16
GNU General Public License for more details.
 
17
 
 
18
You should have received a copy of the GNU General Public License
 
19
along with Gephi.  If not, see <http://www.gnu.org/licenses/>.
 
20
 */
 
21
package org.gephi.statistics.plugin;
 
22
 
 
23
import java.io.File;
 
24
import java.io.IOException;
 
25
import java.util.Hashtable;
 
26
import org.gephi.data.attributes.api.AttributeTable;
 
27
import org.gephi.data.attributes.api.AttributeColumn;
 
28
import org.gephi.data.attributes.api.AttributeController;
 
29
import org.gephi.data.attributes.api.AttributeModel;
 
30
import org.gephi.data.attributes.api.AttributeOrigin;
 
31
import org.gephi.data.attributes.api.AttributeRow;
 
32
import org.gephi.data.attributes.api.AttributeType;
 
33
import org.gephi.graph.api.DirectedGraph;
 
34
import org.gephi.graph.api.Edge;
 
35
import org.gephi.graph.api.EdgeIterable;
 
36
import org.gephi.graph.api.Graph;
 
37
import org.gephi.graph.api.GraphModel;
 
38
import org.gephi.graph.api.Node;
 
39
import org.gephi.graph.api.UndirectedGraph;
 
40
import org.gephi.statistics.spi.Statistics;
 
41
import org.gephi.ui.utils.TempDirUtils;
 
42
import org.gephi.ui.utils.TempDirUtils.TempDir;
 
43
import org.gephi.utils.longtask.LongTask;
 
44
import org.gephi.utils.progress.Progress;
 
45
import org.gephi.utils.progress.ProgressTicket;
 
46
import org.jfree.chart.ChartFactory;
 
47
import org.jfree.chart.ChartRenderingInfo;
 
48
import org.jfree.chart.ChartUtilities;
 
49
import org.jfree.chart.JFreeChart;
 
50
import org.jfree.chart.entity.StandardEntityCollection;
 
51
import org.jfree.chart.plot.PlotOrientation;
 
52
import org.jfree.chart.plot.XYPlot;
 
53
import org.jfree.chart.renderer.xy.XYLineAndShapeRenderer;
 
54
import org.jfree.data.xy.XYSeries;
 
55
import org.jfree.data.xy.XYSeriesCollection;
 
56
import org.openide.util.Lookup;
 
57
 
 
58
/**
 
59
 *
 
60
 * @author pjmcswee
 
61
 */
 
62
public class PageRank implements Statistics, LongTask {
 
63
 
 
64
    /** */
 
65
    private ProgressTicket mProgress;
 
66
    /** */
 
67
    private boolean mIsCanceled;
 
68
    /** */
 
69
    private double mEpsilon = 0.001;
 
70
    /** */
 
71
    private double mProbability = 0.85;
 
72
    /** */
 
73
    private double[] mPageranks;
 
74
    /** */
 
75
    private boolean mDirected;
 
76
    /** */
 
77
    private String mGraphRevision;
 
78
 
 
79
    /**
 
80
     *
 
81
     * @param pUndirected
 
82
     */
 
83
    public void setUndirected(boolean pUndirected) {
 
84
        mDirected = pUndirected;
 
85
    }
 
86
 
 
87
    /**
 
88
     * 
 
89
     * @return
 
90
     */
 
91
    public boolean getUndirected() {
 
92
        return mDirected;
 
93
    }
 
94
 
 
95
    /**
 
96
     *
 
97
     * @param graphModel
 
98
     */
 
99
    public void execute(GraphModel graphModel, AttributeModel attributeModel) {
 
100
        mIsCanceled = false;
 
101
 
 
102
        Graph graph;
 
103
        if (mDirected) {
 
104
            graph = graphModel.getUndirectedGraph();
 
105
        } else {
 
106
            graph = graphModel.getDirectedGraph();
 
107
        }
 
108
 
 
109
 
 
110
        this.mGraphRevision = "(" + graph.getNodeVersion() + ", " + graph.getEdgeVersion() + ")";
 
111
        //DirectedGraph digraph = graphController.getDirectedGraph();
 
112
        int N = graph.getNodeCount();
 
113
        mPageranks = new double[N];
 
114
        double[] temp = new double[N];
 
115
        Hashtable<Node, Integer> indicies = new Hashtable<Node, Integer>();
 
116
        int index = 0;
 
117
 
 
118
        Progress.start(mProgress);
 
119
        for (Node s : graph.getNodes()) {
 
120
            indicies.put(s, index);
 
121
            mPageranks[index] = 1.0f / N;
 
122
            index++;
 
123
        }
 
124
 
 
125
        while (true) {
 
126
            double r = 0;
 
127
            for (Node s : graph.getNodes()) {
 
128
                int s_index = indicies.get(s);
 
129
                boolean out;
 
130
                if (mDirected) {
 
131
                    out = graph.getDegree(s) > 0;
 
132
                } else {
 
133
                    out = ((DirectedGraph) graph).getOutDegree(s) > 0;
 
134
                }
 
135
 
 
136
                if (out) {
 
137
                    r += (1.0 - mProbability) * (mPageranks[s_index] / N);
 
138
                } else {
 
139
                    r += (mPageranks[s_index] / N);
 
140
                }
 
141
                if (mIsCanceled) {
 
142
                    return;
 
143
                }
 
144
            }
 
145
 
 
146
            boolean done = true;
 
147
            for (Node s : graph.getNodes()) {
 
148
                int s_index = indicies.get(s);
 
149
                temp[s_index] = r;
 
150
 
 
151
                EdgeIterable eIter;
 
152
                if (mDirected) {
 
153
                    eIter = ((UndirectedGraph) graph).getEdges(s);
 
154
                } else {
 
155
                    eIter = ((DirectedGraph) graph).getInEdges(s);
 
156
                }
 
157
 
 
158
                for (Edge edge : eIter) {
 
159
                    Node neighbor = graph.getOpposite(s, edge);
 
160
                    int neigh_index = indicies.get(neighbor);
 
161
                    int normalize;
 
162
                    if (mDirected) {
 
163
                        normalize = ((UndirectedGraph) graph).getDegree(neighbor);
 
164
                    } else {
 
165
                        normalize = ((DirectedGraph) graph).getOutDegree(neighbor);
 
166
                    }
 
167
 
 
168
                    temp[s_index] += mProbability * (mPageranks[neigh_index] / normalize);
 
169
                }
 
170
 
 
171
                if ((temp[s_index] - mPageranks[s_index]) / mPageranks[s_index] >= mEpsilon) {
 
172
                    done = false;
 
173
                }
 
174
 
 
175
                if (mIsCanceled) {
 
176
                    return;
 
177
                }
 
178
 
 
179
            }
 
180
            mPageranks = temp;
 
181
            temp = new double[N];
 
182
            if ((done) || (mIsCanceled)) {
 
183
                break;
 
184
            }
 
185
 
 
186
        }
 
187
 
 
188
        AttributeTable nodeClass = attributeModel.getNodeTable();
 
189
        AttributeColumn pangeRanksCol = nodeClass.addColumn("pageranks", "Page Ranks", AttributeType.DOUBLE, AttributeOrigin.COMPUTED, new Double(0));
 
190
 
 
191
        for (Node s : graph.getNodes()) {
 
192
            int s_index = indicies.get(s);
 
193
            AttributeRow row = (AttributeRow) s.getNodeData().getAttributes();
 
194
            row.setValue(pangeRanksCol, mPageranks[s_index]);
 
195
        }
 
196
 
 
197
 
 
198
    }
 
199
 
 
200
    /**
 
201
     *
 
202
     * @return
 
203
     */
 
204
    public String getReport() {
 
205
 
 
206
        double max = 0;
 
207
        XYSeries series = new XYSeries("Series 2");
 
208
        for (int i = 0; i < mPageranks.length; i++) {
 
209
            series.add(i, mPageranks[i]);
 
210
 
 
211
        }
 
212
 
 
213
 
 
214
        XYSeriesCollection dataset = new XYSeriesCollection();
 
215
        dataset.addSeries(series);
 
216
 
 
217
        JFreeChart chart = ChartFactory.createXYLineChart(
 
218
                "Page Ranks",
 
219
                "Node",
 
220
                "Page Rank",
 
221
                dataset,
 
222
                PlotOrientation.VERTICAL,
 
223
                true,
 
224
                false,
 
225
                false);
 
226
        XYPlot plot = (XYPlot) chart.getPlot();
 
227
        XYLineAndShapeRenderer renderer = new XYLineAndShapeRenderer();
 
228
        renderer.setSeriesLinesVisible(0, true);
 
229
        renderer.setSeriesShapesVisible(0, false);
 
230
        renderer.setSeriesLinesVisible(1, false);
 
231
        renderer.setSeriesShapesVisible(1, true);
 
232
        renderer.setSeriesShape(1, new java.awt.geom.Ellipse2D.Double(0, 0, 1, 1));
 
233
        plot.setBackgroundPaint(java.awt.Color.WHITE);
 
234
        plot.setDomainGridlinePaint(java.awt.Color.GRAY);
 
235
        plot.setRangeGridlinePaint(java.awt.Color.GRAY);
 
236
 
 
237
        plot.setRenderer(renderer);
 
238
 
 
239
 
 
240
        String imageFile = "";
 
241
        try {
 
242
            final ChartRenderingInfo info = new ChartRenderingInfo(new StandardEntityCollection());
 
243
            TempDir tempDir = TempDirUtils.createTempDir();
 
244
            String fileName = "pageranks.png";
 
245
            File file1 = tempDir.createFile(fileName);
 
246
            imageFile = "<IMG SRC=\"file:" + file1.getAbsolutePath() + "\" " + "WIDTH=\"600\" HEIGHT=\"400\" BORDER=\"0\" USEMAP=\"#chart\"></IMG>";
 
247
            ChartUtilities.saveChartAsPNG(file1, chart, 600, 400, info);
 
248
        } catch (IOException e) {
 
249
            System.out.println(e.toString());
 
250
        }
 
251
        String report = new String("<HTML> <BODY> <h1>PageRank Report </h1> "
 
252
                + "<hr> <br> <h2>Network Revision Number:</h2>"
 
253
                + mGraphRevision
 
254
                + "<h2> Parameters: </h2>"
 
255
                + "Epsilon = " + this.mEpsilon + "<br>"
 
256
                + "Probability = " + this.mProbability
 
257
                + "<br> <h2> Results: </h2>"
 
258
                + imageFile
 
259
                + "</BODY></HTML>");
 
260
 
 
261
        return report;
 
262
 
 
263
    }
 
264
 
 
265
    /**
 
266
     *
 
267
     * @return
 
268
     */
 
269
    public boolean cancel() {
 
270
        mIsCanceled = true;
 
271
        return true;
 
272
    }
 
273
 
 
274
    /**
 
275
     *
 
276
     * @param progressTicket
 
277
     */
 
278
    public void setProgressTicket(ProgressTicket progressTicket) {
 
279
        mProgress = progressTicket;
 
280
    }
 
281
 
 
282
    /**
 
283
     * 
 
284
     * @param prob
 
285
     */
 
286
    public void setProbability(double prob) {
 
287
        mProbability = prob;
 
288
    }
 
289
 
 
290
    /**
 
291
     *
 
292
     * @param eps
 
293
     */
 
294
    public void setEpsilon(double eps) {
 
295
        mEpsilon = eps;
 
296
    }
 
297
 
 
298
    /**
 
299
     *
 
300
     * @return
 
301
     */
 
302
    public double getProbability() {
 
303
        return mProbability;
 
304
    }
 
305
 
 
306
    /**
 
307
     *
 
308
     * @return
 
309
     */
 
310
    public double getEpsilon() {
 
311
        return mEpsilon;
 
312
    }
 
313
}