rete_core/
tiling.rs

1//! Size-targeted tiling and graph summarization (SPEC.md §7).
2//!
3//! Given the community [`Dendrogram`], this layer turns triples into the
4//! pyramid's two products:
5//!
6//! - **Tiles** — each triple is assigned to the tile of its *subject's*
7//!   community (so every triple lives in exactly one tile, and a tile's triples
8//!   reconstruct losslessly). Tiles are sized by their encoded triple block, and
9//!   [`choose_round_for_budget`] picks the coarsest dendrogram round whose tiles
10//!   all fit the byte budget `T`.
11//! - **Summary** — aggregated [`SuperEdge`]s `(s_community, predicate,
12//!   o_community, count)`: the quotient graph a client fetches first for an
13//!   overview before zooming into any tile.
14
15use std::collections::BTreeMap;
16
17use crate::dictionary::Dictionary;
18use crate::pyramid::Dendrogram;
19use crate::triples::TripleBlockBuilder;
20
21/// Community of a subject term at the given dendrogram round (round is ignored
22/// when the graph had no community structure — everything is community 0).
23fn subject_comm(dict: &Dictionary, dend: &Dendrogram, round: usize, sid: u32) -> usize {
24    if dend.rounds() == 0 {
25        0
26    } else {
27        dend.base_community(dict.subject_node(sid) as usize, round)
28    }
29}
30
31/// Community of an object term at the given dendrogram round.
32fn object_comm(dict: &Dictionary, dend: &Dendrogram, round: usize, oid: u32) -> usize {
33    if dend.rounds() == 0 {
34        0
35    } else {
36        dend.base_community(dict.object_node(oid) as usize, round)
37    }
38}
39
40/// One tile: a community's triples and their encoded SPO block.
41#[derive(Debug, Clone)]
42pub struct Tile {
43    pub community: usize,
44    pub triples: Vec<(u32, u32, u32)>,
45    pub encoded: Vec<u8>,
46}
47
48/// Partition triples into per-community tiles at `round`, ordered by community.
49pub fn tile_by_community(
50    dict: &Dictionary,
51    triples: &[(u32, u32, u32)],
52    dend: &Dendrogram,
53    round: usize,
54) -> Vec<Tile> {
55    let mut groups: BTreeMap<usize, Vec<(u32, u32, u32)>> = BTreeMap::new();
56    for &t in triples {
57        let c = subject_comm(dict, dend, round, t.0);
58        groups.entry(c).or_default().push(t);
59    }
60    groups
61        .into_iter()
62        .map(|(community, ts)| {
63            let mut b = TripleBlockBuilder::new();
64            for &t in &ts {
65                b.push(t);
66            }
67            Tile {
68                community,
69                encoded: b.build(),
70                triples: ts,
71            }
72        })
73        .collect()
74}
75
76/// The coarsest round whose every tile fits `budget_bytes`, else round 0.
77/// Coarser rounds mean fewer, larger tiles; we want the fewest tiles that still
78/// respect the per-tile budget (PMTiles-style).
79pub fn choose_round_for_budget(
80    dict: &Dictionary,
81    triples: &[(u32, u32, u32)],
82    dend: &Dendrogram,
83    budget_bytes: usize,
84) -> usize {
85    // 0 rounds = no community structure; 1 round = the only choice is round 0
86    // anyway (the loop below would measure it and still return 0). Short-circuit
87    // both so a single-level dendrogram (e.g. `--pyramid-algo types`) never
88    // encodes every tile just to discard the measurement — on a 256 M-triple graph
89    // that wasted pass would re-encode the whole index.
90    if dend.rounds() <= 1 {
91        return 0;
92    }
93    for round in (0..dend.rounds()).rev() {
94        let max_tile = tile_by_community(dict, triples, dend, round)
95            .iter()
96            .map(|t| t.encoded.len())
97            .max()
98            .unwrap_or(0);
99        if max_tile <= budget_bytes {
100            return round;
101        }
102    }
103    0
104}
105
106/// An aggregated relation between two communities in the summary graph.
107#[derive(Debug, Clone, PartialEq, Eq)]
108pub struct SuperEdge {
109    pub s_comm: usize,
110    pub predicate: u32,
111    pub o_comm: usize,
112    pub count: u32,
113}
114
115/// Aggregate triples into the quotient (summary) graph at `round`.
116pub fn summarize(
117    dict: &Dictionary,
118    triples: &[(u32, u32, u32)],
119    dend: &Dendrogram,
120    round: usize,
121) -> Vec<SuperEdge> {
122    let mut counts: BTreeMap<(usize, u32, usize), u32> = BTreeMap::new();
123    for &(s, p, o) in triples {
124        let sc = subject_comm(dict, dend, round, s);
125        let oc = object_comm(dict, dend, round, o);
126        *counts.entry((sc, p, oc)).or_default() += 1;
127    }
128    counts
129        .into_iter()
130        .map(|((s_comm, predicate, o_comm), count)| SuperEdge {
131            s_comm,
132            predicate,
133            o_comm,
134            count,
135        })
136        .collect()
137}
138
139#[cfg(test)]
140mod tests {
141    use super::*;
142    use crate::dictionary::DictionaryBuilder;
143    use crate::pyramid::{build_dendrogram, project_graph};
144
145    /// Two clusters of `knows` edges joined by a bridge, plus some intra-cluster
146    /// fan-out so tiles have real size.
147    fn fixture() -> (Dictionary, Vec<(u32, u32, u32)>, Dendrogram) {
148        let edges = [
149            ("A", "B"),
150            ("B", "C"),
151            ("A", "C"),
152            ("C", "A"),
153            ("D", "E"),
154            ("E", "F"),
155            ("D", "F"),
156            ("F", "D"),
157            ("C", "D"), // bridge
158        ];
159        let mut db = DictionaryBuilder::new();
160        for (s, o) in edges {
161            db.observe(s, "knows", o);
162        }
163        let dict = db.build();
164        let triples: Vec<_> = edges
165            .iter()
166            .map(|(s, o)| dict.encode(s, "knows", o).unwrap())
167            .collect();
168        let g = project_graph(&dict, &triples);
169        let dend = build_dendrogram(&g);
170        (dict, triples, dend)
171    }
172
173    #[test]
174    fn tiles_reconstruct_all_triples_losslessly() {
175        let (dict, triples, dend) = fixture();
176        let round = dend.rounds().saturating_sub(1);
177        let tiles = tile_by_community(&dict, &triples, &dend, round);
178
179        let mut from_tiles: Vec<_> = tiles.iter().flat_map(|t| t.triples.clone()).collect();
180        from_tiles.sort_unstable();
181        let mut expected = triples.clone();
182        expected.sort_unstable();
183        assert_eq!(
184            from_tiles, expected,
185            "tiles must cover every triple exactly"
186        );
187        // More than one tile means the summary actually partitioned the graph.
188        assert!(tiles.len() >= 2);
189    }
190
191    #[test]
192    fn summary_preserves_total_count() {
193        let (dict, triples, dend) = fixture();
194        let round = dend.rounds().saturating_sub(1);
195        let summary = summarize(&dict, &triples, &dend, round);
196        let total: u32 = summary.iter().map(|e| e.count).sum();
197        assert_eq!(total as usize, triples.len());
198        // The bridge C->D shows up as a cross-community superedge.
199        assert!(summary.iter().any(|e| e.s_comm != e.o_comm));
200    }
201
202    #[test]
203    fn budget_selects_finer_round_when_tight() {
204        let (dict, triples, dend) = fixture();
205        // Huge budget => coarsest round (fewest tiles).
206        let coarse = choose_round_for_budget(&dict, &triples, &dend, 1_000_000);
207        // Zero budget => finest round 0.
208        let fine = choose_round_for_budget(&dict, &triples, &dend, 0);
209        assert!(coarse >= fine);
210        assert_eq!(fine, 0);
211    }
212}
rete_core/tiling.rs

rete_core/
tiling.rs
