19383593169

Committed 15 Nov 2025 03:16AM UTC coverage: 62.139% (-0.06%) from 62.201%

Build # 19383593169

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #156 from progval/edition2024

Switch webgraph to 2024 edition

Run Details

9 of 19 new or added lines in 6 files covered. (47.37%)

7 existing lines in 3 files now uncovered.

5247 of 8444 relevant lines covered (62.14%)

29479360.02 hits per line

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

76.19

/webgraph/src/transform/transpose.rs

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

use crate::graphs::arc_list_graph;
use crate::prelude::proj::Left;
use crate::prelude::sort_pairs::KMergeIters;
use crate::prelude::{LabeledSequentialGraph, SequentialGraph, SortPairs};
use crate::traits::graph::UnitLabelGraph;
use crate::traits::{NodeLabelsLender, SplitLabeling};
use crate::utils::{
    BatchCodec, CodecIter, DefaultBatchCodec, MemoryUsage, ParSortIters, SplitIters,
};
use anyhow::Result;
use dsi_progress_logger::prelude::*;
use lender::prelude::*;
use tempfile::Builder;

/// Returns the transpose of the provided labeled graph as a [sequential
/// graph](crate::traits::SequentialGraph).
///
/// For the meaning of the additional parameters, see [`SortPairs`].
#[allow(clippy::type_complexity)]
pub fn transpose_labeled<C: BatchCodec>(
    graph: &impl LabeledSequentialGraph<C::Label>,
    memory_usage: MemoryUsage,
    batch_codec: C,
) -> Result<arc_list_graph::ArcListGraph<KMergeIters<CodecIter<C>, C::Label>>>
where
    C::Label: Clone + 'static,
    CodecIter<C>: Clone + Send + Sync,
{
    let dir = Builder::new().prefix("transpose_").tempdir()?;
    let mut sorted = SortPairs::new_labeled(memory_usage, dir.path(), batch_codec)?;

    let mut pl = progress_logger![
        item_name = "node",
        expected_updates = Some(graph.num_nodes()),
        display_memory = true
    ];
    pl.start("Creating batches...");
    // create batches of sorted edges
    for_!( (src, succ) in graph.iter() {
        for (dst, l) in succ {
            sorted.push_labeled(dst, src, l)?;
        }
        pl.light_update();
    });
    // merge the batches
    let sorted = arc_list_graph::ArcListGraph::new_labeled(graph.num_nodes(), sorted.iter()?);
    pl.done();

    Ok(sorted)
}

/// Returns the transpose of the provided graph as a [sequential
/// graph](crate::traits::SequentialGraph).
///
/// For the meaning of the additional parameter, see [`SortPairs`].
pub fn transpose(
    graph: impl SequentialGraph,
    memory_usage: MemoryUsage,
) -> Result<Left<arc_list_graph::ArcListGraph<KMergeIters<CodecIter<DefaultBatchCodec>, ()>>>> {
    Ok(Left(transpose_labeled(
        &UnitLabelGraph(graph),
        memory_usage,
        DefaultBatchCodec::default(),
    )?))
}

/// Returns a [`SplitIters`] structure representing the
/// transpose of the provided labeled splittable graph.
///
/// The [`SplitIters`] structure can easily converted into a vector of `(node,
/// lender)` pairs using [this `From`
/// implementation](crate::prelude::SplitIters#impl-From<SplitIters<IT>-for-Vec<(usize,+Iter<L,+I>)>).
///
/// For the meaning of the additional parameters, see [`SortPairs`].
pub fn transpose_labeled_split<
    'graph,
    G: 'graph
        + LabeledSequentialGraph<C::Label>
        + for<'a> SplitLabeling<
            SplitLender<'a>: for<'b> NodeLabelsLender<
                'b,
                Label: crate::traits::Pair<Left = usize, Right = C::Label> + Copy,
                IntoIterator: IntoIterator<IntoIter: Send + Sync>,
            > + Send
                                 + Sync,
            IntoIterator<'a>: IntoIterator<IntoIter: Send + Sync>,
        >,
    C: BatchCodec + 'graph,
>(
    graph: &'graph G,
    memory_usage: MemoryUsage,
    batch_codec: C,
) -> Result<
    SplitIters<
        impl IntoIterator<Item = ((usize, usize), C::Label), IntoIter: Send + Sync> + use<'graph, G, C>,
    >,
>
where
    CodecIter<C>: Clone + Send + Sync,
{
    let par_sort_iters = ParSortIters::new(graph.num_nodes())?.memory_usage(memory_usage);
    let parts = num_cpus::get();

    let pairs: Vec<_> = graph
        .split_iter(parts)
        .into_iter()
        .map(|iter| iter.into_labeled_pairs().map(|((a, b), l)| ((b, a), l)))
        .collect();

    par_sort_iters.try_sort_labeled::<C, std::convert::Infallible, _>(batch_codec, pairs)
}

/// Returns a [`SplitIters`] structure representing the
/// transpose of the provided splittable graph.
///
/// The [`SplitIters`] structure can easily converted into a vector of `(node,
/// lender)` pairs using [this `From`
/// implementation](crate::prelude::SplitIters#impl-From<SplitIters<IT>-for-Vec<(usize,+LeftIterator<Iter<(),+Map<I,+fn((usize,+usize))+->+(usize,+usize,+())>)>).
///
/// For the meaning of the additional parameters, see [`SortPairs`].
pub fn transpose_split<
    'graph,
    G: 'graph
        + SequentialGraph
        + for<'a> SplitLabeling<
            SplitLender<'a>: for<'b> NodeLabelsLender<
                'b,
                Label = usize,
                IntoIterator: IntoIterator<IntoIter: Send + Sync>,
            > + Send
                                 + Sync,
            IntoIterator<'a>: IntoIterator<IntoIter: Send + Sync>,
        >,
>(
    graph: &'graph G,
    memory_usage: MemoryUsage,
) -> Result<
    SplitIters<impl IntoIterator<Item = (usize, usize), IntoIter: Send + Sync> + use<'graph, G>>,
> {
    let par_sort_iters = ParSortIters::new(graph.num_nodes())?.memory_usage(memory_usage);
    let parts = num_cpus::get();

    let pairs: Vec<_> = graph
        .split_iter(parts)
        .into_iter()
        .map(|iter| iter.into_pairs().map(|(src, dst)| ((dst, src), ())))
        .collect();

    let batch_codec = DefaultBatchCodec::default();
    let SplitIters { boundaries, iters } = par_sort_iters
        .try_sort_labeled::<DefaultBatchCodec, std::convert::Infallible, _>(batch_codec, pairs)?;

    Ok(SplitIters {
        boundaries,
        iters: Box::into_iter(iters)
            .map(|iter| iter.into_iter().map(|(pair, _)| pair))
            .collect::<Vec<_>>()
            .into_boxed_slice(),
    })
}

1	/*
2	* SPDX-FileCopyrightText: 2023 Inria
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::graphs::arc_list_graph;
9	use crate::prelude::proj::Left;
10	use crate::prelude::sort_pairs::KMergeIters;
11	use crate::prelude::{LabeledSequentialGraph, SequentialGraph, SortPairs};
12	use crate::traits::graph::UnitLabelGraph;
13	use crate::traits::{NodeLabelsLender, SplitLabeling};
14	use crate::utils::{
15	BatchCodec, CodecIter, DefaultBatchCodec, MemoryUsage, ParSortIters, SplitIters,
16	};
17	use anyhow::Result;
18	use dsi_progress_logger::prelude::*;
19	use lender::prelude::*;
20	use tempfile::Builder;
21
22	/// Returns the transpose of the provided labeled graph as a [sequential
23	/// graph](crate::traits::SequentialGraph).
24	///
25	/// For the meaning of the additional parameters, see [`SortPairs`].
26	#[allow(clippy::type_complexity)]
27	pub fn transpose_labeled<C: BatchCodec>(	99✔
28	graph: &impl LabeledSequentialGraph<C::Label>,
29	memory_usage: MemoryUsage,
30	batch_codec: C,
31	) -> Result<arc_list_graph::ArcListGraph<KMergeIters<CodecIter<C>, C::Label>>>
32	where
33	C::Label: Clone + 'static,
34	CodecIter<C>: Clone + Send + Sync,
35	{
36	let dir = Builder::new().prefix("transpose_").tempdir()?;	396✔
37	let mut sorted = SortPairs::new_labeled(memory_usage, dir.path(), batch_codec)?;	594✔
38
39	let mut pl = progress_logger![	198✔
40	item_name = "node",	×
41	expected_updates = Some(graph.num_nodes()),	99✔
42	display_memory = true	×
43	];
44	pl.start("Creating batches...");	198✔
45	// create batches of sorted edges
46	for_!( (src, succ) in graph.iter() {	11,047✔
47	for (dst, l) in succ {	526,445✔
48	sorted.push_labeled(dst, src, l)?;	868,450✔
49	}
50	pl.light_update();	10,750✔
51	});
52	// merge the batches
53	let sorted = arc_list_graph::ArcListGraph::new_labeled(graph.num_nodes(), sorted.iter()?);	594✔
54	pl.done();	198✔
55
56	Ok(sorted)	99✔
57	}
58
59	/// Returns the transpose of the provided graph as a [sequential
60	/// graph](crate::traits::SequentialGraph).
61	///
62	/// For the meaning of the additional parameter, see [`SortPairs`].
63	pub fn transpose(	97✔
64	graph: impl SequentialGraph,
65	memory_usage: MemoryUsage,
66	) -> Result<Left<arc_list_graph::ArcListGraph<KMergeIters<CodecIter<DefaultBatchCodec>, ()>>>> {
67	Ok(Left(transpose_labeled(	97✔
68	&UnitLabelGraph(graph),	97✔
69	memory_usage,	97✔
70	DefaultBatchCodec::default(),	97✔
71	)?))
72	}
73
74	/// Returns a [`SplitIters`] structure representing the
75	/// transpose of the provided labeled splittable graph.
76	///
77	/// The [`SplitIters`] structure can easily converted into a vector of `(node,
78	/// lender)` pairs using [this `From`
79	/// implementation](crate::prelude::SplitIters#impl-From<SplitIters<IT>-for-Vec<(usize,+Iter<L,+I>)>).
80	///
81	/// For the meaning of the additional parameters, see [`SortPairs`].
82	pub fn transpose_labeled_split<	×
83	'graph,
84	G: 'graph
85	+ LabeledSequentialGraph<C::Label>
86	+ for<'a> SplitLabeling<
87	SplitLender<'a>: for<'b> NodeLabelsLender<
88	'b,
89	Label: crate::traits::Pair<Left = usize, Right = C::Label> + Copy,
90	IntoIterator: IntoIterator<IntoIter: Send + Sync>,
91	> + Send
92	+ Sync,
93	IntoIterator<'a>: IntoIterator<IntoIter: Send + Sync>,
94	>,
95	C: BatchCodec + 'graph,
96	>(
97	graph: &'graph G,
98	memory_usage: MemoryUsage,
99	batch_codec: C,
100	) -> Result<
101	SplitIters<
102	impl IntoIterator<Item = ((usize, usize), C::Label), IntoIter: Send + Sync> + use<'graph, G, C>,
103	>,
104	>
105	where
106	CodecIter<C>: Clone + Send + Sync,
107	{
108	let par_sort_iters = ParSortIters::new(graph.num_nodes())?.memory_usage(memory_usage);	×
109	let parts = num_cpus::get();	×
110
111	let pairs: Vec<_> = graph	×
112	.split_iter(parts)	×
113	.into_iter()
114	.map(\|iter\| iter.into_labeled_pairs().map(\|((a, b), l)\| ((b, a), l)))	×
115	.collect();
116
NEW 117	par_sort_iters.try_sort_labeled::<C, std::convert::Infallible, _>(batch_codec, pairs)	×
118	}
119
120	/// Returns a [`SplitIters`] structure representing the
121	/// transpose of the provided splittable graph.
122	///
123	/// The [`SplitIters`] structure can easily converted into a vector of `(node,
124	/// lender)` pairs using [this `From`
125	/// implementation](crate::prelude::SplitIters#impl-From<SplitIters<IT>-for-Vec<(usize,+LeftIterator<Iter<(),+Map<I,+fn((usize,+usize))+->+(usize,+usize,+())>)>).
126	///
127	/// For the meaning of the additional parameters, see [`SortPairs`].
128	pub fn transpose_split<	1✔
129	'graph,
130	G: 'graph
131	+ SequentialGraph
132	+ for<'a> SplitLabeling<
133	SplitLender<'a>: for<'b> NodeLabelsLender<
134	'b,
135	Label = usize,
136	IntoIterator: IntoIterator<IntoIter: Send + Sync>,
137	> + Send
138	+ Sync,
139	IntoIterator<'a>: IntoIterator<IntoIter: Send + Sync>,
140	>,
141	>(
142	graph: &'graph G,
143	memory_usage: MemoryUsage,
144	) -> Result<
145	SplitIters<impl IntoIterator<Item = (usize, usize), IntoIter: Send + Sync> + use<'graph, G>>,
146	> {
147	let par_sort_iters = ParSortIters::new(graph.num_nodes())?.memory_usage(memory_usage);	6✔
148	let parts = num_cpus::get();	2✔
149
150	let pairs: Vec<_> = graph	3✔
151	.split_iter(parts)	2✔
152	.into_iter()
153	.map(\|iter\| iter.into_pairs().map(\|(src, dst)\| ((dst, src), ())))	25✔
154	.collect();
155
156	let batch_codec = DefaultBatchCodec::default();	2✔
157	let SplitIters { boundaries, iters } = par_sort_iters	3✔
158	.try_sort_labeled::<DefaultBatchCodec, std::convert::Infallible, _>(batch_codec, pairs)?;	3✔
159
160	Ok(SplitIters {	×
161	boundaries,	1✔
162	iters: Box::into_iter(iters)	2✔
163	.map(\|iter\| iter.into_iter().map(\|(pair, _)\| pair))	13✔
164	.collect::<Vec<_>>()	1✔
165	.into_boxed_slice(),	1✔
166	})
167	}

vigna / webgraph-rs / 19383593169

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