graphrust_algos/
triangle_count.rs

1//! Triangle counting algorithm implementation.
2//!
3//! Counts triangles and computes clustering coefficients in graphs.
4
5use graphrust_core::{Graph, NodeId};
6use std::collections::HashMap;
7
8/// Counts the total number of triangles in the graph.
9///
10/// A triangle is a set of three nodes {a, b, c} where all three edges exist:
11/// a-b, b-c, a-c.
12///
13/// # Arguments
14/// * `graph` - The graph (usually undirected for meaningful triangle counting)
15///
16/// # Returns
17/// Total count of triangles
18pub fn triangle_count(graph: &Graph) -> u64 {
19    let mut count = 0u64;
20
21    for node_a in graph.nodes() {
22        let neighbors_a = graph.neighbors(node_a);
23
24        for (_i, &node_b) in neighbors_a.iter().enumerate() {
25            if node_b <= node_a {
26                continue; // Avoid counting same triangle multiple times
27            }
28
29            let neighbors_b = graph.neighbors(node_b);
30
31            for &node_c in neighbors_b.iter() {
32                if node_c <= node_b {
33                    continue; // Avoid counting same triangle multiple times
34                }
35
36                // Check if edge exists between node_a and node_c
37                if graph.neighbors(node_a).contains(&node_c) {
38                    count += 1;
39                }
40            }
41        }
42    }
43
44    count
45}
46
47/// Counts triangles each node participates in.
48///
49/// # Arguments
50/// * `graph` - The graph
51///
52/// # Returns
53/// HashMap mapping each node to the number of triangles it's part of
54pub fn triangles_per_node(graph: &Graph) -> HashMap<NodeId, u32> {
55    let mut counts: HashMap<NodeId, u32> = HashMap::new();
56
57    for node in graph.nodes() {
58        counts.insert(node, 0);
59    }
60
61    for node_a in graph.nodes() {
62        let neighbors_a = graph.neighbors(node_a);
63
64        for (_i, &node_b) in neighbors_a.iter().enumerate() {
65            if node_b <= node_a {
66                continue;
67            }
68
69            let neighbors_b = graph.neighbors(node_b);
70
71            for &node_c in neighbors_b.iter() {
72                if node_c <= node_b {
73                    continue;
74                }
75
76                // Check if edge exists between node_a and node_c
77                if graph.neighbors(node_a).contains(&node_c) {
78                    *counts.entry(node_a).or_insert(0) += 1;
79                    *counts.entry(node_b).or_insert(0) += 1;
80                    *counts.entry(node_c).or_insert(0) += 1;
81                }
82            }
83        }
84    }
85
86    counts
87}
88
89/// Computes the global clustering coefficient of the graph.
90///
91/// Clustering coefficient = (3 * number_of_triangles) / number_of_connected_triplets
92///
93/// # Arguments
94/// * `graph` - The graph
95///
96/// # Returns
97/// Global clustering coefficient (0.0 to 1.0)
98pub fn clustering_coefficient(graph: &Graph) -> f64 {
99    let triangles = triangle_count(graph);
100
101    // Count connected triplets (paths of length 2)
102    let mut triplets = 0u64;
103
104    for node in graph.nodes() {
105        let degree = graph.neighbors(node).len() as u64;
106        // Number of pairs of neighbors is C(degree, 2) = degree * (degree - 1) / 2
107        triplets += degree * (degree - 1) / 2;
108    }
109
110    if triplets == 0 {
111        return 0.0;
112    }
113
114    (3.0 * triangles as f64) / triplets as f64
115}
116
117#[cfg(test)]
118mod tests {
119    use super::*;
120    use graphrust_core::GraphBuilder;
121
122    fn create_triangle_graph() -> Graph {
123        // Create a triangle: 0-1-2-0
124        GraphBuilder::new(3)
125            .add_edge(NodeId(0), NodeId(1))
126            .add_edge(NodeId(1), NodeId(2))
127            .add_edge(NodeId(2), NodeId(0))
128            .build()
129    }
130
131    fn create_multi_triangle_graph() -> Graph {
132        // Create two triangles sharing an edge: 0-1-2-0 and 1-2-3-1
133        GraphBuilder::new(4)
134            .add_edge(NodeId(0), NodeId(1))
135            .add_edge(NodeId(1), NodeId(2))
136            .add_edge(NodeId(2), NodeId(0))
137            .add_edge(NodeId(1), NodeId(3))
138            .add_edge(NodeId(3), NodeId(2))
139            .build()
140    }
141
142    #[test]
143    fn test_single_triangle() {
144        let graph = create_triangle_graph();
145        assert_eq!(triangle_count(&graph), 1);
146    }
147
148    #[test]
149    fn test_triangles_per_node_single() {
150        let graph = create_triangle_graph();
151        let counts = triangles_per_node(&graph);
152
153        assert_eq!(counts.get(&NodeId(0)), Some(&1));
154        assert_eq!(counts.get(&NodeId(1)), Some(&1));
155        assert_eq!(counts.get(&NodeId(2)), Some(&1));
156    }
157
158    #[test]
159    fn test_clustering_coefficient() {
160        let graph = create_triangle_graph();
161        let cc = clustering_coefficient(&graph);
162
163        // For a perfect triangle, clustering coefficient should be 1.0
164        assert!((cc - 1.0).abs() < 0.01);
165    }
166
167    #[test]
168    fn test_no_triangles() {
169        let graph = GraphBuilder::new(3)
170            .add_edge(NodeId(0), NodeId(1))
171            .add_edge(NodeId(1), NodeId(2))
172            .build();
173
174        assert_eq!(triangle_count(&graph), 0);
175        assert_eq!(clustering_coefficient(&graph), 0.0);
176    }
177}
graphrust_algos/triangle_count.rs

graphrust_algos/
triangle_count.rs
