uni-algo 0.1.5

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

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

//! Dijkstra's Shortest Path Algorithm.

use crate::algo::GraphProjection;
use crate::algo::algorithms::Algorithm;
use std::cmp::Reverse;
use std::collections::BinaryHeap;
use uni_common::core::id::Vid;

pub struct Dijkstra;

#[derive(Debug, Clone)]
pub struct DijkstraConfig {
    pub source: Vid,
    pub target: Option<Vid>,
    pub max_distance: Option<f64>,
}

impl Default for DijkstraConfig {
    fn default() -> Self {
        Self {
            source: Vid::from(0),
            target: None,
            max_distance: None,
        }
    }
}

pub struct DijkstraResult {
    pub distances: Vec<(Vid, f64)>,
    pub path: Option<Vec<Vid>>,
}

impl Algorithm for Dijkstra {
    type Config = DijkstraConfig;
    type Result = DijkstraResult;

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

    fn run(graph: &GraphProjection, config: Self::Config) -> Self::Result {
        let source_slot = match graph.to_slot(config.source) {
            Some(slot) => slot,
            None => {
                return DijkstraResult {
                    distances: Vec::new(),
                    path: None,
                };
            }
        };

        let n = graph.vertex_count();
        let mut dist = vec![f64::INFINITY; n];
        let mut prev: Vec<Option<u32>> = vec![None; n];
        let mut heap = BinaryHeap::new();

        dist[source_slot as usize] = 0.0;
        heap.push(Reverse((0.0f64.to_bits(), source_slot)));

        let target_slot = config.target.and_then(|t| graph.to_slot(t));

        while let Some(Reverse((d_bits, u))) = heap.pop() {
            let d = f64::from_bits(d_bits);
            if d > dist[u as usize] {
                continue;
            }

            // Early exit for point-to-point
            if target_slot == Some(u) {
                break;
            }

            // Max distance cutoff
            if let Some(max_d) = config.max_distance
                && d > max_d
            {
                continue;
            }

            for (i, &v) in graph.out_neighbors(u).iter().enumerate() {
                let weight = if graph.has_weights() {
                    graph.out_weight(u, i)
                } else {
                    1.0
                };
                let new_dist = d + weight;

                if new_dist < dist[v as usize] {
                    dist[v as usize] = new_dist;
                    prev[v as usize] = Some(u);
                    heap.push(Reverse((new_dist.to_bits(), v)));
                }
            }
        }

        // Reconstruct path if target specified
        let mut path = None;
        if let Some(t_slot) = target_slot
            && dist[t_slot as usize] < f64::INFINITY
        {
            let mut p = Vec::new();
            let mut curr = Some(t_slot);
            while let Some(slot) = curr {
                p.push(graph.to_vid(slot));
                if slot == source_slot {
                    break;
                }
                curr = prev[slot as usize];
            }
            p.reverse();
            path = Some(p);
        }

        let results = dist
            .into_iter()
            .enumerate()
            .filter(|(_, d)| *d < f64::INFINITY)
            .map(|(slot, d)| (graph.to_vid(slot as u32), d))
            .collect();

        DijkstraResult {
            distances: results,
            path,
        }
    }
}