-
Notifications
You must be signed in to change notification settings - Fork 1
/
mod.rs
100 lines (85 loc) · 3.21 KB
/
mod.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
use soroban_decimal_numbers::DecimalNumberWrapper;
use soroban_sdk::{Env, Map, String};
use crate::types::DecimalNumber;
pub struct Rank {
graph: Map<String, Map<String, ()>>,
}
impl Rank {
pub fn new(env: &Env) -> Rank {
Rank {
graph: Map::new(env),
}
}
pub fn from_pages(env: &Env, pages: Map<String, Map<String, ()>>) -> Rank {
let mut result = Rank::new(env);
for (page, links) in pages {
result.add_page(page, links);
}
result
}
pub fn add_page(&mut self, page: String, links: Map<String, ()>) {
self.graph.set(page, links);
}
pub fn calculate(&self, env: &Env) -> Map<String, DecimalNumber> {
// TODO this algorithm probably needs some work
let initial_rank: DecimalNumber = DecimalNumberWrapper::div(
DecimalNumberWrapper::from((1, 0)),
DecimalNumberWrapper::from((self.graph.len(), 0)),
)
.as_tuple();
let mut page_ranks: Map<String, DecimalNumber> = Map::new(&env);
for page in self.graph.keys() {
page_ranks.set(page, initial_rank);
}
// Perform PageRank iterations
let num_iterations = 10;
let damping_factor = DecimalNumberWrapper::from((0, 850)).as_tuple();
for _ in 0..num_iterations {
let mut new_ranks: Map<String, DecimalNumber> = Map::new(&env);
let total_pages = self.graph.len();
// let dead_end_rank = DecimalNumberWrapper::new(0, 0);
// Calculate PageRank for each page
for (page, links) in self.graph.clone() {
let mut rank = DecimalNumberWrapper::sub(
DecimalNumberWrapper::from((1, 0)),
DecimalNumberWrapper::from(damping_factor),
);
rank = DecimalNumberWrapper::div(rank, DecimalNumberWrapper::from((total_pages, 0)));
for link in links.keys() {
let link_count = match self.graph.get(link.clone()) {
Some(val) => val.len(),
None => 0,
};
let link_count = DecimalNumberWrapper::from((link_count, 0));
if link_count.as_raw() == 0 {
// dead_end_rank += damping_factor * page_ranks[page];
} else {
// rank += damping_factor * page_ranks[link] / link_count;
let mut modifier = DecimalNumberWrapper::mul(
DecimalNumberWrapper::from(damping_factor),
DecimalNumberWrapper::from(page_ranks.get(link.clone()).unwrap()),
);
modifier = DecimalNumberWrapper::div(modifier, link_count);
rank = DecimalNumberWrapper::add(rank, modifier);
}
}
new_ranks.set(page, rank.as_tuple());
}
// Calculate PageRank for dead-end pages and distribute it equally
// let redistributed_dead_end_rank = DecimalNumberWrapper::div(dead_end_rank, DecimalNumberWrapper::from((total_pages, 0))).as_tuple();
// Update PageRank values
// for (page, rank) in new_ranks {
// // *rank += redistributed_dead_end_rank;
// let new_rank = DecimalNumberWrapper::add(
// DecimalNumberWrapper::from(rank),
// DecimalNumberWrapper::from(redistributed_dead_end_rank),
// );
// new_ranks.set(page, new_rank.as_tuple());
// }
page_ranks = new_ranks;
}
page_ranks
}
}
#[cfg(test)]
mod page_rank_test;