weavatrix-graph 0.6.0

Deterministic, evidence-carrying graph primitives for repository intelligence
Documentation 
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 crate::{GraphError, IndexGraphView, Result};
use crate::{ToString, Vec};

/// Computes `PageRank` in graph node order.
///
/// # Errors
///
/// Returns an error when `damping` is not finite or outside `0.0..=1.0`.
pub fn page_rank<G>(graph: &G, damping: f64, iterations: usize) -> Result<Vec<(G::Node, f64)>>
where
    G: IndexGraphView,
{
    page_rank_filtered(graph, damping, iterations, |_| true)
}

/// Computes `PageRank` over the selected edges in graph node order.
///
/// Dangling-node mass is distributed uniformly. Parallel edges contribute
/// independently, matching the multigraph contract used by traversal.
///
/// # Errors
///
/// Returns an error when `damping` is not finite or outside `0.0..=1.0`.
pub fn page_rank_filtered<G, F>(
    graph: &G,
    damping: f64,
    iterations: usize,
    allows_edge: F,
) -> Result<Vec<(G::Node, f64)>>
where
    G: IndexGraphView,
    F: Fn(G::Edge) -> bool,
{
    validate_damping(damping)?;
    let nodes = graph.node_indices().collect::<Vec<_>>();
    if nodes.is_empty() {
        return Ok(Vec::new());
    }
    let mut positions = vec![None; graph.node_bound()];
    for (position, &node) in nodes.iter().enumerate() {
        positions[G::node_slot(node)] = Some(position);
    }
    let edges = graph
        .edge_references()
        .filter(|(edge, _)| allows_edge(*edge))
        .filter_map(|(_, endpoints)| {
            let source = positions[G::node_slot(endpoints.source())]?;
            let target = positions[G::node_slot(endpoints.target())]?;
            Some((source, target))
        })
        .collect::<Vec<_>>();
    let mut out_degree = vec![0_usize; nodes.len()];
    for &(source, _) in &edges {
        out_degree[source] += 1;
    }

    let node_count = usize_as_f64(nodes.len());
    let mut ranks = vec![1.0 / node_count; nodes.len()];
    let mut next = vec![0.0; nodes.len()];
    for _ in 0..iterations {
        let dangling = ranks
            .iter()
            .zip(&out_degree)
            .filter(|(_, degree)| **degree == 0)
            .map(|(rank, _)| rank)
            .sum::<f64>();
        next.fill((1.0 - damping + damping * dangling) / node_count);
        for &(source, target) in &edges {
            next[target] += damping * ranks[source] / usize_as_f64(out_degree[source]);
        }
        normalize(&mut next);
        core::mem::swap(&mut ranks, &mut next);
    }
    Ok(nodes.into_iter().zip(ranks).collect())
}

fn validate_damping(damping: f64) -> Result<()> {
    if damping.is_finite() && (0.0..=1.0).contains(&damping) {
        return Ok(());
    }
    Err(GraphError::InvalidAlgorithmParameter {
        algorithm: "PageRank",
        parameter: "damping",
        value: damping.to_string(),
    })
}

fn normalize(values: &mut [f64]) {
    let sum = values.iter().sum::<f64>();
    if sum > 0.0 {
        for value in values {
            *value /= sum;
        }
    }
}

#[allow(clippy::cast_precision_loss)]
fn usize_as_f64(value: usize) -> f64 {
    value as f64
}