rust_igraph/algorithms/properties/
list_triangles.rs

1//! Triangle listing (ALGO-PR-040).
2//!
3//! Counterpart of `igraph_list_triangles()` from
4//! `references/igraph/src/properties/triangles.c`.
5//!
6//! Enumerates all triangles in a graph, reporting each exactly once as
7//! a triplet of vertex IDs.
8
9use crate::core::{Graph, IgraphResult};
10
11/// List all triangles in a graph.
12///
13/// Returns a vector of `(u, v, w)` triples where each triple represents
14/// a triangle. Each triangle is listed exactly once. Edge directions
15/// and multi-edges are ignored.
16///
17/// Uses degree-ordering to ensure each triangle is counted once: for
18/// each edge `(u, v)` where `rank(u) > rank(v)`, checks neighbors of
19/// `v` that are also neighbors of `u`.
20///
21/// # Examples
22///
23/// ```
24/// use rust_igraph::{Graph, list_triangles};
25///
26/// let mut g = Graph::with_vertices(4);
27/// g.add_edge(0, 1).unwrap();
28/// g.add_edge(1, 2).unwrap();
29/// g.add_edge(2, 0).unwrap();
30/// g.add_edge(2, 3).unwrap();
31/// g.add_edge(3, 0).unwrap();
32///
33/// let tris = list_triangles(&g).unwrap();
34/// assert_eq!(tris.len(), 2); // triangles: (0,1,2) and (0,2,3)
35/// ```
36pub fn list_triangles(graph: &Graph) -> IgraphResult<Vec<(u32, u32, u32)>> {
37    let n = graph.vcount() as usize;
38
39    if n < 3 {
40        return Ok(Vec::new());
41    }
42
43    // Build simple undirected adjacency list.
44    let adj = build_simple_adj(graph)?;
45
46    // Compute degree and rank (higher degree = higher rank).
47    let mut degree_order: Vec<usize> = (0..n).collect();
48    degree_order.sort_by(|&a, &b| adj[a].len().cmp(&adj[b].len()));
49
50    let mut rank: Vec<usize> = vec![0; n];
51    for (i, &node) in degree_order.iter().enumerate() {
52        rank[node] = i;
53    }
54
55    // Filter adjacency list: keep only neighbors with higher rank.
56    let filtered: Vec<Vec<usize>> = (0..n)
57        .map(|v| {
58            adj[v]
59                .iter()
60                .copied()
61                .filter(|&w| rank[w] > rank[v])
62                .collect()
63        })
64        .collect();
65
66    // Mark array for neighbor lookup.
67    let mut mark: Vec<usize> = vec![usize::MAX; n];
68    let mut triangles: Vec<(u32, u32, u32)> = Vec::new();
69
70    for node_idx in (0..n).rev() {
71        let node = degree_order[node_idx];
72
73        // Mark neighbors of node.
74        for &nei in &filtered[node] {
75            mark[nei] = node;
76        }
77
78        // For each neighbor, check its filtered neighbors.
79        for &nei in &filtered[node] {
80            for &nei2 in &filtered[nei] {
81                if mark[nei2] == node {
82                    #[allow(clippy::cast_possible_truncation)]
83                    triangles.push((node as u32, nei as u32, nei2 as u32));
84                }
85            }
86        }
87    }
88
89    Ok(triangles)
90}
91
92/// Build simple undirected adjacency list (sorted, no loops, no multi-edges).
93fn build_simple_adj(graph: &Graph) -> IgraphResult<Vec<Vec<usize>>> {
94    let n = graph.vcount() as usize;
95    let m = graph.ecount();
96    let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
97
98    for eid_usize in 0..m {
99        #[allow(clippy::cast_possible_truncation)]
100        let eid = eid_usize as u32;
101        let (from, to) = graph.edge(eid)?;
102        let f = from as usize;
103        let t = to as usize;
104        if f != t {
105            adj[f].push(t);
106            adj[t].push(f);
107        }
108    }
109
110    for neighbors in &mut adj {
111        neighbors.sort_unstable();
112        neighbors.dedup();
113    }
114
115    Ok(adj)
116}
117
118#[cfg(test)]
119mod tests {
120    use super::*;
121    use std::collections::HashSet;
122
123    fn normalize_triangle(t: (u32, u32, u32)) -> Vec<u32> {
124        let mut v = vec![t.0, t.1, t.2];
125        v.sort_unstable();
126        v
127    }
128
129    fn triangle_set(tris: &[(u32, u32, u32)]) -> HashSet<Vec<u32>> {
130        tris.iter().map(|&t| normalize_triangle(t)).collect()
131    }
132
133    #[test]
134    fn empty_graph() {
135        let g = Graph::with_vertices(0);
136        let tris = list_triangles(&g).unwrap();
137        assert!(tris.is_empty());
138    }
139
140    #[test]
141    fn no_triangles() {
142        let mut g = Graph::with_vertices(4);
143        g.add_edge(0, 1).unwrap();
144        g.add_edge(1, 2).unwrap();
145        g.add_edge(2, 3).unwrap();
146        g.add_edge(3, 0).unwrap();
147        // C4 has no triangles
148        let tris = list_triangles(&g).unwrap();
149        assert!(tris.is_empty());
150    }
151
152    #[test]
153    fn single_triangle() {
154        let mut g = Graph::with_vertices(3);
155        g.add_edge(0, 1).unwrap();
156        g.add_edge(1, 2).unwrap();
157        g.add_edge(2, 0).unwrap();
158
159        let tris = list_triangles(&g).unwrap();
160        assert_eq!(tris.len(), 1);
161        let t = normalize_triangle(tris[0]);
162        assert_eq!(t, vec![0, 1, 2]);
163    }
164
165    #[test]
166    fn complete_4() {
167        let mut g = Graph::with_vertices(4);
168        for i in 0..4u32 {
169            for j in (i + 1)..4 {
170                g.add_edge(i, j).unwrap();
171            }
172        }
173        // K4 has C(4,3) = 4 triangles
174        let tris = list_triangles(&g).unwrap();
175        assert_eq!(tris.len(), 4);
176        let set = triangle_set(&tris);
177        assert!(set.contains(&vec![0, 1, 2]));
178        assert!(set.contains(&vec![0, 1, 3]));
179        assert!(set.contains(&vec![0, 2, 3]));
180        assert!(set.contains(&vec![1, 2, 3]));
181    }
182
183    #[test]
184    fn two_triangles_sharing_edge() {
185        let mut g = Graph::with_vertices(4);
186        g.add_edge(0, 1).unwrap();
187        g.add_edge(1, 2).unwrap();
188        g.add_edge(2, 0).unwrap();
189        g.add_edge(2, 3).unwrap();
190        g.add_edge(3, 0).unwrap();
191
192        let tris = list_triangles(&g).unwrap();
193        assert_eq!(tris.len(), 2);
194        let set = triangle_set(&tris);
195        assert!(set.contains(&vec![0, 1, 2]));
196        assert!(set.contains(&vec![0, 2, 3]));
197    }
198
199    #[test]
200    fn disconnected_triangles() {
201        let mut g = Graph::with_vertices(6);
202        g.add_edge(0, 1).unwrap();
203        g.add_edge(1, 2).unwrap();
204        g.add_edge(2, 0).unwrap();
205        g.add_edge(3, 4).unwrap();
206        g.add_edge(4, 5).unwrap();
207        g.add_edge(5, 3).unwrap();
208
209        let tris = list_triangles(&g).unwrap();
210        assert_eq!(tris.len(), 2);
211        let set = triangle_set(&tris);
212        assert!(set.contains(&vec![0, 1, 2]));
213        assert!(set.contains(&vec![3, 4, 5]));
214    }
215
216    #[test]
217    fn directed_ignores_direction() {
218        let mut g = Graph::new(3, true).unwrap();
219        g.add_edge(0, 1).unwrap();
220        g.add_edge(1, 2).unwrap();
221        g.add_edge(2, 0).unwrap();
222
223        let tris = list_triangles(&g).unwrap();
224        assert_eq!(tris.len(), 1);
225    }
226
227    #[test]
228    fn self_loops_ignored() {
229        let mut g = Graph::with_vertices(3);
230        g.add_edge(0, 0).unwrap();
231        g.add_edge(0, 1).unwrap();
232        g.add_edge(1, 2).unwrap();
233        // No triangle
234        let tris = list_triangles(&g).unwrap();
235        assert!(tris.is_empty());
236    }
237
238    #[test]
239    fn multi_edges_ignored() {
240        let mut g = Graph::with_vertices(3);
241        g.add_edge(0, 1).unwrap();
242        g.add_edge(0, 1).unwrap();
243        g.add_edge(1, 2).unwrap();
244        g.add_edge(2, 0).unwrap();
245
246        let tris = list_triangles(&g).unwrap();
247        assert_eq!(tris.len(), 1);
248    }
249
250    #[test]
251    fn uniqueness() {
252        // Each triangle appears exactly once
253        let mut g = Graph::with_vertices(5);
254        for i in 0..5u32 {
255            for j in (i + 1)..5 {
256                g.add_edge(i, j).unwrap();
257            }
258        }
259        // K5 has C(5,3) = 10 triangles
260        let tris = list_triangles(&g).unwrap();
261        assert_eq!(tris.len(), 10);
262        let set = triangle_set(&tris);
263        assert_eq!(set.len(), 10);
264    }
265
266    #[test]
267    fn star_no_triangles() {
268        let mut g = Graph::with_vertices(5);
269        g.add_edge(0, 1).unwrap();
270        g.add_edge(0, 2).unwrap();
271        g.add_edge(0, 3).unwrap();
272        g.add_edge(0, 4).unwrap();
273
274        let tris = list_triangles(&g).unwrap();
275        assert!(tris.is_empty());
276    }
277
278    #[test]
279    fn two_vertices() {
280        let mut g = Graph::with_vertices(2);
281        g.add_edge(0, 1).unwrap();
282        let tris = list_triangles(&g).unwrap();
283        assert!(tris.is_empty());
284    }
285}
rust_igraph/algorithms/properties/list_triangles.rs

rust_igraph/algorithms/properties/
list_triangles.rs
