oxgraph_hyper_bcsr/internal/
traits.rs

1//! Topology and hypergraph trait implementations for [`BcsrHypergraph`].
2//!
3//! [`BcsrHypergraph`]: crate::BcsrHypergraph
4
5use oxgraph_hyper::{
6    ContainsElement, ContainsIncidence, ContainsRelation, DirectedHyperedgeIncidences,
7    DirectedHyperedgeParticipants, DirectedVertexHyperedges, ElementIncidenceCount,
8    ElementIncidences, ElementIndex, ElementPredecessors, ElementSuccessors, HyperedgeParticipants,
9    HypergraphCounts, IncidenceBase, IncidenceCounts, IncidenceElement, IncidenceIndex,
10    IncidenceRelation, IncidenceRole, IncidentHyperedges, RelationIncidenceCount,
11    RelationIncidences, RelationIndex, TopologyBase, TopologyCounts,
12};
13
14use crate::{
15    id::{BcsrHyperedgeId, BcsrParticipantId, BcsrRole, BcsrVertexId},
16    internal::{
17        iter::{
18            BcsrChainedHyperedges, BcsrChainedParticipants, BcsrChainedRelationIncidences,
19            BcsrElementIncidences, BcsrHyperedgeSlice, BcsrParticipantSlice,
20            BcsrPredecessorVertices, BcsrSuccessorVertices, BcsrVertexSlice,
21        },
22        validation::{index_to_usize_validated, usize_to_index_validated},
23        view::BcsrHypergraph,
24    },
25    word::{LayoutIndex, LayoutWord},
26};
27
28/// Private shorthand for the generic BCSR view.
29type View<'a, V, R, I, O, VW, RW> = BcsrHypergraph<'a, V, R, I, O, VW, RW>;
30
31impl<V, R, I, O, VW, RW> TopologyBase for View<'_, V, R, I, O, VW, RW>
32where
33    V: LayoutIndex,
34    R: LayoutIndex,
35    I: LayoutIndex,
36    O: LayoutWord<Index = I>,
37    VW: LayoutWord<Index = V>,
38    RW: LayoutWord<Index = R>,
39{
40    type ElementId = BcsrVertexId<V>;
41    type RelationId = BcsrHyperedgeId<R>;
42}
43
44impl<V, R, I, O, VW, RW> IncidenceBase for View<'_, V, R, I, O, VW, RW>
45where
46    V: LayoutIndex,
47    R: LayoutIndex,
48    I: LayoutIndex,
49    O: LayoutWord<Index = I>,
50    VW: LayoutWord<Index = V>,
51    RW: LayoutWord<Index = R>,
52{
53    type IncidenceId = BcsrParticipantId<I>;
54    type Role = BcsrRole;
55}
56
57impl<V, R, I, O, VW, RW> TopologyCounts for View<'_, V, R, I, O, VW, RW>
58where
59    V: LayoutIndex,
60    R: LayoutIndex,
61    I: LayoutIndex,
62    O: LayoutWord<Index = I>,
63    VW: LayoutWord<Index = V>,
64    RW: LayoutWord<Index = R>,
65{
66    fn element_count(&self) -> usize {
67        self.vertex_count()
68    }
69
70    fn relation_count(&self) -> usize {
71        self.hyperedge_count()
72    }
73}
74
75impl<V, R, I, O, VW, RW> IncidenceCounts for View<'_, V, R, I, O, VW, RW>
76where
77    V: LayoutIndex,
78    R: LayoutIndex,
79    I: LayoutIndex,
80    O: LayoutWord<Index = I>,
81    VW: LayoutWord<Index = V>,
82    RW: LayoutWord<Index = R>,
83{
84    fn incidence_count(&self) -> usize {
85        self.counts().total_incidences
86    }
87}
88
89impl<V, R, I, O, VW, RW> HypergraphCounts for View<'_, V, R, I, O, VW, RW>
90where
91    V: LayoutIndex,
92    R: LayoutIndex,
93    I: LayoutIndex,
94    O: LayoutWord<Index = I>,
95    VW: LayoutWord<Index = V>,
96    RW: LayoutWord<Index = R>,
97{
98}
99
100impl<V, R, I, O, VW, RW> ElementIndex for View<'_, V, R, I, O, VW, RW>
101where
102    V: LayoutIndex,
103    R: LayoutIndex,
104    I: LayoutIndex,
105    O: LayoutWord<Index = I>,
106    VW: LayoutWord<Index = V>,
107    RW: LayoutWord<Index = R>,
108{
109    fn element_bound(&self) -> usize {
110        self.vertex_count()
111    }
112
113    fn element_index(&self, element: BcsrVertexId<V>) -> usize {
114        index_to_usize_validated(element.get())
115    }
116}
117
118impl<V, R, I, O, VW, RW> RelationIndex for View<'_, V, R, I, O, VW, RW>
119where
120    V: LayoutIndex,
121    R: LayoutIndex,
122    I: LayoutIndex,
123    O: LayoutWord<Index = I>,
124    VW: LayoutWord<Index = V>,
125    RW: LayoutWord<Index = R>,
126{
127    fn relation_bound(&self) -> usize {
128        self.hyperedge_count()
129    }
130
131    fn relation_index(&self, relation: BcsrHyperedgeId<R>) -> usize {
132        index_to_usize_validated(relation.get())
133    }
134}
135
136impl<V, R, I, O, VW, RW> IncidenceIndex for View<'_, V, R, I, O, VW, RW>
137where
138    V: LayoutIndex,
139    R: LayoutIndex,
140    I: LayoutIndex,
141    O: LayoutWord<Index = I>,
142    VW: LayoutWord<Index = V>,
143    RW: LayoutWord<Index = R>,
144{
145    fn incidence_bound(&self) -> usize {
146        self.counts().total_incidences
147    }
148
149    fn incidence_index(&self, incidence: BcsrParticipantId<I>) -> usize {
150        index_to_usize_validated(incidence.get())
151    }
152}
153
154impl<V, R, I, O, VW, RW> ContainsElement for View<'_, V, R, I, O, VW, RW>
155where
156    V: LayoutIndex,
157    R: LayoutIndex,
158    I: LayoutIndex,
159    O: LayoutWord<Index = I>,
160    VW: LayoutWord<Index = V>,
161    RW: LayoutWord<Index = R>,
162{
163    fn contains_element(&self, element: BcsrVertexId<V>) -> bool {
164        index_to_usize_validated(element.get()) < self.counts().vertex_count
165    }
166}
167
168impl<V, R, I, O, VW, RW> ContainsRelation for View<'_, V, R, I, O, VW, RW>
169where
170    V: LayoutIndex,
171    R: LayoutIndex,
172    I: LayoutIndex,
173    O: LayoutWord<Index = I>,
174    VW: LayoutWord<Index = V>,
175    RW: LayoutWord<Index = R>,
176{
177    fn contains_relation(&self, relation: BcsrHyperedgeId<R>) -> bool {
178        index_to_usize_validated(relation.get()) < self.counts().hyperedge_count
179    }
180}
181
182impl<V, R, I, O, VW, RW> ContainsIncidence for View<'_, V, R, I, O, VW, RW>
183where
184    V: LayoutIndex,
185    R: LayoutIndex,
186    I: LayoutIndex,
187    O: LayoutWord<Index = I>,
188    VW: LayoutWord<Index = V>,
189    RW: LayoutWord<Index = R>,
190{
191    fn contains_incidence(&self, incidence: BcsrParticipantId<I>) -> bool {
192        index_to_usize_validated(incidence.get()) < self.counts().total_incidences
193    }
194}
195
196impl<V, R, I, O, VW, RW> IncidenceElement for View<'_, V, R, I, O, VW, RW>
197where
198    V: LayoutIndex,
199    R: LayoutIndex,
200    I: LayoutIndex,
201    O: LayoutWord<Index = I>,
202    VW: LayoutWord<Index = V>,
203    RW: LayoutWord<Index = R>,
204{
205    fn incidence_element(&self, incidence: BcsrParticipantId<I>) -> BcsrVertexId<V> {
206        let incidence_index = index_to_usize_validated(incidence.get());
207        let counts = self.counts();
208        let sections = self.sections();
209        if incidence_index < counts.p_outgoing {
210            BcsrVertexId::new(sections.head_participants[incidence_index].get())
211        } else {
212            let position = incidence_index - counts.p_outgoing;
213            BcsrVertexId::new(sections.tail_participants[position].get())
214        }
215    }
216}
217
218impl<V, R, I, O, VW, RW> IncidenceRelation for View<'_, V, R, I, O, VW, RW>
219where
220    V: LayoutIndex,
221    R: LayoutIndex,
222    I: LayoutIndex,
223    O: LayoutWord<Index = I>,
224    VW: LayoutWord<Index = V>,
225    RW: LayoutWord<Index = R>,
226{
227    fn incidence_relation(&self, incidence: BcsrParticipantId<I>) -> BcsrHyperedgeId<R> {
228        let incidence_index = index_to_usize_validated(incidence.get());
229        let counts = self.counts();
230        let sections = self.sections();
231        if incidence_index < counts.p_outgoing {
232            BcsrHyperedgeId::new(locate_owning_bucket(sections.head_offsets, incidence_index))
233        } else {
234            let position = incidence_index - counts.p_outgoing;
235            BcsrHyperedgeId::new(locate_owning_bucket(sections.tail_offsets, position))
236        }
237    }
238}
239
240impl<V, R, I, O, VW, RW> IncidenceRole for View<'_, V, R, I, O, VW, RW>
241where
242    V: LayoutIndex,
243    R: LayoutIndex,
244    I: LayoutIndex,
245    O: LayoutWord<Index = I>,
246    VW: LayoutWord<Index = V>,
247    RW: LayoutWord<Index = R>,
248{
249    fn incidence_role(&self, incidence: BcsrParticipantId<I>) -> BcsrRole {
250        if index_to_usize_validated(incidence.get()) < self.counts().p_outgoing {
251            BcsrRole::Head
252        } else {
253            BcsrRole::Tail
254        }
255    }
256}
257
258impl<V, R, I, O, VW, RW> RelationIncidences for View<'_, V, R, I, O, VW, RW>
259where
260    V: LayoutIndex,
261    R: LayoutIndex,
262    I: LayoutIndex,
263    O: LayoutWord<Index = I>,
264    VW: LayoutWord<Index = V>,
265    RW: LayoutWord<Index = R>,
266{
267    type Incidences<'view>
268        = BcsrChainedRelationIncidences<I>
269    where
270        Self: 'view;
271
272    fn relation_incidences(&self, relation: BcsrHyperedgeId<R>) -> Self::Incidences<'_> {
273        let sections = self.sections();
274        let p_outgoing = self.counts().p_outgoing;
275        let h_index = index_to_usize_validated(relation.get());
276        let head_start = index_to_usize_validated(sections.head_offsets[h_index].get());
277        let head_end = index_to_usize_validated(sections.head_offsets[h_index + 1].get());
278        let tail_start = index_to_usize_validated(sections.tail_offsets[h_index].get());
279        let tail_end = index_to_usize_validated(sections.tail_offsets[h_index + 1].get());
280        BcsrParticipantSlice::new(head_start, head_end, 0)
281            .chain(BcsrParticipantSlice::new(tail_start, tail_end, p_outgoing))
282    }
283}
284
285impl<V, R, I, O, VW, RW> ElementIncidences for View<'_, V, R, I, O, VW, RW>
286where
287    V: LayoutIndex,
288    R: LayoutIndex,
289    I: LayoutIndex,
290    O: LayoutWord<Index = I>,
291    VW: LayoutWord<Index = V>,
292    RW: LayoutWord<Index = R>,
293{
294    type Incidences<'view>
295        = BcsrElementIncidences<'view, O, VW, RW>
296    where
297        Self: 'view;
298
299    fn element_incidences(&self, element: BcsrVertexId<V>) -> Self::Incidences<'_> {
300        let sections = self.sections();
301        let counts = self.counts();
302        let v_index = index_to_usize_validated(element.get());
303        let outgoing = vertex_bucket(
304            sections.vertex_outgoing_offsets,
305            sections.vertex_outgoing_hyperedges,
306            v_index,
307        );
308        let incoming = vertex_bucket(
309            sections.vertex_incoming_offsets,
310            sections.vertex_incoming_hyperedges,
311            v_index,
312        );
313        BcsrElementIncidences::new(v_index, counts.p_outgoing, outgoing, incoming, sections)
314    }
315}
316
317impl<V, R, I, O, VW, RW> RelationIncidenceCount for View<'_, V, R, I, O, VW, RW>
318where
319    V: LayoutIndex,
320    R: LayoutIndex,
321    I: LayoutIndex,
322    O: LayoutWord<Index = I>,
323    VW: LayoutWord<Index = V>,
324    RW: LayoutWord<Index = R>,
325{
326    fn relation_incidence_count(&self, relation: BcsrHyperedgeId<R>) -> usize {
327        let sections = self.sections();
328        let h_index = index_to_usize_validated(relation.get());
329        let head_size = index_to_usize_validated(sections.head_offsets[h_index + 1].get())
330            - index_to_usize_validated(sections.head_offsets[h_index].get());
331        let tail_size = index_to_usize_validated(sections.tail_offsets[h_index + 1].get())
332            - index_to_usize_validated(sections.tail_offsets[h_index].get());
333        head_size + tail_size
334    }
335}
336
337impl<V, R, I, O, VW, RW> ElementIncidenceCount for View<'_, V, R, I, O, VW, RW>
338where
339    V: LayoutIndex,
340    R: LayoutIndex,
341    I: LayoutIndex,
342    O: LayoutWord<Index = I>,
343    VW: LayoutWord<Index = V>,
344    RW: LayoutWord<Index = R>,
345{
346    fn element_incidence_count(&self, element: BcsrVertexId<V>) -> usize {
347        let sections = self.sections();
348        let v_index = index_to_usize_validated(element.get());
349        let out_size =
350            index_to_usize_validated(sections.vertex_outgoing_offsets[v_index + 1].get())
351                - index_to_usize_validated(sections.vertex_outgoing_offsets[v_index].get());
352        let in_size = index_to_usize_validated(sections.vertex_incoming_offsets[v_index + 1].get())
353            - index_to_usize_validated(sections.vertex_incoming_offsets[v_index].get());
354        out_size + in_size
355    }
356}
357
358// `HyperedgeParticipantCount` and `IncidentHyperedgeCount` are provided for free
359// by the blanket impls in `oxgraph-hyper` over `RelationIncidenceCount` /
360// `ElementIncidenceCount`, which this view implements above.
361
362impl<V, R, I, O, VW, RW> HyperedgeParticipants for View<'_, V, R, I, O, VW, RW>
363where
364    V: LayoutIndex,
365    R: LayoutIndex,
366    I: LayoutIndex,
367    O: LayoutWord<Index = I>,
368    VW: LayoutWord<Index = V>,
369    RW: LayoutWord<Index = R>,
370{
371    type Participants<'view>
372        = BcsrChainedParticipants<'view, VW>
373    where
374        Self: 'view;
375
376    fn hyperedge_participants(&self, hyperedge: BcsrHyperedgeId<R>) -> Self::Participants<'_> {
377        let sections = self.sections();
378        let h_index = index_to_usize_validated(hyperedge.get());
379        let head = vertex_bucket(sections.head_offsets, sections.head_participants, h_index);
380        let tail = vertex_bucket(sections.tail_offsets, sections.tail_participants, h_index);
381        BcsrVertexSlice::new(head).chain(BcsrVertexSlice::new(tail))
382    }
383}
384
385impl<V, R, I, O, VW, RW> IncidentHyperedges for View<'_, V, R, I, O, VW, RW>
386where
387    V: LayoutIndex,
388    R: LayoutIndex,
389    I: LayoutIndex,
390    O: LayoutWord<Index = I>,
391    VW: LayoutWord<Index = V>,
392    RW: LayoutWord<Index = R>,
393{
394    type IncidentHyperedges<'view>
395        = BcsrChainedHyperedges<'view, RW>
396    where
397        Self: 'view;
398
399    fn incident_hyperedges(&self, vertex: BcsrVertexId<V>) -> Self::IncidentHyperedges<'_> {
400        let sections = self.sections();
401        let v_index = index_to_usize_validated(vertex.get());
402        let outgoing = vertex_bucket(
403            sections.vertex_outgoing_offsets,
404            sections.vertex_outgoing_hyperedges,
405            v_index,
406        );
407        let incoming = vertex_bucket(
408            sections.vertex_incoming_offsets,
409            sections.vertex_incoming_hyperedges,
410            v_index,
411        );
412        BcsrHyperedgeSlice::new(outgoing).chain(BcsrHyperedgeSlice::new(incoming))
413    }
414}
415
416impl<V, R, I, O, VW, RW> DirectedHyperedgeParticipants for View<'_, V, R, I, O, VW, RW>
417where
418    V: LayoutIndex,
419    R: LayoutIndex,
420    I: LayoutIndex,
421    O: LayoutWord<Index = I>,
422    VW: LayoutWord<Index = V>,
423    RW: LayoutWord<Index = R>,
424{
425    type SourceParticipants<'view>
426        = BcsrVertexSlice<'view, VW>
427    where
428        Self: 'view;
429
430    type TargetParticipants<'view>
431        = BcsrVertexSlice<'view, VW>
432    where
433        Self: 'view;
434
435    fn source_participants(&self, hyperedge: BcsrHyperedgeId<R>) -> Self::SourceParticipants<'_> {
436        let sections = self.sections();
437        let h_index = index_to_usize_validated(hyperedge.get());
438        let head = vertex_bucket(sections.head_offsets, sections.head_participants, h_index);
439        BcsrVertexSlice::new(head)
440    }
441
442    fn target_participants(&self, hyperedge: BcsrHyperedgeId<R>) -> Self::TargetParticipants<'_> {
443        let sections = self.sections();
444        let h_index = index_to_usize_validated(hyperedge.get());
445        let tail = vertex_bucket(sections.tail_offsets, sections.tail_participants, h_index);
446        BcsrVertexSlice::new(tail)
447    }
448}
449
450impl<V, R, I, O, VW, RW> DirectedHyperedgeIncidences for View<'_, V, R, I, O, VW, RW>
451where
452    V: LayoutIndex,
453    R: LayoutIndex,
454    I: LayoutIndex,
455    O: LayoutWord<Index = I>,
456    VW: LayoutWord<Index = V>,
457    RW: LayoutWord<Index = R>,
458{
459    type SourceIncidences<'view>
460        = BcsrParticipantSlice<I>
461    where
462        Self: 'view;
463
464    type TargetIncidences<'view>
465        = BcsrParticipantSlice<I>
466    where
467        Self: 'view;
468
469    fn source_incidences(&self, hyperedge: BcsrHyperedgeId<R>) -> Self::SourceIncidences<'_> {
470        let sections = self.sections();
471        let h_index = index_to_usize_validated(hyperedge.get());
472        let head_start = index_to_usize_validated(sections.head_offsets[h_index].get());
473        let head_end = index_to_usize_validated(sections.head_offsets[h_index + 1].get());
474        BcsrParticipantSlice::new(head_start, head_end, 0)
475    }
476
477    fn target_incidences(&self, hyperedge: BcsrHyperedgeId<R>) -> Self::TargetIncidences<'_> {
478        let sections = self.sections();
479        let h_index = index_to_usize_validated(hyperedge.get());
480        let tail_start = index_to_usize_validated(sections.tail_offsets[h_index].get());
481        let tail_end = index_to_usize_validated(sections.tail_offsets[h_index + 1].get());
482        BcsrParticipantSlice::new(tail_start, tail_end, self.counts().p_outgoing)
483    }
484}
485
486impl<V, R, I, O, VW, RW> DirectedVertexHyperedges for View<'_, V, R, I, O, VW, RW>
487where
488    V: LayoutIndex,
489    R: LayoutIndex,
490    I: LayoutIndex,
491    O: LayoutWord<Index = I>,
492    VW: LayoutWord<Index = V>,
493    RW: LayoutWord<Index = R>,
494{
495    type OutgoingHyperedges<'view>
496        = BcsrHyperedgeSlice<'view, RW>
497    where
498        Self: 'view;
499
500    type IncomingHyperedges<'view>
501        = BcsrHyperedgeSlice<'view, RW>
502    where
503        Self: 'view;
504
505    fn outgoing_hyperedges(&self, vertex: BcsrVertexId<V>) -> Self::OutgoingHyperedges<'_> {
506        let sections = self.sections();
507        let v_index = index_to_usize_validated(vertex.get());
508        let outgoing = vertex_bucket(
509            sections.vertex_outgoing_offsets,
510            sections.vertex_outgoing_hyperedges,
511            v_index,
512        );
513        BcsrHyperedgeSlice::new(outgoing)
514    }
515
516    fn incoming_hyperedges(&self, vertex: BcsrVertexId<V>) -> Self::IncomingHyperedges<'_> {
517        let sections = self.sections();
518        let v_index = index_to_usize_validated(vertex.get());
519        let incoming = vertex_bucket(
520            sections.vertex_incoming_offsets,
521            sections.vertex_incoming_hyperedges,
522            v_index,
523        );
524        BcsrHyperedgeSlice::new(incoming)
525    }
526}
527
528impl<V, R, I, O, VW, RW> ElementSuccessors for View<'_, V, R, I, O, VW, RW>
529where
530    V: LayoutIndex,
531    R: LayoutIndex,
532    I: LayoutIndex,
533    O: LayoutWord<Index = I>,
534    VW: LayoutWord<Index = V>,
535    RW: LayoutWord<Index = R>,
536{
537    type Successors<'view>
538        = BcsrSuccessorVertices<'view, RW, O, VW>
539    where
540        Self: 'view;
541
542    fn element_successors(&self, vertex: BcsrVertexId<V>) -> Self::Successors<'_> {
543        let sections = self.sections();
544        let v_index = index_to_usize_validated(vertex.get());
545        let outgoing = vertex_bucket(
546            sections.vertex_outgoing_offsets,
547            sections.vertex_outgoing_hyperedges,
548            v_index,
549        );
550        BcsrSuccessorVertices::new(outgoing, sections.tail_offsets, sections.tail_participants)
551    }
552}
553
554impl<V, R, I, O, VW, RW> ElementPredecessors for View<'_, V, R, I, O, VW, RW>
555where
556    V: LayoutIndex,
557    R: LayoutIndex,
558    I: LayoutIndex,
559    O: LayoutWord<Index = I>,
560    VW: LayoutWord<Index = V>,
561    RW: LayoutWord<Index = R>,
562{
563    type Predecessors<'view>
564        = BcsrPredecessorVertices<'view, RW, O, VW>
565    where
566        Self: 'view;
567
568    fn element_predecessors(&self, vertex: BcsrVertexId<V>) -> Self::Predecessors<'_> {
569        let sections = self.sections();
570        let v_index = index_to_usize_validated(vertex.get());
571        let incoming = vertex_bucket(
572            sections.vertex_incoming_offsets,
573            sections.vertex_incoming_hyperedges,
574            v_index,
575        );
576        BcsrPredecessorVertices::new(incoming, sections.head_offsets, sections.head_participants)
577    }
578}
579
580/// Returns the slice `values[offsets[index].get()..offsets[index + 1].get()]`.
581fn vertex_bucket<'view, OffsetWord, ValueWord>(
582    offsets: &'view [OffsetWord],
583    values: &'view [ValueWord],
584    index: usize,
585) -> &'view [ValueWord]
586where
587    OffsetWord: LayoutWord,
588{
589    let start = index_to_usize_validated(offsets[index].get());
590    let end = index_to_usize_validated(offsets[index + 1].get());
591    &values[start..end]
592}
593
594/// Binary search over an offset array, returning the bucket index that owns
595/// absolute position `target`.
596fn locate_owning_bucket<OffsetWord, RelationIndex>(
597    offsets: &[OffsetWord],
598    target: usize,
599) -> RelationIndex
600where
601    OffsetWord: LayoutWord,
602    RelationIndex: LayoutIndex,
603{
604    let mut low = 0_usize;
605    let mut high = offsets.len() - 1;
606    while low + 1 < high {
607        let mid = low + (high - low) / 2;
608        if index_to_usize_validated(offsets[mid].get()) <= target {
609            low = mid;
610        } else {
611            high = mid;
612        }
613    }
614    usize_to_index_validated(low)
615}
oxgraph_hyper_bcsr/internal/traits.rs

oxgraph_hyper_bcsr/internal/
traits.rs
