webgraph_algo/distances/exact_sum_sweep/
level.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
8use super::{computer::DirExactSumSweepComputer, output, output_symm};
9use dsi_progress_logger::ConcurrentProgressLog;
10use sux::bits::AtomicBitVec;
11use webgraph::traits::RandomAccessGraph;
12
13#[doc(hidden)]
14#[derive(Debug, Clone, Copy, Default)]
15pub struct Missing {
16    pub radius: usize,
17    pub diameter_forward: usize,
18    pub diameter_backward: usize,
19    pub all_forward: usize,
20    pub all_backward: usize,
21}
22
23impl core::ops::Add for Missing {
24    type Output = Self;
25
26    fn add(self, rhs: Self) -> Self {
27        Self {
28            radius: self.radius + rhs.radius,
29            diameter_forward: self.diameter_forward + rhs.diameter_forward,
30            diameter_backward: self.diameter_backward + rhs.diameter_backward,
31            all_forward: self.all_forward + rhs.all_forward,
32            all_backward: self.all_backward + rhs.all_backward,
33        }
34    }
35}
36
37/// Trait used to run the ExactSumSweep algorithm.
38///
39/// This trait can be used to run the algorithm either [providing a graph and
40/// its transpose](Self::run) or [using a symmetric graph](Self::run_symm).
41///
42/// It is implemented by the following structs: [`All`], [`AllForward`],
43/// [`RadiusDiameter`], [`Diameter`], and [`Radius`], which correspond to
44/// different level of computation, with decreasing cost in term of memory and
45/// execution time.
46///
47/// # Examples
48///
49/// See the [module documentation](crate::distances::exact_sum_sweep).
50pub trait Level: Sync {
51    /// The type of the result of [`run`](Self::run).
52    type Output: Send;
53    /// The type of the result of [`run_symm`](Self::run_symm).
54    type OutputSymm: Send;
55
56    /// Runs the ExactSumSweep algorithm on the specified graph.
57    ///
58    /// # Arguments
59    ///
60    /// * `graph`: a graph.
61    ///
62    /// * `transpose`: the transpose of `graph`. Note that you are responsible
63    ///   for providing a correct transpose. The result of the computation is
64    ///   undefined otherwise.
65    ///
66    /// * `radial_vertices`: an [`AtomicBitVec`] where `v[i]` is true if node
67    ///   `i` is to be considered radial vertex. If [`None`] the algorithm will
68    ///   use the biggest connected component.
69    ///
70    /// * `pl`: a progress logger.
71    fn run(
72        graph: impl RandomAccessGraph + Sync,
73        transpose: impl RandomAccessGraph + Sync,
74        radial_vertices: Option<AtomicBitVec>,
75        pl: &mut impl ConcurrentProgressLog,
76    ) -> Self::Output;
77
78    /// Runs the ExactSumSweep algorithm on the specified symmetric graph.
79    ///
80    /// # Arguments
81    ///
82    /// * `graph`: a symmetric graph. Note that you are responsible for the
83    ///   graph being symmetric. The result of the computation is undefined
84    ///   otherwise.
85    ///
86    /// * `pl`: a progress logger.
87    fn run_symm(
88        graph: impl RandomAccessGraph + Sync,
89        pl: &mut impl ConcurrentProgressLog,
90    ) -> Self::OutputSymm;
91
92    #[doc(hidden)]
93    fn missing_nodes(missing_nodes: &Missing) -> usize;
94}
95
96/// Computes all eccentricities of a graph, its diameter, and its radius.
97///
98/// This variant is equivalent to [`AllForward`] in the symmetric case.
99pub struct All;
100
101impl Level for All {
102    type Output = output::All;
103    type OutputSymm = output_symm::All;
104
105    fn run(
106        graph: impl RandomAccessGraph + Sync,
107        transpose: impl RandomAccessGraph + Sync,
108        radial_vertices: Option<AtomicBitVec>,
109        pl: &mut impl ConcurrentProgressLog,
110    ) -> Self::Output {
111        let mut computer = DirExactSumSweepComputer::<_, _, _, _, Self>::new(
112            &graph,
113            &transpose,
114            radial_vertices,
115            pl,
116        );
117        computer.compute(pl);
118
119        assert!(computer.all_iter.is_some(),);
120        assert!(computer.forward_iter.is_some(),);
121        assert!(computer.diameter_iterations.is_some(),);
122        assert!(computer.radius_iterations.is_some(),);
123
124        let diameter = computer.diameter_low;
125        let radius = computer.radius_high;
126        let diametral_vertex = computer.diameter_vertex;
127        let radial_vertex = computer.radius_vertex;
128        let radius_iterations = computer.radius_iterations.unwrap();
129        let diameter_iterations = computer.diameter_iterations.unwrap();
130        let forward_iterations = computer.forward_iter.unwrap();
131        let all_iterations = computer.all_iter.unwrap();
132        let forward_eccentricities = computer.forward_low;
133        let backward_eccentricities = computer.backward_high;
134
135        Self::Output {
136            forward_eccentricities,
137            backward_eccentricities,
138            diameter,
139            radius,
140            diametral_vertex,
141            radial_vertex,
142            radius_iterations,
143            diameter_iterations,
144            forward_iterations,
145            all_iterations,
146        }
147    }
148
149    fn run_symm(
150        graph: impl RandomAccessGraph + Sync,
151        pl: &mut impl ConcurrentProgressLog,
152    ) -> Self::OutputSymm {
153        let mut computer = DirExactSumSweepComputer::<_, _, _, _, Self>::new_symm(&graph, pl);
154        computer.compute(pl);
155
156        assert!(computer.forward_iter.is_some(),);
157        assert!(computer.diameter_iterations.is_some(),);
158        assert!(computer.radius_iterations.is_some(),);
159
160        let diameter = computer.diameter_low;
161        let radius = computer.radius_high;
162        let diametral_vertex = computer.diameter_vertex;
163        let radial_vertex = computer.radius_vertex;
164        let radius_iterations = computer.radius_iterations.unwrap();
165        let diameter_iterations = computer.diameter_iterations.unwrap();
166        let iterations = computer.forward_iter.unwrap();
167        let eccentricities = computer.forward_low;
168
169        Self::OutputSymm {
170            eccentricities,
171            diameter,
172            radius,
173            diametral_vertex,
174            radial_vertex,
175            radius_iterations,
176            diameter_iterations,
177            iterations,
178        }
179    }
180
181    fn missing_nodes(missing: &Missing) -> usize {
182        missing.all_forward + missing.all_backward
183    }
184}
185
186/// Computes all forward eccentricities of a graph, its diameter, and its radius.
187pub struct AllForward;
188
189impl Level for AllForward {
190    type Output = output::AllForward;
191    type OutputSymm = output_symm::All;
192
193    fn run(
194        graph: impl RandomAccessGraph + Sync,
195        transpose: impl RandomAccessGraph + Sync,
196        radial_vertices: Option<AtomicBitVec>,
197        pl: &mut impl ConcurrentProgressLog,
198    ) -> Self::Output {
199        let mut computer = DirExactSumSweepComputer::<_, _, _, _, Self>::new(
200            &graph,
201            &transpose,
202            radial_vertices,
203            pl,
204        );
205        computer.compute(pl);
206
207        assert!(computer.forward_iter.is_some(),);
208        assert!(computer.diameter_iterations.is_some());
209        assert!(computer.radius_iterations.is_some(),);
210
211        let diameter = computer.diameter_low;
212        let radius = computer.radius_high;
213        let diametral_vertex = computer.diameter_vertex;
214        let radial_vertex = computer.radius_vertex;
215        let radius_iterations = computer.radius_iterations.unwrap();
216        let diameter_iterations = computer.diameter_iterations.unwrap();
217        let forward_iterations = computer.forward_iter.unwrap();
218        let forward_eccentricities = computer.forward_low;
219
220        Self::Output {
221            forward_eccentricities,
222            diameter,
223            radius,
224            diametral_vertex,
225            radial_vertex,
226            radius_iterations,
227            diameter_iterations,
228            forward_iterations,
229        }
230    }
231
232    #[inline(always)]
233    fn run_symm(
234        graph: impl RandomAccessGraph + Sync,
235        pl: &mut impl ConcurrentProgressLog,
236    ) -> Self::OutputSymm {
237        All::run_symm(graph, pl)
238    }
239
240    fn missing_nodes(missing: &Missing) -> usize {
241        missing.all_forward
242    }
243}
244
245/// Computes the diameter and the radius of a graph.
246pub struct RadiusDiameter;
247
248impl Level for RadiusDiameter {
249    type Output = output::RadiusDiameter;
250    type OutputSymm = output_symm::RadiusDiameter;
251
252    fn run(
253        graph: impl RandomAccessGraph + Sync,
254        transpose: impl RandomAccessGraph + Sync,
255        radial_vertices: Option<AtomicBitVec>,
256        pl: &mut impl ConcurrentProgressLog,
257    ) -> Self::Output {
258        let mut computer = DirExactSumSweepComputer::<_, _, _, _, Self>::new(
259            &graph,
260            &transpose,
261            radial_vertices,
262            pl,
263        );
264        computer.compute(pl);
265
266        assert!(computer.diameter_iterations.is_some(),);
267        assert!(computer.radius_iterations.is_some(),);
268
269        let diameter = computer.diameter_low;
270        let radius = computer.radius_high;
271        let diametral_vertex = computer.diameter_vertex;
272        let radial_vertex = computer.radius_vertex;
273        let radius_iterations = computer.radius_iterations.unwrap();
274        let diameter_iterations = computer.diameter_iterations.unwrap();
275
276        Self::Output {
277            diameter,
278            radius,
279            diametral_vertex,
280            radial_vertex,
281            radius_iterations,
282            diameter_iterations,
283        }
284    }
285
286    fn run_symm(
287        graph: impl RandomAccessGraph + Sync,
288        pl: &mut impl ConcurrentProgressLog,
289    ) -> Self::OutputSymm {
290        let mut computer = DirExactSumSweepComputer::<_, _, _, _, Self>::new_symm(&graph, pl);
291        computer.compute(pl);
292
293        assert!(computer.diameter_iterations.is_some(),);
294        assert!(computer.radius_iterations.is_some(),);
295
296        let diameter = computer.diameter_low;
297        let radius = computer.radius_high;
298        let diametral_vertex = computer.diameter_vertex;
299        let radial_vertex = computer.radius_vertex;
300        let radius_iterations = computer.radius_iterations.unwrap();
301        let diameter_iterations = computer.diameter_iterations.unwrap();
302
303        Self::OutputSymm {
304            diameter,
305            radius,
306            diametral_vertex,
307            radial_vertex,
308            radius_iterations,
309            diameter_iterations,
310        }
311    }
312
313    #[doc(hidden)]
314    fn missing_nodes(missing: &Missing) -> usize {
315        missing.radius + std::cmp::min(missing.diameter_forward, missing.diameter_backward)
316    }
317}
318
319/// Computes the diameter of a graph.
320pub struct Diameter;
321
322impl Level for Diameter {
323    type Output = output::Diameter;
324    type OutputSymm = output_symm::Diameter;
325
326    fn run(
327        graph: impl RandomAccessGraph + Sync,
328        transpose: impl RandomAccessGraph + Sync,
329        radial_vertices: Option<AtomicBitVec>,
330        pl: &mut impl ConcurrentProgressLog,
331    ) -> Self::Output {
332        let mut computer = DirExactSumSweepComputer::<_, _, _, _, Self>::new(
333            &graph,
334            &transpose,
335            radial_vertices,
336            pl,
337        );
338        computer.compute(pl);
339
340        assert!(computer.diameter_iterations.is_some(),);
341
342        let diameter = computer.diameter_low;
343        let diametral_vertex = computer.diameter_vertex;
344        let diameter_iterations = computer.diameter_iterations.unwrap();
345
346        Self::Output {
347            diameter,
348            diametral_vertex,
349            diameter_iterations,
350        }
351    }
352
353    fn run_symm(
354        graph: impl RandomAccessGraph + Sync,
355        pl: &mut impl ConcurrentProgressLog,
356    ) -> Self::OutputSymm {
357        let mut computer = DirExactSumSweepComputer::<_, _, _, _, Self>::new_symm(&graph, pl);
358        computer.compute(pl);
359
360        assert!(computer.diameter_iterations.is_some(),);
361
362        let diameter = computer.diameter_low;
363        let diametral_vertex = computer.diameter_vertex;
364        let diameter_iterations = computer.diameter_iterations.unwrap();
365
366        Self::OutputSymm {
367            diameter,
368            diametral_vertex,
369            diameter_iterations,
370        }
371    }
372
373    fn missing_nodes(missing: &Missing) -> usize {
374        std::cmp::min(missing.diameter_forward, missing.diameter_backward)
375    }
376}
377
378/// Computes the radius of a graph.
379pub struct Radius;
380
381impl Level for Radius {
382    type Output = output::Radius;
383    type OutputSymm = output_symm::Radius;
384
385    fn run(
386        graph: impl RandomAccessGraph + Sync,
387        transpose: impl RandomAccessGraph + Sync,
388        radial_vertices: Option<AtomicBitVec>,
389        pl: &mut impl ConcurrentProgressLog,
390    ) -> Self::Output {
391        let mut computer = DirExactSumSweepComputer::<_, _, _, _, Self>::new(
392            &graph,
393            &transpose,
394            radial_vertices,
395            pl,
396        );
397        computer.compute(pl);
398
399        assert!(computer.radius_iterations.is_some(),);
400
401        let radius = computer.radius_high;
402        let radial_vertex = computer.radius_vertex;
403        let radius_iterations = computer.radius_iterations.unwrap();
404
405        Self::Output {
406            radius,
407            radial_vertex,
408            radius_iterations,
409        }
410    }
411
412    fn run_symm(
413        graph: impl RandomAccessGraph + Sync,
414        pl: &mut impl ConcurrentProgressLog,
415    ) -> Self::OutputSymm {
416        let mut computer = DirExactSumSweepComputer::<_, _, _, _, Self>::new_symm(&graph, pl);
417        computer.compute(pl);
418
419        assert!(computer.radius_iterations.is_some(),);
420
421        let radius = computer.radius_high;
422        let radial_vertex = computer.radius_vertex;
423        let radius_iterations = computer.radius_iterations.unwrap();
424
425        Self::OutputSymm {
426            radius,
427            radial_vertex,
428            radius_iterations,
429        }
430    }
431
432    fn missing_nodes(missing: &Missing) -> usize {
433        missing.radius
434    }
435}
webgraph_algo/distances/exact_sum_sweep/level.rs

webgraph_algo/distances/exact_sum_sweep/
level.rs
