uni_algo/algo/algorithms/
triangle_count.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2024-2026 Dragonscale Team
3
4//! Triangle Count Algorithm.
5
6use crate::algo::GraphProjection;
7use crate::algo::algorithms::Algorithm;
8use rayon::prelude::*;
9use uni_common::core::id::Vid;
10
11pub struct TriangleCount;
12
13#[derive(Debug, Clone, Default)]
14pub struct TriangleCountConfig;
15
16pub struct TriangleCountResult {
17    pub global_count: u64,
18    pub node_counts: Vec<(Vid, u64)>,
19}
20
21impl Algorithm for TriangleCount {
22    type Config = TriangleCountConfig;
23    type Result = TriangleCountResult;
24
25    fn name() -> &'static str {
26        "triangleCount"
27    }
28
29    fn needs_reverse() -> bool {
30        // Triangle count typically treats graph as undirected to find {u, v, w} set.
31        // If directed, we look for cycles.
32        // Standard algo.triangleCount is undirected.
33        true
34    }
35
36    fn run(graph: &GraphProjection, _config: Self::Config) -> Self::Result {
37        let n = graph.vertex_count();
38        if n == 0 {
39            return TriangleCountResult {
40                global_count: 0,
41                node_counts: Vec::new(),
42            };
43        }
44
45        let mut node_counts = vec![0u64; n];
46
47        // Parallel iteration
48        // To avoid double counting, we iterate u, then v in N(u) where v > u.
49        // Then intersection of N(u) and N(v) gives w.
50        // If w > v, we found a unique triangle {u, v, w}.
51        // But we want per-node counts.
52        // Each triangle {u, v, w} contributes +1 to count(u), count(v), count(w).
53        // Since we iterate u < v < w, we can atomically add.
54        // Or we can just compute per-node: for u, iterate all pairs v, w in N(u) and check edge? O(d^2).
55        // Better: iterate u, neighbors v. intersection = N(u) & N(v).
56        // For each w in intersection, we have triangle.
57
58        // Let's use sorted adjacency lists for fast intersection.
59        // GraphProjection stores neighbors but not necessarily sorted.
60        // Sorting is needed.
61
62        // Pre-processing: Sort neighbor lists (or create sorted view).
63        // Since we can't modify GraphProjection easily in-place (it's immutable ref),
64        // we might just collect and sort, or use HashSet.
65        // HashSet is slower but easier.
66        // Given typically small degrees, simple scan might be okay?
67        // Let's create sorted adjacency for efficient intersection.
68
69        // Actually, we can just parallelize over `u` and accumulate local counts.
70        // `count(u)` is number of triangles u participates in.
71        // `count(u) = sum_{v in N(u)} |N(u) intersect N(v)| / 2`.
72
73        // This works for undirected.
74
75        let adj: Vec<Vec<u32>> = (0..n)
76            .into_par_iter()
77            .map(|i| {
78                let mut neighbors = Vec::new();
79                neighbors.extend_from_slice(graph.out_neighbors(i as u32));
80                if graph.has_reverse() {
81                    // Merge in_neighbors, dedup
82                    let in_n = graph.in_neighbors(i as u32);
83                    neighbors.extend_from_slice(in_n);
84                    neighbors.sort_unstable();
85                    neighbors.dedup();
86                } else {
87                    neighbors.sort_unstable();
88                }
89                neighbors
90            })
91            .collect();
92
93        // Now compute counts
94        // To update node_counts in parallel without atomics per node, we can just return counts?
95        // Actually, `count(u)` depends on `u`'s neighbors.
96        // We can compute `count(u)` independently.
97
98        node_counts
99            .par_iter_mut()
100            .enumerate()
101            .for_each(|(u, count)| {
102                let neighbors = &adj[u];
103                let mut local_triangles = 0;
104
105                // For each pair of neighbors, check if they are connected
106                // Using intersection is faster if degree is large: sum_{v in N(u)} |N(u) intersect N(v)|
107                // Then divide by 2 because each edge (v, w) is counted twice (once for v, once for w).
108
109                for &v in neighbors {
110                    let neighbors_v = &adj[v as usize];
111                    // Intersect sorted lists
112                    local_triangles += intersect_sorted_len(neighbors, neighbors_v);
113                }
114
115                *count = local_triangles as u64 / 2;
116            });
117
118        let total: u64 = node_counts.iter().sum::<u64>() / 3; // Each triangle counted 3 times (once per node)
119
120        let results = node_counts
121            .into_iter()
122            .enumerate()
123            .map(|(i, c)| (graph.to_vid(i as u32), c))
124            .collect();
125
126        TriangleCountResult {
127            global_count: total,
128            node_counts: results,
129        }
130    }
131}
132
133fn intersect_sorted_len(a: &[u32], b: &[u32]) -> usize {
134    let mut i = 0;
135    let mut j = 0;
136    let mut count = 0;
137
138    // Branchless intersection
139    // Compiler auto-vectorization friendly
140    while i < a.len() && j < b.len() {
141        let va = a[i];
142        let vb = b[j];
143
144        let le = va <= vb;
145        let ge = va >= vb;
146
147        count += (le && ge) as usize;
148        i += le as usize;
149        j += ge as usize;
150    }
151    count
152}
uni_algo/algo/algorithms/triangle_count.rs

uni_algo/algo/algorithms/
triangle_count.rs
