18700773632

Committed 21 Oct 2025 11:42PM UTC coverage: 49.299% (+1.2%) from 48.112%

Build # 18700773632

Build Type

push

github

Committed by

vigna

Commit Message

Fixed doctest

Coverage Stats

4078 of 8272 relevant lines covered (49.3%)

23258698.55 hits per line

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

37.21

/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::{BatchIterator, BitReader, BitWriter, KMergeIters};
use crate::prelude::{
    BitDeserializer, BitSerializer, LabeledSequentialGraph, SequentialGraph, SortPairs,
};
use crate::traits::graph::UnitLabelGraph;
use crate::traits::{NodeLabelsLender, SplitLabeling};
use crate::utils::{MemoryUsage, ParSortIters, SplitIters};
use anyhow::Result;
use dsi_bitstream::traits::NE;
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<
    S: BitSerializer<NE, BitWriter> + Clone,
    D: BitDeserializer<NE, BitReader> + Clone + 'static,
>(
    graph: &impl LabeledSequentialGraph<S::SerType>,
    memory_usage: MemoryUsage,
    serializer: S,
    deserializer: D,
) -> Result<arc_list_graph::ArcListGraph<KMergeIters<BatchIterator<D>, D::DeserType>>>
where
    S::SerType: Send + Sync + Copy,
    D::DeserType: Clone + Copy,
{
    let dir = Builder::new().prefix("transpose_").tempdir()?;
    let mut sorted = SortPairs::new_labeled(memory_usage, dir.path(), serializer, deserializer)?;

    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).
#[allow(clippy::type_complexity)]
pub fn transpose(
    graph: impl SequentialGraph,
    memory_usage: MemoryUsage,
) -> Result<Left<arc_list_graph::ArcListGraph<KMergeIters<BatchIterator<()>, ()>>>> {
    Ok(Left(transpose_labeled(
        &UnitLabelGraph(graph),
        memory_usage,
        (),
        (),
    )?))
}

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

vigna / webgraph-rs / 18700773632

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