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

Coverage Stats

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

79.17

/cli/src/perm/bfs.rs

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

use crate::{IntSliceFormat, LogIntervalArg, create_parent_dir};
use anyhow::Result;
use clap::Parser;
use dsi_bitstream::dispatch::factory::CodesReaderFactoryHelper;
use dsi_bitstream::prelude::*;
use dsi_progress_logger::prelude::*;
use std::path::PathBuf;
use webgraph::prelude::*;

#[derive(Parser, Debug)]
#[command(name = "bfs", about = "Computes the permutation induced by a breadth-first visit.", long_about = None, next_line_help = true)]
pub struct CliArgs {
    /// The basename of the graph.​
    pub basename: PathBuf,

    /// The filename of the permutation.​
    pub perm: PathBuf,

    #[arg(long, value_enum, default_value_t)]
    /// The format of the permutation file.​
    pub fmt: IntSliceFormat,

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

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

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

pub fn bfs<E: Endianness + 'static + Send + Sync>(args: CliArgs) -> Result<()>
where
    MemoryFactory<E, MmapHelper<u32>>: CodesReaderFactoryHelper<E>,
    for<'a> LoadModeCodesReader<'a, E, LoadMmap>: BitSeek,
{
    // load the graph
    let graph = BvGraph::with_basename(&args.basename)
        .mode::<LoadMmap>()
        .flags(MemoryFlags::TRANSPARENT_HUGE_PAGES | MemoryFlags::RANDOM_ACCESS)
        .endianness::<E>()
        .load()?;

    let mut pl = progress_logger![
        display_memory = true,
        item_name = "nodes",
        expected_updates = Some(graph.num_nodes()),
    ];
    if let Some(duration) = args.log_interval.log_interval {
        pl.log_interval(duration);
    }

    // create the permutation
    let mut perm = vec![0; graph.num_nodes()];
    pl.start("Computing BFS permutation...");
    let mut visit = webgraph::visits::breadth_first::Seq::new(&graph);
    for (i, event) in visit.into_iter().enumerate() {
        perm[event.node] = i;
        pl.light_update();
    }
    pl.done();

    args.fmt.store(&args.perm, &perm, None)?;

    Ok(())
}

1	/*
2	* SPDX-FileCopyrightText: 2023 Sebastiano Vigna
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::{IntSliceFormat, LogIntervalArg, create_parent_dir};
9	use anyhow::Result;
10	use clap::Parser;
11	use dsi_bitstream::dispatch::factory::CodesReaderFactoryHelper;
12	use dsi_bitstream::prelude::*;
13	use dsi_progress_logger::prelude::*;
14	use std::path::PathBuf;
15	use webgraph::prelude::*;
16
17	#[derive(Parser, Debug)]
18	#[command(name = "bfs", about = "Computes the permutation induced by a breadth-first visit.", long_about = None, next_line_help = true)]
19	pub struct CliArgs {
20	/// The basename of the graph.
21	pub basename: PathBuf,
22
23	/// The filename of the permutation.
24	pub perm: PathBuf,
25
26	#[arg(long, value_enum, default_value_t)]
27	/// The format of the permutation file.
28	pub fmt: IntSliceFormat,
29
30	#[clap(flatten)]
31	pub log_interval: LogIntervalArg,
32	}
33
34	pub fn main(args: CliArgs) -> Result<()> {	5✔
35	create_parent_dir(&args.perm)?;	10✔
36
37	match get_endianness(&args.basename)?.as_str() {	15✔
38	#[cfg(feature = "be_bins")]
39	BE::NAME => bfs::<BE>(args),	15✔
40	#[cfg(feature = "le_bins")]
41	LE::NAME => bfs::<LE>(args),	×
42	e => panic!("Unknown endianness: {}", e),	×
43	}
44	}
45
46	pub fn bfs<E: Endianness + 'static + Send + Sync>(args: CliArgs) -> Result<()>	5✔
47	where
48	MemoryFactory<E, MmapHelper<u32>>: CodesReaderFactoryHelper<E>,
49	for<'a> LoadModeCodesReader<'a, E, LoadMmap>: BitSeek,
50	{
51	// load the graph
52	let graph = BvGraph::with_basename(&args.basename)	15✔
53	.mode::<LoadMmap>()
54	.flags(MemoryFlags::TRANSPARENT_HUGE_PAGES \| MemoryFlags::RANDOM_ACCESS)	10✔
55	.endianness::<E>()
56	.load()?;
57
58	let mut pl = progress_logger![	10✔
59	display_memory = true,	×
60	item_name = "nodes",	×
61	expected_updates = Some(graph.num_nodes()),	5✔
62	];
63	if let Some(duration) = args.log_interval.log_interval {	5✔
64	pl.log_interval(duration);	×
65	}
66
67	// create the permutation
68	let mut perm = vec![0; graph.num_nodes()];	20✔
69	pl.start("Computing BFS permutation...");	10✔
70	let mut visit = webgraph::visits::breadth_first::Seq::new(&graph);	15✔
71	for (i, event) in visit.into_iter().enumerate() {	4,883,370✔
72	perm[event.node] = i;	3,255,570✔
73	pl.light_update();	1,627,785✔
74	}
75	pl.done();	10✔
76
77	args.fmt.store(&args.perm, &perm, None)?;	25✔
78
79	Ok(())	5✔
80	}

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