webgraph_algo/distances/exact_sum_sweep/
mod.rs

1/*
2 * SPDX-FileCopyrightText: 2024 Matteo Dell'Acqua
3 * SPDX-FileCopyrightText: 2025 Sebastiano Vigna
4 *
5 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
6 */
7
8//! An implementation of the ExactSumSweep algorithm.
9//!
10//! The algorithm has been described by Michele Borassi, Pierluigi Crescenzi,
11//! Michel Habib, Walter A. Kosters, Andrea Marino, and Frank W. Takes in “[Fast
12//! diameter and radius BFS-based computation in (weakly connected) real-world
13//! graphs–With an application to the six degrees of separation
14//! games](https://doi.org/10.1016/j.tcs.2015.02.033)”.
15//!
16//! The algorithm can compute the diameter, the radius, and even the
17//! eccentricities (forward and backward) of a graph. These tasks are quadratic
18//! in nature, but ExactSumSweep uses a number of heuristic to reduce the
19//! computation to a relatively small number of visits on real-world graphs. It
20//! has been used, for examples, on the [whole Facebook
21//! graph](https://doi.org/10.1145/2380718.2380723).
22//!
23//! Depending on what you intend to compute, you have to choose the right
24//! [*level*](Level) between [`All`], [`AllForward`], [`RadiusDiameter`],
25//! [`Diameter`], and [`Radius`]. Then you have to invoke [`run`](Level::run) or
26//! [`run_symm`](Level::run_symm). In the first case, you have to provide a
27//! graph and its transpose; in the second case, you have to provide a symmetric
28//! graph. The methods returns a suitable structure containing the result of the
29//! algorithm.
30//!
31//! # Examples
32//!
33//! ```
34//! use webgraph_algo::distances::exact_sum_sweep::{self, *};
35//! use dsi_progress_logger::no_logging;
36//! use webgraph::graphs::vec_graph::VecGraph;
37//! use webgraph::labels::proj::Left;
38//!
39//! let graph = VecGraph::from_arcs([(0, 1), (1, 2), (2, 3), (3, 0), (2, 4)]);
40//! let transpose = VecGraph::from_arcs([(1, 0), (2, 1), (3, 2), (0, 3), (4, 2)]);
41//!
42//! // Let's compute all eccentricities
43//! let result = exact_sum_sweep::All::run(
44//!     &graph,
45//!     &transpose,
46//!     None,
47//!     no_logging![]
48//! );
49//!
50//! assert_eq!(result.diameter, 4);
51//! assert_eq!(result.radius, 3);
52//! assert_eq!(result.forward_eccentricities.as_ref(), &vec![3, 3, 3, 4, 0]);
53//! assert_eq!(result.backward_eccentricities.as_ref(), &vec![3, 3, 3, 3, 4]);
54//!
55//! // Let's just compute the radius and diameter
56//! let result = exact_sum_sweep::RadiusDiameter::run(
57//!     &graph,
58//!     &transpose,
59//!     None,
60//!     no_logging![]
61//! );
62//!
63//! assert_eq!(result.diameter, 4);
64//! assert_eq!(result.radius, 3);
65//! ```
66//!
67//! Note how certain information is not available if not computed.
68//! ```compile_fail
69//! use webgraph_algo::distances::exact_sum_sweep::{self, *};
70//! use dsi_progress_logger::no_logging;
71//! use webgraph::graphs::vec_graph::VecGraph;
72//!
73//! let graph = VecGraph::from_arcs([(0, 1), (1, 2), (2, 3), (3, 0), (2, 4)]);
74//! let transpose = VecGraph::from_arcs([(1, 0), (2, 1), (3, 2), (0, 3), (4, 2)]);
75//!
76//! let result = exact_sum_sweep::RadiusDiameter::run(
77//!     &graph,
78//!     &transpose,
79//!     None,
80//!     no_logging![]
81//! );
82//!
83//! assert_eq!(result.diameter, 4);
84//! assert_eq!(result.radius, 3);
85//! // Without these it would compile
86//! assert_eq!(result.forward_eccentricities.as_ref(), &vec![3, 3, 3, 4, 0]);
87//! assert_eq!(result.backward_eccentricities.as_ref(), &vec![3, 3, 3, 3, 4]);
88//! ```
89//!
90//! If the graph is symmetric (i.e., undirected), you may use
91//! [run_symm](Level::run_symm).
92//! ```
93//! use webgraph_algo::distances::exact_sum_sweep::{self, *};
94//! use dsi_progress_logger::no_logging;
95//! use webgraph::graphs::vec_graph::VecGraph;
96//!
97//! let graph = VecGraph::from_arcs(
98//!     [(0, 1), (1, 0), (1, 2), (2, 1), (2, 0), (0, 2), (3, 4), (4, 3)]
99//! );
100//!
101//! let result = exact_sum_sweep::RadiusDiameter::run_symm(
102//!     &graph,
103//!     no_logging![]
104//! );
105//!
106//! assert_eq!(result.diameter, 1);
107//! assert_eq!(result.radius, 1);
108//! ```
109
110mod computer;
111mod level;
112pub mod output;
113pub mod output_symm;
114mod scc_graph;
115
116pub use level::*;
webgraph_algo/distances/exact_sum_sweep/mod.rs

webgraph_algo/distances/exact_sum_sweep/
mod.rs
