uni-algo 2.1.0

Graph algorithms for Uni - PageRank, Louvain, shortest paths, and more
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

// SPDX-License-Identifier: Apache-2.0
// Copyright 2024-2026 Dragonscale Team

//! All Pairs Shortest Path Algorithm.

use crate::algo::GraphProjection;
use crate::algo::algorithms::{Algorithm, bfs_levels};
use rayon::prelude::*;
use uni_common::core::id::Vid;

pub struct AllPairsShortestPath;

#[derive(Debug, Clone, Default)]
pub struct AllPairsShortestPathConfig;

pub struct AllPairsShortestPathResult {
    pub distances: Vec<(Vid, Vid, u32)>, // (source, target, distance)
}

impl Algorithm for AllPairsShortestPath {
    type Config = AllPairsShortestPathConfig;
    type Result = AllPairsShortestPathResult;

    fn name() -> &'static str {
        "allPairsShortestPath"
    }

    fn run(graph: &GraphProjection, _config: Self::Config) -> Self::Result {
        let n = graph.vertex_count();
        if n == 0 {
            return AllPairsShortestPathResult {
                distances: Vec::new(),
            };
        }

        // O(V(V+E)): one BFS per source, collected in parallel.
        let distances = (0..n as u32)
            .into_par_iter()
            .flat_map_iter(|s| {
                let d = bfs_levels(graph, s);
                let src_vid = graph.to_vid(s);
                d.into_iter()
                    .enumerate()
                    .filter(|&(_, dist)| dist > 0)
                    .map(move |(tgt, dist)| (src_vid, graph.to_vid(tgt as u32), dist as u32))
            })
            .collect();

        AllPairsShortestPathResult { distances }
    }
}