uni_algo/algo/algorithms/
scc.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2024-2026 Dragonscale Team
3
4//! Strongly Connected Components (SCC) Algorithm using Tarjan's algorithm.
5
6use crate::algo::GraphProjection;
7use crate::algo::algorithms::Algorithm;
8use uni_common::core::id::Vid;
9
10pub struct Scc;
11
12#[derive(Debug, Clone, Default)]
13pub struct SccConfig {}
14
15pub struct SccResult {
16    pub components: Vec<(Vid, u64)>, // (node, component_id)
17    pub component_count: usize,
18}
19
20struct TarjanContext<'a> {
21    graph: &'a GraphProjection,
22    index: usize,
23    stack: Vec<u32>,
24    on_stack: Vec<bool>,
25    indices: Vec<Option<usize>>,
26    lowlink: Vec<usize>,
27    components: Vec<u32>,
28    component_count: usize,
29}
30
31impl Algorithm for Scc {
32    type Config = SccConfig;
33    type Result = SccResult;
34
35    fn name() -> &'static str {
36        "scc"
37    }
38
39    fn run(graph: &GraphProjection, _config: Self::Config) -> Self::Result {
40        let n = graph.vertex_count();
41        if n == 0 {
42            return SccResult {
43                components: Vec::new(),
44                component_count: 0,
45            };
46        }
47
48        let mut ctx = TarjanContext {
49            graph,
50            index: 0,
51            stack: Vec::new(),
52            on_stack: vec![false; n],
53            indices: vec![None; n],
54            lowlink: vec![0; n],
55            components: vec![0; n],
56            component_count: 0,
57        };
58
59        for v in 0..n as u32 {
60            if ctx.indices[v as usize].is_none() {
61                strongconnect(v, &mut ctx);
62            }
63        }
64
65        let results = ctx
66            .components
67            .into_iter()
68            .enumerate()
69            .map(|(i, c)| (graph.to_vid(i as u32), c as u64))
70            .collect();
71
72        SccResult {
73            components: results,
74            component_count: ctx.component_count,
75        }
76    }
77}
78
79fn strongconnect(v: u32, ctx: &mut TarjanContext) {
80    ctx.indices[v as usize] = Some(ctx.index);
81    ctx.lowlink[v as usize] = ctx.index;
82    ctx.index += 1;
83    ctx.stack.push(v);
84    ctx.on_stack[v as usize] = true;
85
86    for &w in ctx.graph.out_neighbors(v) {
87        if ctx.indices[w as usize].is_none() {
88            strongconnect(w, ctx);
89            ctx.lowlink[v as usize] =
90                std::cmp::min(ctx.lowlink[v as usize], ctx.lowlink[w as usize]);
91        } else if ctx.on_stack[w as usize] {
92            ctx.lowlink[v as usize] =
93                std::cmp::min(ctx.lowlink[v as usize], ctx.indices[w as usize].unwrap());
94        }
95    }
96
97    if ctx.lowlink[v as usize] == ctx.indices[v as usize].unwrap() {
98        loop {
99            let w = ctx.stack.pop().unwrap();
100            ctx.on_stack[w as usize] = false;
101            ctx.components[w as usize] = ctx.component_count as u32;
102            if w == v {
103                break;
104            }
105        }
106        ctx.component_count += 1;
107    }
108}
uni_algo/algo/algorithms/scc.rs

uni_algo/algo/algorithms/
scc.rs
