swh_graph/views/contiguous_subgraph/
iterators.rs

1// Copyright (C) 2025  The Software Heritage developers
2// See the AUTHORS file at the top-level directory of this distribution
3// License: GNU General Public License version 3, or any later version
4// See top-level LICENSE file for more information
5
6//! Implementation of [`SwhForwardGraph`], [`SwhBackwardGraph`], [`SwhLabeledForwardGraph`],
7//! and [`SwhLabeledBackwardGraph`] for [`ContiguousSubgraph`].
8
9use crate::arc_iterators::FlattenedSuccessorsIterator;
10
11use webgraph::traits::labels::SortedIterator;
12
13use super::*;
14
15macro_rules! make_filtered_arcs_iterator {
16    ($name:ident, $inner:ident, $( $next:tt )*) => {
17        pub struct $name<
18            'a,
19            $inner: Iterator<Item = NodeId> + 'a,
20            N: ContractionBackend
21        > {
22            inner: $inner,
23            contraction: &'a Contraction<N>,
24        }
25
26        impl<
27            'a,
28            $inner: Iterator<Item = NodeId> + 'a,
29            N: ContractionBackend,
30
31        > Iterator for $name<'a, $inner, N> {
32            type Item = $inner::Item;
33
34            $( $next )*
35        }
36
37        // SAFETY: filtering out elements out of an iterator preserves sortedness,
38        // and so does N (because it is monotone)
39        unsafe impl<
40            'a,
41            $inner: SortedIterator<Item = NodeId> + 'a,
42            N: MonotoneContractionBackend,
43
44        > SortedIterator for $name<'a, $inner, N> {}
45    }
46}
47
48make_filtered_arcs_iterator! {
49    TranslatedSuccessors,
50    Successors,
51    fn next(&mut self) -> Option<Self::Item> {
52        for underlying_successor in self.inner.by_ref() {
53            if let Some(self_successor) = self.contraction.node_id_from_underlying(underlying_successor) {
54                return Some(self_successor)
55            }
56        }
57        None
58    }
59}
60
61macro_rules! make_filtered_labeled_arcs_iterator {
62    ($name:ident, $inner:ident, $( $next:tt )*) => {
63        pub struct $name<
64            'a,
65            Labels,
66            $inner: Iterator<Item = (NodeId, Labels)> + 'a,
67            N: ContractionBackend
68        > {
69            inner: $inner,
70            contraction: &'a Contraction<N>,
71        }
72
73        impl<
74            'a,
75            Labels,
76            $inner: Iterator<Item = (NodeId, Labels)> + 'a,
77            N: ContractionBackend
78        > Iterator for $name<'a, Labels, $inner, N> {
79            type Item = $inner::Item;
80
81            $( $next )*
82        }
83
84        // SAFETY: filtering out elements out of an iterator preserves sortedness,
85        // and so does N (because it is monotone).
86        // 'Labels' itself does not need to be sorted because we only implement
87        // SortedIterator on the outer iterator, not in the inner one.
88        unsafe impl<
89            'a,
90            Labels,
91            $inner: SortedIterator<Item = (NodeId, Labels)> + 'a,
92            N: MonotoneContractionBackend
93        > SortedIterator for $name<'a, Labels, $inner, N> {}
94
95        impl<
96            'a,
97            Labels: IntoIterator,
98            $inner: Iterator<Item = (NodeId, Labels)> + 'a,
99            N: ContractionBackend
100        > IntoFlattenedLabeledArcsIterator<<Labels as IntoIterator>::Item> for $name<'a, Labels, $inner, N> {
101            type Flattened = FlattenedSuccessorsIterator<Self>;
102
103            fn flatten_labels(self) -> Self::Flattened {
104                FlattenedSuccessorsIterator::new(self)
105            }
106        }
107    }
108}
109
110make_filtered_labeled_arcs_iterator! {
111    TranslatedLabeledSuccessors,
112    LabeledSuccessors,
113    fn next(&mut self) -> Option<Self::Item> {
114        for (underlying_successor, label) in self.inner.by_ref() {
115            if let Some(self_successor) = self.contraction.node_id_from_underlying(underlying_successor) {
116                return Some((self_successor, label))
117            }
118        }
119        None
120    }
121}
122
123// Edge direction doesn't matter, so we can reuse the symmetric iterators
124type TranslatedPredecessors<'a, G, N> = TranslatedSuccessors<'a, G, N>;
125type TranslatedLabeledPredecessors<'a, Labels, G, N> =
126    TranslatedLabeledSuccessors<'a, Labels, G, N>;
127
128impl<
129        G: SwhForwardGraph,
130        N: ContractionBackend,
131        MAPS: properties::MaybeMaps,
132        TIMESTAMPS: properties::MaybeTimestamps,
133        PERSONS: properties::MaybePersons,
134        CONTENTS: properties::MaybeContents,
135        STRINGS: properties::MaybeStrings,
136        LABELNAMES: properties::MaybeLabelNames,
137    > SwhForwardGraph
138    for ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, PERSONS, CONTENTS, STRINGS, LABELNAMES>
139{
140    type Successors<'succ>
141        = TranslatedSuccessors<
142        'succ,
143        <<G as SwhForwardGraph>::Successors<'succ> as IntoIterator>::IntoIter,
144        N,
145    >
146    where
147        Self: 'succ;
148
149    fn successors(&self, node_id: NodeId) -> Self::Successors<'_> {
150        TranslatedSuccessors {
151            inner: self
152                .inner
153                .underlying_graph
154                .successors(self.inner.contraction.underlying_node_id(node_id))
155                .into_iter(),
156            contraction: &self.inner.contraction,
157        }
158    }
159    fn outdegree(&self, node_id: NodeId) -> usize {
160        self.successors(node_id).count()
161    }
162}
163
164impl<
165        G: SwhBackwardGraph,
166        N: ContractionBackend,
167        MAPS: properties::MaybeMaps,
168        TIMESTAMPS: properties::MaybeTimestamps,
169        PERSONS: properties::MaybePersons,
170        CONTENTS: properties::MaybeContents,
171        STRINGS: properties::MaybeStrings,
172        LABELNAMES: properties::MaybeLabelNames,
173    > SwhBackwardGraph
174    for ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, PERSONS, CONTENTS, STRINGS, LABELNAMES>
175{
176    type Predecessors<'succ>
177        = TranslatedPredecessors<
178        'succ,
179        <<G as SwhBackwardGraph>::Predecessors<'succ> as IntoIterator>::IntoIter,
180        N,
181    >
182    where
183        Self: 'succ;
184
185    fn predecessors(&self, node_id: NodeId) -> Self::Predecessors<'_> {
186        TranslatedPredecessors {
187            inner: self
188                .inner
189                .underlying_graph
190                .predecessors(self.inner.contraction.underlying_node_id(node_id))
191                .into_iter(),
192            contraction: &self.inner.contraction,
193        }
194    }
195    fn indegree(&self, node_id: NodeId) -> usize {
196        self.predecessors(node_id).count()
197    }
198}
199
200impl<
201        G: SwhLabeledForwardGraph,
202        N: ContractionBackend,
203        MAPS: properties::MaybeMaps,
204        TIMESTAMPS: properties::MaybeTimestamps,
205        PERSONS: properties::MaybePersons,
206        CONTENTS: properties::MaybeContents,
207        STRINGS: properties::MaybeStrings,
208        LABELNAMES: properties::MaybeLabelNames,
209    > SwhLabeledForwardGraph
210    for ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, PERSONS, CONTENTS, STRINGS, LABELNAMES>
211{
212    type LabeledArcs<'arc>
213        = <G as SwhLabeledForwardGraph>::LabeledArcs<'arc>
214    where
215        Self: 'arc;
216    type LabeledSuccessors<'node>
217        = TranslatedLabeledSuccessors<
218        'node,
219        Self::LabeledArcs<'node>,
220        <<G as SwhLabeledForwardGraph>::LabeledSuccessors<'node> as IntoIterator>::IntoIter,
221        N,
222    >
223    where
224        Self: 'node;
225
226    fn untyped_labeled_successors(&self, node_id: NodeId) -> Self::LabeledSuccessors<'_> {
227        TranslatedLabeledSuccessors {
228            inner: self
229                .inner
230                .underlying_graph
231                .untyped_labeled_successors(self.inner.contraction.underlying_node_id(node_id))
232                .into_iter(),
233            contraction: &self.inner.contraction,
234        }
235    }
236}
237
238impl<
239        G: SwhLabeledBackwardGraph,
240        N: ContractionBackend,
241        MAPS: properties::MaybeMaps,
242        TIMESTAMPS: properties::MaybeTimestamps,
243        PERSONS: properties::MaybePersons,
244        CONTENTS: properties::MaybeContents,
245        STRINGS: properties::MaybeStrings,
246        LABELNAMES: properties::MaybeLabelNames,
247    > SwhLabeledBackwardGraph
248    for ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, PERSONS, CONTENTS, STRINGS, LABELNAMES>
249{
250    type LabeledArcs<'arc>
251        = <G as SwhLabeledBackwardGraph>::LabeledArcs<'arc>
252    where
253        Self: 'arc;
254    type LabeledPredecessors<'node>
255        = TranslatedLabeledPredecessors<
256        'node,
257        Self::LabeledArcs<'node>,
258        <<G as SwhLabeledBackwardGraph>::LabeledPredecessors<'node> as IntoIterator>::IntoIter,
259        N,
260    >
261    where
262        Self: 'node;
263
264    fn untyped_labeled_predecessors(&self, node_id: NodeId) -> Self::LabeledPredecessors<'_> {
265        TranslatedLabeledSuccessors {
266            inner: self
267                .inner
268                .underlying_graph
269                .untyped_labeled_predecessors(self.inner.contraction.underlying_node_id(node_id))
270                .into_iter(),
271            contraction: &self.inner.contraction,
272        }
273    }
274}
swh_graph/views/contiguous_subgraph/iterators.rs

swh_graph/views/contiguous_subgraph/
iterators.rs
