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

use std::{collections::HashMap, hash::Hash};

#[derive(Debug, Clone)]
pub struct Graph<T> {
    nodes: HashMap<T, Node<T>>,
    damping: f64,
}

#[derive(Debug, Clone)]
pub struct Node<T> {
    incoming_links: Vec<T>,
    outgoing_links: Vec<T>,
    score: f64,
}

impl<T> Node<T> {
    pub fn new() -> Self {
        Node { incoming_links: vec![], outgoing_links: vec![], score: 1.0 }
    }
}

impl<T: Hash + Eq + PartialEq + Clone> Graph<T> {
    pub fn new() -> Self {
        Graph { nodes: HashMap::new(), damping: 0.85 }
    }

    pub fn add_page(&mut self, value: T) {
        self.nodes.insert(value, Node::new());
    }

    pub fn add_link(&mut self, link: T, page: T) {
        self.nodes.get_mut(&link).unwrap().incoming_links.push(page.clone());
        self.nodes.get_mut(&page).unwrap().outgoing_links.push(link);
    }

    pub fn page_rank(&mut self, depth: usize) {
        if depth == 0 { return }

        let nodes = self.nodes.clone();
        for (_, node) in self.nodes.iter_mut() {
            let mut link_scores = 0.0;
            for link in node.incoming_links.iter() {
                let n = nodes.get(link).unwrap();
                link_scores += n.score / n.outgoing_links.len() as f64
            }
            node.score = (1.0 - self.damping) + (self.damping * link_scores)
        }

        self.page_rank(depth - 1)
    }

    pub fn get_sorted_scores(&self) -> Vec<(T, f64)> {
        let mut scores = vec![];
        for (key, node) in &self.nodes {
            scores.push((key.clone(), node.score))
        }
        scores.sort_by(|a, b| 
            a.1.partial_cmp(&b.1).unwrap());

        scores
    }
}