1use bytemuck::Pod;
7
8use crate::topology::header::{
9 AnchorDomain, CellAnchor, HarbouredGraphHeader, TopologyError, TopologyInvariants,
10};
11
12#[derive(Copy, Clone, Debug, PartialEq)]
15pub struct HarbouredCsrView<'a> {
16 header: &'a HarbouredGraphHeader,
17 anchors: &'a [CellAnchor],
18 csr_row_ptr: &'a [u32],
19 csr_col_idx: &'a [u32],
20 edge_anchor: &'a [u32],
21 csc_col_ptr: &'a [u32],
22 csc_row_idx: &'a [u32],
23 edge_weights: Option<&'a [f32]>,
24}
25
26impl<'a> HarbouredCsrView<'a> {
27 #[allow(clippy::too_many_arguments)]
29 pub fn from_slices(
30 header: &'a HarbouredGraphHeader,
31 anchors: &'a [CellAnchor],
32 csr_row_ptr: &'a [u32],
33 csr_col_idx: &'a [u32],
34 edge_anchor: &'a [u32],
35 csc_col_ptr: &'a [u32],
36 csc_row_idx: &'a [u32],
37 edge_weights: Option<&'a [f32]>,
38 ) -> Result<Self, TopologyError> {
39 if header.embed_role != 0 && header.embed_role_enum().is_none() {
40 return Err(TopologyError::InvalidEmbedRole(header.embed_role));
41 }
42 if header.morphology != 0 && header.morphology_enum().is_none() {
43 return Err(TopologyError::InvalidMorphology(header.morphology));
44 }
45
46 let v_count = header.vertex_count as usize;
47 let e_count = header.edge_count as usize;
48
49 if anchors.len() != v_count
50 || csr_row_ptr.len() != v_count + 1
51 || csr_col_idx.len() != e_count
52 || edge_anchor.len() != e_count
53 || csc_col_ptr.len() != v_count + 1
54 || csc_row_idx.len() != e_count
55 {
56 return Err(TopologyError::BufferTooSmall);
57 }
58
59 if let Some(weights) = edge_weights {
60 if weights.len() != e_count {
61 return Err(TopologyError::BufferTooSmall);
62 }
63 }
64
65 if csr_row_ptr[0] != 0 {
66 return Err(TopologyError::NonMonotonicRowPtr { vertex: 0 });
67 }
68 for u in 0..v_count {
69 if csr_row_ptr[u] > csr_row_ptr[u + 1] {
70 return Err(TopologyError::NonMonotonicRowPtr { vertex: u as u32 });
71 }
72 }
73 if csr_row_ptr[v_count] != header.edge_count {
74 return Err(TopologyError::NonMonotonicRowPtr {
75 vertex: header.vertex_count,
76 });
77 }
78
79 if csc_col_ptr[0] != 0 {
80 return Err(TopologyError::NonMonotonicRowPtr { vertex: 0 });
81 }
82 for v in 0..v_count {
83 if csc_col_ptr[v] > csc_col_ptr[v + 1] {
84 return Err(TopologyError::NonMonotonicRowPtr { vertex: v as u32 });
85 }
86 }
87 if csc_col_ptr[v_count] != header.edge_count {
88 return Err(TopologyError::NonMonotonicRowPtr {
89 vertex: header.vertex_count,
90 });
91 }
92
93 for &col in csr_col_idx {
94 if col >= header.vertex_count {
95 return Err(TopologyError::VertexOutOfRange {
96 vertex: col,
97 count: header.vertex_count,
98 });
99 }
100 }
101
102 for &row in csc_row_idx {
103 if row >= header.vertex_count {
104 return Err(TopologyError::VertexOutOfRange {
105 vertex: row,
106 count: header.vertex_count,
107 });
108 }
109 }
110
111 Ok(Self {
112 header,
113 anchors,
114 csr_row_ptr,
115 csr_col_idx,
116 edge_anchor,
117 csc_col_ptr,
118 csc_row_idx,
119 edge_weights,
120 })
121 }
122
123 pub fn from_segment_bytes(
125 segment: &'a [u8],
126 header: &'a HarbouredGraphHeader,
127 ) -> Result<Self, TopologyError> {
128 let v_count = header.vertex_count as usize;
129 let e_count = header.edge_count as usize;
130
131 let anchors = slice_pod::<CellAnchor>(segment, header.anchor_table_offset, v_count)?;
132 let csr_row_ptr = slice_pod::<u32>(segment, header.csr_row_ptr_offset, v_count + 1)?;
133 let csr_col_idx = slice_pod::<u32>(segment, header.csr_col_idx_offset, e_count)?;
134 let edge_anchor = slice_pod::<u32>(segment, header.edge_anchor_offset, e_count)?;
135 let csc_col_ptr = slice_pod::<u32>(segment, header.csc_col_ptr_offset, v_count + 1)?;
136 let csc_row_idx = slice_pod::<u32>(segment, header.csc_row_idx_offset, e_count)?;
137 let edge_weights = if header.edge_weight_offset != 0 {
138 Some(slice_pod::<f32>(
139 segment,
140 header.edge_weight_offset,
141 e_count,
142 )?)
143 } else {
144 None
145 };
146
147 Self::from_slices(
148 header,
149 anchors,
150 csr_row_ptr,
151 csr_col_idx,
152 edge_anchor,
153 csc_col_ptr,
154 csc_row_idx,
155 edge_weights,
156 )
157 }
158
159 #[inline]
160 pub const fn header(&self) -> &'a HarbouredGraphHeader {
161 self.header
162 }
163
164 #[inline]
165 pub const fn vertex_count(&self) -> u32 {
166 self.header.vertex_count
167 }
168
169 #[inline]
170 pub const fn edge_count(&self) -> u32 {
171 self.header.edge_count
172 }
173
174 #[inline]
175 pub const fn anchors(&self) -> &'a [CellAnchor] {
176 self.anchors
177 }
178
179 #[inline]
180 pub const fn csr_row_ptr(&self) -> &'a [u32] {
181 self.csr_row_ptr
182 }
183
184 #[inline]
185 pub const fn csr_col_idx(&self) -> &'a [u32] {
186 self.csr_col_idx
187 }
188
189 #[inline]
190 pub const fn edge_anchor(&self) -> &'a [u32] {
191 self.edge_anchor
192 }
193
194 #[inline]
195 pub const fn edge_anchors(&self) -> &'a [u32] {
196 self.edge_anchor
197 }
198
199 #[inline]
200 pub const fn csc_col_ptr(&self) -> &'a [u32] {
201 self.csc_col_ptr
202 }
203
204 #[inline]
205 pub const fn csc_row_idx(&self) -> &'a [u32] {
206 self.csc_row_idx
207 }
208
209 #[inline]
210 pub const fn edge_weights(&self) -> Option<&'a [f32]> {
211 self.edge_weights
212 }
213
214 #[inline]
216 pub fn cell_anchor(&self, v: u32) -> Result<&'a CellAnchor, TopologyError> {
217 self.anchors
218 .get(v as usize)
219 .ok_or(TopologyError::VertexOutOfRange {
220 vertex: v,
221 count: self.header.vertex_count,
222 })
223 }
224
225 #[inline]
227 pub fn out_neighbors(&self, u: u32) -> Result<&'a [u32], TopologyError> {
228 if u >= self.header.vertex_count {
229 return Err(TopologyError::VertexOutOfRange {
230 vertex: u,
231 count: self.header.vertex_count,
232 });
233 }
234 let idx = u as usize;
235 let start = self.csr_row_ptr[idx] as usize;
236 let end = self.csr_row_ptr[idx + 1] as usize;
237 Ok(&self.csr_col_idx[start..end])
238 }
239
240 #[inline]
242 pub fn out_edge_anchors(&self, u: u32) -> Result<&'a [u32], TopologyError> {
243 if u >= self.header.vertex_count {
244 return Err(TopologyError::VertexOutOfRange {
245 vertex: u,
246 count: self.header.vertex_count,
247 });
248 }
249 let idx = u as usize;
250 let start = self.csr_row_ptr[idx] as usize;
251 let end = self.csr_row_ptr[idx + 1] as usize;
252 Ok(&self.edge_anchor[start..end])
253 }
254
255 #[inline]
257 pub fn out_edge_weights(&self, u: u32) -> Result<Option<&'a [f32]>, TopologyError> {
258 if u >= self.header.vertex_count {
259 return Err(TopologyError::VertexOutOfRange {
260 vertex: u,
261 count: self.header.vertex_count,
262 });
263 }
264 let idx = u as usize;
265 let start = self.csr_row_ptr[idx] as usize;
266 let end = self.csr_row_ptr[idx + 1] as usize;
267 Ok(self.edge_weights.map(|w| &w[start..end]))
268 }
269
270 #[inline]
272 pub fn in_neighbors(&self, v: u32) -> Result<&'a [u32], TopologyError> {
273 if v >= self.header.vertex_count {
274 return Err(TopologyError::VertexOutOfRange {
275 vertex: v,
276 count: self.header.vertex_count,
277 });
278 }
279 let idx = v as usize;
280 let start = self.csc_col_ptr[idx] as usize;
281 let end = self.csc_col_ptr[idx + 1] as usize;
282 Ok(&self.csc_row_idx[start..end])
283 }
284
285 #[inline]
287 pub fn out_degree(&self, u: u32) -> Result<u32, TopologyError> {
288 if u >= self.header.vertex_count {
289 return Err(TopologyError::VertexOutOfRange {
290 vertex: u,
291 count: self.header.vertex_count,
292 });
293 }
294 let idx = u as usize;
295 Ok(self.csr_row_ptr[idx + 1] - self.csr_row_ptr[idx])
296 }
297
298 #[inline]
300 pub fn in_degree(&self, v: u32) -> Result<u32, TopologyError> {
301 if v >= self.header.vertex_count {
302 return Err(TopologyError::VertexOutOfRange {
303 vertex: v,
304 count: self.header.vertex_count,
305 });
306 }
307 let idx = v as usize;
308 Ok(self.csc_col_ptr[idx + 1] - self.csc_col_ptr[idx])
309 }
310
311 pub fn find_vertex_by_entity_hash(&self, entity_hash: u64) -> Option<u32> {
314 if let Ok(idx) = self
315 .anchors
316 .binary_search_by_key(&entity_hash, |a| a.entity_hash)
317 {
318 return Some(idx as u32);
319 }
320 let mut i = 0usize;
321 while i < self.anchors.len() {
322 if self.anchors[i].entity_hash == entity_hash {
323 return Some(i as u32);
324 }
325 i += 1;
326 }
327 None
328 }
329
330 pub fn find_vertices_by_cell(
332 &self,
333 domain: AnchorDomain,
334 cell_index: u32,
335 out: &mut [u32],
336 ) -> usize {
337 let domain_u8 = domain as u8;
338 let mut written = 0usize;
339 let mut v = 0usize;
340 while v < self.anchors.len() {
341 let a = &self.anchors[v];
342 if a.anchor_domain == domain_u8 && a.cell_index == cell_index {
343 if written >= out.len() {
344 break;
345 }
346 out[written] = v as u32;
347 written += 1;
348 }
349 v += 1;
350 }
351 written
352 }
353
354 pub fn collect_roots(&self, out: &mut [u32]) -> usize {
356 let mut written = 0usize;
357 let v_count = self.header.vertex_count as usize;
358 let mut v = 0usize;
359 while v < v_count {
360 if self.csc_col_ptr[v + 1] == self.csc_col_ptr[v] {
361 if written >= out.len() {
362 break;
363 }
364 out[written] = v as u32;
365 written += 1;
366 }
367 v += 1;
368 }
369 written
370 }
371
372 pub fn collect_sinks(&self, out: &mut [u32]) -> usize {
374 let mut written = 0usize;
375 let v_count = self.header.vertex_count as usize;
376 let mut u = 0usize;
377 while u < v_count {
378 if self.csr_row_ptr[u + 1] == self.csr_row_ptr[u] {
379 if written >= out.len() {
380 break;
381 }
382 out[written] = u as u32;
383 written += 1;
384 }
385 u += 1;
386 }
387 written
388 }
389
390 pub fn resolve_reified_edge_vertex(
393 &self,
394 quins: &[crate::NQuin],
395 edge_pos: usize,
396 ) -> Option<u32> {
397 if !self
398 .header
399 .invariants
400 .contains(TopologyInvariants::REIFIED_EDGES)
401 {
402 return None;
403 }
404 let quin_idx = *self.edge_anchor.get(edge_pos)? as usize;
405 let q = quins.get(quin_idx)?;
406 let virtual_id = crate::query::rdf_star::create_virtual_id(q.subject, q.predicate, q.object);
407 self.find_vertex_by_entity_hash(virtual_id)
408 }
409}
410
411#[inline]
412pub(crate) fn slice_pod<'a, T: Pod>(
413 segment: &'a [u8],
414 offset: u32,
415 count: usize,
416) -> Result<&'a [T], TopologyError> {
417 let start = offset as usize;
418 if count == 0 {
419 if start > segment.len() {
420 return Err(TopologyError::BufferTooSmall);
421 }
422 return Ok(&[]);
423 }
424 let byte_len = count
425 .checked_mul(core::mem::size_of::<T>())
426 .ok_or(TopologyError::BufferTooSmall)?;
427 let end = start
428 .checked_add(byte_len)
429 .ok_or(TopologyError::BufferTooSmall)?;
430 let bytes = segment
431 .get(start..end)
432 .ok_or(TopologyError::BufferTooSmall)?;
433 bytemuck::try_cast_slice(bytes).map_err(|_| TopologyError::UnalignedBuffer)
434}
435