graphops 0.5.0

Graph operators: PageRank/PPR/walks/reachability/node2vec/betweenness.
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

//! Rosetta correctness fixtures: graphops PageRank asserted against networkx.
//!
//! Reference values in `fixtures/rosetta/graphops_pagerank.json` come from
//! `gen_graphops.py` (their provenance). graphops and networkx use the same
//! random-surfer model (uniform teleport, dangling mass redistributed
//! uniformly), so the unique PageRank fixed point agrees once both are
//! converged tightly. The two stop rules differ (graphops: L1 delta < tol;
//! networkx: L1 delta < n*tol), so both run far tighter than the 1e-9
//! comparison to remove that as a variable.
//!
//! Covered: pagerank (unweighted, with a dangling node) and pagerank_weighted.
//! Brandes betweenness (petgraph-feature-gated) is now covered in the sibling
//! file `rosetta_graphops_betweenness.rs`. Deferred: connected components (no
//! single graphops function maps cleanly to networkx).
//!
//! Regenerate the fixture: `uv run tests/fixtures/rosetta/gen_graphops.py`.

use graphops::{pagerank, pagerank_weighted, AdjacencyMatrix, PageRankConfig};
use serde::Deserialize;

const FIXTURE: &str = include_str!("fixtures/rosetta/graphops_pagerank.json");

#[derive(Deserialize)]
struct Fixture {
    params: Params,
    adj_unweighted: Vec<Vec<f64>>,
    adj_weighted: Vec<Vec<f64>>,
    expected: Expected,
}

#[derive(Deserialize)]
struct Params {
    damping: f64,
    graphops_tolerance: f64,
    max_iterations: usize,
}

#[derive(Deserialize)]
struct Expected {
    pagerank: Vec<f64>,
    pagerank_weighted: Vec<f64>,
}

fn vec_close(got: &[f64], want: &[f64], label: &str) {
    assert_eq!(got.len(), want.len(), "{label}: length");
    for (i, (&g, &w)) in got.iter().zip(want.iter()).enumerate() {
        let tol = 1e-9 * (1.0 + w.abs());
        let diff = (g - w).abs();
        assert!(
            diff <= tol,
            "{label}[{i}]: graphops={g} networkx={w} diff={diff} tol={tol}"
        );
    }
}

#[test]
fn rosetta_pagerank_matches_networkx() {
    let fx: Fixture = serde_json::from_str(FIXTURE).expect("parse rosetta fixture");
    let config = PageRankConfig {
        damping: fx.params.damping,
        max_iterations: fx.params.max_iterations,
        tolerance: fx.params.graphops_tolerance,
    };

    let scores = pagerank(&AdjacencyMatrix(&fx.adj_unweighted), config);
    vec_close(&scores, &fx.expected.pagerank, "pagerank");

    let wscores = pagerank_weighted(&AdjacencyMatrix(&fx.adj_weighted), config);
    vec_close(
        &wscores,
        &fx.expected.pagerank_weighted,
        "pagerank_weighted",
    );
}