18008720487

Committed 25 Sep 2025 01:16PM UTC coverage: 49.589% (-0.4%) from 49.949%

Build # 18008720487

Build Type

push

github

Committed by

vigna

Commit Message

Fixed fuzzing code for new epserde

Run Details

0 of 2 new or added lines in 1 file covered. (0.0%)

650 existing lines in 25 files now uncovered.

3862 of 7788 relevant lines covered (49.59%)

25127316.85 hits per line

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

0.0

/cli/src/dist/hyperball/mod.rs

/*
 * SPDX-FileCopyrightText: 2025 Tommaso Fontana
 * SPDX-FileCopyrightText: 2025 Sebastiano Vigna
 *
 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
 */
use crate::{get_thread_pool, FloatVectorFormat, GlobalArgs, GranularityArgs, NumThreadsArg};
use anyhow::{ensure, Result};
use clap::{ArgGroup, Args, Parser};
use dsi_bitstream::prelude::*;
use dsi_progress_logger::{concurrent_progress_logger, ProgressLog};
use epserde::deser::{Deserialize, Flags};
use rand::SeedableRng;
use std::path::PathBuf;
use webgraph::{
    graphs::bvgraph::get_endianness,
    prelude::{BvGraph, DCF, DEG_CUMUL_EXTENSION},
};
use webgraph_algo::distances::hyperball::HyperBallBuilder;

#[derive(Args, Debug, Clone)]
#[clap(group = ArgGroup::new("centralities"))]
/// Centralities that can be computed with hyperball.
///
/// To compress the result you can use named pipes or process substitution
/// like `--harmonic >(zstd > harmonic.zstd)`.
pub struct Centralities {
    /// How all the centralities will be stored.
    #[clap(long, value_enum, default_value_t = FloatVectorFormat::Ascii)]
    pub fmt: FloatVectorFormat,
    #[clap(long)]
    /// How many decimal digits will be used to store centralities in text formats.
    pub precision: Option<usize>,

    /// Compute the approximate sum of distances and save them as at the given path.
    #[clap(long)]
    pub sum_of_distances: Option<PathBuf>,
    /// Compute the approximate number of reachable nodes and save them as at the given path.
    #[clap(long)]
    pub reachable_nodes: Option<PathBuf>,
    /// Compute the approximate harmonic centralities and save them as at the given path.
    #[clap(long)]
    pub harmonic: Option<PathBuf>,
    /// Compute the approximate closeness centralities and save them as at the given path.
    #[clap(long)]
    pub closeness: Option<PathBuf>,
    #[clap(long)]
    /// Compute the approximate neighborhood function and save it as at the given path.
    pub neighborhood_function: Option<PathBuf>,
}

impl Centralities {
    pub fn should_compute_sum_of_distances(&self) -> bool {
        self.sum_of_distances.is_some() || self.closeness.is_some()
    }
    pub fn should_compute_sum_of_inverse_distances(&self) -> bool {
        self.harmonic.is_some()
    }
}

#[derive(Parser, Debug)]
#[command(
    name = "hyperball",
    about = "Use hyperball to compute centralities.",
    long_about = ""
)]
pub struct CliArgs {
    /// The basename of the graph.
    pub basename: PathBuf,

    #[clap(long, default_value_t = false)]
    /// Whether the graph is symmetric or not. If true, the algorithm will
    /// use the graph as its transposed.
    pub symm: bool,

    /// The basename of the transposed graph. If available, HyperBall will
    /// perform systolic iterations which will speed up the computation.
    /// If the graph is symmetric, use the --symm option instead.
    #[clap(short, long)]
    pub transposed: Option<PathBuf>,

    /// Compute the approximate neighborhood function, which will be
    /// store in ASCII format as BASENAME.nf.
    #[clap(short, long)]
    pub neighborhood_function: bool,

    #[clap(flatten)]
    pub centralities: Centralities,

    #[clap(short = 'm', long, default_value_t = 14)]
    /// The base-2 logarithm of the number of registers for the HyperLogLog
    /// cardinality estimators.
    pub log2m: usize,

    #[clap(long, default_value_t = usize::MAX)]
    /// Maximum number of iterations to run.
    pub upper_bound: usize,

    #[clap(long)]
    /// A value that will be used to stop the computation by relative increment
    /// if the neighborhood function is being computed. Otherwise, the
    /// computation will stop all estimators do not change their values.
    pub threshold: Option<f64>,

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

    #[clap(flatten)]
    pub granularity: GranularityArgs,

    #[clap(long, default_value_t = 0)]
    /// The seed of the pseudorandom number generator used for initialization.
    pub seed: u64,
}

pub fn main(global_args: GlobalArgs, args: CliArgs) -> Result<()> {
    ensure!(
        !args.symm || args.transposed.is_none(),
        "If the graph is symmetric, you should not pass the transpose."
    );

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

pub fn hyperball<E: Endianness>(global_args: GlobalArgs, args: CliArgs) -> Result<()> {
    let mut pl = concurrent_progress_logger![];
    if let Some(log_interval) = global_args.log_interval {
        pl.log_interval(log_interval);
    }
    let thread_pool = get_thread_pool(args.num_threads.num_threads);

    let graph = BvGraph::with_basename(&args.basename).load()?;

    log::info!("Loading DCF...");
    if !args.basename.with_extension(DEG_CUMUL_EXTENSION).exists() {
        log::error!(
            "Missing DCF file. Please run `webgraph build dcf {}`.",
            args.basename.display()
        );
    }
    let deg_cumul = unsafe {
        DCF::mmap(
            args.basename.with_extension(DEG_CUMUL_EXTENSION),
            Flags::RANDOM_ACCESS,
        )
    }?;

    log::info!("Loading Transposed graph...");
    let mut transposed = None;
    if let Some(transposed_path) = args.transposed.as_ref() {
        transposed = Some(BvGraph::with_basename(transposed_path).load()?);
    }
    let mut transposed_ref = transposed.as_ref();
    if args.symm {
        transposed_ref = Some(&graph);
    }

    let mut hb = HyperBallBuilder::with_hyper_log_log(
        &graph,
        transposed_ref,
        deg_cumul.uncase(),
        args.log2m,
        None,
    )?
    .granularity(args.granularity.into_granularity())
    .sum_of_distances(args.centralities.should_compute_sum_of_distances())
    .sum_of_inverse_distances(args.centralities.should_compute_sum_of_inverse_distances())
    .build(&mut pl);

    log::info!("Starting Hyperball...");
    let rng = rand::rngs::SmallRng::seed_from_u64(args.seed);
    hb.run(args.upper_bound, args.threshold, &thread_pool, rng, &mut pl)?;

    log::info!("Storing the results...");

    /// here we use a macro to avoid duplicating the code, it can't be a function
    /// because different centralities have different return types
    macro_rules! store_centrality {
        ($flag:ident, $method:ident, $description:expr) => {{
            if let Some(path) = args.centralities.$flag {
                log::info!("Saving {} to {}", $description, path.display());
                let value = hb.$method()?;
                args.centralities
                    .fmt
                    .store(path, &value, args.centralities.precision)?;
            }
        }};
    }

    store_centrality!(sum_of_distances, sum_of_distances, "sum of distances");
    store_centrality!(harmonic, harmonic_centralities, "harmonic centralities");
    store_centrality!(closeness, closeness_centrality, "closeness centralities");
    store_centrality!(reachable_nodes, reachable_nodes, "reachable nodes");
    store_centrality!(
        neighborhood_function,
        neighborhood_function,
        "neighborhood function"
    );

    Ok(())
}

1	/*
2	* SPDX-FileCopyrightText: 2025 Tommaso Fontana
3	* SPDX-FileCopyrightText: 2025 Sebastiano Vigna
4	*
5	* SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
6	*/
7	use crate::{get_thread_pool, FloatVectorFormat, GlobalArgs, GranularityArgs, NumThreadsArg};
8	use anyhow::{ensure, Result};
9	use clap::{ArgGroup, Args, Parser};
10	use dsi_bitstream::prelude::*;
11	use dsi_progress_logger::{concurrent_progress_logger, ProgressLog};
12	use epserde::deser::{Deserialize, Flags};
13	use rand::SeedableRng;
14	use std::path::PathBuf;
15	use webgraph::{
16	graphs::bvgraph::get_endianness,
17	prelude::{BvGraph, DCF, DEG_CUMUL_EXTENSION},
18	};
19	use webgraph_algo::distances::hyperball::HyperBallBuilder;
20
21	#[derive(Args, Debug, Clone)]
22	#[clap(group = ArgGroup::new("centralities"))]
23	/// Centralities that can be computed with hyperball.
24	///
25	/// To compress the result you can use named pipes or process substitution
26	/// like `--harmonic >(zstd > harmonic.zstd)`.
27	pub struct Centralities {
28	/// How all the centralities will be stored.
29	#[clap(long, value_enum, default_value_t = FloatVectorFormat::Ascii)]
30	pub fmt: FloatVectorFormat,
31	#[clap(long)]
32	/// How many decimal digits will be used to store centralities in text formats.
33	pub precision: Option<usize>,
34
35	/// Compute the approximate sum of distances and save them as at the given path.
36	#[clap(long)]
37	pub sum_of_distances: Option<PathBuf>,
38	/// Compute the approximate number of reachable nodes and save them as at the given path.
39	#[clap(long)]
40	pub reachable_nodes: Option<PathBuf>,
41	/// Compute the approximate harmonic centralities and save them as at the given path.
42	#[clap(long)]
43	pub harmonic: Option<PathBuf>,
44	/// Compute the approximate closeness centralities and save them as at the given path.
45	#[clap(long)]
46	pub closeness: Option<PathBuf>,
47	#[clap(long)]
48	/// Compute the approximate neighborhood function and save it as at the given path.
49	pub neighborhood_function: Option<PathBuf>,
50	}
51
52	impl Centralities {
53	pub fn should_compute_sum_of_distances(&self) -> bool {	×
54	self.sum_of_distances.is_some() \|\| self.closeness.is_some()	×
55	}
56	pub fn should_compute_sum_of_inverse_distances(&self) -> bool {	×
57	self.harmonic.is_some()	×
58	}
59	}
60
61	#[derive(Parser, Debug)]
62	#[command(
63	name = "hyperball",
64	about = "Use hyperball to compute centralities.",
65	long_about = ""
66	)]
67	pub struct CliArgs {
68	/// The basename of the graph.
69	pub basename: PathBuf,
70
71	#[clap(long, default_value_t = false)]
72	/// Whether the graph is symmetric or not. If true, the algorithm will
73	/// use the graph as its transposed.
74	pub symm: bool,
75
76	/// The basename of the transposed graph. If available, HyperBall will
77	/// perform systolic iterations which will speed up the computation.
78	/// If the graph is symmetric, use the --symm option instead.
79	#[clap(short, long)]
80	pub transposed: Option<PathBuf>,
81
82	/// Compute the approximate neighborhood function, which will be
83	/// store in ASCII format as BASENAME.nf.
84	#[clap(short, long)]
85	pub neighborhood_function: bool,
86
87	#[clap(flatten)]
88	pub centralities: Centralities,
89
90	#[clap(short = 'm', long, default_value_t = 14)]
91	/// The base-2 logarithm of the number of registers for the HyperLogLog
92	/// cardinality estimators.
93	pub log2m: usize,
94
95	#[clap(long, default_value_t = usize::MAX)]
96	/// Maximum number of iterations to run.
97	pub upper_bound: usize,
98
99	#[clap(long)]
100	/// A value that will be used to stop the computation by relative increment
101	/// if the neighborhood function is being computed. Otherwise, the
102	/// computation will stop all estimators do not change their values.
103	pub threshold: Option<f64>,
104
105	#[clap(flatten)]
106	pub num_threads: NumThreadsArg,
107
108	#[clap(flatten)]
109	pub granularity: GranularityArgs,
110
111	#[clap(long, default_value_t = 0)]
112	/// The seed of the pseudorandom number generator used for initialization.
113	pub seed: u64,
114	}
115
116	pub fn main(global_args: GlobalArgs, args: CliArgs) -> Result<()> {	×
117	ensure!(	×
118	!args.symm \|\| args.transposed.is_none(),	×
119	"If the graph is symmetric, you should not pass the transpose."	×
120	);
121
122	match get_endianness(&args.basename)?.as_str() {	×
123	#[cfg(feature = "be_bins")]
124	BE::NAME => hyperball::<BE>(global_args, args),	×
125	#[cfg(feature = "le_bins")]
126	LE::NAME => hyperball::<LE>(global_args, args),	×
127	e => panic!("Unknown endianness: {}", e),	×
128	}
129	}
130
131	pub fn hyperball<E: Endianness>(global_args: GlobalArgs, args: CliArgs) -> Result<()> {	×
132	let mut pl = concurrent_progress_logger![];	×
133	if let Some(log_interval) = global_args.log_interval {	×
134	pl.log_interval(log_interval);	×
135	}
136	let thread_pool = get_thread_pool(args.num_threads.num_threads);	×
137
138	let graph = BvGraph::with_basename(&args.basename).load()?;	×
139
140	log::info!("Loading DCF...");	×
141	if !args.basename.with_extension(DEG_CUMUL_EXTENSION).exists() {	×
142	log::error!(	×
143	"Missing DCF file. Please run `webgraph build dcf {}`.",	×
144	args.basename.display()	×
145	);
146	}
147	let deg_cumul = unsafe {
148	DCF::mmap(
149	args.basename.with_extension(DEG_CUMUL_EXTENSION),	×
UNCOV 150	Flags::RANDOM_ACCESS,	×
151	)
152	}?;
153
154	log::info!("Loading Transposed graph...");	×
155	let mut transposed = None;	×
UNCOV 156	if let Some(transposed_path) = args.transposed.as_ref() {	×
157	transposed = Some(BvGraph::with_basename(transposed_path).load()?);	×
158	}
159	let mut transposed_ref = transposed.as_ref();	×
UNCOV 160	if args.symm {	×
UNCOV 161	transposed_ref = Some(&graph);	×
162	}
163
164	let mut hb = HyperBallBuilder::with_hyper_log_log(
165	&graph,	×
166	transposed_ref,	×
167	deg_cumul.uncase(),	×
UNCOV 168	args.log2m,	×
169	None,	×
170	)?
171	.granularity(args.granularity.into_granularity())	×
172	.sum_of_distances(args.centralities.should_compute_sum_of_distances())	×
UNCOV 173	.sum_of_inverse_distances(args.centralities.should_compute_sum_of_inverse_distances())	×
174	.build(&mut pl);	×
175
176	log::info!("Starting Hyperball...");	×
UNCOV 177	let rng = rand::rngs::SmallRng::seed_from_u64(args.seed);	×
178	hb.run(args.upper_bound, args.threshold, &thread_pool, rng, &mut pl)?;	×
179
UNCOV 180	log::info!("Storing the results...");	×
181
182	/// here we use a macro to avoid duplicating the code, it can't be a function
183	/// because different centralities have different return types
184	macro_rules! store_centrality {	×
185	($flag:ident, $method:ident, $description:expr) => {{	×
186	if let Some(path) = args.centralities.$flag {	×
187	log::info!("Saving {} to {}", $description, path.display());	×
188	let value = hb.$method()?;	×
189	args.centralities	×
UNCOV 190	.fmt	×
UNCOV 191	.store(path, &value, args.centralities.precision)?;	×
192	}
193	}};
194	}
195
196	store_centrality!(sum_of_distances, sum_of_distances, "sum of distances");	×
197	store_centrality!(harmonic, harmonic_centralities, "harmonic centralities");	×
198	store_centrality!(closeness, closeness_centrality, "closeness centralities");	×
199	store_centrality!(reachable_nodes, reachable_nodes, "reachable nodes");	×
200	store_centrality!(	×
201	neighborhood_function,	×
UNCOV 202	neighborhood_function,	×
UNCOV 203	"neighborhood function"	×
204	);
205
UNCOV 206	Ok(())	×
207	}

vigna / webgraph-rs / 18008720487

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