webgraph-algo 0.6.1

Algorithms for the 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

/*
 * SPDX-FileCopyrightText: 2024 Tommaso Fontana
 * SPDX-FileCopyrightText: 2024 Sebastiano Vigna
 *
 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
 */

use rayon::prelude::*;
use std::{
    cell::Cell,
    sync::atomic::{AtomicUsize, Ordering},
};

use super::RAYON_MIN_LEN;

pub(crate) struct LabelStore {
    labels: Box<[Cell<usize>]>,
    volumes: Box<[AtomicUsize]>,
}

impl LabelStore {
    pub(crate) fn new(n: usize) -> Self {
        let mut labels = Vec::with_capacity(n);
        labels.extend((0..n).map(|_| Cell::new(0)));
        let mut volumes = Vec::with_capacity(n);
        volumes.extend((0..n).map(|_| AtomicUsize::new(0)));

        Self {
            labels: labels.into_boxed_slice(),
            volumes: volumes.into_boxed_slice(),
        }
    }

    pub(crate) fn init(&mut self) {
        self.volumes
            .par_iter()
            .with_min_len(RAYON_MIN_LEN)
            .for_each(|v| v.store(1, Ordering::Relaxed));
        self.labels
            .par_iter_mut()
            .with_min_len(RAYON_MIN_LEN)
            .enumerate()
            .for_each(|(i, l)| *l.get_mut() = i);
    }

    #[inline(always)]
    pub(crate) fn label(&self, node: usize) -> usize {
        self.labels[node].get()
    }

    #[inline(always)]
    pub(crate) fn volume(&self, node: usize) -> usize {
        self.volumes[node].load(Ordering::Relaxed)
    }

    /// Updates the label of a node.
    #[inline(always)]
    pub(crate) fn update(&self, node: usize, new_label: usize) {
        let old_label = self.labels[node].replace(new_label);
        self.volumes[old_label].fetch_sub(1, Ordering::Relaxed);
        self.volumes[new_label].fetch_add(1, Ordering::Relaxed);
    }

    pub(crate) fn labels_and_volumes(&mut self) -> (&mut [usize], &mut [usize]) {
        unsafe {
            (
                // This is just a transparent wrapper
                std::mem::transmute::<&mut [Cell<usize>], &mut [usize]>(&mut self.labels),
                // Transmuting &mut from atomic to non-atomic is sound
                std::mem::transmute::<&mut [AtomicUsize], &mut [usize]>(&mut self.volumes),
            )
        }
    }
}

unsafe impl Send for LabelStore {}
unsafe impl Sync for LabelStore {}