uni_algo/algo/algorithms/
degree_centrality.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2024-2026 Dragonscale Team
3
4//! Degree Centrality Algorithm.
5//!
6//! Measures the centrality of a node based on its degree (number of connections).
7//! Can compute in-degree, out-degree, or total degree.
8
9use crate::algo::GraphProjection;
10use crate::algo::algorithms::Algorithm;
11use uni_common::core::id::Vid;
12
13pub struct DegreeCentrality;
14
15#[derive(Debug, Clone)]
16pub struct DegreeCentralityConfig {
17    pub direction: DegreeDirection,
18}
19
20#[derive(Debug, Clone, Copy, PartialEq, Eq)]
21pub enum DegreeDirection {
22    Incoming,
23    Outgoing,
24    Both,
25}
26
27impl Default for DegreeCentralityConfig {
28    fn default() -> Self {
29        Self {
30            direction: DegreeDirection::Outgoing,
31        }
32    }
33}
34
35pub struct DegreeCentralityResult {
36    pub scores: Vec<(Vid, f64)>,
37}
38
39impl Algorithm for DegreeCentrality {
40    type Config = DegreeCentralityConfig;
41    type Result = DegreeCentralityResult;
42
43    fn name() -> &'static str {
44        "degree_centrality"
45    }
46
47    fn run(graph: &GraphProjection, config: Self::Config) -> Self::Result {
48        let n = graph.vertex_count();
49        if n == 0 {
50            return DegreeCentralityResult { scores: Vec::new() };
51        }
52
53        let mut scores = Vec::with_capacity(n);
54
55        for i in 0..n as u32 {
56            let degree = match config.direction {
57                DegreeDirection::Outgoing => graph.out_degree(i),
58                DegreeDirection::Incoming => {
59                    if graph.has_reverse() {
60                        graph.in_degree(i)
61                    } else {
62                        // Fallback or error?
63                        // If no reverse edges, in-degree is 0? Or unknown?
64                        // Usually GraphProjection should have reverse if needed.
65                        0
66                    }
67                }
68                DegreeDirection::Both => {
69                    let out_d = graph.out_degree(i);
70                    let in_d = if graph.has_reverse() {
71                        graph.in_degree(i)
72                    } else {
73                        0
74                    };
75                    out_d + in_d
76                }
77            };
78            scores.push((graph.to_vid(i), degree as f64));
79        }
80
81        DegreeCentralityResult { scores }
82    }
83}
84
85#[cfg(test)]
86mod tests {
87    use super::*;
88    use crate::algo::test_utils::build_test_graph;
89
90    #[test]
91    fn test_degree_centrality_outgoing() {
92        // 0 -> 1, 0 -> 2
93        let vids = vec![Vid::from(0), Vid::from(1), Vid::from(2)];
94        let edges = vec![(Vid::from(0), Vid::from(1)), (Vid::from(0), Vid::from(2))];
95        let graph = build_test_graph(vids, edges);
96
97        let config = DegreeCentralityConfig {
98            direction: DegreeDirection::Outgoing,
99        };
100        let result = DegreeCentrality::run(&graph, config);
101
102        let map: std::collections::HashMap<_, _> = result.scores.into_iter().collect();
103        assert_eq!(map[&Vid::from(0)], 2.0);
104        assert_eq!(map[&Vid::from(1)], 0.0);
105        assert_eq!(map[&Vid::from(2)], 0.0);
106    }
107}
uni_algo/algo/algorithms/degree_centrality.rs

uni_algo/algo/algorithms/
degree_centrality.rs
