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 super::*;
12
13macro_rules! make_filtered_arcs_iterator {
14    ($name:ident, $inner:ident, $( $next:tt )*) => {
15        pub struct $name<
16            'a,
17            $inner: Iterator<Item = NodeId> + 'a,
18            N: ContractionBackend
19        > {
20            inner: $inner,
21            contraction: &'a Contraction<N>,
22        }
23
24        impl<
25            'a,
26            $inner: Iterator<Item = NodeId> + 'a,
27            N: ContractionBackend,
28
29        > Iterator for $name<'a, $inner, N> {
30            type Item = $inner::Item;
31
32            $( $next )*
33        }
34    }
35}
36
37make_filtered_arcs_iterator! {
38    TranslatedSuccessors,
39    Successors,
40    fn next(&mut self) -> Option<Self::Item> {
41        for underlying_successor in self.inner.by_ref() {
42            if let Some(self_successor) = self.contraction.node_id_from_underlying(underlying_successor) {
43                return Some(self_successor)
44            }
45        }
46        None
47    }
48}
49
50macro_rules! make_filtered_labeled_arcs_iterator {
51    ($name:ident, $inner:ident, $( $next:tt )*) => {
52        pub struct $name<
53            'a,
54            Labels,
55            $inner: Iterator<Item = (NodeId, Labels)> + 'a,
56            N: ContractionBackend
57        > {
58            inner: $inner,
59            contraction: &'a Contraction<N>,
60        }
61
62        impl<
63            'a,
64            Labels,
65            $inner: Iterator<Item = (NodeId, Labels)> + 'a,
66            N: ContractionBackend
67        > Iterator for $name<'a, Labels, $inner, N> {
68            type Item = $inner::Item;
69
70            $( $next )*
71        }
72
73        impl<
74            'a,
75            Labels: IntoIterator,
76            $inner: Iterator<Item = (NodeId, Labels)> + 'a,
77            N: ContractionBackend
78        > IntoFlattenedLabeledArcsIterator<<Labels as IntoIterator>::Item> for $name<'a, Labels, $inner, N> {
79            type Flattened = FlattenedSuccessorsIterator<Self>;
80
81            fn flatten_labels(self) -> Self::Flattened {
82                FlattenedSuccessorsIterator::new(self)
83            }
84        }
85    }
86}
87
88make_filtered_labeled_arcs_iterator! {
89    TranslatedLabeledSuccessors,
90    LabeledSuccessors,
91    fn next(&mut self) -> Option<Self::Item> {
92        for (underlying_successor, label) in self.inner.by_ref() {
93            if let Some(self_successor) = self.contraction.node_id_from_underlying(underlying_successor) {
94                return Some((self_successor, label))
95            }
96        }
97        None
98    }
99}
100
101// Edge direction doesn't matter, so we can reuse the symmetric iterators
102type TranslatedPredecessors<'a, G, N> = TranslatedSuccessors<'a, G, N>;
103type TranslatedLabeledPredecessors<'a, Labels, G, N> =
104    TranslatedLabeledSuccessors<'a, Labels, G, N>;
105
106impl<
107        G: SwhForwardGraph,
108        N: ContractionBackend,
109        MAPS: properties::MaybeMaps,
110        TIMESTAMPS: properties::MaybeTimestamps,
111        PERSONS: properties::MaybePersons,
112        CONTENTS: properties::MaybeContents,
113        STRINGS: properties::MaybeStrings,
114        LABELNAMES: properties::MaybeLabelNames,
115    > SwhForwardGraph
116    for ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, PERSONS, CONTENTS, STRINGS, LABELNAMES>
117{
118    type Successors<'succ>
119        = TranslatedSuccessors<
120        'succ,
121        <<G as SwhForwardGraph>::Successors<'succ> as IntoIterator>::IntoIter,
122        N,
123    >
124    where
125        Self: 'succ;
126
127    fn successors(&self, node_id: NodeId) -> Self::Successors<'_> {
128        TranslatedSuccessors {
129            inner: self
130                .inner
131                .underlying_graph
132                .successors(self.inner.contraction.underlying_node_id(node_id))
133                .into_iter(),
134            contraction: &self.inner.contraction,
135        }
136    }
137    fn outdegree(&self, node_id: NodeId) -> usize {
138        self.successors(node_id).count()
139    }
140}
141
142impl<
143        G: SwhBackwardGraph,
144        N: ContractionBackend,
145        MAPS: properties::MaybeMaps,
146        TIMESTAMPS: properties::MaybeTimestamps,
147        PERSONS: properties::MaybePersons,
148        CONTENTS: properties::MaybeContents,
149        STRINGS: properties::MaybeStrings,
150        LABELNAMES: properties::MaybeLabelNames,
151    > SwhBackwardGraph
152    for ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, PERSONS, CONTENTS, STRINGS, LABELNAMES>
153{
154    type Predecessors<'succ>
155        = TranslatedPredecessors<
156        'succ,
157        <<G as SwhBackwardGraph>::Predecessors<'succ> as IntoIterator>::IntoIter,
158        N,
159    >
160    where
161        Self: 'succ;
162
163    fn predecessors(&self, node_id: NodeId) -> Self::Predecessors<'_> {
164        TranslatedPredecessors {
165            inner: self
166                .inner
167                .underlying_graph
168                .predecessors(self.inner.contraction.underlying_node_id(node_id))
169                .into_iter(),
170            contraction: &self.inner.contraction,
171        }
172    }
173    fn indegree(&self, node_id: NodeId) -> usize {
174        self.predecessors(node_id).count()
175    }
176}
177
178impl<
179        G: SwhLabeledForwardGraph,
180        N: ContractionBackend,
181        MAPS: properties::MaybeMaps,
182        TIMESTAMPS: properties::MaybeTimestamps,
183        PERSONS: properties::MaybePersons,
184        CONTENTS: properties::MaybeContents,
185        STRINGS: properties::MaybeStrings,
186        LABELNAMES: properties::MaybeLabelNames,
187    > SwhLabeledForwardGraph
188    for ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, PERSONS, CONTENTS, STRINGS, LABELNAMES>
189{
190    type LabeledArcs<'arc>
191        = <G as SwhLabeledForwardGraph>::LabeledArcs<'arc>
192    where
193        Self: 'arc;
194    type LabeledSuccessors<'node>
195        = TranslatedLabeledSuccessors<
196        'node,
197        Self::LabeledArcs<'node>,
198        <<G as SwhLabeledForwardGraph>::LabeledSuccessors<'node> as IntoIterator>::IntoIter,
199        N,
200    >
201    where
202        Self: 'node;
203
204    fn untyped_labeled_successors(&self, node_id: NodeId) -> Self::LabeledSuccessors<'_> {
205        TranslatedLabeledSuccessors {
206            inner: self
207                .inner
208                .underlying_graph
209                .untyped_labeled_successors(self.inner.contraction.underlying_node_id(node_id))
210                .into_iter(),
211            contraction: &self.inner.contraction,
212        }
213    }
214}
215
216impl<
217        G: SwhLabeledBackwardGraph,
218        N: ContractionBackend,
219        MAPS: properties::MaybeMaps,
220        TIMESTAMPS: properties::MaybeTimestamps,
221        PERSONS: properties::MaybePersons,
222        CONTENTS: properties::MaybeContents,
223        STRINGS: properties::MaybeStrings,
224        LABELNAMES: properties::MaybeLabelNames,
225    > SwhLabeledBackwardGraph
226    for ContiguousSubgraph<G, N, MAPS, TIMESTAMPS, PERSONS, CONTENTS, STRINGS, LABELNAMES>
227{
228    type LabeledArcs<'arc>
229        = <G as SwhLabeledBackwardGraph>::LabeledArcs<'arc>
230    where
231        Self: 'arc;
232    type LabeledPredecessors<'node>
233        = TranslatedLabeledPredecessors<
234        'node,
235        Self::LabeledArcs<'node>,
236        <<G as SwhLabeledBackwardGraph>::LabeledPredecessors<'node> as IntoIterator>::IntoIter,
237        N,
238    >
239    where
240        Self: 'node;
241
242    fn untyped_labeled_predecessors(&self, node_id: NodeId) -> Self::LabeledPredecessors<'_> {
243        TranslatedLabeledSuccessors {
244            inner: self
245                .inner
246                .underlying_graph
247                .untyped_labeled_predecessors(self.inner.contraction.underlying_node_id(node_id))
248                .into_iter(),
249            contraction: &self.inner.contraction,
250        }
251    }
252}
swh_graph/views/contiguous_subgraph/iterators.rs

swh_graph/views/contiguous_subgraph/
iterators.rs
