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

58.7

/webgraph/src/graphs/union_graph.rs

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

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

/// A wrapper exhibiting the union of two graphs.
#[derive(Debug, Clone)]
pub struct UnionGraph<G: SequentialGraph, H: SequentialGraph>(pub G, pub H);

impl<G: SequentialGraph, H: SequentialGraph> SequentialLabeling for UnionGraph<G, H>
where
    for<'a> G::Lender<'a>: SortedLender,
    for<'a, 'b> LenderIntoIter<'b, G::Lender<'a>>: SortedIterator,
    for<'a> H::Lender<'a>: SortedLender,
    for<'a, 'b> LenderIntoIter<'b, H::Lender<'a>>: SortedIterator,
{
    type Label = usize;
    type Lender<'b>
        = NodeLabels<G::Lender<'b>, H::Lender<'b>>
    where
        Self: 'b;

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

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

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

impl<G: SequentialGraph, H: SequentialGraph> SplitLabeling for UnionGraph<G, H>
where
    for<'a> G::Lender<'a>: SortedLender + Clone + Send + Sync,
    for<'a, 'b> LenderIntoIter<'b, G::Lender<'a>>: SortedIterator,
    for<'a> H::Lender<'a>: SortedLender + Clone + Send + Sync,
    for<'a, 'b> LenderIntoIter<'b, H::Lender<'a>>: SortedIterator,
{
    type SplitLender<'a>
        = split::seq::Lender<'a, UnionGraph<G, H>>
    where
        Self: 'a;
    type IntoIterator<'a>
        = split::seq::IntoIterator<'a, UnionGraph<G, H>>
    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, H: SequentialGraph> SequentialGraph for UnionGraph<G, H>
where
    for<'a> G::Lender<'a>: SortedLender + Clone,
    for<'a, 'b> LenderIntoIter<'b, G::Lender<'a>>: SortedIterator,
    for<'a> H::Lender<'a>: SortedLender + Clone,
    for<'a, 'b> LenderIntoIter<'b, H::Lender<'a>>: SortedIterator,
{
}

/// Convenience implementation that makes it possible to iterate
/// over the graph using the [`for_`] macro
/// (see the [crate documentation](crate)).
impl<'c, G: SequentialGraph, H: SequentialGraph> IntoLender for &'c UnionGraph<G, H>
where
    for<'a> G::Lender<'a>: SortedLender + Clone,
    for<'a, 'b> LenderIntoIter<'b, G::Lender<'a>>: SortedIterator,
    for<'a> H::Lender<'a>: SortedLender + Clone,
    for<'a, 'b> LenderIntoIter<'b, H::Lender<'a>>: SortedIterator,
{
    type Lender = <UnionGraph<G, H> as SequentialLabeling>::Lender<'c>;

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

#[doc(hidden)]
#[derive(Debug, Clone)]
pub struct NodeLabels<L, M>(L, M);

impl<L, M> NodeLabels<L, M> {
    /// Creates a new [`NodeLabels`] lender merging two lenders.
    pub fn new(left: L, right: M) -> Self {
        Self(left, right)
    }
}

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

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

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

    #[inline(always)]
    fn next(&mut self) -> Option<Lend<'_, Self>> {
        let (node0, iter0) = self.0.next().unzip();
        let (node1, iter1) = self.1.next().unzip();
        Some((
            node0.or(node1)?,
            Succ::new(
                iter0.map(IntoIterator::into_iter),
                iter1.map(IntoIterator::into_iter),
            ),
        ))
    }

    #[inline(always)]
    fn size_hint(&self) -> (usize, Option<usize>) {
        let (min0, max0) = self.0.size_hint();
        let (min1, max1) = self.1.size_hint();
        (
            min0.max(min1),
            match (max0, max1) {
                (None, None) => None,
                (Some(max), None) => Some(max),
                (None, Some(max)) => Some(max),
                (Some(max0), Some(max1)) => Some(max0.max(max1)),
            },
        )
    }
}

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

// SAFETY: the merge of two sorted lenders produces a sorted lender.
unsafe impl<
    L: Lender + for<'next> NodeLabelsLender<'next, Label = usize> + SortedLender,
    M: Lender + for<'next> NodeLabelsLender<'next, Label = usize> + SortedLender,
> SortedLender for NodeLabels<L, M>
{
}

#[derive(Debug, Clone)]
pub struct Succ<I: Iterator<Item = usize>, J: Iterator<Item = usize>> {
    iter0: Option<core::iter::Peekable<I>>,
    iter1: Option<core::iter::Peekable<J>>,
}

impl<I: Iterator<Item = usize>, J: Iterator<Item = usize>> Succ<I, J> {
    pub fn new(iter0: Option<I>, iter1: Option<J>) -> Self {
        Self {
            iter0: iter0.map(Iterator::peekable),
            iter1: iter1.map(Iterator::peekable),
        }
    }
}
impl<I: Iterator<Item = usize>, J: Iterator<Item = usize>> Iterator for Succ<I, J> {
    type Item = usize;
    #[inline(always)]
    fn next(&mut self) -> Option<Self::Item> {
        let next0 = self.iter0.as_mut().and_then(|iter| iter.peek().copied());
        let next1 = self.iter1.as_mut().and_then(|iter| iter.peek().copied());
        match next0
            .unwrap_or(usize::MAX)
            .cmp(&next1.unwrap_or(usize::MAX))
        {
            std::cmp::Ordering::Greater => self.iter1.as_mut().and_then(Iterator::next),
            std::cmp::Ordering::Less => self.iter0.as_mut().and_then(Iterator::next),
            std::cmp::Ordering::Equal => {
                self.iter0.as_mut().and_then(Iterator::next);
                self.iter1.as_mut().and_then(Iterator::next)
            }
        }
    }
}

// SAFETY: the merge of two sorted iterators produces a sorted iterator.
unsafe impl<I: Iterator<Item = usize> + SortedIterator, J: Iterator<Item = usize> + SortedIterator>
    SortedIterator for Succ<I, J>
{
}

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

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_union_graph() -> anyhow::Result<()> {
        use crate::graphs::vec_graph::VecGraph;
        let g = [
            VecGraph::from_arcs([
                (0, 1),
                (0, 3),
                (1, 2),
                (2, 0),
                (2, 2),
                (2, 4),
                (3, 4),
                (3, 5),
                (4, 1),
            ]),
            VecGraph::from_arcs([
                (1, 2),
                (1, 3),
                (2, 1),
                (2, 3),
                (2, 4),
                (4, 0),
                (5, 1),
                (5, 2),
                (6, 6),
            ]),
        ];
        for i in 0..2 {
            let union = UnionGraph(g[i].clone(), g[1 - i].clone());
            assert_eq!(union.num_nodes(), 7);

            let mut iter = union.iter();
            let Some((x, s)) = iter.next() else { panic!() };
            assert_eq!(x, 0);
            assert_eq!(s.collect::<Vec<_>>(), vec![1, 3]);
            let Some((x, s)) = iter.next() else { panic!() };
            assert_eq!(x, 1);
            assert_eq!(s.collect::<Vec<_>>(), vec![2, 3]);
            let Some((x, s)) = iter.next() else { panic!() };
            assert_eq!(x, 2);
            assert_eq!(s.collect::<Vec<_>>(), vec![0, 1, 2, 3, 4]);
            let Some((x, s)) = iter.next() else { panic!() };
            assert_eq!(x, 3);
            assert_eq!(s.collect::<Vec<_>>(), vec![4, 5]);
            let Some((x, s)) = iter.next() else { panic!() };
            assert_eq!(x, 4);
            assert_eq!(s.collect::<Vec<_>>(), vec![0, 1]);
            let Some((x, s)) = iter.next() else { panic!() };
            assert_eq!(x, 5);
            assert_eq!(s.collect::<Vec<_>>(), vec![1, 2]);
            let Some((x, s)) = iter.next() else { panic!() };
            assert_eq!(x, 6);
            assert_eq!(s.collect::<Vec<_>>(), vec![6]);
            assert!(iter.next().is_none());
        }
        Ok(())
    }
}

1	/*
2	* SPDX-FileCopyrightText: 2023 Sebastiano Vigna
3	*
4	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
5	*/
6
7	use crate::prelude::*;
8	use lender::*;
9
10	/// A wrapper exhibiting the union of two graphs.
11	#[derive(Debug, Clone)]
12	pub struct UnionGraph<G: SequentialGraph, H: SequentialGraph>(pub G, pub H);
13
14	impl<G: SequentialGraph, H: SequentialGraph> SequentialLabeling for UnionGraph<G, H>
15	where
16	for<'a> G::Lender<'a>: SortedLender,
17	for<'a, 'b> LenderIntoIter<'b, G::Lender<'a>>: SortedIterator,
18	for<'a> H::Lender<'a>: SortedLender,
19	for<'a, 'b> LenderIntoIter<'b, H::Lender<'a>>: SortedIterator,
20	{
21	type Label = usize;
22	type Lender<'b>
23	= NodeLabels<G::Lender<'b>, H::Lender<'b>>
24	where
25	Self: 'b;
26
27	#[inline(always)]
28	fn num_nodes(&self) -> usize {	5✔
29	self.0.num_nodes().max(self.1.num_nodes())	25✔
30	}
31
32	#[inline(always)]
33	fn num_arcs_hint(&self) -> Option<u64> {	1✔
34	None	1✔
35	}
36
37	#[inline(always)]
38	fn iter_from(&self, from: usize) -> Self::Lender<'_> {	4✔
39	NodeLabels(
40	self.0.iter_from(from.min(self.0.num_nodes())),	28✔
41	self.1.iter_from(from.min(self.1.num_nodes())),	20✔
42	)
43	}
44	}
45
46	impl<G: SequentialGraph, H: SequentialGraph> SplitLabeling for UnionGraph<G, H>
47	where
48	for<'a> G::Lender<'a>: SortedLender + Clone + Send + Sync,
49	for<'a, 'b> LenderIntoIter<'b, G::Lender<'a>>: SortedIterator,
50	for<'a> H::Lender<'a>: SortedLender + Clone + Send + Sync,
51	for<'a, 'b> LenderIntoIter<'b, H::Lender<'a>>: SortedIterator,
52	{
53	type SplitLender<'a>
54	= split::seq::Lender<'a, UnionGraph<G, H>>
55	where
56	Self: 'a;
57	type IntoIterator<'a>
58	= split::seq::IntoIterator<'a, UnionGraph<G, H>>
59	where
60	Self: 'a;
61
62	fn split_iter_at(&self, cutpoints: impl IntoIterator<Item = usize>) -> Self::IntoIterator<'_> {	×
63	split::seq::Iter::new(self.iter(), cutpoints)	×
64	}
65	}
66
67	impl<G: SequentialGraph, H: SequentialGraph> SequentialGraph for UnionGraph<G, H>
68	where
69	for<'a> G::Lender<'a>: SortedLender + Clone,
70	for<'a, 'b> LenderIntoIter<'b, G::Lender<'a>>: SortedIterator,
71	for<'a> H::Lender<'a>: SortedLender + Clone,
72	for<'a, 'b> LenderIntoIter<'b, H::Lender<'a>>: SortedIterator,
73	{
74	}
75
76	/// Convenience implementation that makes it possible to iterate
77	/// over the graph using the [`for_`] macro
78	/// (see the [crate documentation](crate)).
79	impl<'c, G: SequentialGraph, H: SequentialGraph> IntoLender for &'c UnionGraph<G, H>
80	where
81	for<'a> G::Lender<'a>: SortedLender + Clone,
82	for<'a, 'b> LenderIntoIter<'b, G::Lender<'a>>: SortedIterator,
83	for<'a> H::Lender<'a>: SortedLender + Clone,
84	for<'a, 'b> LenderIntoIter<'b, H::Lender<'a>>: SortedIterator,
85	{
86	type Lender = <UnionGraph<G, H> as SequentialLabeling>::Lender<'c>;
87
88	#[inline(always)]
89	fn into_lender(self) -> Self::Lender {	×
90	self.iter()	×
91	}
92	}
93
94	#[doc(hidden)]
95	#[derive(Debug, Clone)]
96	pub struct NodeLabels<L, M>(L, M);
97
98	impl<L, M> NodeLabels<L, M> {
99	/// Creates a new [`NodeLabels`] lender merging two lenders.
100	pub fn new(left: L, right: M) -> Self {	×
101	Self(left, right)	×
102	}
103	}
104
105	impl<
106	'succ,
107	L: Lender + for<'next> NodeLabelsLender<'next, Label = usize>,
108	M: Lender + for<'next> NodeLabelsLender<'next, Label = usize>,
109	> NodeLabelsLender<'succ> for NodeLabels<L, M>
110	{
111	type Label = usize;
112	type IntoIterator = Succ<LenderIntoIter<'succ, L>, LenderIntoIter<'succ, M>>;
113	}
114
115	impl<
116	'succ,
117	L: Lender + for<'next> NodeLabelsLender<'next, Label = usize>,
118	M: Lender + for<'next> NodeLabelsLender<'next, Label = usize>,
119	> Lending<'succ> for NodeLabels<L, M>
120	{
121	type Lend = (usize, <Self as NodeLabelsLender<'succ>>::IntoIterator);
122	}
123
124	impl<
125	L: Lender + for<'next> NodeLabelsLender<'next, Label = usize>,
126	M: Lender + for<'next> NodeLabelsLender<'next, Label = usize>,
127	> Lender for NodeLabels<L, M>
128	{
129	// SAFETY: the lend is covariant as it contains only a usize and an iterator
130	// over usize values derived from the underlying lenders L and M.
131	unsafe_assume_covariance!();
132
133	#[inline(always)]
134	fn next(&mut self) -> Option<Lend<'_, Self>> {	325,586✔
135	let (node0, iter0) = self.0.next().unzip();	1,302,344✔
136	let (node1, iter1) = self.1.next().unzip();	1,302,344✔
137	Some((	×
138	node0.or(node1)?,	976,764✔
139	Succ::new(	325,580✔
140	iter0.map(IntoIterator::into_iter),	651,160✔
141	iter1.map(IntoIterator::into_iter),	651,160✔
142	),
143	))
144	}
145
146	#[inline(always)]
147	fn size_hint(&self) -> (usize, Option<usize>) {	×
148	let (min0, max0) = self.0.size_hint();	×
149	let (min1, max1) = self.1.size_hint();	×
150	(
151	min0.max(min1),	×
152	match (max0, max1) {	×
153	(None, None) => None,	×
154	(Some(max), None) => Some(max),	×
155	(None, Some(max)) => Some(max),	×
156	(Some(max0), Some(max1)) => Some(max0.max(max1)),	×
157	},
158	)
159	}
160	}
161
162	impl<
163	L: Lender + for<'next> NodeLabelsLender<'next, Label = usize> + ExactSizeLender,
164	M: Lender + for<'next> NodeLabelsLender<'next, Label = usize> + ExactSizeLender,
165	> ExactSizeLender for NodeLabels<L, M>
166	{
167	#[inline(always)]
168	fn len(&self) -> usize {	×
169	self.0.len().max(self.1.len())	×
170	}
171	}
172
173	// SAFETY: the merge of two sorted lenders produces a sorted lender.
174	unsafe impl<
175	L: Lender + for<'next> NodeLabelsLender<'next, Label = usize> + SortedLender,
176	M: Lender + for<'next> NodeLabelsLender<'next, Label = usize> + SortedLender,
177	> SortedLender for NodeLabels<L, M>
178	{
179	}
180
181	#[derive(Debug, Clone)]
182	pub struct Succ<I: Iterator<Item = usize>, J: Iterator<Item = usize>> {
183	iter0: Option<core::iter::Peekable<I>>,
184	iter1: Option<core::iter::Peekable<J>>,
185	}
186
187	impl<I: Iterator<Item = usize>, J: Iterator<Item = usize>> Succ<I, J> {
188	pub fn new(iter0: Option<I>, iter1: Option<J>) -> Self {	325,580✔
189	Self {
190	iter0: iter0.map(Iterator::peekable),	976,740✔
191	iter1: iter1.map(Iterator::peekable),	325,580✔
192	}
193	}
194	}
195	impl<I: Iterator<Item = usize>, J: Iterator<Item = usize>> Iterator for Succ<I, J> {
196	type Item = usize;
197	#[inline(always)]
198	fn next(&mut self) -> Option<Self::Item> {	3,541,772✔
199	let next0 = self.iter0.as_mut().and_then(\|iter\| iter.peek().copied());	24,792,389✔
200	let next1 = self.iter1.as_mut().and_then(\|iter\| iter.peek().copied());	24,792,398✔
201	match next0	7,083,544✔
202	.unwrap_or(usize::MAX)	7,083,544✔
203	.cmp(&next1.unwrap_or(usize::MAX))	7,083,544✔
204	{
205	std::cmp::Ordering::Greater => self.iter1.as_mut().and_then(Iterator::next),	54✔
206	std::cmp::Ordering::Less => self.iter0.as_mut().and_then(Iterator::next),	51✔
207	std::cmp::Ordering::Equal => {	×
208	self.iter0.as_mut().and_then(Iterator::next);	10,625,211✔
209	self.iter1.as_mut().and_then(Iterator::next)	10,625,211✔
210	}
211	}
212	}
213	}
214
215	// SAFETY: the merge of two sorted iterators produces a sorted iterator.
216	unsafe impl<I: Iterator<Item = usize> + SortedIterator, J: Iterator<Item = usize> + SortedIterator>
217	SortedIterator for Succ<I, J>
218	{
219	}
220
221	impl<I: Iterator<Item = usize>, J: Iterator<Item = usize>> std::iter::FusedIterator for Succ<I, J> {}
222
223	#[cfg(test)]
224	mod tests {
225	use super::*;
226
227	#[test]
228	fn test_union_graph() -> anyhow::Result<()> {
229	use crate::graphs::vec_graph::VecGraph;
230	let g = [
231	VecGraph::from_arcs([
232	(0, 1),
233	(0, 3),
234	(1, 2),
235	(2, 0),
236	(2, 2),
237	(2, 4),
238	(3, 4),
239	(3, 5),
240	(4, 1),
241	]),
242	VecGraph::from_arcs([
243	(1, 2),
244	(1, 3),
245	(2, 1),
246	(2, 3),
247	(2, 4),
248	(4, 0),
249	(5, 1),
250	(5, 2),
251	(6, 6),
252	]),
253	];
254	for i in 0..2 {
255	let union = UnionGraph(g[i].clone(), g[1 - i].clone());
256	assert_eq!(union.num_nodes(), 7);
257
258	let mut iter = union.iter();
259	let Some((x, s)) = iter.next() else { panic!() };
260	assert_eq!(x, 0);
261	assert_eq!(s.collect::<Vec<_>>(), vec![1, 3]);
262	let Some((x, s)) = iter.next() else { panic!() };
263	assert_eq!(x, 1);
264	assert_eq!(s.collect::<Vec<_>>(), vec![2, 3]);
265	let Some((x, s)) = iter.next() else { panic!() };
266	assert_eq!(x, 2);
267	assert_eq!(s.collect::<Vec<_>>(), vec![0, 1, 2, 3, 4]);
268	let Some((x, s)) = iter.next() else { panic!() };
269	assert_eq!(x, 3);
270	assert_eq!(s.collect::<Vec<_>>(), vec![4, 5]);
271	let Some((x, s)) = iter.next() else { panic!() };
272	assert_eq!(x, 4);
273	assert_eq!(s.collect::<Vec<_>>(), vec![0, 1]);
274	let Some((x, s)) = iter.next() else { panic!() };
275	assert_eq!(x, 5);
276	assert_eq!(s.collect::<Vec<_>>(), vec![1, 2]);
277	let Some((x, s)) = iter.next() else { panic!() };
278	assert_eq!(x, 6);
279	assert_eq!(s.collect::<Vec<_>>(), vec![6]);
280	assert!(iter.next().is_none());
281	}
282	Ok(())
283	}
284	}

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