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        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    fn num_nodes(&self) -> usize {
64        self.0.num_nodes()
65    }
66    fn iter_from(&self, from: usize) -> Self::Lender<'_> {
67        self.0.iter_from(from)
68    }
69
70    // Specialized methods
71    fn num_arcs_hint(&self) -> Option<u64> {
72        self.0.num_arcs_hint()
73    }
74}
75impl SequentialGraph for DefaultUnderlyingGraph {}
76
77impl RandomAccessLabeling for DefaultUnderlyingGraph {
78    type Labels<'succ>
79        = <DefaultUnderlyingGraphInner as RandomAccessLabeling>::Labels<'succ>
80    where
81        Self: 'succ;
82
83    fn num_arcs(&self) -> u64 {
84        <DefaultUnderlyingGraphInner as RandomAccessLabeling>::num_arcs(&self.0)
85    }
86
87    fn labels(&self, node_id: usize) -> <Self as RandomAccessLabeling>::Labels<'_> {
88        <DefaultUnderlyingGraphInner as RandomAccessLabeling>::labels(&self.0, node_id)
89    }
90
91    fn outdegree(&self, node_id: usize) -> usize {
92        <DefaultUnderlyingGraphInner as RandomAccessLabeling>::outdegree(&self.0, node_id)
93    }
94}
95
96impl RandomAccessGraph for DefaultUnderlyingGraph {}
97
98impl UnderlyingGraph for DefaultUnderlyingGraph {
99    type UnlabeledSuccessors<'succ>
100        = <DefaultUnderlyingGraphInner as RandomAccessLabeling>::Labels<'succ>
101    where
102        Self: 'succ;
103
104    fn num_arcs(&self) -> u64 {
105        <DefaultUnderlyingGraphInner as UnderlyingGraph>::num_arcs(&self.0)
106    }
107    fn has_arc(&self, src_node_id: NodeId, dst_node_id: NodeId) -> bool {
108        <DefaultUnderlyingGraphInner as UnderlyingGraph>::has_arc(&self.0, src_node_id, dst_node_id)
109    }
110    fn unlabeled_successors(&self, node_id: NodeId) -> Self::UnlabeledSuccessors<'_> {
111        <DefaultUnderlyingGraphInner as UnderlyingGraph>::unlabeled_successors(&self.0, node_id)
112    }
113}
swh_graph/underlying_graph.rs

swh_graph/
underlying_graph.rs
