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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
//! Size-targeted tiling and graph summarization (SPEC.md §7).
//!
//! Given the community [`Dendrogram`], this layer turns triples into the
//! pyramid's two products:
//!
//! - **Tiles** — each triple is assigned to the tile of its *subject's*
//! community (so every triple lives in exactly one tile, and a tile's triples
//! reconstruct losslessly). Tiles are sized by their encoded triple block, and
//! [`choose_round_for_budget`] picks the coarsest dendrogram round whose tiles
//! all fit the byte budget `T`.
//! - **Summary** — aggregated [`SuperEdge`]s `(s_community, predicate,
//! o_community, count)`: the quotient graph a client fetches first for an
//! overview before zooming into any tile.
use std::collections::BTreeMap;
use crate::dictionary::Dictionary;
use crate::pyramid::Dendrogram;
use crate::triples::TripleBlockBuilder;
/// Community of a subject term at the given dendrogram round (round is ignored
/// when the graph had no community structure — everything is community 0).
fn subject_comm(dict: &Dictionary, dend: &Dendrogram, round: usize, sid: u32) -> usize {
if dend.rounds() == 0 {
0
} else {
dend.base_community(dict.subject_node(sid) as usize, round)
}
}
/// Community of an object term at the given dendrogram round.
fn object_comm(dict: &Dictionary, dend: &Dendrogram, round: usize, oid: u32) -> usize {
if dend.rounds() == 0 {
0
} else {
dend.base_community(dict.object_node(oid) as usize, round)
}
}
/// One tile: a community's triples and their encoded SPO block.
#[derive(Debug, Clone)]
pub struct Tile {
pub community: usize,
pub triples: Vec<(u32, u32, u32)>,
pub encoded: Vec<u8>,
}
/// Partition triples into per-community tiles at `round`, ordered by community.
pub fn tile_by_community(
dict: &Dictionary,
triples: &[(u32, u32, u32)],
dend: &Dendrogram,
round: usize,
) -> Vec<Tile> {
let mut groups: BTreeMap<usize, Vec<(u32, u32, u32)>> = BTreeMap::new();
for &t in triples {
let c = subject_comm(dict, dend, round, t.0);
groups.entry(c).or_default().push(t);
}
groups
.into_iter()
.map(|(community, ts)| {
let mut b = TripleBlockBuilder::new();
for &t in &ts {
b.push(t);
}
Tile {
community,
encoded: b.build(),
triples: ts,
}
})
.collect()
}
/// The coarsest round whose every tile fits `budget_bytes`, else round 0.
/// Coarser rounds mean fewer, larger tiles; we want the fewest tiles that still
/// respect the per-tile budget (PMTiles-style).
pub fn choose_round_for_budget(
dict: &Dictionary,
triples: &[(u32, u32, u32)],
dend: &Dendrogram,
budget_bytes: usize,
) -> usize {
// 0 rounds = no community structure; 1 round = the only choice is round 0
// anyway (the loop below would measure it and still return 0). Short-circuit
// both so a single-level dendrogram (e.g. `--pyramid-algo types`) never
// encodes every tile just to discard the measurement — on a 256 M-triple graph
// that wasted pass would re-encode the whole index.
if dend.rounds() <= 1 {
return 0;
}
for round in (0..dend.rounds()).rev() {
let max_tile = tile_by_community(dict, triples, dend, round)
.iter()
.map(|t| t.encoded.len())
.max()
.unwrap_or(0);
if max_tile <= budget_bytes {
return round;
}
}
0
}
/// An aggregated relation between two communities in the summary graph.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct SuperEdge {
pub s_comm: usize,
pub predicate: u32,
pub o_comm: usize,
pub count: u32,
}
/// Aggregate triples into the quotient (summary) graph at `round`.
pub fn summarize(
dict: &Dictionary,
triples: &[(u32, u32, u32)],
dend: &Dendrogram,
round: usize,
) -> Vec<SuperEdge> {
let mut counts: BTreeMap<(usize, u32, usize), u32> = BTreeMap::new();
for &(s, p, o) in triples {
let sc = subject_comm(dict, dend, round, s);
let oc = object_comm(dict, dend, round, o);
*counts.entry((sc, p, oc)).or_default() += 1;
}
counts
.into_iter()
.map(|((s_comm, predicate, o_comm), count)| SuperEdge {
s_comm,
predicate,
o_comm,
count,
})
.collect()
}
#[cfg(test)]
mod tests {
use super::*;
use crate::dictionary::DictionaryBuilder;
use crate::pyramid::{build_dendrogram, project_graph};
/// Two clusters of `knows` edges joined by a bridge, plus some intra-cluster
/// fan-out so tiles have real size.
fn fixture() -> (Dictionary, Vec<(u32, u32, u32)>, Dendrogram) {
let edges = [
("A", "B"),
("B", "C"),
("A", "C"),
("C", "A"),
("D", "E"),
("E", "F"),
("D", "F"),
("F", "D"),
("C", "D"), // bridge
];
let mut db = DictionaryBuilder::new();
for (s, o) in edges {
db.observe(s, "knows", o);
}
let dict = db.build();
let triples: Vec<_> = edges
.iter()
.map(|(s, o)| dict.encode(s, "knows", o).unwrap())
.collect();
let g = project_graph(&dict, &triples);
let dend = build_dendrogram(&g);
(dict, triples, dend)
}
#[test]
fn tiles_reconstruct_all_triples_losslessly() {
let (dict, triples, dend) = fixture();
let round = dend.rounds().saturating_sub(1);
let tiles = tile_by_community(&dict, &triples, &dend, round);
let mut from_tiles: Vec<_> = tiles.iter().flat_map(|t| t.triples.clone()).collect();
from_tiles.sort_unstable();
let mut expected = triples.clone();
expected.sort_unstable();
assert_eq!(
from_tiles, expected,
"tiles must cover every triple exactly"
);
// More than one tile means the summary actually partitioned the graph.
assert!(tiles.len() >= 2);
}
#[test]
fn summary_preserves_total_count() {
let (dict, triples, dend) = fixture();
let round = dend.rounds().saturating_sub(1);
let summary = summarize(&dict, &triples, &dend, round);
let total: u32 = summary.iter().map(|e| e.count).sum();
assert_eq!(total as usize, triples.len());
// The bridge C->D shows up as a cross-community superedge.
assert!(summary.iter().any(|e| e.s_comm != e.o_comm));
}
#[test]
fn budget_selects_finer_round_when_tight() {
let (dict, triples, dend) = fixture();
// Huge budget => coarsest round (fewest tiles).
let coarse = choose_round_for_budget(&dict, &triples, &dend, 1_000_000);
// Zero budget => finest round 0.
let fine = choose_round_for_budget(&dict, &triples, &dend, 0);
assert!(coarse >= fine);
assert_eq!(fine, 0);
}
}