23365769388

Committed 20 Mar 2026 10:52PM UTC coverage: 68.228% (-3.0%) from 71.245%

Build # 23365769388

Build Type

push

github

Committed by

vigna

Commit Message

No le_bins,be_bins for webgraph

Run Details

6655 of 9754 relevant lines covered (68.23%)

46582760.24 hits per line

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

0.0

/cli/src/transform/transpose.rs

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

use crate::*;
use anyhow::Result;
use dsi_bitstream::{dispatch::factory::CodesReaderFactoryHelper, prelude::*};
use std::path::PathBuf;
use tempfile::Builder;
use webgraph::prelude::*;

#[derive(Parser, Debug)]
#[command(name = "transpose", about = "Transposes a graph in the BV format.", long_about = None, next_line_help = true)]
pub struct CliArgs {
    /// The basename of the graph.​
    pub src: PathBuf,
    /// The basename of the transposed graph.​
    pub dst: PathBuf,

    #[arg(short, long)]
    /// Use the sequential algorithm (does not need offsets).​
    pub sequential: bool,

    #[clap(flatten)]
    pub num_threads: NumThreadsArg,

    #[clap(flatten)]
    pub memory_usage: MemoryUsageArg,

    #[arg(long, conflicts_with = "sequential")]
    /// Use the degree cumulative function to balance work by arcs rather than
    /// by nodes; the DCF must have been pre-built with `webgraph build dcf`.​
    pub dcf: bool,

    #[clap(flatten)]
    pub ca: CompressArgs,
}

pub fn main(args: CliArgs) -> Result<()> {
    create_parent_dir(&args.dst)?;

    match get_endianness(&args.src)?.as_str() {
        #[cfg(feature = "be_bins")]
        BE::NAME => {
            if args.sequential {
                transpose::<BE>(args)
            } else {
                par_transpose::<BE>(args)
            }
        }
        #[cfg(feature = "le_bins")]
        LE::NAME => {
            if args.sequential {
                transpose::<LE>(args)
            } else {
                par_transpose::<LE>(args)
            }
        }
        e => panic!("Unknown endianness: {}", e),
    }
}

pub fn transpose<E: Endianness>(args: CliArgs) -> Result<()>
where
    MmapHelper<u32>: CodesReaderFactoryHelper<E>,
{
    let thread_pool = crate::get_thread_pool(args.num_threads.num_threads);

    // TODO!: speed it up by using random access graph if possible
    let seq_graph = webgraph::graphs::bvgraph::sequential::BvGraphSeq::with_basename(&args.src)
        .endianness::<E>()
        .load()?;

    // transpose the graph
    let sorted = webgraph::transform::transpose(&seq_graph, args.memory_usage.memory_usage)?;

    let target_endianness = args.ca.endianness.clone().unwrap_or_else(|| E::NAME.into());
    let dir = Builder::new().prefix("transform_transpose_").tempdir()?;
    let chunk_size = args.ca.chunk_size;
    let bvgraphz = args.ca.bvgraphz;
    let mut builder = BvCompConfig::new(&args.dst)
        .with_comp_flags(args.ca.into())
        .with_tmp_dir(&dir);

    if bvgraphz {
        builder = builder.with_chunk_size(chunk_size);
    }

    // Use uniform cutpoints for compression of the transposed graph
    // (the source DCF does not match the transpose's degree distribution)
    let num_nodes = sorted.num_nodes();
    thread_pool.install(|| {
        par_comp_lenders!(
            builder,
            sorted.split_iter(rayon::current_num_threads()),
            num_nodes,
            target_endianness
        )
    })?;

    Ok(())
}

pub fn par_transpose<E: Endianness>(args: CliArgs) -> Result<()>
where
    MmapHelper<u32>: CodesReaderFactoryHelper<E>,
    for<'a> LoadModeCodesReader<'a, E, Mmap>: BitSeek + Clone + Send + Sync,
{
    let thread_pool = crate::get_thread_pool(args.num_threads.num_threads);

    let graph = webgraph::graphs::bvgraph::BvGraph::with_basename(&args.src)
        .endianness::<E>()
        .load()?;

    let cp = crate::cutpoints(
        &args.src,
        graph.num_nodes(),
        graph.num_arcs_hint(),
        args.dcf,
    )?;

    // transpose the graph
    let split =
        webgraph::transform::transpose_split(&graph, args.memory_usage.memory_usage, Some(cp))?;

    // Convert to (node, lender) pairs
    let pairs: Vec<_> = split.into();

    let target_endianness = args.ca.endianness.clone().unwrap_or_else(|| E::NAME.into());
    let dir = Builder::new().prefix("transform_transpose_").tempdir()?;
    let chunk_size = args.ca.chunk_size;
    let bvgraphz = args.ca.bvgraphz;
    let mut builder = BvCompConfig::new(&args.dst)
        .with_comp_flags(args.ca.into())
        .with_tmp_dir(&dir);

    if bvgraphz {
        builder = builder.with_chunk_size(chunk_size);
    }

    let num_nodes = graph.num_nodes();
    thread_pool
        .install(|| par_comp_lenders!(builder, pairs.into_iter(), num_nodes, target_endianness))?;
    Ok(())
}

1	/*
2	* SPDX-FileCopyrightText: 2023 Inria
3	* SPDX-FileCopyrightText: 2023 Tommaso Fontana
4	* SPDX-FileCopyrightText: 2026 Sebastiano Vigna
5	*
6	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
7	*/
8
9	use crate::*;
10	use anyhow::Result;
11	use dsi_bitstream::{dispatch::factory::CodesReaderFactoryHelper, prelude::*};
12	use std::path::PathBuf;
13	use tempfile::Builder;
14	use webgraph::prelude::*;
15
16	#[derive(Parser, Debug)]
17	#[command(name = "transpose", about = "Transposes a graph in the BV format.", long_about = None, next_line_help = true)]
18	pub struct CliArgs {
19	/// The basename of the graph.
20	pub src: PathBuf,
21	/// The basename of the transposed graph.
22	pub dst: PathBuf,
23
24	#[arg(short, long)]
25	/// Use the sequential algorithm (does not need offsets).
26	pub sequential: bool,
27
28	#[clap(flatten)]
29	pub num_threads: NumThreadsArg,
30
31	#[clap(flatten)]
32	pub memory_usage: MemoryUsageArg,
33
34	#[arg(long, conflicts_with = "sequential")]
35	/// Use the degree cumulative function to balance work by arcs rather than
36	/// by nodes; the DCF must have been pre-built with `webgraph build dcf`.
37	pub dcf: bool,
38
39	#[clap(flatten)]
40	pub ca: CompressArgs,
41	}
42
43	pub fn main(args: CliArgs) -> Result<()> {	×
44	create_parent_dir(&args.dst)?;	×
45
46	match get_endianness(&args.src)?.as_str() {	×
47	#[cfg(feature = "be_bins")]
48	BE::NAME => {	×
49	if args.sequential {	×
50	transpose::<BE>(args)	×
51	} else {
52	par_transpose::<BE>(args)	×
53	}
54	}
55	#[cfg(feature = "le_bins")]
56	LE::NAME => {	×
57	if args.sequential {	×
58	transpose::<LE>(args)	×
59	} else {
60	par_transpose::<LE>(args)	×
61	}
62	}
63	e => panic!("Unknown endianness: {}", e),	×
64	}
65	}
66
67	pub fn transpose<E: Endianness>(args: CliArgs) -> Result<()>	×
68	where
69	MmapHelper<u32>: CodesReaderFactoryHelper<E>,
70	{
71	let thread_pool = crate::get_thread_pool(args.num_threads.num_threads);	×
72
73	// TODO!: speed it up by using random access graph if possible
74	let seq_graph = webgraph::graphs::bvgraph::sequential::BvGraphSeq::with_basename(&args.src)	×
75	.endianness::<E>()
76	.load()?;
77
78	// transpose the graph
79	let sorted = webgraph::transform::transpose(&seq_graph, args.memory_usage.memory_usage)?;	×
80
81	let target_endianness = args.ca.endianness.clone().unwrap_or_else(\|\| E::NAME.into());	×
82	let dir = Builder::new().prefix("transform_transpose_").tempdir()?;	×
83	let chunk_size = args.ca.chunk_size;	×
84	let bvgraphz = args.ca.bvgraphz;	×
85	let mut builder = BvCompConfig::new(&args.dst)	×
86	.with_comp_flags(args.ca.into())	×
87	.with_tmp_dir(&dir);	×
88
89	if bvgraphz {	×
90	builder = builder.with_chunk_size(chunk_size);	×
91	}
92
93	// Use uniform cutpoints for compression of the transposed graph
94	// (the source DCF does not match the transpose's degree distribution)
95	let num_nodes = sorted.num_nodes();	×
96	thread_pool.install(\|\| {	×
97	par_comp_lenders!(	×
98	builder,	×
99	sorted.split_iter(rayon::current_num_threads()),	×
100	num_nodes,	×
101	target_endianness	×
102	)
103	})?;
104
105	Ok(())	×
106	}
107
108	pub fn par_transpose<E: Endianness>(args: CliArgs) -> Result<()>	×
109	where
110	MmapHelper<u32>: CodesReaderFactoryHelper<E>,
111	for<'a> LoadModeCodesReader<'a, E, Mmap>: BitSeek + Clone + Send + Sync,
112	{
113	let thread_pool = crate::get_thread_pool(args.num_threads.num_threads);	×
114
115	let graph = webgraph::graphs::bvgraph::BvGraph::with_basename(&args.src)	×
116	.endianness::<E>()
117	.load()?;
118
119	let cp = crate::cutpoints(
120	&args.src,	×
121	graph.num_nodes(),	×
122	graph.num_arcs_hint(),	×
123	args.dcf,	×
124	)?;
125
126	// transpose the graph
127	let split =	×
128	webgraph::transform::transpose_split(&graph, args.memory_usage.memory_usage, Some(cp))?;	×
129
130	// Convert to (node, lender) pairs
131	let pairs: Vec<_> = split.into();	×
132
133	let target_endianness = args.ca.endianness.clone().unwrap_or_else(\|\| E::NAME.into());	×
134	let dir = Builder::new().prefix("transform_transpose_").tempdir()?;	×
135	let chunk_size = args.ca.chunk_size;	×
136	let bvgraphz = args.ca.bvgraphz;	×
137	let mut builder = BvCompConfig::new(&args.dst)	×
138	.with_comp_flags(args.ca.into())	×
139	.with_tmp_dir(&dir);	×
140
141	if bvgraphz {	×
142	builder = builder.with_chunk_size(chunk_size);	×
143	}
144
145	let num_nodes = graph.num_nodes();	×
146	thread_pool	×
147	.install(\|\| par_comp_lenders!(builder, pairs.into_iter(), num_nodes, target_endianness))?;	×
148	Ok(())	×
149	}

vigna / webgraph-rs / 23365769388

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