page_rank/
lib.rs

1use std::{collections::HashMap, hash::Hash};
2
3#[derive(Debug, Clone)]
4pub struct Graph<T> {
5    nodes: HashMap<T, Node<T>>,
6    damping: f64,
7}
8
9#[derive(Debug, Clone)]
10pub struct Node<T> {
11    incoming_links: Vec<T>,
12    outgoing_links: Vec<T>,
13    score: f64,
14}
15
16impl<T> Node<T> {
17    pub fn new() -> Self {
18        Node { incoming_links: vec![], outgoing_links: vec![], score: 1.0 }
19    }
20}
21
22impl<T: Hash + Eq + PartialEq + Clone> Graph<T> {
23    pub fn new() -> Self {
24        Graph { nodes: HashMap::new(), damping: 0.85 }
25    }
26
27    pub fn add_page(&mut self, value: T) {
28        self.nodes.insert(value, Node::new());
29    }
30
31    pub fn add_link(&mut self, link: T, page: T) {
32        self.nodes.get_mut(&link).unwrap().incoming_links.push(page.clone());
33        self.nodes.get_mut(&page).unwrap().outgoing_links.push(link);
34    }
35
36    pub fn page_rank(&mut self, depth: usize) {
37        if depth == 0 { return }
38
39        let nodes = self.nodes.clone();
40        for (_, node) in self.nodes.iter_mut() {
41            let mut link_scores = 0.0;
42            for link in node.incoming_links.iter() {
43                let n = nodes.get(link).unwrap();
44                link_scores += n.score / n.outgoing_links.len() as f64
45            }
46            node.score = (1.0 - self.damping) + (self.damping * link_scores)
47        }
48
49        self.page_rank(depth - 1)
50    }
51
52    pub fn get_sorted_scores(&self) -> Vec<(T, f64)> {
53        let mut scores = vec![];
54        for (key, node) in &self.nodes {
55            scores.push((key.clone(), node.score))
56        }
57        scores.sort_by(|a, b| 
58            a.1.partial_cmp(&b.1).unwrap());
59
60        scores
61    }
62}
page_rank/lib.rs

page_rank/
lib.rs
