graphmind_graph_algorithms/
topology.rs

1//! Graph topology analysis algorithms
2//!
3//! Implements REQ-ALGO-005 (Triangle Counting)
4
5use super::common::GraphView;
6use std::collections::HashSet;
7
8/// Triangle Counting
9///
10/// Returns total number of triangles in the graph.
11/// For undirected graphs, each triangle is counted once.
12/// For directed, we treat as undirected for counting.
13pub fn count_triangles(view: &GraphView) -> usize {
14    let mut triangle_count = 0;
15
16    // Using simple algorithm: for each edge (u, v), find common neighbors of u and v.
17    // To avoid overcounting, we only consider nodes with indices i < j < k.
18
19    for u in 0..view.node_count {
20        let u_neighbors: HashSet<_> = view
21            .successors(u)
22            .iter()
23            .chain(view.predecessors(u).iter())
24            .cloned()
25            .collect();
26
27        for &v in &u_neighbors {
28            if v <= u {
29                continue;
30            } // Order u < v
31
32            let v_neighbors: HashSet<_> = view
33                .successors(v)
34                .iter()
35                .chain(view.predecessors(v).iter())
36                .cloned()
37                .collect();
38
39            for &w in &v_neighbors {
40                if w <= v {
41                    continue;
42                } // Order v < w
43
44                // Check if w is also neighbor of u
45                if u_neighbors.contains(&w) {
46                    triangle_count += 1;
47                }
48            }
49        }
50    }
51
52    triangle_count
53}
54
55#[cfg(test)]
56mod tests {
57    use super::*;
58    use std::collections::HashMap;
59
60    #[test]
61    fn test_triangle_counting() {
62        // Complete graph K4: 4 nodes, all connected.
63        // Triangles: (0,1,2), (0,1,3), (0,2,3), (1,2,3) -> 4 triangles.
64
65        let node_count = 4;
66        let mut outgoing = vec![vec![]; 4];
67        let mut incoming = vec![vec![]; 4];
68
69        for i in 0..4 {
70            for j in (i + 1)..4 {
71                outgoing[i].push(j);
72                incoming[j].push(i);
73            }
74        }
75
76        let view = GraphView::from_adjacency_list(
77            node_count,
78            vec![0, 1, 2, 3],
79            HashMap::new(),
80            outgoing,
81            incoming,
82            None,
83        );
84
85        let count = count_triangles(&view);
86        assert_eq!(count, 4);
87    }
88}
graphmind_graph_algorithms/topology.rs

graphmind_graph_algorithms/
topology.rs
