18008720487

Committed 25 Sep 2025 01:16PM UTC coverage: 49.589% (-0.4%) from 49.949%

Build # 18008720487

Build Type

push

github

Committed by

vigna

Commit Message

Fixed fuzzing code for new epserde

Run Details

0 of 2 new or added lines in 1 file covered. (0.0%)

650 existing lines in 25 files now uncovered.

3862 of 7788 relevant lines covered (49.59%)

25127316.85 hits per line

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

61.59

/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)]
pub struct LabelledArc<L>(usize, L);

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

impl<L> From<LabelledArc<L>> for (usize, L) {
    fn from(value: LabelledArc<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.
    number_of_arcs: u64,
    /// For each node, its list of successors.
    succ: Vec<Vec<LabelledArc<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 {
            number_of_arcs: 0,
            succ: vec![],
        }
    }

    /// Creates a new empty graph with `n` nodes.
    pub fn empty(n: usize) -> Self {
        Self {
            number_of_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.number_of_arcs += 1;
            }
            Some(LabelledArc(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.number_of_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 labeled arcs from an [`IntoIterator`], adding new nodes as needed.
    ///
    /// The items must be triples 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, x.1));
        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 triples 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()),
        }
    }
}

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, LabelledArc<L>>>,
            fn(LabelledArc<L>) -> (usize, L),
        >,
    >;
    #[inline(always)]
    fn num_arcs(&self) -> u64 {
        self.number_of_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 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(|(u, v)| (u, v, ())));
    }

    /// 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();
    }
}

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

vigna / webgraph-rs / 18008720487

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