1 # This file is part of NIT (http://www.nitlanguage.org).
3 # Licensed under the Apache License, Version 2.0 (the "License");
4 # you may not use this file except in compliance with the License.
5 # You may obtain a copy of the License at
7 # http://www.apache.org/licenses/LICENSE-2.0
9 # Unless required by applicable law or agreed to in writing, software
10 # distributed under the License is distributed on an "AS IS" BASIS,
11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 # See the License for the specific language governing permissions and
13 # limitations under the License.
15 # Add PageRank computation for vertices in Digraph.
18 import graphs
::digraph
20 redef class Digraph[V
]
22 # Compute PageRank for each vertex
24 # Details of the algorithm can be found in:
25 # > L. Page, S. Brin, R. Motwani, and T.Winograd.
26 # > **The pagerank citation ranking: Bringing order to the web.**
27 # > *Technical report, Stanford Digital Library Technologies Project, 1998*
31 # var g = new HashDigraph[String]
38 # assert g.pagerank.join(", ", ":") == "A:1.488, B:0.782, C:1.575, D:0.15"
40 fun pagerank
: PRMap[V
] do
41 # `d` constant such as `initial_pagerank(node) == (1 - d) != 0`
42 var d
= 0.85 # commonly-choosen value
43 # Init each node page rank with an initial_value
44 var values
= new PRMap[V
]
45 var vertices
= self.vertices
46 for v
in vertices
do values
[v
] = 1.0 - d
47 # Compute page rank until convergence
48 var prev
= new PRMap[V
]
49 while not values
.is_approx
(prev
, 0.001) do
50 prev
= new PRMap[V
].from
(values
)
53 for o
in predecessors
(v
) do
54 in_pr
+= values
[o
] / out_degree
(o
).to_f
56 values
[v
] = (1.0 - d
) + d
* in_pr
63 # Map each Vertice of a Digraph to it's PageRank.
65 # See: `Digraph::pagerank`.
67 super HashMap[V
, Float]
69 # Init `self` by copying `other` values.
70 init from
(other
: PRMap[V
]) do
72 for k
, v
in other
do self[k
] = v
75 # Is `self` approximately equal to another PRMap?
77 # `self` is approximately equal to `o` if `o` contains all the key from `self`
78 # with the same values.
80 # Values equality is based on `Float::is_approx` with `precision`.
81 fun is_approx
(o
: SELF, precision
: Float): Bool do
83 if not o
.has_key
(k1
) then return false
84 if not v1
.is_approx
(o
[k1
], precision
) then return false