18279564945

Committed 06 Oct 2025 11:36AM UTC coverage: 48.839% (-0.2%) from 49.006%

Build # 18279564945

Build Type

push

github

Committed by

vigna

Commit Message

Moved SortPairs to MemoryUsage

Coverage Stats

12 of 23 new or added lines in 6 files covered. (52.17%)

14 existing lines in 3 files now uncovered.

3890 of 7965 relevant lines covered (48.84%)

23444471.85 hits per line

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

45.45

/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, SortPairs};
use crate::prelude::{BitDeserializer, BitSerializer, LabeledSequentialGraph, SequentialGraph};
use crate::traits::graph::UnitLabelGraph;
use crate::utils::MemoryUsage;
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>,
    batch_size: usize,
    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(
        MemoryUsage::BatchSize(batch_size),
        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,
    batch_size: usize,
) -> Result<Left<arc_list_graph::ArcListGraph<KMergeIters<BatchIterator<()>, ()>>>> {
    Ok(Left(transpose_labeled(
        &UnitLabelGraph(graph),
        batch_size,
        (),
        (),
    )?))
}

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, SortPairs};
11	use crate::prelude::{BitDeserializer, BitSerializer, LabeledSequentialGraph, SequentialGraph};
12	use crate::traits::graph::UnitLabelGraph;
13	use crate::utils::MemoryUsage;
14	use anyhow::Result;
15	use dsi_bitstream::traits::NE;
16	use dsi_progress_logger::prelude::*;
17	use lender::prelude::*;
18	use tempfile::Builder;
19
20	/// Returns the transpose of the provided labeled graph as a [sequential
21	/// graph](crate::traits::SequentialGraph).
22	///
23	/// For the meaning of the additional parameters, see
24	/// [`SortPairs`](crate::prelude::sort_pairs::SortPairs).
25	#[allow(clippy::type_complexity)]
26	pub fn transpose_labeled<	98✔
27	S: BitSerializer<NE, BitWriter> + Clone,
28	D: BitDeserializer<NE, BitReader> + Clone + 'static,
29	>(
30	graph: &impl LabeledSequentialGraph<S::SerType>,
31	batch_size: usize,
32	serializer: S,
33	deserializer: D,
34	) -> Result<arc_list_graph::ArcListGraph<KMergeIters<BatchIterator<D>, D::DeserType>>>
35	where
36	S::SerType: Send + Sync + Copy,
37	D::DeserType: Clone + Copy,
38	{
39	let dir = Builder::new().prefix("transpose_").tempdir()?;	392✔
40	let mut sorted = SortPairs::new_labeled(
NEW 41	MemoryUsage::BatchSize(batch_size),	×
NEW 42	dir.path(),	×
NEW 43	serializer,	×
NEW 44	deserializer,	×
45	)?;
46
47	let mut pl = progress_logger![	×
48	item_name = "node",	×
49	expected_updates = Some(graph.num_nodes()),	×
50	display_memory = true	×
51	];
52	pl.start("Creating batches...");	×
53	// create batches of sorted edges
54	for_!( (src, succ) in graph.iter() {	5,370✔
55	for (dst, l) in succ {	352,738✔
56	sorted.push_labeled(dst, src, l)?;	×
57	}
58	pl.light_update();	5,370✔
59	});
60	// merge the batches
61	let sorted = arc_list_graph::ArcListGraph::new_labeled(graph.num_nodes(), sorted.iter()?);	490✔
62	pl.done();	×
63
64	Ok(sorted)	×
65	}
66
67	/// Returns the transpose of the provided graph as a [sequential
68	/// graph](crate::traits::SequentialGraph).
69	///
70	/// For the meaning of the additional parameter, see
71	/// [`SortPairs`](crate::prelude::sort_pairs::SortPairs).
72	#[allow(clippy::type_complexity)]
73	pub fn transpose(	96✔
74	graph: impl SequentialGraph,
75	batch_size: usize,
76	) -> Result<Left<arc_list_graph::ArcListGraph<KMergeIters<BatchIterator<()>, ()>>>> {
77	Ok(Left(transpose_labeled(	96✔
78	&UnitLabelGraph(graph),	96✔
79	batch_size,	96✔
80	(),
81	(),
82	)?))
83	}

vigna / webgraph-rs / 18279564945

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