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

64.29

/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, SortedPairIter, 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, computed in parallel.
///
/// The [`SplitIters`] structure can be 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>)>).
///
/// Parallelism is controlled via the current Rayon thread pool. Please
/// [install](rayon::ThreadPool::install) a custom pool if you want to customize
/// the parallelism.
///
/// For the meaning of the additional parameters, see [`SortPairs`].
pub fn transpose_labeled_split<
    G: 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: &G,
    memory_usage: MemoryUsage,
    batch_codec: C,
    cutpoints: Option<Vec<usize>>,
) -> Result<SplitIters<KMergeIters<CodecIter<C>, C::Label>>>
where
    CodecIter<C>: Clone + Send + Sync,
{
    let mut par_sort_iters = ParSortIters::new(graph.num_nodes())?.memory_usage(memory_usage);
    if let Some(num_arcs) = graph.num_arcs_hint() {
        par_sort_iters = par_sort_iters.expected_num_pairs(num_arcs as usize);
    }

    let pairs: Vec<_> = match cutpoints {
        Some(cp) => graph.split_iter_at(cp),
        None => {
            let parts = rayon::current_num_threads();
            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, computed in parallel.
///
/// Parallelism is controlled via the current Rayon thread pool. Please
/// [install](rayon::ThreadPool::install) a custom pool if you want to customize
/// the parallelism.
///
/// The [`SplitIters`] structure can be 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<
    'g,
    G: SequentialGraph
        + for<'a> SplitLabeling<
            SplitLender<'g>: NodeLabelsLender<
                'a,
                IntoIterator: IntoIterator<IntoIter: Send + Sync>,
            >,
        >,
>(
    graph: &'g G,
    memory_usage: MemoryUsage,
    cutpoints: Option<Vec<usize>>,
) -> Result<SplitIters<SortedPairIter>> {
    let mut par_sort_iters = ParSortIters::new(graph.num_nodes())?.memory_usage(memory_usage);
    if let Some(num_arcs) = graph.num_arcs_hint() {
        par_sort_iters = par_sort_iters.expected_num_pairs(num_arcs as usize);
    }

    let pairs: Vec<_> = match cutpoints {
        Some(cp) => graph.split_iter_at(cp),
        None => {
            let parts = rayon::current_num_threads();
            graph.split_iter(parts)
        }
    }
    .into_iter()
    .map(|iter| iter.into_pairs().map(|(src, dst)| (dst, src)))
    .collect();

    par_sort_iters.sort(pairs)
}

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, SortedPairIter, 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>(	100✔
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()?;	400✔
37	let mut sorted = SortPairs::new_labeled(memory_usage, dir.path(), batch_codec)?;	600✔
38
39	let mut pl = progress_logger![	200✔
40	item_name = "node",	×
41	expected_updates = Some(graph.num_nodes()),	100✔
42	display_memory = true	×
43	];
44	pl.start("Creating batches...");	200✔
45	// create batches of sorted edges
46	for_!( (src, succ) in graph.iter() {	10,856✔
47	for (dst, l) in succ {	350,624✔
48	sorted.push_labeled(dst, src, l)?;	863,365✔
49	}
50	pl.light_update();	10,556✔
51	});
52	// merge the batches
53	let sorted = arc_list_graph::ArcListGraph::new_labeled(graph.num_nodes(), sorted.iter()?);	600✔
54	pl.done();	200✔
55
56	Ok(sorted)	100✔
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 transpose of the
75	/// provided labeled splittable graph, computed in parallel.
76	///
77	/// The [`SplitIters`] structure can be 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	/// Parallelism is controlled via the current Rayon thread pool. Please
82	/// [install](rayon::ThreadPool::install) a custom pool if you want to customize
83	/// the parallelism.
84	///
85	/// For the meaning of the additional parameters, see [`SortPairs`].
86	pub fn transpose_labeled_split<	×
87	G: LabeledSequentialGraph<C::Label>
88	+ for<'a> SplitLabeling<
89	SplitLender<'a>: for<'b> NodeLabelsLender<
90	'b,
91	Label: crate::traits::Pair<Left = usize, Right = C::Label> + Copy,
92	IntoIterator: IntoIterator<IntoIter: Send + Sync>,
93	> + Send
94	+ Sync,
95	IntoIterator<'a>: IntoIterator<IntoIter: Send + Sync>,
96	>,
97	C: BatchCodec,
98	>(
99	graph: &G,
100	memory_usage: MemoryUsage,
101	batch_codec: C,
102	cutpoints: Option<Vec<usize>>,
103	) -> Result<SplitIters<KMergeIters<CodecIter<C>, C::Label>>>
104	where
105	CodecIter<C>: Clone + Send + Sync,
106	{
107	let mut par_sort_iters = ParSortIters::new(graph.num_nodes())?.memory_usage(memory_usage);	×
108	if let Some(num_arcs) = graph.num_arcs_hint() {	×
109	par_sort_iters = par_sort_iters.expected_num_pairs(num_arcs as usize);	×
110	}
111
112	let pairs: Vec<_> = match cutpoints {	×
113	Some(cp) => graph.split_iter_at(cp),	×
114	None => {	×
115	let parts = rayon::current_num_threads();	×
116	graph.split_iter(parts)	×
117	}
118	}
119	.into_iter()
120	.map(\|iter\| iter.into_labeled_pairs().map(\|((a, b), l)\| ((b, a), l)))	×
121	.collect();
122
123	par_sort_iters.try_sort_labeled::<C, std::convert::Infallible, _>(batch_codec, pairs)	×
124	}
125
126	/// Returns a [`SplitIters`] structure representing the
127	/// transpose of the provided splittable graph, computed in parallel.
128	///
129	/// Parallelism is controlled via the current Rayon thread pool. Please
130	/// [install](rayon::ThreadPool::install) a custom pool if you want to customize
131	/// the parallelism.
132	///
133	/// The [`SplitIters`] structure can be easily converted into a vector of `(node,
134	/// lender)` pairs using [this `From`
135	/// implementation](crate::prelude::SplitIters#impl-From<SplitIters<IT>-for-Vec<(usize,+LeftIterator<Iter<(),+Map<I,+fn((usize,+usize))+->+(usize,+usize,+())>)>).
136	///
137	/// For the meaning of the additional parameters, see [`SortPairs`].
138	pub fn transpose_split<	2✔
139	'g,
140	G: SequentialGraph
141	+ for<'a> SplitLabeling<
142	SplitLender<'g>: NodeLabelsLender<
143	'a,
144	IntoIterator: IntoIterator<IntoIter: Send + Sync>,
145	>,
146	>,
147	>(
148	graph: &'g G,
149	memory_usage: MemoryUsage,
150	cutpoints: Option<Vec<usize>>,
151	) -> Result<SplitIters<SortedPairIter>> {
152	let mut par_sort_iters = ParSortIters::new(graph.num_nodes())?.memory_usage(memory_usage);	12✔
153	if let Some(num_arcs) = graph.num_arcs_hint() {	6✔
154	par_sort_iters = par_sort_iters.expected_num_pairs(num_arcs as usize);	4✔
155	}
156
157	let pairs: Vec<_> = match cutpoints {	6✔
158	Some(cp) => graph.split_iter_at(cp),	×
159	None => {	×
160	let parts = rayon::current_num_threads();	4✔
161	graph.split_iter(parts)	6✔
162	}
163	}
164	.into_iter()
165	.map(\|iter\| iter.into_pairs().map(\|(src, dst)\| (dst, src)))	6,432,336✔
166	.collect();
167
168	par_sort_iters.sort(pairs)	6✔
169	}

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