|
2
|
1 package pagerank;
|
|
|
2
|
|
|
3 import java.util.HashMap;
|
|
|
4
|
|
|
5 import com.tinkerpop.blueprints.Direction;
|
|
|
6 import com.tinkerpop.blueprints.Edge;
|
|
|
7 import com.tinkerpop.blueprints.Graph;
|
|
|
8 import com.tinkerpop.blueprints.Vertex;
|
|
13
|
9 import com.tinkerpop.gremlin.java.GremlinPipeline;
|
|
|
10 import com.tinkerpop.pipes.util.iterators.SingleIterator;
|
|
2
|
11
|
|
|
12 import pagerank.WikiPage;
|
|
|
13
|
|
|
14 public class LinkToVertex {
|
|
|
15
|
|
|
16 Graph graph;
|
|
|
17 public final static String PAGE_TITLE = "pageTitle";
|
|
|
18 public final static String PAGE_RANK = "pageRank";
|
|
13
|
19
|
|
|
20 /* pageIdTable
|
|
|
21 * key: pageTitle value: Vertex ID
|
|
|
22 */
|
|
5
|
23 private HashMap<String, Object> pageIdTable = new HashMap<String, Object>();
|
|
2
|
24
|
|
13
|
25 /* wikiPageHash
|
|
|
26 * key: pageTitle value: wikiPage(class)
|
|
|
27 */
|
|
2
|
28 private HashMap<String, WikiPage> wikiPageHash = new HashMap<String, WikiPage>();
|
|
4
|
29 private long AllVertexNumber;
|
|
2
|
30
|
|
8
|
31 private final double weight = 0.85;
|
|
2
|
32
|
|
|
33 public static final String HAS_LINK = "HasLink";
|
|
|
34
|
|
4
|
35 public LinkToVertex(Graph graph) {
|
|
2
|
36 this.graph = graph;
|
|
4
|
37 AllVertexNumber = 0;
|
|
2
|
38 }
|
|
|
39
|
|
5
|
40 public Object getId(String pageTitle) {
|
|
2
|
41 return pageIdTable.get(pageTitle);
|
|
|
42 }
|
|
|
43
|
|
4
|
44 public boolean isHasLink(String label) {
|
|
2
|
45 return label.equals(HAS_LINK);
|
|
|
46 }
|
|
|
47
|
|
4
|
48 public Vertex createVertex() {
|
|
2
|
49 return graph.addVertex(null);
|
|
|
50 }
|
|
|
51
|
|
4
|
52 public Vertex createVertex(Object id) {
|
|
2
|
53 return graph.addVertex(id);
|
|
|
54 }
|
|
|
55
|
|
5
|
56
|
|
|
57 Vertex createVertexWithProperty(String key, Object value, Object id) {
|
|
|
58 Vertex v = createVertex(id);
|
|
2
|
59 v.setProperty(key,value);
|
|
|
60 return v;
|
|
|
61 }
|
|
|
62
|
|
5
|
63 Vertex createVertexWithProperty(String key, Object value) {
|
|
|
64 return createVertexWithProperty(key, value, null);
|
|
|
65 }
|
|
|
66
|
|
4
|
67 public String getPageTitle(Vertex v) {
|
|
2
|
68 return (String) v.getProperty(PAGE_TITLE);
|
|
|
69 }
|
|
|
70
|
|
4
|
71 public Double getPageRank(Vertex v) {
|
|
2
|
72 return (Double) v.getProperty(PAGE_RANK);
|
|
|
73 }
|
|
|
74
|
|
5
|
75
|
|
|
76 Vertex createVertexWithPageTitle(String pageTitle, Object id) {
|
|
|
77 Vertex v = createVertexWithProperty(PAGE_TITLE, pageTitle, id);
|
|
|
78 setPageRank(v, (Double)0.0);
|
|
|
79 pageIdTable.put(pageTitle, id );
|
|
|
80 return v;
|
|
|
81 }
|
|
|
82
|
|
2
|
83 Vertex createVertexWithPageTitle(String pageTitle) {
|
|
5
|
84 return createVertexWithPageTitle(pageTitle, null);
|
|
2
|
85 }
|
|
|
86
|
|
|
87 Vertex setPageRank(Vertex v, Double rank) {
|
|
|
88 v.setProperty(PAGE_RANK, rank);
|
|
|
89 return v;
|
|
|
90 }
|
|
|
91
|
|
|
92 Vertex getVertex(String name) {
|
|
5
|
93 Object id = pageIdTable.get(name);
|
|
2
|
94 return graph.getVertex(id);
|
|
|
95 }
|
|
|
96
|
|
7
|
97 Vertex getVertexById(String id) {
|
|
|
98 return graph.getVertex(id);
|
|
2
|
99 }
|
|
|
100
|
|
|
101 Edge setRelationship(Vertex v1, Vertex v2, String label) {
|
|
|
102 Edge e = graph.addEdge(null, v1, v2, label);
|
|
|
103 return e;
|
|
|
104 }
|
|
|
105
|
|
|
106 Edge setHasLink(Vertex v1, Vertex v2) {
|
|
|
107 return setRelationship(v1, v2, HAS_LINK);
|
|
|
108 }
|
|
|
109
|
|
8
|
110 void initPageRankAllVertex() {
|
|
|
111 for (Vertex v : graph.getVertices()) {
|
|
|
112 setPageRank(v, 0.0);
|
|
|
113 }
|
|
|
114 }
|
|
|
115
|
|
13
|
116 public long searchAllVertices() {
|
|
4
|
117 AllVertexNumber = 0;
|
|
2
|
118 for (Vertex v : graph.getVertices()) {
|
|
|
119 if ( (v.getProperty(PAGE_TITLE) != null) &&
|
|
|
120 (v.getProperty(PAGE_RANK)) != null ) {
|
|
5
|
121 WikiPage wiki = new WikiPage(v);
|
|
|
122 pageIdTable.put((String) v.getProperty(PAGE_TITLE), v.getId());
|
|
2
|
123 wiki.setInHasLink(computeInHasLink(v));
|
|
|
124 wiki.setOutHasLink(computeOutHasLink(v));
|
|
|
125 wikiPageHash.put((String) v.getProperty(PAGE_TITLE), wiki);
|
|
4
|
126 AllVertexNumber++;
|
|
2
|
127 }
|
|
|
128 }
|
|
4
|
129 return AllVertexNumber;
|
|
2
|
130 }
|
|
|
131
|
|
|
132 void searchRegiNodes(Vertex v) {
|
|
|
133
|
|
|
134 if ( (v.getProperty(PAGE_TITLE) != null) &&
|
|
|
135 (v.getProperty(PAGE_RANK) != null)) {
|
|
|
136 WikiPage wiki = new WikiPage(v);
|
|
5
|
137 pageIdTable.put((String) v.getProperty(PAGE_TITLE), v.getId());
|
|
2
|
138 wiki.setInHasLink(computeInHasLink(v));
|
|
|
139 wiki.setOutHasLink(computeOutHasLink(v));
|
|
|
140 wikiPageHash.put((String) v.getProperty(PAGE_TITLE), wiki);
|
|
4
|
141 AllVertexNumber++;
|
|
2
|
142 }
|
|
|
143 }
|
|
|
144
|
|
|
145 HashMap<String, WikiPage> getWikiPageHash() {
|
|
|
146 return wikiPageHash;
|
|
|
147 }
|
|
|
148
|
|
5
|
149 HashMap<String, Object> getPageIdTable() {
|
|
2
|
150 return pageIdTable;
|
|
|
151 }
|
|
|
152
|
|
4
|
153 public Iterable<Vertex> getAllVertices() {
|
|
2
|
154 return graph.getVertices();
|
|
|
155 }
|
|
|
156
|
|
4
|
157 public void printAllVertices() {
|
|
2
|
158 for (Vertex v : graph.getVertices() ) {
|
|
|
159 System.out.println("ID = "+ v.getId());
|
|
|
160 for (String key: v.getPropertyKeys()) {
|
|
|
161 System.out.println(key + "=" + v.getProperty(key));
|
|
|
162 }
|
|
|
163 /*
|
|
|
164 for (Edge e : v.getEdges(Direction.IN, HAS_LINK) ) {
|
|
|
165 System.out.println();
|
|
|
166 }
|
|
|
167 */
|
|
|
168 }
|
|
|
169 System.out.println("--");
|
|
|
170
|
|
|
171 }
|
|
|
172
|
|
|
173 public long computeOutHasLink(Vertex v) {
|
|
|
174 long count = 0;
|
|
|
175 for (Edge edge : v.getEdges(Direction.OUT, HAS_LINK)) {
|
|
|
176 count++;
|
|
|
177 }
|
|
|
178 return count;
|
|
|
179 }
|
|
|
180
|
|
|
181 public long computeInHasLink(Vertex v) {
|
|
|
182 long count = 0;
|
|
|
183 for (Edge edge : v.getEdges(Direction.IN, HAS_LINK)) {
|
|
|
184 count++;
|
|
|
185 }
|
|
|
186 return count;
|
|
|
187 }
|
|
|
188
|
|
|
189 public void printOutHasLink(Vertex v, int depth) {
|
|
|
190 int numberOfLinkPages = 0;
|
|
4
|
191 String output = "title:"+v.getProperty(PAGE_TITLE) + " outHasLink pages:";
|
|
2
|
192 System.out.println(output);
|
|
|
193 for (Edge edge : v.getEdges(Direction.OUT, HAS_LINK)) {
|
|
|
194 Vertex outV = edge.getVertex(Direction.IN);
|
|
|
195 String str = (String) outV.getProperty(PAGE_TITLE);
|
|
|
196 System.out.println(str);
|
|
|
197 numberOfLinkPages++;
|
|
|
198 }
|
|
|
199 String numOutput = "Number of outHaslink pages: " + numberOfLinkPages;
|
|
|
200 System.out.println(numOutput);
|
|
|
201 }
|
|
|
202
|
|
|
203 public void printInHasLink(Vertex v, int depth) {
|
|
|
204 int numberOfLinkPages = 0;
|
|
4
|
205 String output = "title:" +v.getProperty(PAGE_TITLE) + " inHasLink pages:";
|
|
2
|
206 System.out.println(output);
|
|
|
207 for (Edge edge : v.getEdges(Direction.IN, HAS_LINK)) {
|
|
|
208 Vertex outV = edge.getVertex(Direction.OUT);
|
|
|
209 String str = (String) outV.getProperty(PAGE_TITLE);
|
|
|
210 System.out.println(str);
|
|
|
211 numberOfLinkPages++;
|
|
|
212 }
|
|
|
213 String numOutput = "Number of inHaslink pages: " + numberOfLinkPages + "\n";
|
|
|
214 System.out.println(numOutput);
|
|
|
215 }
|
|
|
216
|
|
|
217 public double computePageRank(Vertex v) {
|
|
7
|
218 double sum = 0.0;
|
|
|
219 double pageRank = 0.0;
|
|
2
|
220 String title = getPageTitle(v);
|
|
|
221 WikiPage wiki = wikiPageHash.get(title);
|
|
|
222
|
|
|
223 for (Edge edge : v.getEdges(Direction.IN, HAS_LINK) ) {
|
|
|
224 Vertex linkV = edge.getVertex(Direction.OUT);
|
|
9
|
225 assert computeOutHasLink(linkV)!=0 ;
|
|
|
226 double pr = (Double)linkV.getProperty(PAGE_RANK);
|
|
|
227 sum += (double) pr / computeOutHasLink(linkV) ;
|
|
2
|
228 }
|
|
13
|
229 pageRank = (double) 1 - weight + (double) sum * weight;
|
|
7
|
230
|
|
2
|
231 wiki.setRank(pageRank);
|
|
|
232 v.setProperty(PAGE_RANK, pageRank);
|
|
|
233 return pageRank;
|
|
|
234 }
|
|
|
235
|
|
13
|
236 public double computePageRankUsingPipes(Object id) {
|
|
|
237 double sum = 0.0;
|
|
|
238 double pageRank = 0.0;
|
|
|
239 Vertex v = graph.getVertex(id);
|
|
|
240 WikiPage wiki = wikiPageHash.get(v.getProperty(PAGE_TITLE));
|
|
|
241
|
|
|
242 GremlinPipeline<Vertex,Vertex> pipe = new GremlinPipeline<Vertex,Vertex>();
|
|
|
243 pipe.start(graph.getVertex(id)).in("HasLink");
|
|
|
244 for (Vertex inVer : pipe) {
|
|
|
245 Object inVerId = inVer.getId();
|
|
|
246 GremlinPipeline<Vertex,Vertex> inPipe = new GremlinPipeline<Vertex,Vertex>();
|
|
|
247 inPipe.start(graph.getVertex(inVerId)).out("HasLink");
|
|
|
248 long linkNum = inPipe.count();
|
|
|
249 double pr = (Double) inVer.getProperty(PAGE_RANK);
|
|
|
250 sum += (double) pr / linkNum;
|
|
|
251 }
|
|
|
252 pageRank = (double) 1 - weight + (double) sum * weight;
|
|
|
253 wiki.setRank(pageRank);
|
|
|
254 v.setProperty(PAGE_RANK, pageRank);
|
|
|
255 return pageRank;
|
|
|
256 }
|
|
|
257
|
|
4
|
258 public void printVertexInfo(int nodeId) {
|
|
2
|
259 Vertex v = graph.getVertex(nodeId);
|
|
|
260 printInHasLink(v, 1);
|
|
|
261 printOutHasLink(v, 1);
|
|
|
262
|
|
|
263 String title = getPageTitle(v);
|
|
|
264 double rank = getPageRank(v);
|
|
|
265 long inHasLink = computeInHasLink(v);
|
|
|
266 long outHasLink = computeOutHasLink(v);
|
|
|
267
|
|
|
268 System.out.println("id:"+nodeId+" title:"+title+" rank:"+rank);
|
|
|
269 System.out.println("inHasLink:"+inHasLink+" outHasLink:"+outHasLink);
|
|
4
|
270 System.out.println();
|
|
2
|
271
|
|
|
272 }
|
|
|
273
|
|
|
274 }
|
