ruvector_memopt/algorithms/
pagerank.rs

1//! PageRank algorithm for process importance scoring
2//!
3//! Ranks processes by their importance in the process dependency graph.
4//! High-rank processes are preserved; low-rank processes are trimmed first.
5
6use std::collections::HashMap;
7use sysinfo::System;
8
9/// PageRank-based process prioritization
10pub struct ProcessPageRank {
11    /// PageRank scores for each process
12    scores: HashMap<u32, f64>,
13    /// Adjacency list (outgoing edges)
14    outlinks: HashMap<u32, Vec<u32>>,
15    /// Damping factor (typically 0.85)
16    damping: f64,
17    /// Convergence threshold
18    epsilon: f64,
19    /// Maximum iterations
20    max_iterations: usize,
21}
22
23impl ProcessPageRank {
24    pub fn new() -> Self {
25        Self {
26            scores: HashMap::new(),
27            outlinks: HashMap::new(),
28            damping: 0.85,
29            epsilon: 1e-6,
30            max_iterations: 100,
31        }
32    }
33
34    /// Build the process graph and compute PageRank scores
35    pub fn compute(&mut self, system: &System) {
36        self.outlinks.clear();
37        self.scores.clear();
38
39        let processes: Vec<u32> = system.processes().keys().map(|p| p.as_u32()).collect();
40        let n = processes.len();
41
42        if n == 0 {
43            return;
44        }
45
46        // Build outlink graph (parent -> children)
47        for (pid, process) in system.processes() {
48            let pid_u32 = pid.as_u32();
49
50            // Parent points to child (influence flows from parent)
51            if let Some(parent_pid) = process.parent() {
52                self.outlinks
53                    .entry(parent_pid.as_u32())
54                    .or_insert_with(Vec::new)
55                    .push(pid_u32);
56            }
57        }
58
59        // Initialize scores uniformly
60        let initial_score = 1.0 / n as f64;
61        for &pid in &processes {
62            self.scores.insert(pid, initial_score);
63        }
64
65        // Power iteration
66        for iteration in 0..self.max_iterations {
67            let mut new_scores: HashMap<u32, f64> = HashMap::new();
68            let mut max_delta = 0.0f64;
69
70            // Teleport component (random jump)
71            let teleport = (1.0 - self.damping) / n as f64;
72
73            for &pid in &processes {
74                let mut score = teleport;
75
76                // Sum contributions from all processes that link to this one
77                for (&source, targets) in &self.outlinks {
78                    if targets.contains(&pid) {
79                        let source_score = self.scores.get(&source).unwrap_or(&0.0);
80                        let out_degree = targets.len() as f64;
81                        score += self.damping * source_score / out_degree;
82                    }
83                }
84
85                // Handle dangling nodes (no outlinks)
86                if !self.outlinks.contains_key(&pid) {
87                    // Distribute to all nodes
88                    let dangling_contrib = self.damping * self.scores.get(&pid).unwrap_or(&0.0) / n as f64;
89                    score += dangling_contrib;
90                }
91
92                let old_score = self.scores.get(&pid).unwrap_or(&0.0);
93                max_delta = max_delta.max((score - old_score).abs());
94                new_scores.insert(pid, score);
95            }
96
97            self.scores = new_scores;
98
99            // Check convergence
100            if max_delta < self.epsilon {
101                tracing::debug!("PageRank converged after {} iterations", iteration + 1);
102                break;
103            }
104        }
105
106        // Normalize scores
107        let total: f64 = self.scores.values().sum();
108        if total > 0.0 {
109            for score in self.scores.values_mut() {
110                *score /= total;
111            }
112        }
113    }
114
115    /// Get PageRank score for a process (higher = more important)
116    pub fn get_score(&self, pid: u32) -> f64 {
117        *self.scores.get(&pid).unwrap_or(&0.0)
118    }
119
120    /// Get processes ranked by importance (least important first - trim these)
121    pub fn get_trim_candidates(&self, limit: usize) -> Vec<(u32, f64)> {
122        let mut ranked: Vec<(u32, f64)> = self.scores.iter().map(|(&k, &v)| (k, v)).collect();
123        // Sort ascending (lowest rank first)
124        ranked.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(std::cmp::Ordering::Equal));
125        ranked.into_iter().take(limit).collect()
126    }
127
128    /// Get most important processes (preserve these)
129    pub fn get_critical_processes(&self, limit: usize) -> Vec<(u32, f64)> {
130        let mut ranked: Vec<(u32, f64)> = self.scores.iter().map(|(&k, &v)| (k, v)).collect();
131        // Sort descending (highest rank first)
132        ranked.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal));
133        ranked.into_iter().take(limit).collect()
134    }
135
136    /// Statistics for benchmarking
137    pub fn stats(&self) -> PageRankStats {
138        let scores: Vec<f64> = self.scores.values().copied().collect();
139        let n = scores.len();
140
141        if n == 0 {
142            return PageRankStats::default();
143        }
144
145        let sum: f64 = scores.iter().sum();
146        let mean = sum / n as f64;
147        let variance: f64 = scores.iter().map(|s| (s - mean).powi(2)).sum::<f64>() / n as f64;
148        let max = scores.iter().cloned().fold(0.0f64, f64::max);
149        let min = scores.iter().cloned().fold(1.0f64, f64::min);
150
151        PageRankStats {
152            process_count: n,
153            mean_score: mean,
154            std_dev: variance.sqrt(),
155            max_score: max,
156            min_score: min,
157            iterations_to_converge: self.max_iterations, // Would need to track this
158        }
159    }
160
161    /// Combine PageRank with memory usage for final priority
162    pub fn get_weighted_candidates(
163        &self,
164        system: &System,
165        memory_weight: f64,
166        rank_weight: f64,
167        limit: usize,
168    ) -> Vec<(u32, f64)> {
169        let mut candidates: Vec<(u32, f64)> = Vec::new();
170
171        // Find max memory for normalization
172        let max_memory = system
173            .processes()
174            .values()
175            .map(|p| p.memory())
176            .max()
177            .unwrap_or(1) as f64;
178
179        for (pid, process) in system.processes() {
180            let pid_u32 = pid.as_u32();
181            let rank_score = self.get_score(pid_u32);
182            let memory_score = process.memory() as f64 / max_memory;
183
184            // Combined score: high memory + low rank = good trim candidate
185            let combined = memory_weight * memory_score + rank_weight * (1.0 - rank_score);
186            candidates.push((pid_u32, combined));
187        }
188
189        candidates.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal));
190        candidates.into_iter().take(limit).collect()
191    }
192}
193
194impl Default for ProcessPageRank {
195    fn default() -> Self {
196        Self::new()
197    }
198}
199
200#[derive(Debug, Clone, Default)]
201pub struct PageRankStats {
202    pub process_count: usize,
203    pub mean_score: f64,
204    pub std_dev: f64,
205    pub max_score: f64,
206    pub min_score: f64,
207    pub iterations_to_converge: usize,
208}
209
210#[cfg(test)]
211mod tests {
212    use super::*;
213
214    #[test]
215    fn test_pagerank_basic() {
216        let pagerank = ProcessPageRank::new();
217        let stats = pagerank.stats();
218        assert_eq!(stats.process_count, 0);
219    }
220}
ruvector_memopt/algorithms/pagerank.rs

ruvector_memopt/algorithms/
pagerank.rs
