graphrust_algos/
pagerank.rs

1//! PageRank algorithm implementation.
2//!
3//! Computes importance scores for nodes in a graph using the PageRank algorithm.
4
5use graphrust_core::{Graph, NodeId};
6
7/// Computes PageRank scores for all nodes using a fixed number of iterations.
8///
9/// # Arguments
10/// * `graph` - The graph
11/// * `iterations` - Number of iterations to run
12/// * `damping_factor` - Damping factor (typically 0.85)
13///
14/// # Returns
15/// Vector of ranks indexed by node ID (as u32)
16pub fn pagerank(graph: &Graph, iterations: u32, damping_factor: f64) -> Vec<f64> {
17    let n = graph.num_nodes() as usize;
18    let mut ranks = vec![1.0 / n as f64; n];
19    let mut new_ranks = vec![0.0; n];
20
21    // Precompute out-degrees
22    let mut out_degrees = vec![0u32; n];
23    for node in graph.nodes() {
24        out_degrees[node.as_usize()] = graph.neighbors(node).len() as u32;
25    }
26
27    let _dangling_sum = ranks.iter().sum::<f64>() / n as f64;
28
29    for _ in 0..iterations {
30        new_ranks.fill(0.0);
31
32        for node in graph.nodes() {
33            let node_idx = node.as_usize();
34            let out_degree = out_degrees[node_idx];
35
36            if out_degree > 0 {
37                let contribution = ranks[node_idx] / out_degree as f64;
38                for &neighbor in graph.neighbors(node) {
39                    new_ranks[neighbor.as_usize()] += contribution;
40                }
41            }
42        }
43
44        for rank in &mut new_ranks {
45            *rank = (1.0 - damping_factor) / n as f64 + damping_factor * *rank;
46        }
47
48        std::mem::swap(&mut ranks, &mut new_ranks);
49    }
50
51    ranks
52}
53
54/// Computes PageRank scores using convergence criterion.
55///
56/// # Arguments
57/// * `graph` - The graph
58/// * `tolerance` - Convergence tolerance (e.g., 1e-6)
59/// * `damping_factor` - Damping factor (typically 0.85)
60///
61/// # Returns
62/// Vector of final ranks
63pub fn pagerank_converge(graph: &Graph, tolerance: f64, damping_factor: f64) -> Vec<f64> {
64    let n = graph.num_nodes() as usize;
65    let mut ranks = vec![1.0 / n as f64; n];
66    let mut new_ranks = vec![0.0; n];
67
68    let mut out_degrees = vec![0u32; n];
69    for node in graph.nodes() {
70        out_degrees[node.as_usize()] = graph.neighbors(node).len() as u32;
71    }
72
73    loop {
74        new_ranks.fill(0.0);
75
76        for node in graph.nodes() {
77            let node_idx = node.as_usize();
78            let out_degree = out_degrees[node_idx];
79
80            if out_degree > 0 {
81                let contribution = ranks[node_idx] / out_degree as f64;
82                for &neighbor in graph.neighbors(node) {
83                    new_ranks[neighbor.as_usize()] += contribution;
84                }
85            }
86        }
87
88        for rank in &mut new_ranks {
89            *rank = (1.0 - damping_factor) / n as f64 + damping_factor * *rank;
90        }
91
92        // Check convergence
93        let mut converged = true;
94        for (old, new) in ranks.iter().zip(new_ranks.iter()) {
95            if (old - new).abs() > tolerance {
96                converged = false;
97                break;
98            }
99        }
100
101        ranks = new_ranks.clone();
102
103        if converged {
104            break;
105        }
106    }
107
108    ranks
109}
110
111/// Returns top k nodes by PageRank score.
112///
113/// # Arguments
114/// * `graph` - The graph
115/// * `k` - Number of top nodes to return
116/// * `iterations` - Number of PageRank iterations
117///
118/// # Returns
119/// Vector of (NodeId, rank) tuples sorted by rank descending
120pub fn top_k_pagerank(graph: &Graph, k: usize, iterations: u32) -> Vec<(NodeId, f64)> {
121    let ranks = pagerank(graph, iterations, 0.85);
122    let mut nodes_with_ranks: Vec<(NodeId, f64)> = ranks
123        .iter()
124        .enumerate()
125        .map(|(i, &rank)| (NodeId(i as u32), rank))
126        .collect();
127
128    nodes_with_ranks.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal));
129    nodes_with_ranks.truncate(k);
130    nodes_with_ranks
131}
132
133#[cfg(test)]
134mod tests {
135    use super::*;
136    use graphrust_core::GraphBuilder;
137
138    fn create_test_graph() -> Graph {
139        GraphBuilder::new(4)
140            .directed(true)
141            .add_edge(NodeId(0), NodeId(1))
142            .add_edge(NodeId(1), NodeId(2))
143            .add_edge(NodeId(2), NodeId(0))
144            .add_edge(NodeId(2), NodeId(3))
145            .build()
146    }
147
148    #[test]
149    fn test_pagerank_basic() {
150        let graph = create_test_graph();
151        let ranks = pagerank(&graph, 10, 0.85);
152
153        assert_eq!(ranks.len(), 4);
154        assert!(ranks.iter().all(|r| *r > 0.0));
155        // PageRank scores may not sum to exactly 1.0 due to dangling nodes
156        // Just check they're normalized reasonably
157        let sum: f64 = ranks.iter().sum();
158        assert!(sum > 0.0 && sum < 2.0);
159    }
160
161    #[test]
162    fn test_top_k_pagerank() {
163        let graph = create_test_graph();
164        let top_k = top_k_pagerank(&graph, 2, 10);
165
166        assert_eq!(top_k.len(), 2);
167        assert!(top_k[0].1 >= top_k[1].1);
168    }
169
170    #[test]
171    fn test_pagerank_converge() {
172        let graph = create_test_graph();
173        let ranks = pagerank_converge(&graph, 1e-6, 0.85);
174
175        assert_eq!(ranks.len(), 4);
176        assert!(ranks.iter().all(|r| *r > 0.0));
177    }
178}
graphrust_algos/pagerank.rs

graphrust_algos/
pagerank.rs
