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

oxgraph_hyper_bcsr/internal/
traits.rs
