19278972970

Committed 11 Nov 2025 09:25PM UTC coverage: 62.316% (+14.3%) from 48.052%

Build # 19278972970

Build Type

push

github

Committed by

zommiommy

Commit Message

BatchCodec print stats and encoding time

Run Details

40 of 53 new or added lines in 4 files covered. (75.47%)

814 existing lines in 46 files now uncovered.

5252 of 8428 relevant lines covered (62.32%)

29580067.92 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

85.37

/webgraph/src/graphs/vec_graph.rs

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

use crate::prelude::*;
use epserde::Epserde;
use lender::prelude::*;

#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Epserde, Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
#[epserde_deep_copy]
pub struct LabeledArc<L>(usize, L);

impl<L> From<(usize, L)> for LabeledArc<L> {
    fn from((v, l): (usize, L)) -> Self {
        Self(v, l)
    }
}

impl<L> From<LabeledArc<L>> for (usize, L) {
    fn from(value: LabeledArc<L>) -> (usize, L) {
        (value.0, value.1)
    }
}

/// A mutable [`LabeledRandomAccessGraph`] implementation based on a vector of
/// vectors.
///
/// This implementation is faster and uses less resources than a
/// [`LabeledBTreeGraph`](crate::graphs::btree_graph::LabeledBTreeGraph), but it
/// is less flexible as arcs can be added only in increasing successor order.
///
/// This struct can be serialized with
/// [ε-serde](https://crates.io/crates/epserde). By setting the feature `serde`,
/// this struct can be serialized using [serde](https://crates.io/crates/serde),
/// too.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Epserde, Clone, Debug, PartialEq, Eq)]
pub struct LabeledVecGraph<L: Clone + 'static> {
    /// The number of arcs in the graph.
    num_arcs: u64,
    /// For each node, its list of successors.
    succ: Vec<Vec<LabeledArc<L>>>,
}

impl<L: Clone + 'static> core::default::Default for LabeledVecGraph<L> {
    fn default() -> Self {
        Self::new()
    }
}

impl<L: Clone + 'static> LabeledVecGraph<L> {
    /// Creates a new empty graph.
    pub fn new() -> Self {
        Self {
            num_arcs: 0,
            succ: vec![],
        }
    }

    /// Creates a new empty graph with `n` nodes.
    pub fn empty(n: usize) -> Self {
        Self {
            num_arcs: 0,
            succ: Vec::from_iter((0..n).map(|_| Vec::new())),
        }
    }

    /// Add an isolated node to the graph and return true if it is a new node.
    pub fn add_node(&mut self, node: usize) -> bool {
        let len = self.succ.len();
        self.succ.extend((len..=node).map(|_| Vec::new()));
        len <= node
    }

    /// Add an arc to the graph.
    ///
    /// New arcs must be added in increasing successor order, or this method
    /// will panic.
    ///
    /// # Panics
    ///
    /// This method will panic:
    /// - if one of the given nodes is greater or equal than the number of nodes
    ///   in the graph;
    /// - if the successor is lesser than or equal to the current last successor
    ///   of the source node.
    pub fn add_arc(&mut self, u: usize, v: usize, l: L) {
        let max = u.max(v);
        if max >= self.succ.len() {
            panic!(
                "Node {} does not exist (the graph has {} nodes)",
                max,
                self.succ.len(),
            );
        }
        let succ = &mut self.succ[u];

        match succ.last() {
            None => {
                succ.push((v, l).into());
                self.num_arcs += 1;
            }
            Some(LabeledArc(last, _label)) => {
                if v <= *last {
                    // arcs have to be inserted in increasing successor order
                    panic!(
                        "Error adding arc ({u}, {v}): successor is not increasing; the last arc inserted was ({u}, {last})"
                    );
                }
                succ.push((v, l).into());
                self.num_arcs += 1;
            }
        }
    }

    /// Add nodes and successors from an [`IntoLender`] yielding a
    /// [`NodeLabelsLender`].
    ///
    /// If the lender is sorted, consider using
    /// [`add_sorted_lender`](Self::add_sorted_lender), as it does not need to
    /// sort the output of the lender.
    pub fn add_lender<I: IntoLender>(&mut self, iter_nodes: I) -> &mut Self
    where
        I::Lender: for<'next> NodeLabelsLender<'next, Label = (usize, L)>,
    {
        let mut arcs = Vec::new();
        for_!( (node, succ) in iter_nodes {
            self.add_node(node);
            for (v, l) in succ {
                arcs.push((v, l));
                self.add_node(v);
            }
            arcs.sort_by_key(|x| x.0);
            for (v, l) in arcs.drain(..) {
                self.add_arc(node, v, l);
            }
        });
        self
    }

    /// Creates a new graph from an [`IntoLender`] yielding a
    /// [`NodeLabelsLender`].
    ///
    /// If the lender is sorted, consider using
    /// [`from_sorted_lender`](Self::from_sorted_lender), as it does not need to
    /// sort the output of the lender.
    pub fn from_lender<I: IntoLender>(iter_nodes: I) -> Self
    where
        I::Lender: for<'next> NodeLabelsLender<'next, Label = (usize, L)>,
    {
        let mut g = Self::new();
        g.add_lender(iter_nodes);
        g
    }

    /// Add nodes and successors from an [`IntoLender`] yielding a sorted
    /// [`NodeLabelsLender`].
    ///
    /// This method is faster than [`add_lender`](Self::add_lender) as
    /// it does not need to sort the output of the lender.
    pub fn add_sorted_lender<I: IntoLender>(&mut self, iter_nodes: I) -> &mut Self
    where
        I::Lender: for<'next> NodeLabelsLender<'next, Label = (usize, L)>,
        I::Lender: SortedLender,
        for<'succ> LenderIntoIter<'succ, I::Lender>: SortedIterator,
    {
        for_!( (node, succ) in iter_nodes {
            self.add_node(node);
            for (v, l) in succ {
                self.add_node(v);
                self.add_arc(node, v, l);
            }
        });
        self
    }

    /// Creates a new graph from a sorted [`IntoLender`] yielding a
    /// [`NodeLabelsLender`].
    ///
    /// This method is faster than [`from_lender`](Self::from_lender) as
    /// it does not need to sort the output of the lender.
    pub fn from_sorted_lender<I: IntoLender>(iter_nodes: I) -> Self
    where
        I::Lender: for<'next> NodeLabelsLender<'next, Label = (usize, L)>,
        I::Lender: SortedLender,
        for<'succ> LenderIntoIter<'succ, I::Lender>: SortedIterator,
    {
        let mut g = Self::new();
        g.add_sorted_lender(iter_nodes);
        g
    }

    /// Add nodes and successors from an [`IntoLender`] yielding a sorted
    /// [`NodeLabelsLender`] whose successors implement [`ExactSizeIterator`].
    ///
    /// This method has a better memory behavior than
    /// [`add_sorted_lender`](Self::add_sorted_lender) as it can allocate
    /// the right amount of memory for each node at once.
    pub fn add_exact_lender<I: IntoLender>(&mut self, iter_nodes: I) -> &mut Self
    where
        I::Lender: for<'next> NodeLabelsLender<'next, Label = (usize, L)>,
        I::Lender: SortedLender,
        for<'succ> LenderIntoIter<'succ, I::Lender>: SortedIterator + ExactSizeIterator,
    {
        for_!( (node, succ) in iter_nodes {
            self.add_node(node);
            let succ = succ.into_iter();
            let d = succ.len();
            self.succ[node].reserve_exact(d);
            self.succ[node].extend(succ.map(Into::into));
            self.num_arcs += d as u64;
        });
        self
    }

    /// Creates a new graph from a sorted [`IntoLender`] yielding a
    /// [`NodeLabelsLender`] whose successors implement [`ExactSizeIterator`].
    ///
    /// This method has a better memory behavior than
    /// [`from_sorted_lender`](Self::from_sorted_lender) as it can allocate
    /// the right amount of memory for each node at once.
    pub fn from_exact_lender<I: IntoLender>(iter_nodes: I) -> Self
    where
        I::Lender: for<'next> NodeLabelsLender<'next, Label = (usize, L)>,
        I::Lender: SortedLender,
        for<'succ> LenderIntoIter<'succ, I::Lender>: SortedIterator + ExactSizeIterator,
    {
        let mut g = Self::new();
        g.add_exact_lender(iter_nodes);
        g
    }

    /// Add labeled arcs from an [`IntoIterator`], adding new nodes as needed.
    ///
    /// The items must be labeled pairs of the form `((usize, usize), l)` specifying an
    /// arc and its label.
    pub fn add_arcs(&mut self, arcs: impl IntoIterator<Item = ((usize, usize), L)>) {
        let mut arcs = arcs.into_iter().collect::<Vec<_>>();
        arcs.sort_by_key(|x| x.0);
        for ((u, v), l) in arcs {
            self.add_node(u);
            self.add_node(v);
            self.add_arc(u, v, l);
        }
    }

    /// Creates a new graph from an [`IntoIterator`].
    ///
    /// The items must be labeled pairs of the form `((usize, usize), l)` specifying an
    /// arc and its label.
    pub fn from_arcs(arcs: impl IntoIterator<Item = ((usize, usize), L)>) -> Self {
        let mut g = Self::new();
        g.add_arcs(arcs);
        g
    }

    /// Shrink the capacity of the graph to fit its current size.
    pub fn shrink_to_fit(&mut self) {
        self.succ.shrink_to_fit();
        for s in self.succ.iter_mut() {
            s.shrink_to_fit();
        }
    }
}

impl<L: Clone + 'static> SequentialLabeling for LabeledVecGraph<L> {
    type Label = (usize, L);
    type Lender<'a>
        = IteratorImpl<'a, Self>
    where
        Self: 'a;

    #[inline(always)]
    fn num_nodes(&self) -> usize {
        self.succ.len()
    }

    #[inline(always)]
    fn num_arcs_hint(&self) -> Option<u64> {
        Some(self.num_arcs())
    }

    #[inline(always)]
    fn iter_from(&self, from: usize) -> Self::Lender<'_> {
        IteratorImpl {
            labeling: self,
            nodes: (from..self.num_nodes()),
        }
    }
}

/// Convenience implementation that makes it possible to iterate
/// over the graph using the [`for_`] macro
/// (see the [crate documentation](crate)).
impl<'a, L: Clone + 'static> IntoLender for &'a LabeledVecGraph<L> {
    type Lender = <LabeledVecGraph<L> as SequentialLabeling>::Lender<'a>;

    #[inline(always)]
    fn into_lender(self) -> Self::Lender {
        self.iter()
    }
}

impl<L: Clone + 'static> LabeledSequentialGraph<L> for LabeledVecGraph<L> {}

impl<L: Clone + 'static> RandomAccessLabeling for LabeledVecGraph<L> {
    type Labels<'succ> = AssumeSortedIterator<
        core::iter::Map<
            core::iter::Cloned<core::slice::Iter<'succ, LabeledArc<L>>>,
            fn(LabeledArc<L>) -> (usize, L),
        >,
    >;
    #[inline(always)]
    fn num_arcs(&self) -> u64 {
        self.num_arcs
    }

    #[inline(always)]
    fn outdegree(&self, node: usize) -> usize {
        self.succ[node].len()
    }

    #[inline(always)]
    fn labels(&self, node: usize) -> <Self as RandomAccessLabeling>::Labels<'_> {
        unsafe { AssumeSortedIterator::new(self.succ[node].iter().cloned().map(Into::into)) }
    }
}

impl<L: Clone + 'static> LabeledRandomAccessGraph<L> for LabeledVecGraph<L> {}

impl<L: Clone + Sync> SplitLabeling for LabeledVecGraph<L> {
    type SplitLender<'a>
        = split::ra::Lender<'a, LabeledVecGraph<L>>
    where
        Self: 'a;

    type IntoIterator<'a>
        = split::ra::IntoIterator<'a, LabeledVecGraph<L>>
    where
        Self: 'a;

    fn split_iter(&self, how_many: usize) -> Self::IntoIterator<'_> {
        split::ra::Iter::new(self, how_many)
    }
}

/// A mutable [`RandomAccessGraph`] implementation based on a vector of
/// vectors.
///
/// This implementation is faster and uses less resources than a [`BTreeGraph`],
/// but it is less flexible as arcs can be added only in increasing successor
/// order.
///
/// This struct can be serialized with
/// [ε-serde](https://crates.io/crates/epserde). By setting the feature `serde`,
/// this struct can be serialized using [serde](https://crates.io/crates/serde),
/// too.
///
/// # Implementation Notes
///
/// This is just a newtype for a [`LabeledVecGraph`] with
/// [`()`](https://doc.rust-lang.org/std/primitive.unit.html) labels. All
/// mutation methods are delegated.
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[derive(Epserde, Clone, Debug, Default, PartialEq, Eq)]
pub struct VecGraph(LabeledVecGraph<()>);

impl VecGraph {
    /// Creates a new empty graph.
    pub fn new() -> Self {
        LabeledVecGraph::new().into()
    }

    /// Creates a new empty graph with `n` nodes.
    pub fn empty(n: usize) -> Self {
        LabeledVecGraph::empty(n).into()
    }

    /// Add an isolated node to the graph and return true if it is a new node.
    pub fn add_node(&mut self, node: usize) -> bool {
        self.0.add_node(node)
    }

    /// Add an arc to the graph.
    ///
    /// New arcs must be added in increasing successor order, or this method
    /// will panic.
    ///
    /// # Panics
    ///
    /// This method will panic:
    /// - if one of the given nodes is greater or equal than the number of nodes
    ///   in the graph;
    /// - if the successor is lesser than or equal to the current last successor
    ///   of the source node.
    pub fn add_arc(&mut self, u: usize, v: usize) {
        self.0.add_arc(u, v, ())
    }

    /// Add nodes and successors from an [`IntoLender`] yielding a
    /// [`NodeLabelsLender`].
    ///
    /// If the lender is sorted, consider using
    /// [`add_sorted_lender`](Self::add_sorted_lender), as it does not need to
    /// sort the output of the lender.
    pub fn add_lender<I: IntoLender>(&mut self, iter_nodes: I) -> &mut Self
    where
        I::Lender: for<'next> NodeLabelsLender<'next, Label = usize>,
    {
        self.0.add_lender(UnitLender(iter_nodes.into_lender()));
        self
    }

    /// Creates a new graph from an [`IntoLender`] yielding a
    /// [`NodeLabelsLender`].
    ///
    /// If the lender is sorted, consider using
    /// [`from_sorted_lender`](Self::from_sorted_lender), as it does not need to
    /// sort the output of the lender.
    pub fn from_lender<I: IntoLender>(iter_nodes: I) -> Self
    where
        I::Lender: for<'next> NodeLabelsLender<'next, Label = usize>,
    {
        let mut g = Self::new();
        g.add_lender(iter_nodes);
        g
    }

    /// Add nodes and successors from an [`IntoLender`] yielding a sorted
    /// [`NodeLabelsLender`].
    ///
    /// This method is faster than [`add_lender`](Self::add_lender) as
    /// it does not need to sort the output of the lender.
    pub fn add_sorted_lender<I: IntoLender>(&mut self, iter_nodes: I) -> &mut Self
    where
        I::Lender: for<'next> NodeLabelsLender<'next, Label = usize>,
        I::Lender: SortedLender,
        for<'succ> LenderIntoIter<'succ, I::Lender>: SortedIterator,
    {
        self.0
            .add_sorted_lender(UnitLender(iter_nodes.into_lender()));
        self
    }

    /// Creates a new graph from a sorted [`IntoLender`] yielding a
    /// [`NodeLabelsLender`].
    ///
    /// This method is faster than [`from_lender`](Self::from_lender) as
    /// it does not need to sort the output of the lender.
    pub fn from_sorted_lender<I: IntoLender>(iter_nodes: I) -> Self
    where
        I::Lender: for<'next> NodeLabelsLender<'next, Label = usize>,
        I::Lender: SortedLender,
        for<'succ> LenderIntoIter<'succ, I::Lender>: SortedIterator,
    {
        let mut g = Self::new();
        g.add_sorted_lender(iter_nodes);
        g
    }

    /// Add nodes and successors from an [`IntoLender`] yielding a sorted
    /// [`NodeLabelsLender`] whose successors implement [`ExactSizeIterator`].
    ///
    /// This method has a better memory behavior than
    /// [`add_sorted_lender`](Self::add_sorted_lender) as it can allocate
    /// the right amount of memory for each node at once.
    pub fn add_exact_lender<I: IntoLender>(&mut self, iter_nodes: I) -> &mut Self
    where
        I::Lender: for<'next> NodeLabelsLender<'next, Label = usize>,
        I::Lender: SortedLender,
        for<'succ> LenderIntoIter<'succ, I::Lender>: SortedIterator + ExactSizeIterator,
    {
        for_!( (node, succ) in iter_nodes {
            self.add_node(node);
            let succ = succ.into_iter();
            let d = succ.len();
            self.0.succ[node].reserve_exact(d);
            self.0.succ[node].extend(succ.map(|x| LabeledArc(x, ())));
            self.0.num_arcs += d as u64;
        });
        self
    }

    /// Creates a new graph from a sorted [`IntoLender`] yielding a
    /// [`NodeLabelsLender`] whose successors implement [`ExactSizeIterator`].
    ///
    /// This method has a better memory behavior than
    /// [`from_sorted_lender`](Self::from_sorted_lender) as it can allocate
    /// the right amount of memory for each node at once.
    pub fn from_exact_lender<I: IntoLender>(iter_nodes: I) -> Self
    where
        I::Lender: for<'next> NodeLabelsLender<'next, Label = usize>,
        I::Lender: SortedLender,
        for<'succ> LenderIntoIter<'succ, I::Lender>: SortedIterator + ExactSizeIterator,
    {
        let mut g = Self::new();
        g.add_exact_lender(iter_nodes);
        g
    }

    /// Add arcs from an [`IntoIterator`], adding new nodes as needed.
    ///
    /// The items must be pairs of the form `(usize, usize)` specifying an arc.
    pub fn add_arcs(&mut self, arcs: impl IntoIterator<Item = (usize, usize)>) {
        self.0.add_arcs(arcs.into_iter().map(|pair| (pair, ())));
    }

    /// Creates a new graph from an [`IntoIterator`].
    ///
    /// The items must be pairs of the form `(usize, usize)` specifying an arc.
    pub fn from_arcs(arcs: impl IntoIterator<Item = (usize, usize)>) -> Self {
        let mut g = Self::new();
        g.add_arcs(arcs);
        g
    }

    /// Shrink the capacity of the graph to fit its current size.
    pub fn shrink_to_fit(&mut self) {
        self.0.shrink_to_fit();
    }
}

/// Convenience implementation that makes it possible to iterate
/// over the graph using the [`for_`] macro
/// (see the [crate documentation](crate)).
impl<'a> IntoLender for &'a VecGraph {
    type Lender = <VecGraph as SequentialLabeling>::Lender<'a>;

    #[inline(always)]
    fn into_lender(self) -> Self::Lender {
        self.iter()
    }
}

impl SequentialLabeling for VecGraph {
    type Label = usize;
    type Lender<'a>
        = IteratorImpl<'a, Self>
    where
        Self: 'a;

    #[inline(always)]
    fn num_nodes(&self) -> usize {
        self.0.num_nodes()
    }

    #[inline(always)]
    fn num_arcs_hint(&self) -> Option<u64> {
        self.0.num_arcs_hint()
    }

    #[inline(always)]
    fn iter_from(&self, from: usize) -> Self::Lender<'_> {
        IteratorImpl {
            labeling: self,
            nodes: (from..self.num_nodes()),
        }
    }
}

impl SequentialGraph for VecGraph {}

impl RandomAccessLabeling for VecGraph {
    type Labels<'succ> = AssumeSortedIterator<
        core::iter::Map<
            core::iter::Copied<core::slice::Iter<'succ, LabeledArc<()>>>,
            fn(LabeledArc<()>) -> usize,
        >,
    >;
    #[inline(always)]
    fn num_arcs(&self) -> u64 {
        self.0.num_arcs()
    }

    #[inline(always)]
    fn outdegree(&self, node: usize) -> usize {
        self.0.outdegree(node)
    }

    #[inline(always)]
    fn labels(&self, node: usize) -> <Self as RandomAccessLabeling>::Labels<'_> {
        // this is safe as we maintain each vector of successors sorted
        unsafe {
            AssumeSortedIterator::new(self.0.succ[node].iter().copied().map(|LabeledArc(x, _)| x))
        }
    }
}

impl RandomAccessGraph for VecGraph {}

impl From<LabeledVecGraph<()>> for VecGraph {
    fn from(g: LabeledVecGraph<()>) -> Self {
        VecGraph(g)
    }
}

impl SplitLabeling for VecGraph {
    type SplitLender<'a>
        = split::ra::Lender<'a, VecGraph>
    where
        Self: 'a;

    type IntoIterator<'a>
        = split::ra::IntoIterator<'a, VecGraph>
    where
        Self: 'a;

    fn split_iter(&self, how_many: usize) -> Self::IntoIterator<'_> {
        split::ra::Iter::new(self, how_many)
    }
}

#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn test_vec_graph() {
        let mut arcs = vec![
            ((0, 1), Some(1.0)),
            ((0, 2), None),
            ((1, 2), Some(2.0)),
            ((2, 4), Some(f64::INFINITY)),
            ((3, 4), Some(f64::NEG_INFINITY)),
            ((1, 3), Some(f64::NAN)),
        ];
        let g = LabeledVecGraph::<_>::from_arcs(arcs.iter().copied());
        assert_ne!(
            g, g,
            "The label contains a NaN which is not equal to itself so the graph must be not equal to itself"
        );

        arcs.pop();
        let g = LabeledVecGraph::<_>::from_arcs(arcs);
        assert_eq!(g, g, "Without NaN the graph should be equal to itself");
    }
}

1	/*
2	* SPDX-FileCopyrightText: 2023 Inria
3	* SPDX-FileCopyrightText: 2023 Sebastiano Vigna
4	*
5	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
6	*/
7
8	use crate::prelude::*;
9	use epserde::Epserde;
10	use lender::prelude::*;
11
12	#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
13	#[derive(Epserde, Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
14	#[epserde_deep_copy]
15	pub struct LabeledArc<L>(usize, L);
16
17	impl<L> From<(usize, L)> for LabeledArc<L> {
18	fn from((v, l): (usize, L)) -> Self {	1,432,949✔
19	Self(v, l)	1,432,949✔
20	}
21	}
22
23	impl<L> From<LabeledArc<L>> for (usize, L) {
24	fn from(value: LabeledArc<L>) -> (usize, L) {	116✔
25	(value.0, value.1)	116✔
26	}
27	}
28
29	/// A mutable [`LabeledRandomAccessGraph`] implementation based on a vector of
30	/// vectors.
31	///
32	/// This implementation is faster and uses less resources than a
33	/// [`LabeledBTreeGraph`](crate::graphs::btree_graph::LabeledBTreeGraph), but it
34	/// is less flexible as arcs can be added only in increasing successor order.
35	///
36	/// This struct can be serialized with
37	/// [ε-serde](https://crates.io/crates/epserde). By setting the feature `serde`,
38	/// this struct can be serialized using [serde](https://crates.io/crates/serde),
39	/// too.
40	#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
41	#[derive(Epserde, Clone, Debug, PartialEq, Eq)]
42	pub struct LabeledVecGraph<L: Clone + 'static> {
43	/// The number of arcs in the graph.
44	num_arcs: u64,
45	/// For each node, its list of successors.
46	succ: Vec<Vec<LabeledArc<L>>>,
47	}
48
49	impl<L: Clone + 'static> core::default::Default for LabeledVecGraph<L> {
50	fn default() -> Self {	×
UNCOV 51	Self::new()	×
52	}
53	}
54
55	impl<L: Clone + 'static> LabeledVecGraph<L> {
56	/// Creates a new empty graph.
57	pub fn new() -> Self {	1,046✔
58	Self {
59	num_arcs: 0,
60	succ: vec![],	1,046✔
61	}
62	}
63
64	/// Creates a new empty graph with `n` nodes.
UNCOV 65	pub fn empty(n: usize) -> Self {	×
66	Self {
67	num_arcs: 0,
UNCOV 68	succ: Vec::from_iter((0..n).map(\|_\| Vec::new())),	×
69	}
70	}
71
72	/// Add an isolated node to the graph and return true if it is a new node.
73	pub fn add_node(&mut self, node: usize) -> bool {	1,427,381✔
74	let len = self.succ.len();	4,282,143✔
75	self.succ.extend((len..=node).map(\|_\| Vec::new()));	5,754,049✔
76	len <= node	1,427,381✔
77	}
78
79	/// Add an arc to the graph.
80	///
81	/// New arcs must be added in increasing successor order, or this method
82	/// will panic.
83	///
84	/// # Panics
85	///
86	/// This method will panic:
87	/// - if one of the given nodes is greater or equal than the number of nodes
88	/// in the graph;
89	/// - if the successor is lesser than or equal to the current last successor
90	/// of the source node.
91	pub fn add_arc(&mut self, u: usize, v: usize, l: L) {	1,432,937✔
92	let max = u.max(v);	5,731,748✔
93	if max >= self.succ.len() {	2,865,874✔
94	panic!(	×
95	"Node {} does not exist (the graph has {} nodes)",	×
96	max,	×
UNCOV 97	self.succ.len(),	×
98	);
99	}
100	let succ = &mut self.succ[u];	2,865,874✔
101
102	match succ.last() {	1,432,937✔
103	None => {	43,622✔
104	succ.push((v, l).into());	174,488✔
105	self.num_arcs += 1;	43,622✔
106	}
107	Some(LabeledArc(last, _label)) => {	2,778,630✔
108	if v <= *last {	1,389,315✔
109	// arcs have to be inserted in increasing successor order
110	panic!(	×
UNCOV 111	"Error adding arc ({u}, {v}): successor is not increasing; the last arc inserted was ({u}, {last})"	×
112	);
113	}
114	succ.push((v, l).into());	5,557,260✔
115	self.num_arcs += 1;	1,389,315✔
116	}
117	}
118	}
119
120	/// Add nodes and successors from an [`IntoLender`] yielding a
121	/// [`NodeLabelsLender`].
122	///
123	/// If the lender is sorted, consider using
124	/// [`add_sorted_lender`](Self::add_sorted_lender), as it does not need to
125	/// sort the output of the lender.
126	pub fn add_lender<I: IntoLender>(&mut self, iter_nodes: I) -> &mut Self	199✔
127	where
128	I::Lender: for<'next> NodeLabelsLender<'next, Label = (usize, L)>,
129	{
130	let mut arcs = Vec::new();	398✔
131	for_!( (node, succ) in iter_nodes {	21,315✔
132	self.add_node(node);	31,674✔
133	for (v, l) in succ {	1,391,978✔
134	arcs.push((v, l));	1,381,420✔
135	self.add_node(v);	690,710✔
136	}
137	arcs.sort_by_key(\|x\| x.0);	21,116✔
138	for (v, l) in arcs.drain(..) {	1,067,739✔
139	self.add_arc(node, v, l);	1,381,420✔
140	}
141	});
142	self	199✔
143	}
144
145	/// Creates a new graph from an [`IntoLender`] yielding a
146	/// [`NodeLabelsLender`].
147	///
148	/// If the lender is sorted, consider using
149	/// [`from_sorted_lender`](Self::from_sorted_lender), as it does not need to
150	/// sort the output of the lender.
151	pub fn from_lender<I: IntoLender>(iter_nodes: I) -> Self	4✔
152	where
153	I::Lender: for<'next> NodeLabelsLender<'next, Label = (usize, L)>,
154	{
155	let mut g = Self::new();	8✔
156	g.add_lender(iter_nodes);	12✔
157	g	4✔
158	}
159
160	/// Add nodes and successors from an [`IntoLender`] yielding a sorted
161	/// [`NodeLabelsLender`].
162	///
163	/// This method is faster than [`add_lender`](Self::add_lender) as
164	/// it does not need to sort the output of the lender.
165	pub fn add_sorted_lender<I: IntoLender>(&mut self, iter_nodes: I) -> &mut Self	2✔
166	where
167	I::Lender: for<'next> NodeLabelsLender<'next, Label = (usize, L)>,
168	I::Lender: SortedLender,
169	for<'succ> LenderIntoIter<'succ, I::Lender>: SortedIterator,
170	{
171	for_!( (node, succ) in iter_nodes {	42✔
172	self.add_node(node);	60✔
173	for (v, l) in succ {	116✔
174	self.add_node(v);	96✔
175	self.add_arc(node, v, l);	96✔
176	}
177	});
178	self	2✔
179	}
180
181	/// Creates a new graph from a sorted [`IntoLender`] yielding a
182	/// [`NodeLabelsLender`].
183	///
184	/// This method is faster than [`from_lender`](Self::from_lender) as
185	/// it does not need to sort the output of the lender.
186	pub fn from_sorted_lender<I: IntoLender>(iter_nodes: I) -> Self	1✔
187	where
188	I::Lender: for<'next> NodeLabelsLender<'next, Label = (usize, L)>,
189	I::Lender: SortedLender,
190	for<'succ> LenderIntoIter<'succ, I::Lender>: SortedIterator,
191	{
192	let mut g = Self::new();	2✔
193	g.add_sorted_lender(iter_nodes);	3✔
194	g	1✔
195	}
196
197	/// Add nodes and successors from an [`IntoLender`] yielding a sorted
198	/// [`NodeLabelsLender`] whose successors implement [`ExactSizeIterator`].
199	///
200	/// This method has a better memory behavior than
201	/// [`add_sorted_lender`](Self::add_sorted_lender) as it can allocate
202	/// the right amount of memory for each node at once.
203	pub fn add_exact_lender<I: IntoLender>(&mut self, iter_nodes: I) -> &mut Self	1✔
204	where
205	I::Lender: for<'next> NodeLabelsLender<'next, Label = (usize, L)>,
206	I::Lender: SortedLender,
207	for<'succ> LenderIntoIter<'succ, I::Lender>: SortedIterator + ExactSizeIterator,
208	{
209	for_!( (node, succ) in iter_nodes {	31✔
210	self.add_node(node);	40✔
211	let succ = succ.into_iter();	40✔
212	let d = succ.len();	40✔
213	self.succ[node].reserve_exact(d);	40✔
214	self.succ[node].extend(succ.map(Into::into));	40✔
215	self.num_arcs += d as u64;	10✔
216	});
217	self	1✔
218	}
219
220	/// Creates a new graph from a sorted [`IntoLender`] yielding a
221	/// [`NodeLabelsLender`] whose successors implement [`ExactSizeIterator`].
222	///
223	/// This method has a better memory behavior than
224	/// [`from_sorted_lender`](Self::from_sorted_lender) as it can allocate
225	/// the right amount of memory for each node at once.
226	pub fn from_exact_lender<I: IntoLender>(iter_nodes: I) -> Self	1✔
227	where
228	I::Lender: for<'next> NodeLabelsLender<'next, Label = (usize, L)>,
229	I::Lender: SortedLender,
230	for<'succ> LenderIntoIter<'succ, I::Lender>: SortedIterator + ExactSizeIterator,
231	{
232	let mut g = Self::new();	2✔
233	g.add_exact_lender(iter_nodes);	3✔
234	g	1✔
235	}
236
237	/// Add labeled arcs from an [`IntoIterator`], adding new nodes as needed.
238	///
239	/// The items must be labeled pairs of the form `((usize, usize), l)` specifying an
240	/// arc and its label.
241	pub fn add_arcs(&mut self, arcs: impl IntoIterator<Item = ((usize, usize), L)>) {	60✔
242	let mut arcs = arcs.into_iter().collect::<Vec<_>>();	240✔
243	arcs.sort_by_key(\|x\| x.0);	120✔
244	for ((u, v), l) in arcs {	1,895✔
245	self.add_node(u);	1,468✔
246	self.add_node(v);	1,468✔
247	self.add_arc(u, v, l);	1,468✔
248	}
249	}
250
251	/// Creates a new graph from an [`IntoIterator`].
252	///
253	/// The items must be labeled pairs of the form `((usize, usize), l)` specifying an
254	/// arc and its label.
255	pub fn from_arcs(arcs: impl IntoIterator<Item = ((usize, usize), L)>) -> Self {	10✔
256	let mut g = Self::new();	20✔
257	g.add_arcs(arcs);	30✔
258	g	10✔
259	}
260
261	/// Shrink the capacity of the graph to fit its current size.
262	pub fn shrink_to_fit(&mut self) {	×
263	self.succ.shrink_to_fit();	×
264	for s in self.succ.iter_mut() {	×
UNCOV 265	s.shrink_to_fit();	×
266	}
267	}
268	}
269
270	impl<L: Clone + 'static> SequentialLabeling for LabeledVecGraph<L> {
271	type Label = (usize, L);
272	type Lender<'a>
273	= IteratorImpl<'a, Self>
274	where
275	Self: 'a;
276
277	#[inline(always)]
278	fn num_nodes(&self) -> usize {	2,708✔
279	self.succ.len()	5,416✔
280	}
281
282	#[inline(always)]
283	fn num_arcs_hint(&self) -> Option<u64> {	13✔
284	Some(self.num_arcs())	13✔
285	}
286
287	#[inline(always)]
288	fn iter_from(&self, from: usize) -> Self::Lender<'_> {	27✔
289	IteratorImpl {
290	labeling: self,
291	nodes: (from..self.num_nodes()),	54✔
292	}
293	}
294	}
295
296	/// Convenience implementation that makes it possible to iterate
297	/// over the graph using the [`for_`] macro
298	/// (see the [crate documentation](crate)).
299	impl<'a, L: Clone + 'static> IntoLender for &'a LabeledVecGraph<L> {
300	type Lender = <LabeledVecGraph<L> as SequentialLabeling>::Lender<'a>;
301
302	#[inline(always)]
UNCOV 303	fn into_lender(self) -> Self::Lender {	×
UNCOV 304	self.iter()	×
305	}
306	}
307
308	impl<L: Clone + 'static> LabeledSequentialGraph<L> for LabeledVecGraph<L> {}
309
310	impl<L: Clone + 'static> RandomAccessLabeling for LabeledVecGraph<L> {
311	type Labels<'succ> = AssumeSortedIterator<
312	core::iter::Map<
313	core::iter::Cloned<core::slice::Iter<'succ, LabeledArc<L>>>,
314	fn(LabeledArc<L>) -> (usize, L),
315	>,
316	>;
317	#[inline(always)]
318	fn num_arcs(&self) -> u64 {	1,728✔
319	self.num_arcs	1,728✔
320	}
321
322	#[inline(always)]
323	fn outdegree(&self, node: usize) -> usize {	791✔
324	self.succ[node].len()	1,582✔
325	}
326
327	#[inline(always)]
328	fn labels(&self, node: usize) -> <Self as RandomAccessLabeling>::Labels<'_> {	99✔
329	unsafe { AssumeSortedIterator::new(self.succ[node].iter().cloned().map(Into::into)) }	495✔
330	}
331	}
332
333	impl<L: Clone + 'static> LabeledRandomAccessGraph<L> for LabeledVecGraph<L> {}
334
335	impl<L: Clone + Sync> SplitLabeling for LabeledVecGraph<L> {
336	type SplitLender<'a>
337	= split::ra::Lender<'a, LabeledVecGraph<L>>
338	where
339	Self: 'a;
340
341	type IntoIterator<'a>
342	= split::ra::IntoIterator<'a, LabeledVecGraph<L>>
343	where
344	Self: 'a;
345
UNCOV 346	fn split_iter(&self, how_many: usize) -> Self::IntoIterator<'_> {	×
UNCOV 347	split::ra::Iter::new(self, how_many)	×
348	}
349	}
350
351	/// A mutable [`RandomAccessGraph`] implementation based on a vector of
352	/// vectors.
353	///
354	/// This implementation is faster and uses less resources than a [`BTreeGraph`],
355	/// but it is less flexible as arcs can be added only in increasing successor
356	/// order.
357	///
358	/// This struct can be serialized with
359	/// [ε-serde](https://crates.io/crates/epserde). By setting the feature `serde`,
360	/// this struct can be serialized using [serde](https://crates.io/crates/serde),
361	/// too.
362	///
363	/// # Implementation Notes
364	///
365	/// This is just a newtype for a [`LabeledVecGraph`] with
366	/// [`()`](https://doc.rust-lang.org/std/primitive.unit.html) labels. All
367	/// mutation methods are delegated.
368	#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
369	#[derive(Epserde, Clone, Debug, Default, PartialEq, Eq)]
370	pub struct VecGraph(LabeledVecGraph<()>);
371
372	impl VecGraph {
373	/// Creates a new empty graph.
374	pub fn new() -> Self {	1,029✔
375	LabeledVecGraph::new().into()	2,058✔
376	}
377
378	/// Creates a new empty graph with `n` nodes.
UNCOV 379	pub fn empty(n: usize) -> Self {	×
UNCOV 380	LabeledVecGraph::empty(n).into()	×
381	}
382
383	/// Add an isolated node to the graph and return true if it is a new node.
384	pub fn add_node(&mut self, node: usize) -> bool {	1,288✔
385	self.0.add_node(node)	3,864✔
386	}
387
388	/// Add an arc to the graph.
389	///
390	/// New arcs must be added in increasing successor order, or this method
391	/// will panic.
392	///
393	/// # Panics
394	///
395	/// This method will panic:
396	/// - if one of the given nodes is greater or equal than the number of nodes
397	/// in the graph;
398	/// - if the successor is lesser than or equal to the current last successor
399	/// of the source node.
400	pub fn add_arc(&mut self, u: usize, v: usize) {	50,300✔
401	self.0.add_arc(u, v, ())	251,500✔
402	}
403
404	/// Add nodes and successors from an [`IntoLender`] yielding a
405	/// [`NodeLabelsLender`].
406	///
407	/// If the lender is sorted, consider using
408	/// [`add_sorted_lender`](Self::add_sorted_lender), as it does not need to
409	/// sort the output of the lender.
410	pub fn add_lender<I: IntoLender>(&mut self, iter_nodes: I) -> &mut Self	195✔
411	where
412	I::Lender: for<'next> NodeLabelsLender<'next, Label = usize>,
413	{
414	self.0.add_lender(UnitLender(iter_nodes.into_lender()));	585✔
415	self	195✔
416	}
417
418	/// Creates a new graph from an [`IntoLender`] yielding a
419	/// [`NodeLabelsLender`].
420	///
421	/// If the lender is sorted, consider using
422	/// [`from_sorted_lender`](Self::from_sorted_lender), as it does not need to
423	/// sort the output of the lender.
424	pub fn from_lender<I: IntoLender>(iter_nodes: I) -> Self	191✔
425	where
426	I::Lender: for<'next> NodeLabelsLender<'next, Label = usize>,
427	{
428	let mut g = Self::new();	382✔
429	g.add_lender(iter_nodes);	573✔
430	g	191✔
431	}
432
433	/// Add nodes and successors from an [`IntoLender`] yielding a sorted
434	/// [`NodeLabelsLender`].
435	///
436	/// This method is faster than [`add_lender`](Self::add_lender) as
437	/// it does not need to sort the output of the lender.
438	pub fn add_sorted_lender<I: IntoLender>(&mut self, iter_nodes: I) -> &mut Self	1✔
439	where
440	I::Lender: for<'next> NodeLabelsLender<'next, Label = usize>,
441	I::Lender: SortedLender,
442	for<'succ> LenderIntoIter<'succ, I::Lender>: SortedIterator,
443	{
444	self.0	1✔
445	.add_sorted_lender(UnitLender(iter_nodes.into_lender()));	2✔
446	self	1✔
447	}
448
449	/// Creates a new graph from a sorted [`IntoLender`] yielding a
450	/// [`NodeLabelsLender`].
451	///
452	/// This method is faster than [`from_lender`](Self::from_lender) as
453	/// it does not need to sort the output of the lender.
454	pub fn from_sorted_lender<I: IntoLender>(iter_nodes: I) -> Self	1✔
455	where
456	I::Lender: for<'next> NodeLabelsLender<'next, Label = usize>,
457	I::Lender: SortedLender,
458	for<'succ> LenderIntoIter<'succ, I::Lender>: SortedIterator,
459	{
460	let mut g = Self::new();	2✔
461	g.add_sorted_lender(iter_nodes);	3✔
462	g	1✔
463	}
464
465	/// Add nodes and successors from an [`IntoLender`] yielding a sorted
466	/// [`NodeLabelsLender`] whose successors implement [`ExactSizeIterator`].
467	///
468	/// This method has a better memory behavior than
469	/// [`add_sorted_lender`](Self::add_sorted_lender) as it can allocate
470	/// the right amount of memory for each node at once.
471	pub fn add_exact_lender<I: IntoLender>(&mut self, iter_nodes: I) -> &mut Self	1✔
472	where
473	I::Lender: for<'next> NodeLabelsLender<'next, Label = usize>,
474	I::Lender: SortedLender,
475	for<'succ> LenderIntoIter<'succ, I::Lender>: SortedIterator + ExactSizeIterator,
476	{
477	for_!( (node, succ) in iter_nodes {	21✔
478	self.add_node(node);	30✔
479	let succ = succ.into_iter();	30✔
480	let d = succ.len();	30✔
481	self.0.succ[node].reserve_exact(d);	30✔
482	self.0.succ[node].extend(succ.map(\|x\| LabeledArc(x, ())));	64✔
483	self.0.num_arcs += d as u64;	10✔
484	});
485	self	1✔
486	}
487
488	/// Creates a new graph from a sorted [`IntoLender`] yielding a
489	/// [`NodeLabelsLender`] whose successors implement [`ExactSizeIterator`].
490	///
491	/// This method has a better memory behavior than
492	/// [`from_sorted_lender`](Self::from_sorted_lender) as it can allocate
493	/// the right amount of memory for each node at once.
494	pub fn from_exact_lender<I: IntoLender>(iter_nodes: I) -> Self	1✔
495	where
496	I::Lender: for<'next> NodeLabelsLender<'next, Label = usize>,
497	I::Lender: SortedLender,
498	for<'succ> LenderIntoIter<'succ, I::Lender>: SortedIterator + ExactSizeIterator,
499	{
500	let mut g = Self::new();	2✔
501	g.add_exact_lender(iter_nodes);	3✔
502	g	1✔
503	}
504
505	/// Add arcs from an [`IntoIterator`], adding new nodes as needed.
506	///
507	/// The items must be pairs of the form `(usize, usize)` specifying an arc.
508	pub fn add_arcs(&mut self, arcs: impl IntoIterator<Item = (usize, usize)>) {	50✔
509	self.0.add_arcs(arcs.into_iter().map(\|pair\| (pair, ())));	894✔
510	}
511
512	/// Creates a new graph from an [`IntoIterator`].
513	///
514	/// The items must be pairs of the form `(usize, usize)` specifying an arc.
515	pub fn from_arcs(arcs: impl IntoIterator<Item = (usize, usize)>) -> Self {	50✔
516	let mut g = Self::new();	100✔
517	g.add_arcs(arcs);	150✔
518	g	50✔
519	}
520
521	/// Shrink the capacity of the graph to fit its current size.
UNCOV 522	pub fn shrink_to_fit(&mut self) {	×
UNCOV 523	self.0.shrink_to_fit();	×
524	}
525	}
526
527	/// Convenience implementation that makes it possible to iterate
528	/// over the graph using the [`for_`] macro
529	/// (see the [crate documentation](crate)).
530	impl<'a> IntoLender for &'a VecGraph {
531	type Lender = <VecGraph as SequentialLabeling>::Lender<'a>;
532
533	#[inline(always)]
UNCOV 534	fn into_lender(self) -> Self::Lender {	×
UNCOV 535	self.iter()	×
536	}
537	}
538
539	impl SequentialLabeling for VecGraph {
540	type Label = usize;
541	type Lender<'a>
542	= IteratorImpl<'a, Self>
543	where
544	Self: 'a;
545
546	#[inline(always)]
547	fn num_nodes(&self) -> usize {	10,740✔
548	self.0.num_nodes()	21,480✔
549	}
550
551	#[inline(always)]
552	fn num_arcs_hint(&self) -> Option<u64> {	13✔
553	self.0.num_arcs_hint()	26✔
554	}
555
556	#[inline(always)]
557	fn iter_from(&self, from: usize) -> Self::Lender<'_> {	138✔
558	IteratorImpl {
559	labeling: self,
560	nodes: (from..self.num_nodes()),	276✔
561	}
562	}
563	}
564
565	impl SequentialGraph for VecGraph {}
566
567	impl RandomAccessLabeling for VecGraph {
568	type Labels<'succ> = AssumeSortedIterator<
569	core::iter::Map<
570	core::iter::Copied<core::slice::Iter<'succ, LabeledArc<()>>>,
571	fn(LabeledArc<()>) -> usize,
572	>,
573	>;
574	#[inline(always)]
575	fn num_arcs(&self) -> u64 {	1,715✔
576	self.0.num_arcs()	3,430✔
577	}
578
579	#[inline(always)]
580	fn outdegree(&self, node: usize) -> usize {	791✔
581	self.0.outdegree(node)	2,373✔
582	}
583
584	#[inline(always)]
585	fn labels(&self, node: usize) -> <Self as RandomAccessLabeling>::Labels<'_> {	88,224✔
586	// this is safe as we maintain each vector of successors sorted
587	unsafe {
588	AssumeSortedIterator::new(self.0.succ[node].iter().copied().map(\|LabeledArc(x, _)\| x))	352,896✔
589	}
590	}
591	}
592
593	impl RandomAccessGraph for VecGraph {}
594
595	impl From<LabeledVecGraph<()>> for VecGraph {
596	fn from(g: LabeledVecGraph<()>) -> Self {	1,029✔
597	VecGraph(g)	1,029✔
598	}
599	}
600
601	impl SplitLabeling for VecGraph {
602	type SplitLender<'a>
603	= split::ra::Lender<'a, VecGraph>
604	where
605	Self: 'a;
606
607	type IntoIterator<'a>
608	= split::ra::IntoIterator<'a, VecGraph>
609	where
610	Self: 'a;
611
612	fn split_iter(&self, how_many: usize) -> Self::IntoIterator<'_> {	4✔
613	split::ra::Iter::new(self, how_many)	12✔
614	}
615	}
616
617	#[cfg(test)]
618	mod test {
619	use super::*;
620	#[test]
621	fn test_vec_graph() {
622	let mut arcs = vec![
623	((0, 1), Some(1.0)),
624	((0, 2), None),
625	((1, 2), Some(2.0)),
626	((2, 4), Some(f64::INFINITY)),
627	((3, 4), Some(f64::NEG_INFINITY)),
628	((1, 3), Some(f64::NAN)),
629	];
630	let g = LabeledVecGraph::<_>::from_arcs(arcs.iter().copied());
631	assert_ne!(
632	g, g,
633	"The label contains a NaN which is not equal to itself so the graph must be not equal to itself"
634	);
635
636	arcs.pop();
637	let g = LabeledVecGraph::<_>::from_arcs(arcs);
638	assert_eq!(g, g, "Without NaN the graph should be equal to itself");
639	}
640	}

vigna / webgraph-rs / 19278972970

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous