swh_graph/views/
webgraph.rs

1// Copyright (C) 2025-2026  The Software Heritage developers
2// Copyright (C) 2025  Tommaso Fontana
3// See the AUTHORS file at the top-level directory of this distribution
4// License: GNU General Public License version 3, or any later version
5// See top-level LICENSE file for more information
6
7use webgraph::prelude::*;
8
9use crate::graph::*;
10
11/// Wraps a [`SwhForwardGraph`] in order to implements webgraph's [`RandomAccessGraph`]
12///
13/// # Example
14///
15/// ```
16/// # #[cfg(not(miri))] // BfsOrder uses sysinfo (through dsi-progress-logger), which is not supported
17/// # {
18/// use std::path::PathBuf;
19///
20/// use webgraph::prelude::VecGraph;
21/// use webgraph::visits::breadth_first::{Seq, IterEvent};
22///
23/// use swh_graph::graph::{SwhForwardGraph, SwhUnidirectionalGraph};
24/// use swh_graph::views::WebgraphAdapter;
25///
26/// fn get_graph() -> impl SwhForwardGraph {
27/// #    if false {
28///     // loads this graph:
29///     // 1 --.
30///     // |    \
31///     // v     v
32///     // 0 --> 2
33///     SwhUnidirectionalGraph::new("./example").unwrap()
34/// #    ; }
35/// #    SwhUnidirectionalGraph::from_underlying_graph(
36/// #        PathBuf::new(),
37/// #        VecGraph::from_arcs(vec![(0, 2), (1, 2), (1, 0)]),
38/// #    )
39/// }
40///
41/// let graph = get_graph();
42/// let adapter = WebgraphAdapter(graph);
43///
44/// // We can now call generic webgraph algorithms on the adapter
45/// let mut order = Seq::new(&adapter);
46/// assert_eq!(order.into_iter().collect::<Vec<_>>(), vec![
47///     IterEvent {
48///         root: 0,
49///         parent: 0,
50///         node: 0,
51///         distance: 0,
52///     },
53///     IterEvent {
54///         root: 0,
55///         parent: 0,
56///         node: 2,
57///         distance: 1
58///     },
59///     IterEvent {
60///         root: 1,
61///         parent: 1,
62///         node: 1,
63///         distance: 0,
64///     }
65/// ]);
66/// # }
67/// ```
68pub struct WebgraphAdapter<G: SwhForwardGraph>(pub G);
69
70impl<G: SwhForwardGraph> SequentialLabeling for WebgraphAdapter<G> {
71    type Label = usize;
72    type Lender<'node>
73        = LenderSwhForwardGraph<'node, G>
74    where
75        Self: 'node;
76
77    #[inline(always)]
78    fn num_nodes(&self) -> usize {
79        SwhGraph::num_nodes(&self.0)
80    }
81
82    #[inline(always)]
83    fn num_arcs_hint(&self) -> Option<u64> {
84        Some(SwhGraph::num_arcs(&self.0))
85    }
86
87    #[inline(always)]
88    fn iter_from(&self, node_id: usize) -> Self::Lender<'_> {
89        LenderSwhForwardGraph {
90            graph: &self.0,
91            node_id,
92        }
93    }
94}
95
96impl<G: SwhForwardGraph> RandomAccessLabeling for WebgraphAdapter<G> {
97    type Labels<'succ>
98        = <G as SwhForwardGraph>::Successors<'succ>
99    where
100        Self: 'succ;
101
102    #[inline(always)]
103    fn num_arcs(&self) -> u64 {
104        SwhGraph::num_arcs(&self.0)
105    }
106
107    #[inline(always)]
108    fn outdegree(&self, node_id: usize) -> usize {
109        SwhForwardGraph::outdegree(&self.0, node_id)
110    }
111
112    #[inline(always)]
113    fn labels(&self, node_id: NodeId) -> Self::Labels<'_> {
114        SwhForwardGraph::successors(&self.0, node_id)
115    }
116}
117
118impl<G: SwhForwardGraph> SequentialGraph for WebgraphAdapter<G> {}
119impl<G: SwhForwardGraph> RandomAccessGraph for WebgraphAdapter<G> {}
120
121/// Manual re-implementation of [`webgraph::traits::labels::IteratorImpl`]
122pub struct LenderSwhForwardGraph<'node, G: SwhForwardGraph> {
123    graph: &'node G,
124    node_id: NodeId,
125}
126
127impl<'succ, G: SwhForwardGraph> lender::Lending<'succ> for LenderSwhForwardGraph<'_, G> {
128    type Lend = (usize, G::Successors<'succ>);
129}
130
131impl<'succ, G: SwhForwardGraph> NodeLabelsLender<'succ> for LenderSwhForwardGraph<'_, G> {
132    type Label = usize;
133    type IntoIterator = G::Successors<'succ>;
134}
135
136// SAFETY: LenderSwhForwardGraph yields nodes in order, and each node's successors
137// in the same order as the underlying iterator
138unsafe impl<G: SwhForwardGraph> SortedLender for LenderSwhForwardGraph<'_, G> where
139    for<'succ> <G as SwhForwardGraph>::Successors<'succ>: SortedLender
140{
141}
142
143impl<G: SwhForwardGraph> lender::Lender for LenderSwhForwardGraph<'_, G> {
144    // SAFETY: the lend is covariant as it contains only a usize and an iterator
145    // over usize values
146    lender::unsafe_assume_covariance!();
147
148    fn next(&mut self) -> Option<<Self as lender::Lending<'_>>::Lend> {
149        let node_id = self.node_id;
150        if node_id >= self.graph.num_nodes() {
151            return None;
152        }
153        self.node_id += 1;
154        // webgraph expects contiguous node ids, so we have return this node even if
155        // self.graph.has_arc(node_id) is false.
156        // self.graph.successors(node_id) is an empty list in that case, so this is mostly fine.
157        Some((node_id, self.graph.successors(node_id)))
158    }
159}
160
161/// Similar to [`WebgraphAdapter`] but exposes a symmetric graph, ie. with each of its
162/// `A -> B` arcs duplicated as a `B -> A` arcs
163pub struct SymmetricWebgraphAdapter<G: SwhForwardGraph + SwhBackwardGraph>(pub G);
164
165impl<G: SwhForwardGraph + SwhBackwardGraph> SequentialLabeling for SymmetricWebgraphAdapter<G>
166where
167    for<'succ> <<G as SwhForwardGraph>::Successors<'succ> as IntoIterator>::IntoIter:
168        SortedIterator,
169    for<'pred> <<G as SwhBackwardGraph>::Predecessors<'pred> as IntoIterator>::IntoIter:
170        SortedIterator,
171{
172    type Label = usize;
173    type Lender<'node>
174        = LenderSwhSymmetricGraph<'node, G>
175    where
176        Self: 'node;
177
178    #[inline(always)]
179    fn num_nodes(&self) -> usize {
180        SwhGraph::num_nodes(&self.0)
181    }
182
183    #[inline(always)]
184    fn num_arcs_hint(&self) -> Option<u64> {
185        Some(SwhGraph::num_arcs(&self.0) * 2)
186    }
187
188    #[inline(always)]
189    fn iter_from(&self, node_id: usize) -> Self::Lender<'_> {
190        LenderSwhSymmetricGraph {
191            graph: &self.0,
192            node_id,
193        }
194    }
195}
196
197impl<G: SwhForwardGraph + SwhBackwardGraph> RandomAccessLabeling for SymmetricWebgraphAdapter<G>
198where
199    for<'succ> <<G as SwhForwardGraph>::Successors<'succ> as IntoIterator>::IntoIter:
200        SortedIterator,
201    for<'pred> <<G as SwhBackwardGraph>::Predecessors<'pred> as IntoIterator>::IntoIter:
202        SortedIterator,
203{
204    type Labels<'succ>
205        = MergedSuccessorsForGraph<'succ, G>
206    where
207        Self: 'succ;
208
209    #[inline(always)]
210    fn num_arcs(&self) -> u64 {
211        SwhGraph::num_arcs(&self.0) * 2
212    }
213
214    #[inline(always)]
215    fn outdegree(&self, node_id: usize) -> usize {
216        // We can simply add them because SWH graphs are acyclic, so no node can be both
217        // a predecessor and a successor
218        SwhForwardGraph::outdegree(&self.0, node_id) + SwhBackwardGraph::indegree(&self.0, node_id)
219    }
220
221    #[inline(always)]
222    fn labels(&self, node_id: NodeId) -> Self::Labels<'_> {
223        webgraph::graphs::union_graph::Succ::new(
224            Some(<G as SwhForwardGraph>::successors(&self.0, node_id).into_iter()),
225            Some(<G as SwhBackwardGraph>::predecessors(&self.0, node_id).into_iter()),
226        )
227    }
228}
229
230impl<G: SwhForwardGraph + SwhBackwardGraph> SequentialGraph for SymmetricWebgraphAdapter<G>
231where
232    for<'succ> <<G as SwhForwardGraph>::Successors<'succ> as IntoIterator>::IntoIter:
233        SortedIterator,
234    for<'pred> <<G as SwhBackwardGraph>::Predecessors<'pred> as IntoIterator>::IntoIter:
235        SortedIterator,
236{
237}
238impl<G: SwhForwardGraph + SwhBackwardGraph> RandomAccessGraph for SymmetricWebgraphAdapter<G>
239where
240    for<'succ> <<G as SwhForwardGraph>::Successors<'succ> as IntoIterator>::IntoIter:
241        SortedIterator,
242    for<'pred> <<G as SwhBackwardGraph>::Predecessors<'pred> as IntoIterator>::IntoIter:
243        SortedIterator,
244{
245}
246
247//struct MergedSuccessors<S1, S2>(S1, S2);
248type MergedSuccessors<S1, S2> = webgraph::graphs::union_graph::Succ<S1, S2>;
249type MergedSuccessorsForGraph<'succ, G> = MergedSuccessors<
250    <<G as SwhForwardGraph>::Successors<'succ> as IntoIterator>::IntoIter,
251    <<G as SwhBackwardGraph>::Predecessors<'succ> as IntoIterator>::IntoIter,
252>;
253
254/// Manual re-implementation of [`webgraph::graphs::union_graph::Iter`]
255pub struct LenderSwhSymmetricGraph<'node, G: SwhForwardGraph + SwhBackwardGraph> {
256    graph: &'node G,
257    node_id: NodeId,
258}
259
260impl<'succ, G: SwhForwardGraph + SwhBackwardGraph> lender::Lending<'succ>
261    for LenderSwhSymmetricGraph<'_, G>
262{
263    type Lend = (usize, MergedSuccessorsForGraph<'succ, G>);
264}
265
266impl<'succ, G: SwhForwardGraph + SwhBackwardGraph> NodeLabelsLender<'succ>
267    for LenderSwhSymmetricGraph<'_, G>
268{
269    type Label = usize;
270    type IntoIterator = MergedSuccessorsForGraph<'succ, G>;
271}
272
273// SAFETY: LenderSwhForwardGraph yields nodes in order, and each node's successors
274// in the same order as the underlying iterator
275unsafe impl<G: SwhForwardGraph + SwhBackwardGraph> SortedLender for LenderSwhSymmetricGraph<'_, G>
276where
277    for<'succ> <G as SwhForwardGraph>::Successors<'succ>: SortedLender,
278    for<'succ> <G as SwhBackwardGraph>::Predecessors<'succ>: SortedLender,
279{
280}
281
282impl<G: SwhForwardGraph + SwhBackwardGraph> lender::Lender for LenderSwhSymmetricGraph<'_, G> {
283    // SAFETY: the lend is covariant as it contains only a usize and an iterator
284    // over usize values
285    lender::unsafe_assume_covariance!();
286
287    fn next(&mut self) -> Option<<Self as lender::Lending<'_>>::Lend> {
288        let node_id = self.node_id;
289        if node_id >= self.graph.num_nodes() {
290            return None;
291        }
292        self.node_id += 1;
293        // webgraph expects contiguous node ids, so we have return this node even if
294        // self.graph.has_arc(node_id) is false.
295        // self.graph.successors(node_id) is an empty list in that case, so this is mostly fine.
296        Some((
297            node_id,
298            webgraph::graphs::union_graph::Succ::new(
299                Some(<G as SwhForwardGraph>::successors(self.graph, node_id).into_iter()),
300                Some(<G as SwhBackwardGraph>::predecessors(self.graph, node_id).into_iter()),
301            ),
302        ))
303    }
304}
swh_graph/views/webgraph.rs

swh_graph/views/
webgraph.rs
