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

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

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