rust_igraph/algorithms/connectivity/
transitive_closure.rs

1//! Transitive closure (ALGO-CC-022).
2//!
3//! Counterpart of `igraph_transitive_closure()` from
4//! `references/igraph/src/connectivity/reachability.c:225-257`. Returns a
5//! new graph with an edge `u -> v` (or `u - v` for undirected) for every
6//! ordered (resp. unordered) reachable pair with `u != v`.
7//!
8//! Built on top of the
9//! [`super::reachability_matrix::reachability_matrix`] primitive.
10//! Phase-1 cost: `O(|V|² + |V|*|V|*log|E|)` from BFS-from-each-vertex
11//! plus the closure construction. Upstream's SCC-condensation
12//! optimisation could shave this in a future perf pass.
13
14use crate::core::{Graph, IgraphResult};
15
16/// Transitive closure of `graph`. The returned graph shares the same
17/// vertex count and direction as the input.
18///
19/// For directed graphs every reachable ordered pair `(u, v)` (`u != v`)
20/// becomes an edge. For undirected graphs each unordered reachable pair
21/// `{u, v}` is added once.
22///
23/// Counterpart of `igraph_transitive_closure(_, _)` from
24/// `references/igraph/src/connectivity/reachability.c:225`.
25///
26/// # Examples
27///
28/// ```
29/// use rust_igraph::{Graph, transitive_closure};
30///
31/// // Directed path 0 -> 1 -> 2: closure adds 0 -> 2.
32/// let mut g = Graph::new(3, true).unwrap();
33/// g.add_edge(0, 1).unwrap();
34/// g.add_edge(1, 2).unwrap();
35/// let tc = transitive_closure(&g).unwrap();
36/// assert_eq!(tc.vcount(), 3);
37/// assert_eq!(tc.ecount(), 3); // 0->1, 0->2, 1->2
38/// assert!(tc.find_eid(0, 2).unwrap().is_some());
39/// ```
40pub fn transitive_closure(graph: &Graph) -> IgraphResult<Graph> {
41    let n = graph.vcount();
42    let directed = graph.is_directed();
43    let m = super::reachability_matrix::reachability_matrix(graph)?;
44    let mut closure = Graph::new(n, directed)?;
45    for (u, row) in m.iter().enumerate() {
46        let start_j = if directed { 0 } else { u + 1 };
47        let u_id = u32::try_from(u).map_err(|_| {
48            crate::core::IgraphError::Internal("vcount overflows u32 in transitive_closure")
49        })?;
50        for (v, &reachable) in row.iter().enumerate().skip(start_j) {
51            if u != v && reachable {
52                let v_id = u32::try_from(v).map_err(|_| {
53                    crate::core::IgraphError::Internal("vcount overflows u32 in transitive_closure")
54                })?;
55                closure.add_edge(u_id, v_id)?;
56            }
57        }
58    }
59    Ok(closure)
60}
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65
66    #[test]
67    fn empty_graph_yields_empty_closure() {
68        let g = Graph::with_vertices(0);
69        let tc = transitive_closure(&g).unwrap();
70        assert_eq!(tc.vcount(), 0);
71        assert_eq!(tc.ecount(), 0);
72    }
73
74    #[test]
75    fn isolated_vertices_no_edges_in_closure() {
76        let g = Graph::with_vertices(5);
77        let tc = transitive_closure(&g).unwrap();
78        assert_eq!(tc.vcount(), 5);
79        assert_eq!(tc.ecount(), 0);
80    }
81
82    #[test]
83    fn directed_path_3_closure_has_three_edges() {
84        // 0 -> 1 -> 2: closure adds 0->1, 0->2, 1->2.
85        let mut g = Graph::new(3, true).unwrap();
86        g.add_edge(0, 1).unwrap();
87        g.add_edge(1, 2).unwrap();
88        let tc = transitive_closure(&g).unwrap();
89        assert!(tc.is_directed());
90        assert_eq!(tc.ecount(), 3);
91        for &(u, v) in &[(0u32, 1u32), (0, 2), (1, 2)] {
92            assert!(tc.find_eid(u, v).unwrap().is_some(), "missing {u}->{v}");
93        }
94        // No reverse edges in directed closure.
95        assert!(tc.find_eid(1, 0).unwrap().is_none());
96        assert!(tc.find_eid(2, 0).unwrap().is_none());
97    }
98
99    #[test]
100    fn undirected_path_3_closure_is_complete_graph() {
101        // 0-1-2 undirected: closure is K3 (3 edges: 01, 02, 12).
102        let mut g = Graph::with_vertices(3);
103        g.add_edge(0, 1).unwrap();
104        g.add_edge(1, 2).unwrap();
105        let tc = transitive_closure(&g).unwrap();
106        assert!(!tc.is_directed());
107        assert_eq!(tc.ecount(), 3);
108        for &(u, v) in &[(0u32, 1u32), (0, 2), (1, 2)] {
109            assert!(tc.find_eid(u, v).unwrap().is_some(), "missing {u}-{v}");
110        }
111    }
112
113    #[test]
114    fn directed_cycle_closure_is_complete_directed() {
115        // 0->1->2->0: closure has all 6 directed pairs.
116        let mut g = Graph::new(3, true).unwrap();
117        g.add_edge(0, 1).unwrap();
118        g.add_edge(1, 2).unwrap();
119        g.add_edge(2, 0).unwrap();
120        let tc = transitive_closure(&g).unwrap();
121        assert_eq!(tc.ecount(), 6); // 3*2 ordered pairs (no self-loops).
122        for u in 0..3u32 {
123            for v in 0..3u32 {
124                if u != v {
125                    assert!(tc.find_eid(u, v).unwrap().is_some());
126                }
127            }
128        }
129    }
130
131    #[test]
132    fn disconnected_components_isolate_in_closure() {
133        // {0-1-2} and {3-4} undirected: closure has edges within each component
134        // only. Component sizes 3 and 2 → 3 + 1 = 4 edges.
135        let mut g = Graph::with_vertices(5);
136        g.add_edge(0, 1).unwrap();
137        g.add_edge(1, 2).unwrap();
138        g.add_edge(3, 4).unwrap();
139        let tc = transitive_closure(&g).unwrap();
140        assert_eq!(tc.ecount(), 4);
141        // Cross-component edges absent.
142        for u in 0..3u32 {
143            for v in 3..5u32 {
144                assert!(tc.find_eid(u, v).unwrap().is_none());
145            }
146        }
147    }
148
149    #[test]
150    fn closure_of_complete_graph_is_itself() {
151        // K3: every pair already connected.
152        let mut g = Graph::with_vertices(3);
153        g.add_edge(0, 1).unwrap();
154        g.add_edge(1, 2).unwrap();
155        g.add_edge(2, 0).unwrap();
156        let tc = transitive_closure(&g).unwrap();
157        assert_eq!(tc.vcount(), 3);
158        assert_eq!(tc.ecount(), 3); // 3 unordered pairs.
159    }
160}
rust_igraph/algorithms/connectivity/transitive_closure.rs

rust_igraph/algorithms/connectivity/
transitive_closure.rs
