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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
// SPDX-License-Identifier: Apache-2.0
//! Integration tests for the `graph_pagerank` public API on `NodeDbLite`.
//!
//! Covers: empty-graph handling, uniform PageRank on a symmetric graph,
//! Personalized PageRank seed concentration, rank-sum invariant, and
//! descending sort of results.
use std::collections::HashMap;
use nodedb_client::NodeDb;
use nodedb_lite::{NodeDbLite, PagedbStorageMem};
use nodedb_types::id::NodeId;
async fn open_db() -> std::sync::Arc<NodeDbLite<PagedbStorageMem>> {
let storage = PagedbStorageMem::open_in_memory().await.unwrap();
NodeDbLite::open(storage).await.unwrap()
}
/// Insert a directed triangle A→B, B→C, C→A into `collection`.
async fn insert_triangle(db: &NodeDbLite<PagedbStorageMem>, collection: &str) {
let a = NodeId::from_validated("A".to_string());
let b = NodeId::from_validated("B".to_string());
let c = NodeId::from_validated("C".to_string());
db.graph_insert_edge(collection, &a, &b, "E", None)
.await
.unwrap();
db.graph_insert_edge(collection, &b, &c, "E", None)
.await
.unwrap();
db.graph_insert_edge(collection, &c, &a, "E", None)
.await
.unwrap();
}
// ---------------------------------------------------------------------------
// Test 1 — pagerank_on_empty_graph_returns_empty
// ---------------------------------------------------------------------------
/// Calling `graph_pagerank` on a collection that has never had edges inserted
/// must return an empty `Vec`, not an error.
#[tokio::test]
async fn pagerank_on_empty_graph_returns_empty() {
let db = open_db().await;
let result = db
.graph_pagerank("nonexistent_collection", None, None, None)
.await
.unwrap();
assert!(
result.is_empty(),
"expected empty result for collection with no edges"
);
}
// ---------------------------------------------------------------------------
// Test 2 — pagerank_uniform_returns_equal_ranks_on_symmetric_graph
// ---------------------------------------------------------------------------
/// A directed triangle is rotationally symmetric; all three nodes must
/// receive approximately the same PageRank (within 0.01).
#[tokio::test]
async fn pagerank_uniform_returns_equal_ranks_on_symmetric_graph() {
let db = open_db().await;
insert_triangle(&db, "tri").await;
let result = db.graph_pagerank("tri", None, None, None).await.unwrap();
assert_eq!(result.len(), 3, "triangle has three nodes");
let ranks: Vec<f64> = result.iter().map(|(_, r)| *r).collect();
let first = ranks[0];
for r in &ranks {
assert!(
(r - first).abs() < 0.01,
"expected equal ranks on symmetric triangle; got {ranks:?}"
);
}
}
// ---------------------------------------------------------------------------
// Test 3 — pagerank_personalized_concentrates_on_seed
// ---------------------------------------------------------------------------
/// Seeding node "A" with full weight must make "A" the highest-ranked node.
#[tokio::test]
async fn pagerank_personalized_concentrates_on_seed() {
let db = open_db().await;
insert_triangle(&db, "tri_ppr").await;
let mut pv: HashMap<String, f64> = HashMap::new();
pv.insert("A".to_string(), 1.0);
let result = db
.graph_pagerank("tri_ppr", Some(pv), None, None)
.await
.unwrap();
assert_eq!(result.len(), 3);
// Results are sorted descending, so the first entry must be "A".
let (top_node, top_rank) = &result[0];
assert_eq!(
top_node, "A",
"seeded node 'A' must have the highest rank; got top={top_node} rank={top_rank}"
);
// "A" must strictly outrank the other two.
for (node, rank) in result.iter().skip(1) {
assert!(
top_rank > rank,
"A ({top_rank}) must outrank {node} ({rank})"
);
}
}
// ---------------------------------------------------------------------------
// Test 4 — pagerank_ranks_sum_to_one
// ---------------------------------------------------------------------------
/// Regardless of personalization the rank vector must sum to ≈1.0.
#[tokio::test]
async fn pagerank_ranks_sum_to_one() {
let db = open_db().await;
insert_triangle(&db, "tri_sum").await;
let result = db
.graph_pagerank("tri_sum", None, None, None)
.await
.unwrap();
let total: f64 = result.iter().map(|(_, r)| r).sum();
assert!(
(total - 1.0).abs() < 0.01,
"ranks must sum to 1.0; got {total}"
);
}
// ---------------------------------------------------------------------------
// Test 5 — pagerank_results_sorted_descending
// ---------------------------------------------------------------------------
/// Results must be in descending rank order (highest rank first).
#[tokio::test]
async fn pagerank_results_sorted_descending() {
let db = open_db().await;
// Build a star graph: A→B, A→C, A→D, A→E.
// A has high out-degree so B/C/D/E receive most rank.
// The exact ordering doesn't matter; what matters is the list is sorted.
let a = NodeId::from_validated("A".to_string());
for target in ["B", "C", "D", "E"] {
let t = NodeId::from_validated(target.to_string());
db.graph_insert_edge("star", &a, &t, "E", None)
.await
.unwrap();
}
let result = db.graph_pagerank("star", None, None, None).await.unwrap();
for window in result.windows(2) {
let (_, r1) = &window[0];
let (_, r2) = &window[1];
assert!(
r1 >= r2,
"results must be sorted descending; found {r1} before {r2}"
);
}
}