swh_graph/views/
webgraph.rs

1// Copyright (C) 2025  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///
22/// use swh_graph::graph::{SwhForwardGraph, SwhUnidirectionalGraph};
23/// use swh_graph::views::WebgraphAdapter;
24///
25/// fn get_graph() -> impl SwhForwardGraph {
26/// #    if false {
27///     // loads this graph:
28///     // 1 --.
29///     // |    \
30///     // v     v
31///     // 0 --> 2
32///     SwhUnidirectionalGraph::new("./example").unwrap()
33/// #    ; }
34/// #    SwhUnidirectionalGraph::from_underlying_graph(
35/// #        PathBuf::new(),
36/// #        VecGraph::from_arcs(vec![(0, 2), (1, 2), (1, 0)]),
37/// #    )
38/// }
39///
40/// let graph = get_graph();
41/// let adapter = WebgraphAdapter(graph);
42///
43/// // We can now call generic webgraph algorithms on the adapter
44/// let order = webgraph::algo::BfsOrder::new(&adapter);
45/// assert_eq!(order.collect::<Vec<_>>(), vec![0, 2, 1]);
46/// # }
47/// ```
48pub struct WebgraphAdapter<G: SwhForwardGraph>(pub G);
49
50impl<G: SwhForwardGraph> SequentialLabeling for WebgraphAdapter<G> {
51    type Label = usize;
52    type Lender<'node>
53        = LenderSwhForwardGraph<'node, G>
54    where
55        Self: 'node;
56
57    #[inline(always)]
58    fn num_nodes(&self) -> usize {
59        SwhGraph::num_nodes(&self.0)
60    }
61
62    #[inline(always)]
63    fn num_arcs_hint(&self) -> Option<u64> {
64        Some(SwhGraph::num_arcs(&self.0))
65    }
66
67    #[inline(always)]
68    fn iter_from(&self, node_id: usize) -> Self::Lender<'_> {
69        LenderSwhForwardGraph {
70            graph: &self.0,
71            node_id,
72        }
73    }
74}
75
76impl<G: SwhForwardGraph> RandomAccessLabeling for WebgraphAdapter<G> {
77    type Labels<'succ>
78        = <G as SwhForwardGraph>::Successors<'succ>
79    where
80        Self: 'succ;
81
82    #[inline(always)]
83    fn num_arcs(&self) -> u64 {
84        SwhGraph::num_arcs(&self.0)
85    }
86
87    #[inline(always)]
88    fn outdegree(&self, node_id: usize) -> usize {
89        SwhForwardGraph::outdegree(&self.0, node_id)
90    }
91
92    #[inline(always)]
93    fn labels(&self, node_id: NodeId) -> Self::Labels<'_> {
94        SwhForwardGraph::successors(&self.0, node_id)
95    }
96}
97
98impl<G: SwhForwardGraph> SequentialGraph for WebgraphAdapter<G> {}
99impl<G: SwhForwardGraph> RandomAccessGraph for WebgraphAdapter<G> {}
100
101/// Manual re-implementation of [`webgraph::traits::labels::IteratorImpl`]
102pub struct LenderSwhForwardGraph<'node, G: SwhForwardGraph> {
103    graph: &'node G,
104    node_id: NodeId,
105}
106
107impl<'succ, G: SwhForwardGraph> lender::Lending<'succ> for LenderSwhForwardGraph<'_, G> {
108    type Lend = (usize, G::Successors<'succ>);
109}
110
111impl<'succ, G: SwhForwardGraph> NodeLabelsLender<'succ> for LenderSwhForwardGraph<'_, G> {
112    type Label = usize;
113    type IntoIterator = G::Successors<'succ>;
114}
115
116impl<G: SwhForwardGraph> lender::Lender for LenderSwhForwardGraph<'_, G> {
117    fn next(&mut self) -> Option<<Self as lender::Lending<'_>>::Lend> {
118        let node_id = self.node_id;
119        if node_id >= self.graph.num_nodes() {
120            return None;
121        }
122        self.node_id += 1;
123        // webgraph expects contiguous node ids, so we have return this node even if
124        // self.graph.has_arc(node_id) is false.
125        // self.graph.successors(node_id) is an empty list in that case, so this is mostly fine.
126        Some((node_id, self.graph.successors(node_id)))
127    }
128}
swh_graph/views/webgraph.rs

swh_graph/views/
webgraph.rs
