25166807764

Committed 30 Apr 2026 01:00PM UTC coverage: 69.005%. Remained the same

Build # 25166807764

Build Type

push

github

Committed by

vigna

Commit Message

Sequential transformation commands end in _seq

Coverage Stats

6 of 13 new or added lines in 10 files covered. (46.15%)

7507 of 10879 relevant lines covered (69.0%)

49558798.21 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 dsi_progress_logger::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)]
    /// Uses 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")]
    /// Uses 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,

    #[clap(flatten)]
    pub log_interval: LogIntervalArg,
}

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_seq::<BE>(args)
            } else {
                transpose_par::<BE>(args)
            }
        }
        #[cfg(feature = "le_bins")]
        LE::NAME => {
            if args.sequential {
                transpose_seq::<LE>(args)
            } else {
                transpose_par::<LE>(args)
            }
        }
        e => panic!("Unknown endianness: {}", e),
    }
}

/// Sequential version of [`transpose_par`].
pub fn transpose_seq<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 mut pl = progress_logger![
        display_memory = true,
        log_interval = args.log_interval.log_interval
    ];
    let sorted =
        webgraph::transform::transpose_seq(&seq_graph, args.memory_usage.memory_usage, &mut pl)?;

    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 = BvCompConf::new(&args.dst)
        .comp_flags(args.ca.into())
        .tmp_dir(&dir);

    if bvgraphz {
        builder = builder.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 mut builder = builder.progress_logger(&mut pl);
    thread_pool.install(|| par_comp!(builder, sorted, target_endianness))?;

    Ok(())
}

/// Parallel version of [`transpose_seq`].
pub fn transpose_par<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 num_nodes = graph.num_nodes();
    let num_arcs_hint = graph.num_arcs_hint();
    let cp = crate::cutpoints(&args.src, num_nodes, num_arcs_hint, args.dcf)?;

    // transpose the graph
    let par_graph = webgraph::graphs::par_graphs::ParGraph::with_cutpoints(graph, cp);
    let mut pl = progress_logger![
        display_memory = true,
        log_interval = args.log_interval.log_interval
    ];
    let sorted =
        webgraph::transform::transpose_par(&par_graph, args.memory_usage.memory_usage, &mut pl)?;

    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 = BvCompConf::new(&args.dst)
        .comp_flags(args.ca.into())
        .tmp_dir(&dir);

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

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

vigna / webgraph-rs / 25166807764

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