webgraph_cli/
sccs.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::{build_info, num_threads_parser, pretty_print_elapsed, IntVectorFormat};
8use anyhow::Result;
9use clap::Parser;
10use dsi_bitstream::prelude::factory::CodesReaderFactoryHelper;
11use dsi_bitstream::prelude::*;
12use dsi_progress_logger::{progress_logger, ProgressLog};
13use std::path::PathBuf;
14use webgraph::graphs::bvgraph::get_endianness;
15use webgraph::prelude::*;
16use webgraph_algo::thread_pool;
17
18use super::GlobalArgs;
19
20#[derive(Parser, Debug)]
21#[command(name = "webgraph-sccs", version=build_info::version_string())]
22/// Computes the strongly connected components of a graph of given basename.
23///
24/// Note that on shells supporting process substitution you compress the results
25/// using a suitable syntax. For example on bash / zsh, you can use the path
26/// `>(zstd > sccs.zstd)`.
27///
28/// Noteworthy environment variables:
29///
30/// - RUST_MIN_STACK: minimum thread stack size (in bytes); we suggest
31///   RUST_MIN_STACK=8388608 (8MiB)
32///
33/// - TMPDIR: where to store temporary files (potentially very large ones)
34///
35/// - RUST_LOG: configuration for env_logger
36///   <https://docs.rs/env_logger/latest/env_logger/>
37pub struct Cli {
38    #[clap(flatten)]
39    global_args: GlobalArgs,
40    #[clap(flatten)]
41    args: CliArgs,
42}
43
44#[derive(Parser, Debug)]
45pub struct CliArgs {
46    /// The basename of the graph.
47    pub basename: PathBuf,
48
49    /// The path where to save the strongly connected components.
50    pub sccs: PathBuf,
51
52    #[arg(short = 's', long)]
53    /// Compute the size of the strongly connected components and store them
54    /// at the given path.
55    pub sizes: Option<PathBuf>,
56
57    #[arg(short, long)]
58    /// Renumber components in decreasing-size order (implicitly, compute sizes).
59    pub renumber: bool,
60
61    #[arg(short = 'j', long, default_value_t = rayon::current_num_threads().max(1), value_parser = num_threads_parser)]
62    /// The number of threads to use to compute the sizes of the components.
63    pub num_threads: usize,
64
65    #[arg(long, value_enum, default_value_t = IntVectorFormat::Ascii)]
66    /// The storage format for components and component sizes.
67    pub fmt: IntVectorFormat,
68}
69
70pub fn cli_main<I, T>(args: I) -> Result<()>
71where
72    I: IntoIterator<Item = T>,
73    T: Into<std::ffi::OsString> + Clone,
74{
75    let start = std::time::Instant::now();
76    let cli = Cli::parse_from(args);
77    main(cli.global_args, cli.args)?;
78
79    log::info!(
80        "The command took {}",
81        pretty_print_elapsed(start.elapsed().as_secs_f64())
82    );
83
84    Ok(())
85}
86
87pub fn main(global_args: GlobalArgs, args: CliArgs) -> Result<()> {
88    match get_endianness(&args.basename)?.as_str() {
89        #[cfg(feature = "be_bins")]
90        BE::NAME => sccs::<BE>(global_args, args),
91        #[cfg(feature = "le_bins")]
92        LE::NAME => sccs::<LE>(global_args, args),
93        e => panic!("Unknown endianness: {}", e),
94    }
95}
96
97pub fn sccs<E: Endianness>(global_args: GlobalArgs, args: CliArgs) -> Result<()>
98where
99    MemoryFactory<E, MmapHelper<u32>>: CodesReaderFactoryHelper<E>,
100    for<'a> LoadModeCodesReader<'a, E, LoadMmap>: BitSeek,
101{
102    log::info!("Loading the graph from {}", args.basename.display());
103    let graph = BvGraph::with_basename(&args.basename)
104        .mode::<LoadMmap>()
105        .flags(MemoryFlags::TRANSPARENT_HUGE_PAGES | MemoryFlags::RANDOM_ACCESS)
106        .endianness::<E>()
107        .load()?;
108
109    let mut pl = progress_logger![];
110    if let Some(log_interval) = global_args.log_interval {
111        pl.log_interval(log_interval);
112    }
113
114    let mut sccs = webgraph_algo::sccs::tarjan(graph, &mut pl);
115    log::info!(
116        "Found {} strongly connected components",
117        sccs.num_components()
118    );
119
120    if args.renumber {
121        log::info!("Renumbering components by decreasing size");
122        let component_sizes = if args.num_threads == 1 {
123            log::debug!("Using sequential algorithm");
124            sccs.sort_by_size()
125        } else {
126            log::debug!("Using parallel algorithm with {} threads", args.num_threads);
127            let thread_pool = thread_pool![args.num_threads];
128            thread_pool.install(|| sccs.par_sort_by_size())
129        };
130        let max = component_sizes.first().copied();
131        args.fmt.store_usizes(&args.sccs, &component_sizes, max)?;
132    } else if let Some(sizes_path) = args.sizes {
133        log::info!("Computing the sizes of the components");
134        let sizes = sccs.compute_sizes();
135        args.fmt.store_usizes(sizes_path, &sizes, None)?;
136    };
137
138    args.fmt
139        .store_usizes(&args.sccs, sccs.components(), Some(sccs.num_components()))?;
140
141    Ok(())
142}
webgraph_cli/sccs.rs

webgraph_cli/
sccs.rs
