webgraph 0.6.1

A Rust port of the WebGraph framework (http://webgraph.di.unimi.it/).
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

/*
 * SPDX-FileCopyrightText: 2023 Inria
 * SPDX-FileCopyrightText: 2025 Sebastiano Vigna
 *
 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
 */

use dsi_bitstream::codes::{GammaRead, GammaWrite};
use dsi_bitstream::traits::{BE, Endianness};
use dsi_bitstream::traits::{BitRead, BitWrite};
use webgraph::graphs::vec_graph::LabeledVecGraph;
use webgraph::prelude::transpose_labeled;
use webgraph::traits::labels::SequentialLabeling;
use webgraph::traits::{BitDeserializer, BitSerializer, graph};
use webgraph::utils::MemoryUsage;
use webgraph::utils::gaps::GapsCodec;
use webgraph::utils::{BitReader, BitWriter};

#[test]
fn test_transpose_labeled() -> anyhow::Result<()> {
    #[derive(Clone, Copy, PartialEq, Debug)]
    struct Payload(f64);

    #[derive(Clone, Copy, PartialEq, Debug, Default)]
    struct BD;

    impl<E: Endianness> BitDeserializer<E, BitReader<E>> for BD
    where
        BitReader<E>: GammaRead<E>,
    {
        type DeserType = Payload;

        fn deserialize(
            &self,
            bitstream: &mut BitReader<E>,
        ) -> Result<Self::DeserType, <BitReader<E> as BitRead<E>>::Error> {
            let mantissa = bitstream.read_gamma()?;
            let exponent = bitstream.read_gamma()?;
            let result = f64::from_bits((exponent << 53) | mantissa);
            Ok(Payload(result))
        }
    }

    #[derive(Clone, Copy, PartialEq, Debug, Default)]
    struct BS;

    impl<E: Endianness> BitSerializer<E, BitWriter<E>> for BS
    where
        BitWriter<E>: GammaWrite<E>,
    {
        type SerType = Payload;

        fn serialize(
            &self,
            value: &Self::SerType,
            bitstream: &mut BitWriter<E>,
        ) -> Result<usize, <BitWriter<E> as BitWrite<E>>::Error> {
            let value = value.0.to_bits();
            let mantissa = value & ((1 << 53) - 1);
            let exponent = value >> 53;
            let mut written_bits = 0;
            written_bits += bitstream.write_gamma(mantissa)?;
            written_bits += bitstream.write_gamma(exponent)?;
            Ok(written_bits)
        }
    }
    let arcs = [
        ((0, 1), Payload(1.0)),
        ((0, 2), Payload(f64::EPSILON)),
        ((1, 2), Payload(2.0)),
        ((2, 4), Payload(f64::INFINITY)),
        ((3, 4), Payload(f64::NEG_INFINITY)),
    ];
    let g = LabeledVecGraph::<Payload>::from_arcs(arcs);

    let trans = transpose_labeled(
        &g,
        MemoryUsage::BatchSize(3),
        GapsCodec::<BE, BS, BD>::new(BS, BD),
    )?;
    let g2 = LabeledVecGraph::<Payload>::from_lender(trans.iter());

    let trans = transpose_labeled(
        &g2,
        MemoryUsage::BatchSize(3),
        GapsCodec::<BE, BS, BD>::new(BS, BD),
    )?;
    let g3 = LabeledVecGraph::<Payload>::from_lender(trans.iter());

    let g4 = LabeledVecGraph::from_lender(g.iter());

    graph::eq_labeled(&g3, &g4)?;
    Ok(())
}