rust_igraph/algorithms/connectivity/
reachability_matrix.rs

1//! Reachability matrix (ALGO-CC-021).
2//!
3//! Returns a dense `Vec<Vec<bool>>` where `r[i][j]` is `true` iff vertex
4//! `j` is reachable from vertex `i` in 0 or more steps (with `r[i][i]`
5//! always `true`).
6//!
7//! Counterpart of `igraph_reachability()` from
8//! `references/igraph/src/connectivity/reachability.c:72-148` (which
9//! returns a `bitset_list` indexed by SCC). Phase-1 minimal slice
10//! returns the dense per-vertex bitmap and uses BFS-from-each-vertex
11//! (O(|V|*(|V|+|E|))). The SCC-condensation O(|C||V|/w + |V|+|E|)
12//! optimisation lands later.
13//!
14//! Edge directions follow `crate::distances`: `IGRAPH_OUT` for
15//! directed graphs, full undirected reachability otherwise.
16
17use crate::algorithms::paths::distances::distances;
18use crate::core::{Graph, IgraphResult};
19
20/// Dense reachability matrix of `graph`.
21/// `result[i][j]` is `true` iff vertex `j` is reachable from `i` in
22/// zero or more steps.
23///
24/// On directed graphs follows out-edges (matches upstream's
25/// `IGRAPH_OUT` mode); on undirected graphs reachability is symmetric.
26///
27/// Counterpart of `igraph_reachability(_, _, _, _, _, IGRAPH_OUT)`
28/// (dense output; upstream returns a per-SCC bitset list).
29///
30/// # Examples
31///
32/// ```
33/// use rust_igraph::{Graph, reachability_matrix};
34///
35/// // Directed 0->1->2: 0 can reach all; 1 can reach 1, 2; 2 only 2.
36/// let mut g = Graph::new(3, true).unwrap();
37/// g.add_edge(0, 1).unwrap();
38/// g.add_edge(1, 2).unwrap();
39/// let m = reachability_matrix(&g).unwrap();
40/// assert_eq!(m[0], vec![true, true, true]);
41/// assert_eq!(m[1], vec![false, true, true]);
42/// assert_eq!(m[2], vec![false, false, true]);
43/// ```
44pub fn reachability_matrix(graph: &Graph) -> IgraphResult<Vec<Vec<bool>>> {
45    let n = graph.vcount();
46    let n_us = n as usize;
47    let mut out = Vec::with_capacity(n_us);
48    for v in 0..n {
49        let d = distances(graph, v)?;
50        // `distances[w] == Some(_)` ⇔ `w` is reachable from `v`.
51        let row: Vec<bool> = d.into_iter().map(|x| x.is_some()).collect();
52        out.push(row);
53    }
54    Ok(out)
55}
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn empty_graph_yields_empty_matrix() {
63        let g = Graph::with_vertices(0);
64        let m = reachability_matrix(&g).unwrap();
65        assert!(m.is_empty());
66    }
67
68    #[test]
69    fn isolated_vertices_only_self_reachable() {
70        let g = Graph::with_vertices(3);
71        let m = reachability_matrix(&g).unwrap();
72        assert_eq!(m[0], vec![true, false, false]);
73        assert_eq!(m[1], vec![false, true, false]);
74        assert_eq!(m[2], vec![false, false, true]);
75    }
76
77    #[test]
78    fn undirected_path_is_symmetric_and_full() {
79        let mut g = Graph::with_vertices(3);
80        g.add_edge(0, 1).unwrap();
81        g.add_edge(1, 2).unwrap();
82        let m = reachability_matrix(&g).unwrap();
83        for (i, row) in m.iter().enumerate() {
84            for (j, &val) in row.iter().enumerate() {
85                assert!(val, "{i}->{j} should be reachable");
86                assert_eq!(val, m[j][i], "asymmetry on undirected");
87            }
88        }
89    }
90
91    #[test]
92    fn directed_chain_is_one_way() {
93        let mut g = Graph::new(3, true).unwrap();
94        g.add_edge(0, 1).unwrap();
95        g.add_edge(1, 2).unwrap();
96        let m = reachability_matrix(&g).unwrap();
97        assert_eq!(m[0], vec![true, true, true]);
98        assert_eq!(m[1], vec![false, true, true]);
99        assert_eq!(m[2], vec![false, false, true]);
100    }
101
102    #[test]
103    fn directed_cycle_makes_all_pairs_reachable() {
104        let mut g = Graph::new(3, true).unwrap();
105        g.add_edge(0, 1).unwrap();
106        g.add_edge(1, 2).unwrap();
107        g.add_edge(2, 0).unwrap();
108        let m = reachability_matrix(&g).unwrap();
109        for (i, row) in m.iter().enumerate() {
110            for (j, &val) in row.iter().enumerate() {
111                assert!(val, "{i}->{j} should be reachable in a 3-cycle");
112            }
113        }
114    }
115
116    #[test]
117    fn disconnected_components_isolate_pairs() {
118        // {0,1,2} ∪ {3,4}: cross-component pairs must be false.
119        let mut g = Graph::with_vertices(5);
120        g.add_edge(0, 1).unwrap();
121        g.add_edge(1, 2).unwrap();
122        g.add_edge(3, 4).unwrap();
123        let m = reachability_matrix(&g).unwrap();
124        // Within-component {0,1,2}: all true.
125        for row in &m[..3] {
126            for &v in &row[..3] {
127                assert!(v);
128            }
129        }
130        // Cross-component {0,1,2} x {3,4}: all false.
131        for (i, row) in m.iter().enumerate().take(3) {
132            for (j, &val) in row.iter().enumerate().skip(3).take(2) {
133                assert!(!val, "{i}->{j} should be unreachable");
134                assert!(!m[j][i], "{j}->{i} should be unreachable");
135            }
136        }
137    }
138
139    #[test]
140    fn diagonal_is_always_true() {
141        let g = Graph::with_vertices(7);
142        let m = reachability_matrix(&g).unwrap();
143        for (i, row) in m.iter().enumerate() {
144            assert!(row[i], "vertex {i} not self-reachable");
145        }
146    }
147}
rust_igraph/algorithms/connectivity/reachability_matrix.rs

rust_igraph/algorithms/connectivity/
reachability_matrix.rs
