webgraph_cli/dist/ess/
mod.rs

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 */
7use crate::{GlobalArgs, IntVectorFormat, NumThreadsArg};
8use anyhow::{Result, ensure};
9use clap::{Parser, ValueEnum};
10use dsi_bitstream::prelude::*;
11use dsi_progress_logger::{ProgressLog, concurrent_progress_logger};
12use std::path::PathBuf;
13use webgraph::{graphs::bvgraph::get_endianness, prelude::BvGraph};
14use webgraph_algo::distances::exact_sum_sweep::{
15    All, AllForward, Diameter, Level, Radius, RadiusDiameter,
16};
17
18#[derive(Parser, Debug)]
19#[command(name = "exact-sum-sweep", about = "Computes radius, diameter, and possibly eccentricities using the ExactSumSweep algorithm (scalar values are printed on stdout).", long_about = None)]
20pub struct CliArgs {
21    /// The basename of the graph.
22    pub basename: PathBuf,
23
24    /// The transposed graph of "basename".
25    pub transposed: Option<PathBuf>,
26
27    #[arg(short, long = "symm")]
28    /// If passed, we assume that the graph is symmetric.
29    pub symmetric: bool,
30
31    /// The path where to store the forward eccentricities.
32    #[arg(short, long)]
33    pub forward: Option<PathBuf>,
34
35    /// The path where to store the backward eccentricities.
36    #[arg(short, long)]
37    pub backward: Option<PathBuf>,
38
39    /// The items to be computed (all-forward computes forward eccentricities, all computes both forward and backward eccentricities).
40    #[arg(long, value_enum)]
41    pub level: LevelArg,
42
43    #[arg(long, value_enum, default_value_t = IntVectorFormat::Ascii)]
44    /// The storage format for eccentricities.
45    pub fmt: IntVectorFormat,
46
47    #[clap(flatten)]
48    pub num_threads: NumThreadsArg,
49}
50
51/// The level of exact sum sweep to compute.
52#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, ValueEnum)]
53pub enum LevelArg {
54    Radius,
55    Diameter,
56    #[clap(name = "radius-diameter")]
57    RadiusDiameter,
58    #[clap(name = "all-forward")]
59    AllForward,
60    All,
61}
62
63pub fn main(global_args: GlobalArgs, args: CliArgs) -> Result<()> {
64    ensure!(
65        args.symmetric || args.transposed.is_some(),
66        "You have to either pass --transposed with the basename of the transposed graph or --symm if the graph is symmetric."
67    );
68    ensure!(
69        !(args.symmetric && args.transposed.is_some()),
70        "--transposed is needed only if the graph is not symmetric."
71    );
72    ensure!(
73        args.forward.is_none() || matches!(args.level, LevelArg::All | LevelArg::AllForward),
74        "You can only pass --forward with --level=all or --level=all-forward, as the forward eccentricities won't be computed otherwise."
75    );
76    ensure!(
77        !(args.forward.is_none() && matches!(args.level, LevelArg::All | LevelArg::AllForward)),
78        "If --level=all or --level=all-forward, you should pass --forward to store the computed eccentricities."
79    );
80    ensure!(
81        !(args.backward.is_some() && args.level != LevelArg::All),
82        "You cannot only pass --backward with --level=all as the backward eccentricities won't be computed otherwise."
83    );
84    ensure!(
85        !(args.level == LevelArg::All && args.symmetric && args.backward.is_some()),
86        "You cannot pass --backward with --symm and --level=all as the eccentricities of a symmetric graph are the same in both directions."
87    );
88
89    match get_endianness(&args.basename)?.as_str() {
90        #[cfg(feature = "be_bins")]
91        BE::NAME => exact_sum_sweep::<BE>(global_args, args),
92        #[cfg(feature = "le_bins")]
93        LE::NAME => exact_sum_sweep::<LE>(global_args, args),
94        e => panic!("Unknown endianness: {}", e),
95    }
96}
97
98/// Stores eccentricities to a file using the specified format.
99fn store_eccentricities(
100    eccentricities: &[usize],
101    path: &PathBuf,
102    fmt: IntVectorFormat,
103) -> Result<()> {
104    fmt.store_usizes(path, eccentricities, None)
105}
106
107pub fn exact_sum_sweep<E: Endianness>(global_args: GlobalArgs, args: CliArgs) -> Result<()> {
108    let graph = BvGraph::with_basename(&args.basename).load()?;
109
110    let thread_pool = crate::get_thread_pool(args.num_threads.num_threads);
111    let mut pl = concurrent_progress_logger![];
112    if let Some(log_interval) = global_args.log_interval {
113        pl.log_interval(log_interval);
114    }
115
116    if args.symmetric {
117        match args.level {
118            LevelArg::Radius => {
119                let out = thread_pool.install(|| Radius::run_symm(graph, &mut pl));
120                println!("Radius: {}", out.radius);
121                println!("Radial vertex: {}", out.radial_vertex);
122                println!("Radius iterations: {}", out.radius_iterations);
123            }
124            LevelArg::Diameter => {
125                let out = thread_pool.install(|| Diameter::run_symm(graph, &mut pl));
126                println!("Diameter: {}", out.diameter);
127                println!("Diametral vertex: {}", out.diametral_vertex);
128                println!("Diameter iterations: {}", out.diameter_iterations);
129            }
130            LevelArg::RadiusDiameter => {
131                let out = thread_pool.install(|| RadiusDiameter::run_symm(graph, &mut pl));
132                println!("Radius: {}", out.radius);
133                println!("Diameter: {}", out.diameter);
134                println!("Radial vertex: {}", out.radial_vertex);
135                println!("Diametral vertex: {}", out.diametral_vertex);
136                println!("Radius iterations: {}", out.radius_iterations);
137                println!("Diameter iterations: {}", out.diameter_iterations);
138            }
139            LevelArg::AllForward | LevelArg::All => {
140                let out = thread_pool.install(|| All::run_symm(graph, &mut pl));
141                println!("Radius: {}", out.radius);
142                println!("Diameter: {}", out.diameter);
143                println!("Radial vertex: {}", out.radial_vertex);
144                println!("Diametral vertex: {}", out.diametral_vertex);
145                println!("Radius iterations: {}", out.radius_iterations);
146                println!("Diameter iterations: {}", out.diameter_iterations);
147                println!("Iterations: {}", out.iterations);
148                store_eccentricities(
149                    &out.eccentricities,
150                    args.forward.as_ref().unwrap(),
151                    args.fmt,
152                )?;
153            }
154        }
155    } else {
156        let transpose_path = args
157            .transposed
158            .as_ref()
159            .expect("You have to pass the transposed graph if the graph is not symmetric.");
160        let transpose = BvGraph::with_basename(transpose_path).load()?;
161
162        match args.level {
163            LevelArg::Radius => {
164                let out = thread_pool.install(|| Radius::run(graph, transpose, None, &mut pl));
165                println!("Radius: {}", out.radius);
166                println!("Radial vertex: {}", out.radial_vertex);
167                println!("Radius iterations: {}", out.radius_iterations);
168            }
169            LevelArg::Diameter => {
170                let out = thread_pool.install(|| Diameter::run(graph, transpose, None, &mut pl));
171                println!("Diameter: {}", out.diameter);
172                println!("Diametral vertex: {}", out.diametral_vertex);
173                println!("Diameter iterations: {}", out.diameter_iterations);
174            }
175            LevelArg::RadiusDiameter => {
176                let out =
177                    thread_pool.install(|| RadiusDiameter::run(graph, transpose, None, &mut pl));
178                println!("Radius: {}", out.radius);
179                println!("Diameter: {}", out.diameter);
180                println!("Radial vertex: {}", out.radial_vertex);
181                println!("Diametral vertex: {}", out.diametral_vertex);
182                println!("Radius iterations: {}", out.radius_iterations);
183                println!("Diameter iterations: {}", out.diameter_iterations);
184            }
185            LevelArg::AllForward => {
186                let out = thread_pool.install(|| AllForward::run(graph, transpose, None, &mut pl));
187                println!("Radius: {}", out.radius);
188                println!("Diameter: {}", out.diameter);
189                println!("Radial vertex: {}", out.radial_vertex);
190                println!("Diametral vertex: {}", out.diametral_vertex);
191                println!("Radius iterations: {}", out.radius_iterations);
192                println!("Diameter iterations: {}", out.diameter_iterations);
193                println!("Forward iterations: {}", out.forward_iterations);
194                store_eccentricities(
195                    &out.forward_eccentricities,
196                    args.forward.as_ref().unwrap(),
197                    args.fmt,
198                )?;
199            }
200            LevelArg::All => {
201                let out = thread_pool.install(|| All::run(graph, transpose, None, &mut pl));
202                println!("Radius: {}", out.radius);
203                println!("Diameter: {}", out.diameter);
204                println!("Radial vertex: {}", out.radial_vertex);
205                println!("Diametral vertex: {}", out.diametral_vertex);
206                println!("Radius iterations: {}", out.radius_iterations);
207                println!("Diameter iterations: {}", out.diameter_iterations);
208                println!("Forward iterations: {}", out.forward_iterations);
209                println!("All iterations: {}", out.all_iterations);
210                store_eccentricities(
211                    &out.forward_eccentricities,
212                    args.forward.as_ref().unwrap(),
213                    args.fmt,
214                )?;
215                if let Some(backward) = args.backward.as_ref() {
216                    store_eccentricities(&out.backward_eccentricities, backward, args.fmt)?;
217                }
218            }
219        }
220    }
221
222    Ok(())
223}
webgraph_cli/dist/ess/mod.rs

webgraph_cli/dist/ess/
mod.rs
