23365769388

Committed 20 Mar 2026 10:52PM UTC coverage: 68.228% (-3.0%) from 71.245%

Build # 23365769388

Build Type

push

github

Committed by

vigna

Commit Message

No le_bins,be_bins for webgraph

Coverage Stats

6655 of 9754 relevant lines covered (68.23%)

46582760.24 hits per line

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

68.0

/webgraph/src/graphs/no_selfloops_graph.rs

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

use crate::prelude::*;
use lender::*;

/// A wrapper that removes self-loops from a graph. Since we don't
/// know how many self-loops there are, we can't provide an exact
/// number of arcs or outdegree for each node. Therefore, we can't
/// implement random access to the successors.
#[derive(Debug, Clone)]
pub struct NoSelfLoopsGraph<G>(pub G);

impl<G: SequentialGraph> SequentialLabeling for NoSelfLoopsGraph<G> {
    type Label = usize;
    type Lender<'b>
        = NodeLabels<G::Lender<'b>>
    where
        Self: 'b;

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

    #[inline(always)]
    fn num_arcs_hint(&self) -> Option<u64> {
        // it's just a hint, and we don't know how many self-loops there are
        self.0.num_arcs_hint()
    }

    #[inline(always)]
    fn iter_from(&self, from: usize) -> Self::Lender<'_> {
        NodeLabels {
            iter: self.0.iter_from(from),
        }
    }
}

impl<G: SequentialGraph + SplitLabeling> SplitLabeling for NoSelfLoopsGraph<G>
where
    for<'a> <G as SequentialLabeling>::Lender<'a>: Clone + Send + Sync,
{
    type SplitLender<'a>
        = split::seq::Lender<'a, NoSelfLoopsGraph<G>>
    where
        Self: 'a;
    type IntoIterator<'a>
        = split::seq::IntoIterator<'a, NoSelfLoopsGraph<G>>
    where
        Self: 'a;

    fn split_iter_at(&self, cutpoints: impl IntoIterator<Item = usize>) -> Self::IntoIterator<'_> {
        split::seq::Iter::new(self.iter(), cutpoints)
    }
}

impl<G: SequentialGraph> SequentialGraph for NoSelfLoopsGraph<G> {}

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

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

#[derive(Debug, Clone)]
pub struct NodeLabels<I> {
    iter: I,
}

impl<I> NodeLabels<I> {
    /// Creates a new [`NodeLabels`] lender filtering out self-loops.
    pub fn new(iter: I) -> Self {
        Self { iter }
    }
}

impl<'succ, I: Lender + for<'next> NodeLabelsLender<'next, Label = usize>> NodeLabelsLender<'succ>
    for NodeLabels<I>
{
    type Label = usize;
    type IntoIterator = Succ<LenderIntoIter<'succ, I>>;
}

impl<'succ, I: Lender + for<'next> NodeLabelsLender<'next, Label = usize>> Lending<'succ>
    for NodeLabels<I>
{
    type Lend = (usize, <Self as NodeLabelsLender<'succ>>::IntoIterator);
}

// SAFETY: removing self-loops preserves the sorted order of the underlying lender.
unsafe impl<I: SortedLender + Lender + for<'next> NodeLabelsLender<'next, Label = usize>>
    SortedLender for NodeLabels<I>
{
}

impl<L: Lender + for<'next> NodeLabelsLender<'next, Label = usize>> Lender for NodeLabels<L> {
    // SAFETY: the lend is covariant as it contains only a usize and an iterator
    // over usize values derived from the underlying lender L.
    unsafe_assume_covariance!();

    #[inline(always)]
    fn next(&mut self) -> Option<Lend<'_, Self>> {
        self.iter.next().map(|x| {
            let (node, succ) = x.into_pair();
            (
                node,
                Succ {
                    src: node,
                    iter: succ.into_iter(),
                },
            )
        })
    }
}

impl<L: ExactSizeLender + for<'next> NodeLabelsLender<'next, Label = usize>> ExactSizeLender
    for NodeLabels<L>
{
    #[inline(always)]
    fn len(&self) -> usize {
        self.iter.len()
    }
}

#[derive(Debug, Clone)]
pub struct Succ<I: Iterator<Item = usize>> {
    src: usize,
    iter: I,
}

impl<I: Iterator<Item = usize>> Iterator for Succ<I> {
    type Item = usize;
    #[inline(always)]
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let dst = self.iter.next()?;
            if dst != self.src {
                return Some(dst);
            }
        }
    }
}

// SAFETY: removing self-loops preserves the sorted order of the underlying iterator.
unsafe impl<I: Iterator<Item = usize> + SortedIterator> SortedIterator for Succ<I> {}

impl<I: Iterator<Item = usize> + std::iter::FusedIterator> std::iter::FusedIterator for Succ<I> {}

#[cfg(test)]
#[test]
fn test_no_self_loops_graph() -> anyhow::Result<()> {
    use crate::graphs::vec_graph::VecGraph;
    let g = VecGraph::from_arcs([(0, 1), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]);
    let p = NoSelfLoopsGraph(g);
    assert_eq!(p.num_nodes(), 3);

    let mut iter = p.iter();
    assert_eq!(iter.next().unwrap().1.collect::<Vec<_>>(), vec![1]);
    assert_eq!(iter.next().unwrap().1.collect::<Vec<_>>(), vec![2]);
    assert_eq!(iter.next().unwrap().1.collect::<Vec<_>>(), vec![0, 1]);
    assert!(iter.next().is_none());

    Ok(())
}

1	/*
2	* SPDX-FileCopyrightText: 2024 Tommaso Fontana
3	* SPDX-FileCopyrightText: 2025 Sebastiano Vigna
4	*
5	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
6	*/
7
8	use crate::prelude::*;
9	use lender::*;
10
11	/// A wrapper that removes self-loops from a graph. Since we don't
12	/// know how many self-loops there are, we can't provide an exact
13	/// number of arcs or outdegree for each node. Therefore, we can't
14	/// implement random access to the successors.
15	#[derive(Debug, Clone)]
16	pub struct NoSelfLoopsGraph<G>(pub G);
17
18	impl<G: SequentialGraph> SequentialLabeling for NoSelfLoopsGraph<G> {
19	type Label = usize;
20	type Lender<'b>
21	= NodeLabels<G::Lender<'b>>
22	where
23	Self: 'b;
24
25	#[inline(always)]
26	fn num_nodes(&self) -> usize {	3✔
27	self.0.num_nodes()	6✔
28	}
29
30	#[inline(always)]
31	fn num_arcs_hint(&self) -> Option<u64> {	×
32	// it's just a hint, and we don't know how many self-loops there are
33	self.0.num_arcs_hint()	×
34	}
35
36	#[inline(always)]
37	fn iter_from(&self, from: usize) -> Self::Lender<'_> {	2✔
38	NodeLabels {
39	iter: self.0.iter_from(from),	4✔
40	}
41	}
42	}
43
44	impl<G: SequentialGraph + SplitLabeling> SplitLabeling for NoSelfLoopsGraph<G>
45	where
46	for<'a> <G as SequentialLabeling>::Lender<'a>: Clone + Send + Sync,
47	{
48	type SplitLender<'a>
49	= split::seq::Lender<'a, NoSelfLoopsGraph<G>>
50	where
51	Self: 'a;
52	type IntoIterator<'a>
53	= split::seq::IntoIterator<'a, NoSelfLoopsGraph<G>>
54	where
55	Self: 'a;
56
57	fn split_iter_at(&self, cutpoints: impl IntoIterator<Item = usize>) -> Self::IntoIterator<'_> {	×
58	split::seq::Iter::new(self.iter(), cutpoints)	×
59	}
60	}
61
62	impl<G: SequentialGraph> SequentialGraph for NoSelfLoopsGraph<G> {}
63
64	/// Convenience implementation that makes it possible to iterate
65	/// over the graph using the [`for_`] macro
66	/// (see the [crate documentation](crate)).
67	impl<'b, G: SequentialGraph> IntoLender for &'b NoSelfLoopsGraph<G> {
68	type Lender = <NoSelfLoopsGraph<G> as SequentialLabeling>::Lender<'b>;
69
70	#[inline(always)]
71	fn into_lender(self) -> Self::Lender {	1✔
72	self.iter()	2✔
73	}
74	}
75
76	#[derive(Debug, Clone)]
77	pub struct NodeLabels<I> {
78	iter: I,
79	}
80
81	impl<I> NodeLabels<I> {
82	/// Creates a new [`NodeLabels`] lender filtering out self-loops.
83	pub fn new(iter: I) -> Self {	×
84	Self { iter }
85	}
86	}
87
88	impl<'succ, I: Lender + for<'next> NodeLabelsLender<'next, Label = usize>> NodeLabelsLender<'succ>
89	for NodeLabels<I>
90	{
91	type Label = usize;
92	type IntoIterator = Succ<LenderIntoIter<'succ, I>>;
93	}
94
95	impl<'succ, I: Lender + for<'next> NodeLabelsLender<'next, Label = usize>> Lending<'succ>
96	for NodeLabels<I>
97	{
98	type Lend = (usize, <Self as NodeLabelsLender<'succ>>::IntoIterator);
99	}
100
101	// SAFETY: removing self-loops preserves the sorted order of the underlying lender.
102	unsafe impl<I: SortedLender + Lender + for<'next> NodeLabelsLender<'next, Label = usize>>
103	SortedLender for NodeLabels<I>
104	{
105	}
106
107	impl<L: Lender + for<'next> NodeLabelsLender<'next, Label = usize>> Lender for NodeLabels<L> {
108	// SAFETY: the lend is covariant as it contains only a usize and an iterator
109	// over usize values derived from the underlying lender L.
110	unsafe_assume_covariance!();
111
112	#[inline(always)]
113	fn next(&mut self) -> Option<Lend<'_, Self>> {	15✔
114	self.iter.next().map(\|x\| {	56✔
115	let (node, succ) = x.into_pair();	33✔
116	(
117	node,	22✔
118	Succ {	11✔
119	src: node,	22✔
120	iter: succ.into_iter(),	11✔
121	},
122	)
123	})
124	}
125	}
126
127	impl<L: ExactSizeLender + for<'next> NodeLabelsLender<'next, Label = usize>> ExactSizeLender
128	for NodeLabels<L>
129	{
130	#[inline(always)]
131	fn len(&self) -> usize {	×
132	self.iter.len()	×
133	}
134	}
135
136	#[derive(Debug, Clone)]
137	pub struct Succ<I: Iterator<Item = usize>> {
138	src: usize,
139	iter: I,
140	}
141
142	impl<I: Iterator<Item = usize>> Iterator for Succ<I> {
143	type Item = usize;
144	#[inline(always)]
145	fn next(&mut self) -> Option<Self::Item> {	13✔
146	loop {	×
147	let dst = self.iter.next()?;	54✔
148	if dst != self.src {	12✔
149	return Some(dst);	7✔
150	}
151	}
152	}
153	}
154
155	// SAFETY: removing self-loops preserves the sorted order of the underlying iterator.
156	unsafe impl<I: Iterator<Item = usize> + SortedIterator> SortedIterator for Succ<I> {}
157
158	impl<I: Iterator<Item = usize> + std::iter::FusedIterator> std::iter::FusedIterator for Succ<I> {}
159
160	#[cfg(test)]
161	#[test]
162	fn test_no_self_loops_graph() -> anyhow::Result<()> {
163	use crate::graphs::vec_graph::VecGraph;
164	let g = VecGraph::from_arcs([(0, 1), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)]);
165	let p = NoSelfLoopsGraph(g);
166	assert_eq!(p.num_nodes(), 3);
167
168	let mut iter = p.iter();
169	assert_eq!(iter.next().unwrap().1.collect::<Vec<_>>(), vec![1]);
170	assert_eq!(iter.next().unwrap().1.collect::<Vec<_>>(), vec![2]);
171	assert_eq!(iter.next().unwrap().1.collect::<Vec<_>>(), vec![0, 1]);
172	assert!(iter.next().is_none());
173
174	Ok(())
175	}

vigna / webgraph-rs / 23365769388

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