25054814280

Committed 28 Apr 2026 01:11PM UTC coverage: 69.158% (-0.04%) from 69.201%

Build # 25054814280

Build Type

push

github

Committed by

vigna

Commit Message

Further cleanup of method names; sorted symmetrization now uses IntoParLenders, too

Coverage Stats

24 of 59 new or added lines in 12 files covered. (40.68%)

761 existing lines in 28 files now uncovered.

7505 of 10852 relevant lines covered (69.16%)

50040578.59 hits per line

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

89.29

/webgraph/src/transform/map.rs

/*
 * SPDX-FileCopyrightText: 2026 Sebastiano Vigna
 *
 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
 */

use crate::graphs::par_sorted_graph::SortedPairIter;
use crate::prelude::*;
use crate::traits::{IntoParLenders, NodeLabelsLender};
use anyhow::{Result, ensure};
use dsi_progress_logger::ProgressLog;
use value_traits::slices::SliceByValue;

/// Returns a [`ParSortedGraph`] obtained by mapping the nodes of the provided
/// graph through the given map.
///
/// The map is not required to be bijective: multiple source nodes may map to the
/// same destination node. Duplicate arcs are removed.
///
/// The `num_nodes` parameter specifies the number of nodes of the resulting
/// graph: it must be strictly greater than every value in the map.
///
/// Note that if the graph implements [`IntoParLenders`], [`map_par`] will be
/// much faster.
///
/// For the meaning of the additional parameter, see
/// [`ParSortedGraphConf`](crate::graphs::par_sorted_graph::ParSortedGraphConf).
pub fn map(
    graph: &impl SequentialGraph,
    map: &impl SliceByValue<Value = usize>,
    num_nodes: usize,
    memory_usage: MemoryUsage,
    pl: &mut impl ProgressLog,
) -> Result<ParSortedGraph<SortedPairIter<true>>> {
    ensure!(
        map.len() == graph.num_nodes(),
        "The given map has {} values and thus it's incompatible with a graph with {} nodes.",
        map.len(),
        graph.num_nodes(),
    );

    ParSortedGraph::config()
        .dedup()
        .memory_usage(memory_usage)
        .progress_logger(pl)
        .sort_pairs(
            num_nodes,
            graph
                .iter()
                .into_pairs()
                .map(|(src, dst)| (map.index_value(src), map.index_value(dst))),
        )
}

/// Returns a [`ParSortedGraph`] representing the mapped graph, computed in
/// parallel.
///
/// The map is not required to be bijective: multiple source nodes may map to the
/// same destination node. Duplicate arcs are removed.
///
/// The `num_nodes` parameter specifies the number of nodes of the resulting
/// graph: it must be strictly greater than every value in the map.
///
/// The graph must implement [`IntoParLenders`]; use [`ParGraph`] to wrap a
/// [splittable] graph as needed.
///
/// Parallelism is controlled via the current Rayon thread pool. Please
/// [install] a custom pool if you want to customize the parallelism.
///
/// For the meaning of the additional parameter, see
/// [`ParSortedGraphConf`](crate::graphs::par_sorted_graph::ParSortedGraphConf).
///
/// [`ParGraph`]: crate::graphs::par_graphs::ParGraph
/// [splittable]: SplitLabeling
/// [install]: rayon::ThreadPool::install
pub fn map_par<G, M>(
    graph: G,
    map: &M,
    num_nodes: usize,
    memory_usage: MemoryUsage,
    pl: &mut impl ProgressLog,
) -> Result<ParSortedGraph<SortedPairIter<true>>>
where
    G: SequentialGraph
        + IntoParLenders<
            ParLender: for<'a> NodeLabelsLender<
                'a,
                Label = usize,
                IntoIterator: IntoIterator<IntoIter: Send>,
            >,
        >,
    M: SliceByValue<Value = usize> + Send + Sync,
{
    ensure!(
        map.len() == graph.num_nodes(),
        "The given map has {} values and thus it's incompatible with a graph with {} nodes.",
        map.len(),
        graph.num_nodes(),
    );

    let conf = ParSortedGraph::config()
        .dedup()
        .memory_usage(memory_usage)
        .progress_logger(pl);
    let (lenders, _boundaries) = graph.into_par_lenders();
    let iters = lenders.into_vec().into_iter().map(|lender| {
        lender
            .into_pairs()
            .map(|(src, dst)| (map.index_value(src), map.index_value(dst)))
    });
    conf.par_sort_pair_iters(num_nodes, iters)
}

1	/*
2	* SPDX-FileCopyrightText: 2026 Sebastiano Vigna
3	*
4	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
5	*/
6
7	use crate::graphs::par_sorted_graph::SortedPairIter;
8	use crate::prelude::*;
9	use crate::traits::{IntoParLenders, NodeLabelsLender};
10	use anyhow::{Result, ensure};
11	use dsi_progress_logger::ProgressLog;
12	use value_traits::slices::SliceByValue;
13
14	/// Returns a [`ParSortedGraph`] obtained by mapping the nodes of the provided
15	/// graph through the given map.
16	///
17	/// The map is not required to be bijective: multiple source nodes may map to the
18	/// same destination node. Duplicate arcs are removed.
19	///
20	/// The `num_nodes` parameter specifies the number of nodes of the resulting
21	/// graph: it must be strictly greater than every value in the map.
22	///
23	/// Note that if the graph implements [`IntoParLenders`], [`map_par`] will be
24	/// much faster.
25	///
26	/// For the meaning of the additional parameter, see
27	/// [`ParSortedGraphConf`](crate::graphs::par_sorted_graph::ParSortedGraphConf).
28	pub fn map(	4✔
29	graph: &impl SequentialGraph,
30	map: &impl SliceByValue<Value = usize>,
31	num_nodes: usize,
32	memory_usage: MemoryUsage,
33	pl: &mut impl ProgressLog,
34	) -> Result<ParSortedGraph<SortedPairIter<true>>> {
35	ensure!(	4✔
36	map.len() == graph.num_nodes(),	12✔
37	"The given map has {} values and thus it's incompatible with a graph with {} nodes.",
38	map.len(),	2✔
39	graph.num_nodes(),	2✔
40	);
41
42	ParSortedGraph::config()	3✔
43	.dedup()
44	.memory_usage(memory_usage)	6✔
45	.progress_logger(pl)	6✔
46	.sort_pairs(
47	num_nodes,	3✔
48	graph	3✔
49	.iter()	3✔
50	.into_pairs()	3✔
51	.map(\|(src, dst)\| (map.index_value(src), map.index_value(dst))),	57✔
52	)
53	}
54
55	/// Returns a [`ParSortedGraph`] representing the mapped graph, computed in
56	/// parallel.
57	///
58	/// The map is not required to be bijective: multiple source nodes may map to the
59	/// same destination node. Duplicate arcs are removed.
60	///
61	/// The `num_nodes` parameter specifies the number of nodes of the resulting
62	/// graph: it must be strictly greater than every value in the map.
63	///
64	/// The graph must implement [`IntoParLenders`]; use [`ParGraph`] to wrap a
65	/// [splittable] graph as needed.
66	///
67	/// Parallelism is controlled via the current Rayon thread pool. Please
68	/// [install] a custom pool if you want to customize the parallelism.
69	///
70	/// For the meaning of the additional parameter, see
71	/// [`ParSortedGraphConf`](crate::graphs::par_sorted_graph::ParSortedGraphConf).
72	///
73	/// [`ParGraph`]: crate::graphs::par_graphs::ParGraph
74	/// [splittable]: SplitLabeling
75	/// [install]: rayon::ThreadPool::install
76	pub fn map_par<G, M>(	2✔
77	graph: G,
78	map: &M,
79	num_nodes: usize,
80	memory_usage: MemoryUsage,
81	pl: &mut impl ProgressLog,
82	) -> Result<ParSortedGraph<SortedPairIter<true>>>
83	where
84	G: SequentialGraph
85	+ IntoParLenders<
86	ParLender: for<'a> NodeLabelsLender<
87	'a,
88	Label = usize,
89	IntoIterator: IntoIterator<IntoIter: Send>,
90	>,
91	>,
92	M: SliceByValue<Value = usize> + Send + Sync,
93	{
94	ensure!(	2✔
95	map.len() == graph.num_nodes(),	6✔
UNCOV 96	"The given map has {} values and thus it's incompatible with a graph with {} nodes.",	×
UNCOV 97	map.len(),	×
UNCOV 98	graph.num_nodes(),	×
99	);
100
101	let conf = ParSortedGraph::config()	4✔
102	.dedup()
103	.memory_usage(memory_usage)	4✔
104	.progress_logger(pl);	4✔
105	let (lenders, _boundaries) = graph.into_par_lenders();	6✔
106	let iters = lenders.into_vec().into_iter().map(\|lender\| {	18✔
107	lender	8✔
108	.into_pairs()	8✔
109	.map(\|(src, dst)\| (map.index_value(src), map.index_value(dst)))	44✔
110	});
111	conf.par_sort_pair_iters(num_nodes, iters)	8✔
112	}

vigna / webgraph-rs / 25054814280

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