20017908129

Committed 08 Dec 2025 05:36AM UTC coverage: 62.065% (+0.4%) from 61.641%

Build # 20017908129

Build Type

push

github

Committed by

zommiommy

Commit Message

Fix doctests

Run Details

5435 of 8757 relevant lines covered (62.06%)

46674689.93 hits per line

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

28.21

/cli/src/transform/simplify.rs

/*
 * SPDX-FileCopyrightText: 2023 Inria
 * SPDX-FileCopyrightText: 2023 Tommaso Fontana
 *
 * 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 mmap_rs::MmapFlags;
use std::path::PathBuf;
use tempfile::Builder;
use webgraph::graphs::union_graph::UnionGraph;
use webgraph::prelude::*;

#[derive(Parser, Debug)]
#[command(name = "simplify", about = "Makes a BvGraph simple (undirected and loopless) by adding missing arcs and removing loops, optionally applying a permutation.", long_about = None)]
pub struct CliArgs {
    /// The basename of the graph.
    pub src: PathBuf,
    /// The basename of the simplified graph.
    pub dst: PathBuf,

    #[arg(long)]
    /// The basename of a pre-computed transposed version of the source graph, which
    /// will be use to speed up the simplification.
    pub transposed: Option<PathBuf>,

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

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

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

    #[arg(long)]
    /// The path to an optional permutation in binary big-endian format to apply to the graph.
    pub permutation: Option<PathBuf>,
}

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

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

fn no_ef_warn(basepath: impl AsRef<std::path::Path>) {
    log::warn!(SEQ_PROC_WARN![], basepath.as_ref().display());
}

pub fn simplify<E: Endianness>(_global_args: GlobalArgs, args: CliArgs) -> Result<()>
where
    MmapHelper<u32>: CodesReaderFactoryHelper<E>,
    for<'a> LoadModeCodesReader<'a, E, Mmap>: BitSeek + Clone + Send + Sync,
{
    // TODO!: speed it up by using random access graph if possible
    let thread_pool = crate::get_thread_pool(args.num_threads.num_threads);

    let target_endianness = args.ca.endianness.clone().unwrap_or_else(|| E::NAME.into());

    let dir = Builder::new().prefix("transform_simplify_").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);
    }

    match (args.permutation, args.transposed) {
        // load the transposed graph and use it to directly compress the graph
        // without doing any sorting
        (None, Some(t_path)) => {
            log::info!("Transposed graph provided, using it to simplify the graph");

            let has_ef_graph =
                std::fs::metadata(args.src.with_extension("ef")).is_ok_and(|x| x.is_file());
            let has_ef_t_graph =
                std::fs::metadata(t_path.with_extension("ef")).is_ok_and(|x| x.is_file());

            match (has_ef_graph, has_ef_t_graph) {
                (true, true) => {
                    log::info!("Both .ef files found, using simplify split");

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

                    if graph_t.num_nodes() != num_nodes {
                        anyhow::bail!(
                            "The number of nodes in the graph and its transpose do not match! {} != {}",
                            num_nodes,
                            graph_t.num_nodes()
                        );
                    }

                    let sorted = NoSelfLoopsGraph(UnionGraph(graph, graph_t));

                    thread_pool.install(|| {
                        builder.par_comp_lenders_endianness(
                            &sorted,
                            sorted.num_nodes(),
                            &target_endianness,
                        )
                    })?;

                    return Ok(());
                }
                (true, false) => {
                    no_ef_warn(&args.src);
                }
                (false, true) => {
                    no_ef_warn(&t_path);
                }
                (false, false) => {
                    no_ef_warn(&args.src);
                    no_ef_warn(&t_path);
                }
            }

            let seq_graph =
                webgraph::graphs::bvgraph::sequential::BvGraphSeq::with_basename(&args.src)
                    .endianness::<E>()
                    .load()?;
            let num_nodes = seq_graph.num_nodes();
            let seq_graph_t =
                webgraph::graphs::bvgraph::sequential::BvGraphSeq::with_basename(&t_path)
                    .endianness::<E>()
                    .load()?;

            if seq_graph_t.num_nodes() != num_nodes {
                anyhow::bail!(
                    "The number of nodes in the graph and its transpose do not match! {} != {}",
                    num_nodes,
                    seq_graph_t.num_nodes()
                );
            }

            let sorted = NoSelfLoopsGraph(UnionGraph(seq_graph, seq_graph_t));

            thread_pool.install(|| {
                builder.par_comp_lenders_endianness(&sorted, sorted.num_nodes(), &target_endianness)
            })?;
        }
        // apply the permutation, don't care if the transposed graph is already computed
        // as we cannot really exploit it
        (Some(perm_path), None | Some(_)) => {
            log::info!("Permutation provided, applying it to the graph");

            let perm = JavaPermutation::mmap(perm_path, MmapFlags::RANDOM_ACCESS)?;

            // if the .ef file exists, we can use the simplify split
            if std::fs::metadata(args.src.with_extension("ef")).is_ok_and(|x| x.is_file()) {
                log::info!(".ef file found, using simplify split");
                let graph =
                    webgraph::graphs::bvgraph::random_access::BvGraph::with_basename(&args.src)
                        .endianness::<E>()
                        .load()?;

                let perm_graph = PermutedGraph {
                    graph: &graph,
                    perm: &perm,
                };

                let sorted = webgraph::transform::simplify_split(
                    &perm_graph,
                    args.memory_usage.memory_usage,
                    &thread_pool,
                )?;

                thread_pool.install(|| {
                    builder.par_comp_lenders_endianness(
                        &sorted,
                        sorted.num_nodes(),
                        &target_endianness,
                    )
                })?;

                return Ok(());
            }

            no_ef_warn(&args.src);

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

            let perm_graph = PermutedGraph {
                graph: &seq_graph,
                perm: &perm,
            };

            // simplify the graph
            let sorted =
                webgraph::transform::simplify(&perm_graph, args.memory_usage.memory_usage).unwrap();

            thread_pool.install(|| {
                builder.par_comp_lenders_endianness(&sorted, sorted.num_nodes(), &target_endianness)
            })?;
        }
        // just compute the transpose on the fly
        (None, None) => {
            log::info!(
                "No permutation or transposed graph provided, computing the transpose on the fly"
            );
            // if the .ef file exists, we can use the simplify split
            if std::fs::metadata(args.src.with_extension("ef")).is_ok_and(|x| x.is_file()) {
                log::info!(".ef file found, using simplify split");

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

                let sorted = webgraph::transform::simplify_split(
                    &graph,
                    args.memory_usage.memory_usage,
                    &thread_pool,
                )?;

                thread_pool.install(|| {
                    builder.par_comp_lenders_endianness(
                        &sorted,
                        sorted.num_nodes(),
                        &target_endianness,
                    )
                })?;

                return Ok(());
            }

            no_ef_warn(&args.src);

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

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

            thread_pool.install(|| {
                builder.par_comp_lenders_endianness(&sorted, sorted.num_nodes(), &target_endianness)
            })?;
        }
    }

    Ok(())
}

1	/*
2	* SPDX-FileCopyrightText: 2023 Inria
3	* SPDX-FileCopyrightText: 2023 Tommaso Fontana
4	*
5	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
6	*/
7
8	use crate::*;
9	use anyhow::Result;
10	use dsi_bitstream::{dispatch::factory::CodesReaderFactoryHelper, prelude::*};
11	use mmap_rs::MmapFlags;
12	use std::path::PathBuf;
13	use tempfile::Builder;
14	use webgraph::graphs::union_graph::UnionGraph;
15	use webgraph::prelude::*;
16
17	#[derive(Parser, Debug)]
18	#[command(name = "simplify", about = "Makes a BvGraph simple (undirected and loopless) by adding missing arcs and removing loops, optionally applying a permutation.", long_about = None)]
19	pub struct CliArgs {
20	/// The basename of the graph.
21	pub src: PathBuf,
22	/// The basename of the simplified graph.
23	pub dst: PathBuf,
24
25	#[arg(long)]
26	/// The basename of a pre-computed transposed version of the source graph, which
27	/// will be use to speed up the simplification.
28	pub transposed: Option<PathBuf>,
29
30	#[clap(flatten)]
31	pub num_threads: NumThreadsArg,
32
33	#[clap(flatten)]
34	pub memory_usage: MemoryUsageArg,
35
36	#[clap(flatten)]
37	pub ca: CompressArgs,
38
39	#[arg(long)]
40	/// The path to an optional permutation in binary big-endian format to apply to the graph.
41	pub permutation: Option<PathBuf>,
42	}
43
44	pub fn main(global_args: GlobalArgs, args: CliArgs) -> Result<()> {	4✔
45	create_parent_dir(&args.dst)?;	8✔
46
47	match get_endianness(&args.src)?.as_str() {	12✔
48	#[cfg(feature = "be_bins")]
49	BE::NAME => simplify::<BE>(global_args, args),	16✔
50	#[cfg(feature = "le_bins")]
51	LE::NAME => simplify::<LE>(global_args, args),	×
52	e => panic!("Unknown endianness: {}", e),	×
53	}
54	}
55
56	fn no_ef_warn(basepath: impl AsRef<std::path::Path>) {	×
57	log::warn!(SEQ_PROC_WARN![], basepath.as_ref().display());	×
58	}
59
60	pub fn simplify<E: Endianness>(_global_args: GlobalArgs, args: CliArgs) -> Result<()>	4✔
61	where
62	MmapHelper<u32>: CodesReaderFactoryHelper<E>,
63	for<'a> LoadModeCodesReader<'a, E, Mmap>: BitSeek + Clone + Send + Sync,
64	{
65	// TODO!: speed it up by using random access graph if possible
66	let thread_pool = crate::get_thread_pool(args.num_threads.num_threads);	12✔
67
68	let target_endianness = args.ca.endianness.clone().unwrap_or_else(\|\| E::NAME.into());	24✔
69
70	let dir = Builder::new().prefix("transform_simplify_").tempdir()?;	16✔
71	let chunk_size = args.ca.chunk_size;	8✔
72	let bvgraphz = args.ca.bvgraphz;	8✔
73	let mut builder = BvCompConfig::new(&args.dst)	12✔
74	.with_comp_flags(args.ca.into())	12✔
75	.with_tmp_dir(&dir);	8✔
76
77	if bvgraphz {	4✔
78	builder = builder.with_chunk_size(chunk_size);	×
79	}
80
81	match (args.permutation, args.transposed) {	8✔
82	// load the transposed graph and use it to directly compress the graph
83	// without doing any sorting
84	(None, Some(t_path)) => {	×
85	log::info!("Transposed graph provided, using it to simplify the graph");	×
86
87	let has_ef_graph =	×
88	std::fs::metadata(args.src.with_extension("ef")).is_ok_and(\|x\| x.is_file());	×
89	let has_ef_t_graph =	×
90	std::fs::metadata(t_path.with_extension("ef")).is_ok_and(\|x\| x.is_file());	×
91
92	match (has_ef_graph, has_ef_t_graph) {	×
93	(true, true) => {	×
94	log::info!("Both .ef files found, using simplify split");	×
95
96	let graph =	×
97	webgraph::graphs::bvgraph::random_access::BvGraph::with_basename(&args.src)	×
98	.endianness::<E>()
99	.load()?;
100	let num_nodes = graph.num_nodes();	×
101	let graph_t =	×
102	webgraph::graphs::bvgraph::random_access::BvGraph::with_basename(&t_path)	×
103	.endianness::<E>()
104	.load()?;
105
106	if graph_t.num_nodes() != num_nodes {	×
107	anyhow::bail!(	×
108	"The number of nodes in the graph and its transpose do not match! {} != {}",	×
109	num_nodes,	×
110	graph_t.num_nodes()	×
111	);
112	}
113
114	let sorted = NoSelfLoopsGraph(UnionGraph(graph, graph_t));	×
115
116	thread_pool.install(\|\| {	×
117	builder.par_comp_lenders_endianness(	×
118	&sorted,	×
119	sorted.num_nodes(),	×
120	&target_endianness,	×
121	)
122	})?;
123
124	return Ok(());	×
125	}
126	(true, false) => {	×
127	no_ef_warn(&args.src);	×
128	}
129	(false, true) => {	×
130	no_ef_warn(&t_path);	×
131	}
132	(false, false) => {	×
133	no_ef_warn(&args.src);	×
134	no_ef_warn(&t_path);	×
135	}
136	}
137
138	let seq_graph =	×
139	webgraph::graphs::bvgraph::sequential::BvGraphSeq::with_basename(&args.src)	×
140	.endianness::<E>()
141	.load()?;
142	let num_nodes = seq_graph.num_nodes();	×
143	let seq_graph_t =	×
144	webgraph::graphs::bvgraph::sequential::BvGraphSeq::with_basename(&t_path)	×
145	.endianness::<E>()
146	.load()?;
147
148	if seq_graph_t.num_nodes() != num_nodes {	×
149	anyhow::bail!(	×
150	"The number of nodes in the graph and its transpose do not match! {} != {}",	×
151	num_nodes,	×
152	seq_graph_t.num_nodes()	×
153	);
154	}
155
156	let sorted = NoSelfLoopsGraph(UnionGraph(seq_graph, seq_graph_t));	×
157
158	thread_pool.install(\|\| {	×
159	builder.par_comp_lenders_endianness(&sorted, sorted.num_nodes(), &target_endianness)	×
160	})?;
161	}
162	// apply the permutation, don't care if the transposed graph is already computed
163	// as we cannot really exploit it
164	(Some(perm_path), None \| Some(_)) => {	4✔
165	log::info!("Permutation provided, applying it to the graph");	4✔
166
167	let perm = JavaPermutation::mmap(perm_path, MmapFlags::RANDOM_ACCESS)?;	12✔
168
169	// if the .ef file exists, we can use the simplify split
170	if std::fs::metadata(args.src.with_extension("ef")).is_ok_and(\|x\| x.is_file()) {	20✔
171	log::info!(".ef file found, using simplify split");	4✔
172	let graph =	4✔
173	webgraph::graphs::bvgraph::random_access::BvGraph::with_basename(&args.src)	8✔
174	.endianness::<E>()
175	.load()?;
176
177	let perm_graph = PermutedGraph {
178	graph: &graph,	4✔
179	perm: &perm,	4✔
180	};
181
182	let sorted = webgraph::transform::simplify_split(
183	&perm_graph,	4✔
184	args.memory_usage.memory_usage,	4✔
185	&thread_pool,	4✔
186	)?;
187
188	thread_pool.install(\|\| {	12✔
189	builder.par_comp_lenders_endianness(	8✔
190	&sorted,	4✔
191	sorted.num_nodes(),	8✔
192	&target_endianness,	4✔
193	)
194	})?;
195
196	return Ok(());	4✔
197	}
198
199	no_ef_warn(&args.src);	×
200
201	let seq_graph =	×
202	webgraph::graphs::bvgraph::sequential::BvGraphSeq::with_basename(&args.src)	×
203	.endianness::<E>()
204	.load()?;
205
206	let perm_graph = PermutedGraph {
207	graph: &seq_graph,	×
208	perm: &perm,	×
209	};
210
211	// simplify the graph
212	let sorted =	×
213	webgraph::transform::simplify(&perm_graph, args.memory_usage.memory_usage).unwrap();	×
214
215	thread_pool.install(\|\| {	×
216	builder.par_comp_lenders_endianness(&sorted, sorted.num_nodes(), &target_endianness)	×
217	})?;
218	}
219	// just compute the transpose on the fly
220	(None, None) => {	×
221	log::info!(	×
222	"No permutation or transposed graph provided, computing the transpose on the fly"	×
223	);
224	// if the .ef file exists, we can use the simplify split
225	if std::fs::metadata(args.src.with_extension("ef")).is_ok_and(\|x\| x.is_file()) {	×
226	log::info!(".ef file found, using simplify split");	×
227
228	let graph =	×
229	webgraph::graphs::bvgraph::random_access::BvGraph::with_basename(&args.src)	×
230	.endianness::<E>()
231	.load()?;
232
233	let sorted = webgraph::transform::simplify_split(
234	&graph,	×
235	args.memory_usage.memory_usage,	×
236	&thread_pool,	×
237	)?;
238
239	thread_pool.install(\|\| {	×
240	builder.par_comp_lenders_endianness(	×
241	&sorted,	×
242	sorted.num_nodes(),	×
243	&target_endianness,	×
244	)
245	})?;
246
247	return Ok(());	×
248	}
249
250	no_ef_warn(&args.src);	×
251
252	let seq_graph =	×
253	webgraph::graphs::bvgraph::sequential::BvGraphSeq::with_basename(&args.src)	×
254	.endianness::<E>()
255	.load()?;
256
257	// transpose the graph
258	let sorted =	×
259	webgraph::transform::simplify_sorted(seq_graph, args.memory_usage.memory_usage)	×
260	.unwrap();
261
262	thread_pool.install(\|\| {	×
263	builder.par_comp_lenders_endianness(&sorted, sorted.num_nodes(), &target_endianness)	×
264	})?;
265	}
266	}
267
268	Ok(())	×
269	}

vigna / webgraph-rs / 20017908129

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