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

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::{FloatSliceFormat, GranularityArgs, LogIntervalArg, NumThreadsArg, get_thread_pool};
use anyhow::{Result, bail, ensure};
use clap::{ArgGroup, Args, Parser};
use dsi_bitstream::prelude::*;
use dsi_progress_logger::{ProgressLog, concurrent_progress_logger};
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 {
    /// Storage format for centralities.​
    #[clap(long, value_enum, default_value_t = FloatSliceFormat::Ascii)]
    pub fmt: FloatSliceFormat,
    #[clap(long)]
    /// Number of decimal digits for centralities in text formats.​
    pub precision: Option<usize>,

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

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

#[derive(Parser, Debug)]
#[command(
    name = "hyperball",
    about = "Computes centralities using HyperBall.",
    long_about = None, next_line_help = true)]
pub struct CliArgs {
    /// The basename of the graph.​
    pub basename: PathBuf,

    #[clap(long, default_value_t = false)]
    /// The graph is symmetric (it will be used as its own transpose).​
    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>,

    #[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 when all estimators do not change their values.​
    pub threshold: Option<f64>,

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

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

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

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

pub fn main(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>(args),
        #[cfg(feature = "le_bins")]
        LE::NAME => hyperball::<LE>(args),
        e => panic!("Unknown endianness: {}", e),
    }
}

pub fn hyperball<E: Endianness>(args: CliArgs) -> Result<()> {
    let mut pl = concurrent_progress_logger![];
    if let Some(log_interval) = args.log_interval.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() {
        bail!(
            "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);
    thread_pool.install(|| hb.run(args.upper_bound, args.threshold, 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::{FloatSliceFormat, GranularityArgs, LogIntervalArg, NumThreadsArg, get_thread_pool};
8	use anyhow::{Result, bail, ensure};
9	use clap::{ArgGroup, Args, Parser};
10	use dsi_bitstream::prelude::*;
11	use dsi_progress_logger::{ProgressLog, concurrent_progress_logger};
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	/// Storage format for centralities.
29	#[clap(long, value_enum, default_value_t = FloatSliceFormat::Ascii)]
30	pub fmt: FloatSliceFormat,
31	#[clap(long)]
32	/// Number of decimal digits for centralities in text formats.
33	pub precision: Option<usize>,
34
35	/// Compute the approximate sum of distances and save them 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 at the given path.
39	#[clap(long)]
40	pub reachable_nodes: Option<PathBuf>,
41	/// Compute the approximate harmonic centralities and save them at the given path.
42	#[clap(long)]
43	pub harmonic: Option<PathBuf>,
44	/// Compute the approximate closeness centralities and save them at the given path.
45	#[clap(long)]
46	pub closeness: Option<PathBuf>,
47	#[clap(long)]
48	/// Compute the approximate neighborhood function and save it at the given path.
49	pub neighborhood_function: Option<PathBuf>,
50	}
51
52	impl Centralities {
53	pub const fn should_compute_sum_of_distances(&self) -> bool {	×
54	self.sum_of_distances.is_some() \|\| self.closeness.is_some()	×
55	}
56	pub const 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 = "Computes centralities using HyperBall.",
65	long_about = None, next_line_help = true)]
66	pub struct CliArgs {
67	/// The basename of the graph.
68	pub basename: PathBuf,
69
70	#[clap(long, default_value_t = false)]
71	/// The graph is symmetric (it will be used as its own transpose).
72	pub symm: bool,
73
74	/// The basename of the transposed graph. If available, HyperBall will
75	/// perform systolic iterations which will speed up the computation.
76	/// If the graph is symmetric, use the --symm option instead.
77	#[clap(short, long)]
78	pub transposed: Option<PathBuf>,
79
80	#[clap(flatten)]
81	pub centralities: Centralities,
82
83	#[clap(short = 'm', long, default_value_t = 14)]
84	/// The base-2 logarithm of the number of registers for the HyperLogLog
85	/// cardinality estimators.
86	pub log2m: usize,
87
88	#[clap(long, default_value_t = usize::MAX)]
89	/// Maximum number of iterations to run.
90	pub upper_bound: usize,
91
92	#[clap(long)]
93	/// A value that will be used to stop the computation by relative increment
94	/// if the neighborhood function is being computed. Otherwise, the
95	/// computation will stop when all estimators do not change their values.
96	pub threshold: Option<f64>,
97
98	#[clap(flatten)]
99	pub num_threads: NumThreadsArg,
100
101	#[clap(flatten)]
102	pub granularity: GranularityArgs,
103
104	#[clap(flatten)]
105	pub log_interval: LogIntervalArg,
106
107	#[clap(long, default_value_t = 0)]
108	/// The seed of the pseudorandom number generator used for initialization.
109	pub seed: u64,
110	}
111
112	pub fn main(args: CliArgs) -> Result<()> {	×
113	ensure!(	×
114	!args.symm \|\| args.transposed.is_none(),	×
115	"If the graph is symmetric, you should not pass the transpose."
116	);
117
118	match get_endianness(&args.basename)?.as_str() {	×
119	#[cfg(feature = "be_bins")]
120	BE::NAME => hyperball::<BE>(args),	×
121	#[cfg(feature = "le_bins")]
122	LE::NAME => hyperball::<LE>(args),	×
123	e => panic!("Unknown endianness: {}", e),	×
124	}
125	}
126
127	pub fn hyperball<E: Endianness>(args: CliArgs) -> Result<()> {	×
128	let mut pl = concurrent_progress_logger![];	×
129	if let Some(log_interval) = args.log_interval.log_interval {	×
130	pl.log_interval(log_interval);	×
131	}
132	let thread_pool = get_thread_pool(args.num_threads.num_threads);	×
133
134	let graph = BvGraph::with_basename(&args.basename).load()?;	×
135
136	log::info!("Loading DCF...");	×
137	if !args.basename.with_extension(DEG_CUMUL_EXTENSION).exists() {	×
138	bail!(	×
139	"Missing DCF file. Please run `webgraph build dcf {}`.",	×
140	args.basename.display()	×
141	);
142	}
143	let deg_cumul = unsafe {
144	DCF::mmap(
145	args.basename.with_extension(DEG_CUMUL_EXTENSION),	×
146	Flags::RANDOM_ACCESS,	×
147	)
148	}?;
149
150	log::info!("Loading Transposed graph...");	×
151	let mut transposed = None;	×
152	if let Some(transposed_path) = args.transposed.as_ref() {	×
153	transposed = Some(BvGraph::with_basename(transposed_path).load()?);	×
154	}
155	let mut transposed_ref = transposed.as_ref();	×
156	if args.symm {	×
157	transposed_ref = Some(&graph);	×
158	}
159
160	let mut hb = HyperBallBuilder::with_hyper_log_log(
161	&graph,	×
162	transposed_ref,	×
163	deg_cumul.uncase(),	×
164	args.log2m,	×
165	None,	×
166	)?
167	.granularity(args.granularity.into_granularity())	×
168	.sum_of_distances(args.centralities.should_compute_sum_of_distances())	×
169	.sum_of_inverse_distances(args.centralities.should_compute_sum_of_inverse_distances())	×
170	.build(&mut pl);	×
171
172	log::info!("Starting Hyperball...");	×
173	let rng = rand::rngs::SmallRng::seed_from_u64(args.seed);	×
174	thread_pool.install(\|\| hb.run(args.upper_bound, args.threshold, rng, &mut pl))?;	×
175
176	log::info!("Storing the results...");	×
177
178	/// here we use a macro to avoid duplicating the code, it can't be a function
179	/// because different centralities have different return types
180	macro_rules! store_centrality {	×
181	($flag:ident, $method:ident, $description:expr) => {{	×
182	if let Some(path) = args.centralities.$flag {	×
183	log::info!("Saving {} to {}", $description, path.display());	×
184	let value = hb.$method()?;	×
185	args.centralities	×
186	.fmt	×
187	.store(path, &value, args.centralities.precision)?;	×
188	}
189	}};
190	}
191
192	store_centrality!(sum_of_distances, sum_of_distances, "sum of distances");	×
193	store_centrality!(harmonic, harmonic_centralities, "harmonic centralities");	×
194	store_centrality!(closeness, closeness_centrality, "closeness centralities");	×
195	store_centrality!(reachable_nodes, reachable_nodes, "reachable nodes");	×
196	store_centrality!(	×
197	neighborhood_function,	×
198	neighborhood_function,	×
199	"neighborhood function"	×
200	);
201
202	Ok(())	×
203	}

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