swh_graph/views/
subgraph.rs

1// Copyright (C) 2023-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
6use std::collections::HashMap;
7use std::path::Path;
8
9use anyhow::{anyhow, Result};
10
11use crate::arc_iterators::FlattenedSuccessorsIterator;
12use crate::graph::*;
13use crate::properties;
14use crate::{NodeConstraint, NodeType};
15
16macro_rules! make_filtered_arcs_iterator {
17    ($name:ident, $inner:ident, $( $next:tt )*) => {
18        pub struct $name<
19            'a,
20            $inner: Iterator<Item = NodeId> + 'a,
21            NodeFilter: Fn(NodeId) -> bool,
22            ArcFilter: Fn(NodeId, NodeId) -> bool,
23        > {
24            inner: $inner,
25            node: NodeId,
26            node_filter: &'a NodeFilter,
27            arc_filter: &'a ArcFilter,
28        }
29
30        impl<
31            'a,
32            $inner: Iterator<Item = NodeId> + 'a,
33            NodeFilter: Fn(NodeId) -> bool,
34            ArcFilter: Fn(NodeId, NodeId) -> bool,
35        > Iterator for $name<'a, $inner, NodeFilter, ArcFilter> {
36            type Item = $inner::Item;
37
38            $( $next )*
39        }
40    }
41}
42
43make_filtered_arcs_iterator! {
44    FilteredSuccessors,
45    Successors,
46    fn next(&mut self) -> Option<Self::Item> {
47        if !(self.node_filter)(self.node) {
48            return None;
49        }
50        for dst in self.inner.by_ref() {
51            if (self.node_filter)(dst) && (self.arc_filter)(self.node, dst) {
52                return Some(dst)
53            }
54        }
55        None
56    }
57}
58make_filtered_arcs_iterator! {
59    FilteredPredecessors,
60    Predecessors,
61    fn next(&mut self) -> Option<Self::Item> {
62        if !(self.node_filter)(self.node) {
63            return None;
64        }
65        for src in self.inner.by_ref() {
66            if (self.node_filter)(src) && (self.arc_filter)(src, self.node) {
67                return Some(src)
68            }
69        }
70        None
71    }
72}
73
74macro_rules! make_filtered_labeled_arcs_iterator {
75    ($name:ident, $inner:ident, $( $next:tt )*) => {
76        pub struct $name<
77            'a,
78            Labels,
79            $inner: Iterator<Item = (NodeId, Labels)> + 'a,
80            NodeFilter: Fn(NodeId) -> bool,
81            ArcFilter: Fn(NodeId, NodeId) -> bool,
82        > {
83            inner: $inner,
84            node: NodeId,
85            node_filter: &'a NodeFilter,
86            arc_filter: &'a ArcFilter,
87        }
88
89        impl<
90            'a,
91            Labels,
92            $inner: Iterator<Item = (NodeId, Labels)> + 'a,
93            NodeFilter: Fn(NodeId) -> bool,
94            ArcFilter: Fn(NodeId, NodeId) -> bool,
95        > Iterator for $name<'a, Labels, $inner, NodeFilter, ArcFilter> {
96            type Item = $inner::Item;
97
98            $( $next )*
99        }
100
101        impl<
102            'a,
103            Labels: IntoIterator,
104            $inner: Iterator<Item = (NodeId, Labels)> + 'a,
105            NodeFilter: Fn(NodeId) -> bool,
106            ArcFilter: Fn(NodeId, NodeId) -> bool,
107        > IntoFlattenedLabeledArcsIterator<<Labels as IntoIterator>::Item> for $name<'a, Labels, $inner, NodeFilter, ArcFilter> {
108            type Flattened = FlattenedSuccessorsIterator<Self>;
109
110            fn flatten_labels(self) -> Self::Flattened {
111                FlattenedSuccessorsIterator::new(self)
112            }
113        }
114    }
115}
116
117make_filtered_labeled_arcs_iterator! {
118    FilteredLabeledSuccessors,
119    LabeledSuccessors,
120    fn next(&mut self) -> Option<Self::Item> {
121        if !(self.node_filter)(self.node) {
122            return None;
123        }
124        for (dst, label) in self.inner.by_ref() {
125            if (self.node_filter)(dst) && (self.arc_filter)(self.node, dst) {
126                return Some((dst, label))
127            }
128        }
129        None
130    }
131}
132make_filtered_labeled_arcs_iterator! {
133    FilteredLabeledPredecessors,
134    LabeledPredecessors,
135    fn next(&mut self) -> Option<Self::Item> {
136        if !(self.node_filter)(self.node) {
137            return None;
138        }
139        for (src, label) in self.inner.by_ref() {
140            if (self.node_filter)(src) && (self.arc_filter)(src, self.node) {
141                return Some((src, label))
142            }
143        }
144        None
145    }
146}
147
148/// A view over [`SwhGraph`] and related traits, that filters out some nodes and arcs
149/// based on arbitrary closures.
150pub struct Subgraph<G: SwhGraph, NodeFilter: Fn(usize) -> bool, ArcFilter: Fn(usize, usize) -> bool>
151{
152    pub graph: G,
153    pub node_filter: NodeFilter,
154    pub arc_filter: ArcFilter,
155    pub num_nodes_by_type: Option<HashMap<NodeType, usize>>,
156    pub num_arcs_by_type: Option<HashMap<(NodeType, NodeType), usize>>,
157}
158
159impl<G: SwhGraph, NodeFilter: Fn(usize) -> bool> Subgraph<G, NodeFilter, fn(usize, usize) -> bool> {
160    /// Create a [Subgraph] keeping only nodes matching a given node filter function.
161    ///
162    /// Shorthand for `Subgraph { graph, node_filter, arc_filter: |_src, _dst| true }`
163    pub fn with_node_filter(
164        graph: G,
165        node_filter: NodeFilter,
166    ) -> Subgraph<G, NodeFilter, fn(usize, usize) -> bool> {
167        Subgraph {
168            graph,
169            node_filter,
170            arc_filter: |_src, _dst| true,
171            num_nodes_by_type: None,
172            num_arcs_by_type: None,
173        }
174    }
175}
176
177impl<G: SwhGraph, ArcFilter: Fn(usize, usize) -> bool> Subgraph<G, fn(usize) -> bool, ArcFilter> {
178    /// Create a [Subgraph] keeping only arcs matching a arc filter function.
179    ///
180    /// Shorthand for `Subgraph { graph, node_filter: |_node| true, arc_filter }`
181    pub fn with_arc_filter(
182        graph: G,
183        arc_filter: ArcFilter,
184    ) -> Subgraph<G, fn(usize) -> bool, ArcFilter> {
185        Subgraph {
186            graph,
187            node_filter: |_node| true,
188            arc_filter,
189            num_nodes_by_type: None,
190            num_arcs_by_type: None,
191        }
192    }
193}
194
195impl<G> Subgraph<G, fn(usize) -> bool, fn(usize, usize) -> bool>
196where
197    G: SwhGraphWithProperties + Clone,
198    <G as SwhGraphWithProperties>::Maps: properties::Maps,
199{
200    /// Create a [Subgraph] keeping only nodes matching a given node constraint.
201    #[allow(clippy::type_complexity)]
202    pub fn with_node_constraint(
203        graph: G,
204        node_constraint: NodeConstraint,
205    ) -> Subgraph<G, impl Fn(NodeId) -> bool, fn(usize, usize) -> bool> {
206        Subgraph {
207            graph: graph.clone(),
208            num_nodes_by_type: graph.num_nodes_by_type().ok().map(|counts| {
209                counts
210                    .into_iter()
211                    .filter(|&(type_, _count)| node_constraint.matches(type_))
212                    .collect()
213            }),
214            num_arcs_by_type: graph.num_arcs_by_type().ok().map(|counts| {
215                counts
216                    .into_iter()
217                    .filter(|&((src_type, dst_type), _count)| {
218                        node_constraint.matches(src_type) && node_constraint.matches(dst_type)
219                    })
220                    .collect()
221            }),
222            node_filter: move |node| node_constraint.matches(graph.properties().node_type(node)),
223            arc_filter: |_src, _dst| true,
224        }
225    }
226}
227
228impl<G: SwhGraph, NodeFilter: Fn(usize) -> bool, ArcFilter: Fn(usize, usize) -> bool> SwhGraph
229    for Subgraph<G, NodeFilter, ArcFilter>
230{
231    fn path(&self) -> &Path {
232        self.graph.path()
233    }
234    fn is_transposed(&self) -> bool {
235        self.graph.is_transposed()
236    }
237    // Note: this return the number or nodes in the original graph, before
238    // subgraph filtering.
239    fn num_nodes(&self) -> usize {
240        self.graph.num_nodes()
241    }
242    fn has_node(&self, node_id: NodeId) -> bool {
243        (self.node_filter)(node_id)
244    }
245    // Note: this return the number or arcs in the original graph, before
246    // subgraph filtering.
247    fn num_arcs(&self) -> u64 {
248        self.graph.num_arcs()
249    }
250    fn num_nodes_by_type(&self) -> Result<HashMap<NodeType, usize>> {
251        self.num_nodes_by_type.clone().ok_or(anyhow!(
252            "num_nodes_by_type is not supported by this Subgraph (if possible, use Subgraph::with_node_constraint to build it)"
253        ))
254    }
255    fn num_arcs_by_type(&self) -> Result<HashMap<(NodeType, NodeType), usize>> {
256        self.num_arcs_by_type.clone().ok_or(anyhow!(
257            "num_arcs_by_type is not supported by this Subgraph (if possible, use Subgraph::with_node_constraint to build it)"
258        ))
259    }
260    fn has_arc(&self, src_node_id: NodeId, dst_node_id: NodeId) -> bool {
261        (self.node_filter)(src_node_id)
262            && (self.node_filter)(dst_node_id)
263            && (self.arc_filter)(src_node_id, dst_node_id)
264            && self.graph.has_arc(src_node_id, dst_node_id)
265    }
266}
267
268impl<G: SwhForwardGraph, NodeFilter: Fn(usize) -> bool, ArcFilter: Fn(usize, usize) -> bool>
269    SwhForwardGraph for Subgraph<G, NodeFilter, ArcFilter>
270{
271    type Successors<'succ>
272        = FilteredSuccessors<
273        'succ,
274        <<G as SwhForwardGraph>::Successors<'succ> as IntoIterator>::IntoIter,
275        NodeFilter,
276        ArcFilter,
277    >
278    where
279        Self: 'succ;
280
281    fn successors(&self, node_id: NodeId) -> Self::Successors<'_> {
282        FilteredSuccessors {
283            inner: self.graph.successors(node_id).into_iter(),
284            node: node_id,
285            node_filter: &self.node_filter,
286            arc_filter: &self.arc_filter,
287        }
288    }
289    fn outdegree(&self, node_id: NodeId) -> usize {
290        self.successors(node_id).count()
291    }
292}
293
294impl<G: SwhBackwardGraph, NodeFilter: Fn(usize) -> bool, ArcFilter: Fn(usize, usize) -> bool>
295    SwhBackwardGraph for Subgraph<G, NodeFilter, ArcFilter>
296{
297    type Predecessors<'succ>
298        = FilteredPredecessors<
299        'succ,
300        <<G as SwhBackwardGraph>::Predecessors<'succ> as IntoIterator>::IntoIter,
301        NodeFilter,
302        ArcFilter,
303    >
304    where
305        Self: 'succ;
306
307    fn predecessors(&self, node_id: NodeId) -> Self::Predecessors<'_> {
308        FilteredPredecessors {
309            inner: self.graph.predecessors(node_id).into_iter(),
310            node: node_id,
311            node_filter: &self.node_filter,
312            arc_filter: &self.arc_filter,
313        }
314    }
315    fn indegree(&self, node_id: NodeId) -> usize {
316        self.predecessors(node_id).count()
317    }
318}
319
320impl<
321        G: SwhLabeledForwardGraph,
322        NodeFilter: Fn(usize) -> bool,
323        ArcFilter: Fn(usize, usize) -> bool,
324    > SwhLabeledForwardGraph for Subgraph<G, NodeFilter, ArcFilter>
325{
326    type LabeledArcs<'arc>
327        = <G as SwhLabeledForwardGraph>::LabeledArcs<'arc>
328    where
329        Self: 'arc;
330    type LabeledSuccessors<'node>
331        = FilteredLabeledSuccessors<
332        'node,
333        Self::LabeledArcs<'node>,
334        <<G as SwhLabeledForwardGraph>::LabeledSuccessors<'node> as IntoIterator>::IntoIter,
335        NodeFilter,
336        ArcFilter,
337    >
338    where
339        Self: 'node;
340
341    fn untyped_labeled_successors(&self, node_id: NodeId) -> Self::LabeledSuccessors<'_> {
342        FilteredLabeledSuccessors {
343            inner: self.graph.untyped_labeled_successors(node_id).into_iter(),
344            node: node_id,
345            node_filter: &self.node_filter,
346            arc_filter: &self.arc_filter,
347        }
348    }
349}
350
351impl<
352        G: SwhLabeledBackwardGraph,
353        NodeFilter: Fn(usize) -> bool,
354        ArcFilter: Fn(usize, usize) -> bool,
355    > SwhLabeledBackwardGraph for Subgraph<G, NodeFilter, ArcFilter>
356{
357    type LabeledArcs<'arc>
358        = <G as SwhLabeledBackwardGraph>::LabeledArcs<'arc>
359    where
360        Self: 'arc;
361    type LabeledPredecessors<'node>
362        = FilteredLabeledPredecessors<
363        'node,
364        Self::LabeledArcs<'node>,
365        <<G as SwhLabeledBackwardGraph>::LabeledPredecessors<'node> as IntoIterator>::IntoIter,
366        NodeFilter,
367        ArcFilter,
368    >
369    where
370        Self: 'node;
371
372    fn untyped_labeled_predecessors(&self, node_id: NodeId) -> Self::LabeledPredecessors<'_> {
373        FilteredLabeledPredecessors {
374            inner: self.graph.untyped_labeled_predecessors(node_id).into_iter(),
375            node: node_id,
376            node_filter: &self.node_filter,
377            arc_filter: &self.arc_filter,
378        }
379    }
380}
381
382impl<
383        G: SwhGraphWithProperties,
384        NodeFilter: Fn(usize) -> bool,
385        ArcFilter: Fn(usize, usize) -> bool,
386    > SwhGraphWithProperties for Subgraph<G, NodeFilter, ArcFilter>
387{
388    type Maps = <G as SwhGraphWithProperties>::Maps;
389    type Timestamps = <G as SwhGraphWithProperties>::Timestamps;
390    type Persons = <G as SwhGraphWithProperties>::Persons;
391    type Contents = <G as SwhGraphWithProperties>::Contents;
392    type Strings = <G as SwhGraphWithProperties>::Strings;
393    type LabelNames = <G as SwhGraphWithProperties>::LabelNames;
394
395    fn properties(
396        &self,
397    ) -> &properties::SwhGraphProperties<
398        Self::Maps,
399        Self::Timestamps,
400        Self::Persons,
401        Self::Contents,
402        Self::Strings,
403        Self::LabelNames,
404    > {
405        self.graph.properties()
406    }
407}
swh_graph/views/subgraph.rs

swh_graph/views/
subgraph.rs
