uni_algo/algo/algorithms/
apsp.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2024-2026 Dragonscale Team
3
4//! All Pairs Shortest Path Algorithm.
5
6use crate::algo::GraphProjection;
7use crate::algo::algorithms::Algorithm;
8use rayon::prelude::*;
9use std::collections::VecDeque;
10use std::sync::Mutex;
11use uni_common::core::id::Vid;
12
13pub struct AllPairsShortestPath;
14
15#[derive(Debug, Clone, Default)]
16pub struct AllPairsShortestPathConfig;
17
18pub struct AllPairsShortestPathResult {
19    pub distances: Vec<(Vid, Vid, u32)>, // (source, target, distance)
20}
21
22impl Algorithm for AllPairsShortestPath {
23    type Config = AllPairsShortestPathConfig;
24    type Result = AllPairsShortestPathResult;
25
26    fn name() -> &'static str {
27        "allPairsShortestPath"
28    }
29
30    fn run(graph: &GraphProjection, _config: Self::Config) -> Self::Result {
31        let n = graph.vertex_count();
32        if n == 0 {
33            return AllPairsShortestPathResult {
34                distances: Vec::new(),
35            };
36        }
37
38        // Limit n? O(V(V+E)).
39
40        let mut results = Vec::new();
41        let results_mutex = Mutex::new(&mut results);
42
43        (0..n as u32).into_par_iter().for_each(|s| {
44            let mut q = VecDeque::with_capacity(n);
45            let mut d = vec![-1; n];
46
47            d[s as usize] = 0;
48            q.push_back(s);
49
50            let mut local_results = Vec::new();
51
52            while let Some(u) = q.pop_front() {
53                let dist_u = d[u as usize];
54
55                if u != s {
56                    local_results.push((s, u, dist_u as u32));
57                }
58
59                for &v in graph.out_neighbors(u) {
60                    if d[v as usize] == -1 {
61                        d[v as usize] = dist_u + 1;
62                        q.push_back(v);
63                    }
64                }
65            }
66
67            if !local_results.is_empty() {
68                let mut guard = results_mutex.lock().unwrap_or_else(|e| e.into_inner());
69                let src_vid = graph.to_vid(s);
70                for (_src_idx, tgt_idx, dist) in local_results {
71                    // src_idx is s
72                    guard.push((src_vid, graph.to_vid(tgt_idx), dist));
73                }
74            }
75        });
76
77        AllPairsShortestPathResult { distances: results }
78    }
79}
uni_algo/algo/algorithms/apsp.rs

uni_algo/algo/algorithms/
apsp.rs
