swh_graph/
underlying_graph.rs

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

swh_graph/
underlying_graph.rs
