18575567968

Committed 16 Oct 2025 09:40PM UTC coverage: 48.064%. Remained the same

Build # 18575567968

Build Type

push

github

Committed by

vigna

Commit Message

Changed name, fixed doc test

Run Details

0 of 2 new or added lines in 1 file covered. (0.0%)

2 existing lines in 2 files now uncovered.

3972 of 8264 relevant lines covered (48.06%)

22122959.79 hits per line

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

30.56

/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, UnitLender};
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 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 par_transpose_labeled<
    '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_graph = ParSortIters::new(graph.num_nodes())?.memory_usage(memory_usage);
    let parts = num_cpus::get();

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

    par_sort_graph.try_sort_labeled::<S, D, std::convert::Infallible>(
        &serializer,
        deserializer,
        pairs,
    )
}

pub fn par_transpose<
    '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_graph = ParSortIters::new(graph.num_nodes())?.memory_usage(memory_usage);
    let parts = num_cpus::get();

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

    par_sort_graph.try_sort_labeled::<(), (), std::convert::Infallible>(&(), (), 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::{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, UnitLender};
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<	98✔
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()?;	392✔
43	let mut sorted = SortPairs::new_labeled(memory_usage, dir.path(), serializer, deserializer)?;	98✔
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,370✔
53	for (dst, l) in succ {	352,738✔
54	sorted.push_labeled(dst, src, l)?;	×
55	}
56	pl.light_update();	5,370✔
57	});
58	// merge the batches
59	let sorted = arc_list_graph::ArcListGraph::new_labeled(graph.num_nodes(), sorted.iter()?);	490✔
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(	96✔
72	graph: impl SequentialGraph,
73	memory_usage: MemoryUsage,
74	) -> Result<Left<arc_list_graph::ArcListGraph<KMergeIters<BatchIterator<()>, ()>>>> {
75	Ok(Left(transpose_labeled(	96✔
76	&UnitLabelGraph(graph),	96✔
77	memory_usage,	96✔
78	(),
79	(),
80	)?))
81	}
82
83	/// Returns the transpose of the provided labeled graph as a [sequential
84	/// graph](crate::traits::SequentialGraph).
85	///
86	/// For the meaning of the additional parameters, see
87	/// [`SortPairs`](crate::prelude::sort_pairs::SortPairs).
88	#[allow(clippy::type_complexity)]
89	pub fn par_transpose_labeled<	×
90	'graph,
91	G: 'graph
92	+ LabeledSequentialGraph<S::SerType>
93	+ for<'a> SplitLabeling<
94	SplitLender<'a>: for<'b> NodeLabelsLender<
95	'b,
96	Label: crate::traits::Pair<Left = usize, Right = S::SerType> + Copy,
97	IntoIterator: IntoIterator<IntoIter: Send + Sync>,
98	> + Send
99	+ Sync,
100	IntoIterator<'a>: IntoIterator<IntoIter: Send + Sync>,
101	>,
102	S: BitSerializer<NE, BitWriter> + Clone + Send + Sync + 'graph,
103	D: BitDeserializer<NE, BitReader, DeserType: Clone + Send + Sync> + Clone + Send + Sync + 'static,
104	>(
105	graph: &'graph G,
106	memory_usage: MemoryUsage,
107	serializer: S,
108	deserializer: D,
109	) -> Result<
110	SplitIters<
111	impl IntoIterator<Item = (usize, usize, D::DeserType), IntoIter: Send + Sync>
112	+ use<'graph, G, S, D>,
113	>,
114	>
115	where
116	S::SerType: Send + Sync + Copy,
117	D::DeserType: Clone + Copy,
118	{
NEW 119	let par_sort_graph = ParSortIters::new(graph.num_nodes())?.memory_usage(memory_usage);	×
120	let parts = num_cpus::get();	×
121
122	let pairs: Vec<_> = graph	×
123	.split_iter(parts)	×
124	.into_iter()
125	.map(\|(_start_node, iter)\| iter.into_labeled_pairs())	×
126	.collect();
127
128	par_sort_graph.try_sort_labeled::<S, D, std::convert::Infallible>(	×
129	&serializer,	×
130	deserializer,	×
131	pairs,	×
132	)
133	}
134
135	pub fn par_transpose<	×
136	'graph,
137	G: 'graph
138	+ SequentialGraph
139	+ for<'a> SplitLabeling<
140	SplitLender<'a>: for<'b> NodeLabelsLender<
141	'b,
142	Label = usize,
143	IntoIterator: IntoIterator<IntoIter: Send + Sync>,
144	> + Send
145	+ Sync,
146	IntoIterator<'a>: IntoIterator<IntoIter: Send + Sync>,
147	>,
148	>(
149	graph: &'graph G,
150	memory_usage: MemoryUsage,
151	) -> Result<
152	SplitIters<
153	impl IntoIterator<Item = (usize, usize, ()), IntoIter: Send + Sync> + use<'graph, G>,
154	>,
155	> {
NEW 156	let par_sort_graph = ParSortIters::new(graph.num_nodes())?.memory_usage(memory_usage);	×
157	let parts = num_cpus::get();	×
158
159	let pairs: Vec<_> = graph	×
160	.split_iter(parts)	×
161	.into_iter()
162	.map(\|(_start_node, iter)\| UnitLender(iter).into_labeled_pairs())	×
163	.collect();
164
165	par_sort_graph.try_sort_labeled::<(), (), std::convert::Infallible>(&(), (), pairs)	×
166	}

vigna / webgraph-rs / 18575567968

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