swh_graph/
underlying_graph.rs

1// Copyright (C) 2023-2026  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#![allow(clippy::type_complexity)]
7
8use std::path::Path;
9
10use anyhow::Result;
11use dsi_bitstream::prelude::BE;
12use webgraph::prelude::*;
13
14use crate::graph::{NodeId, UnderlyingGraph};
15
16#[cfg(not(miri))]
17type DefaultUnderlyingGraphInner = BvGraph<
18    DynCodesDecoderFactory<
19        dsi_bitstream::prelude::BE,
20        MmapHelper<u32>,
21        webgraph::graphs::bvgraph::EF,
22    >,
23>;
24// Miri does not support file-backed mmap
25#[cfg(miri)]
26type DefaultUnderlyingGraphInner = BvGraph<
27    DynCodesDecoderFactory<
28        dsi_bitstream::prelude::BE,
29        webgraph::prelude::MemoryFactory<dsi_bitstream::traits::BigEndian, std::boxed::Box<[u32]>>,
30        webgraph::graphs::bvgraph::EF,
31    >,
32>;
33
34/// Newtype for [`BvGraph`] with its type parameters set to what the SWH graph needs.
35///
36/// This indirection reduces the size of error messages.
37pub struct DefaultUnderlyingGraph(pub DefaultUnderlyingGraphInner);
38
39impl DefaultUnderlyingGraph {
40    pub fn new(basepath: impl AsRef<Path>) -> Result<DefaultUnderlyingGraph> {
41        let basepath = basepath.as_ref().to_owned();
42        let graph_load_config = BvGraph::with_basename(&basepath)
43            .endianness::<BE>()
44            .flags(MemoryFlags::TRANSPARENT_HUGE_PAGES | MemoryFlags::RANDOM_ACCESS);
45
46        // Miri does not support file-backed mmap, so we have to copy the graph to memory
47        // instead of just mapping it.
48        #[cfg(miri)]
49        let graph_load_config = graph_load_config.mode::<webgraph::graphs::bvgraph::LoadMem>();
50
51        Ok(DefaultUnderlyingGraph(graph_load_config.load()?))
52    }
53}
54
55impl SequentialLabeling for DefaultUnderlyingGraph {
56    type Label = <DefaultUnderlyingGraphInner as SequentialLabeling>::Label;
57    type Lender<'node>
58        = <DefaultUnderlyingGraphInner as SequentialLabeling>::Lender<'node>
59    where
60        Self: 'node;
61
62    // Required methods
63    #[inline(always)]
64    fn num_nodes(&self) -> usize {
65        self.0.num_nodes()
66    }
67    #[inline(always)]
68    fn iter_from(&self, from: usize) -> Self::Lender<'_> {
69        self.0.iter_from(from)
70    }
71
72    // Specialized methods
73    #[inline(always)]
74    fn num_arcs_hint(&self) -> Option<u64> {
75        self.0.num_arcs_hint()
76    }
77}
78impl SequentialGraph for DefaultUnderlyingGraph {}
79
80impl RandomAccessLabeling for DefaultUnderlyingGraph {
81    type Labels<'succ>
82        = <DefaultUnderlyingGraphInner as RandomAccessLabeling>::Labels<'succ>
83    where
84        Self: 'succ;
85
86    #[inline(always)]
87    fn num_arcs(&self) -> u64 {
88        <DefaultUnderlyingGraphInner as RandomAccessLabeling>::num_arcs(&self.0)
89    }
90
91    #[inline(always)]
92    fn labels(&self, node_id: usize) -> <Self as RandomAccessLabeling>::Labels<'_> {
93        <DefaultUnderlyingGraphInner as RandomAccessLabeling>::labels(&self.0, node_id)
94    }
95
96    #[inline(always)]
97    fn outdegree(&self, node_id: usize) -> usize {
98        <DefaultUnderlyingGraphInner as RandomAccessLabeling>::outdegree(&self.0, node_id)
99    }
100}
101
102impl RandomAccessGraph for DefaultUnderlyingGraph {}
103
104impl UnderlyingGraph for DefaultUnderlyingGraph {
105    type UnlabeledSuccessors<'succ>
106        = <DefaultUnderlyingGraphInner as RandomAccessLabeling>::Labels<'succ>
107    where
108        Self: 'succ;
109
110    #[inline(always)]
111    fn num_arcs(&self) -> u64 {
112        <DefaultUnderlyingGraphInner as UnderlyingGraph>::num_arcs(&self.0)
113    }
114    #[inline(always)]
115    fn has_arc(&self, src_node_id: NodeId, dst_node_id: NodeId) -> bool {
116        <DefaultUnderlyingGraphInner as UnderlyingGraph>::has_arc(&self.0, src_node_id, dst_node_id)
117    }
118    #[inline(always)]
119    fn unlabeled_successors(&self, node_id: NodeId) -> Self::UnlabeledSuccessors<'_> {
120        <DefaultUnderlyingGraphInner as UnderlyingGraph>::unlabeled_successors(&self.0, node_id)
121    }
122}
swh_graph/underlying_graph.rs

swh_graph/
underlying_graph.rs
