19076069272

Committed 04 Nov 2025 04:42PM UTC coverage: 61.785% (-0.2%) from 61.976%

Build # 19076069272

Build Type

push

github

Committed by

vigna

Commit Message

Fixed doctests

Run Details

5143 of 8324 relevant lines covered (61.79%)

30278823.63 hits per line

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

69.77

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

vigna / webgraph-rs / 19076069272

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