rust_igraph/algorithms/connectivity/
reachability.rs

1//! Reachability counts (ALGO-CC-020).
2//!
3//! Counterpart of `igraph_count_reachable()` from
4//! `references/igraph/src/connectivity/reachability.c:179`. For each
5//! vertex `v`, returns how many vertices (including `v` itself) are
6//! reachable from `v`.
7//!
8//! Phase-1 minimal slice: BFS-from-each-vertex via the existing
9//! [`crate::algorithms::paths::distances::distances`] primitive. The
10//! O(|V|*(|V|+|E|)) cost is simpler to maintain than upstream's
11//! SCC-condensation approach (O(|C||V|/w + |V| + |E|), where |C| is
12//! the number of strongly connected components and w is the word size).
13//! A perf pass with the SCC trick can land later.
14//!
15//! Edge directions follow the same rule as `distances`: out-edges only
16//! for directed graphs (matching upstream's `IGRAPH_OUT` mode default).
17
18use crate::algorithms::paths::distances::distances;
19use crate::core::{Graph, IgraphResult};
20
21/// Per-vertex count of reachable vertices (including the vertex itself).
22///
23/// Counterpart of `igraph_count_reachable(_, _, IGRAPH_OUT)` for
24/// directed graphs and `IGRAPH_ALL` for undirected.
25///
26/// # Examples
27///
28/// ```
29/// use rust_igraph::{Graph, count_reachable};
30///
31/// // Path 0-1-2-3 undirected: every vertex reaches every vertex.
32/// let mut g = Graph::with_vertices(4);
33/// for i in 0..3 { g.add_edge(i, i + 1).unwrap(); }
34/// assert_eq!(count_reachable(&g).unwrap(), vec![4, 4, 4, 4]);
35///
36/// // Directed chain 0 -> 1 -> 2: 0 reaches all 3, 1 reaches 2, 2 reaches just itself.
37/// let mut g = Graph::new(3, true).unwrap();
38/// g.add_edge(0, 1).unwrap();
39/// g.add_edge(1, 2).unwrap();
40/// assert_eq!(count_reachable(&g).unwrap(), vec![3, 2, 1]);
41/// ```
42pub fn count_reachable(graph: &Graph) -> IgraphResult<Vec<u32>> {
43    let n = graph.vcount();
44    let mut out = Vec::with_capacity(n as usize);
45    for v in 0..n {
46        let d = distances(graph, v)?;
47        let count = u32::try_from(d.iter().filter(|x| x.is_some()).count())
48            .map_err(|_| crate::core::IgraphError::Internal("reachable count exceeds u32"))?;
49        out.push(count);
50    }
51    Ok(out)
52}
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57
58    #[test]
59    fn empty_graph_yields_empty_counts() {
60        let g = Graph::with_vertices(0);
61        assert!(count_reachable(&g).unwrap().is_empty());
62    }
63
64    #[test]
65    fn isolated_vertices_each_reach_only_themselves() {
66        let g = Graph::with_vertices(5);
67        assert_eq!(count_reachable(&g).unwrap(), vec![1; 5]);
68    }
69
70    #[test]
71    fn undirected_path_each_reaches_all() {
72        let mut g = Graph::with_vertices(4);
73        for i in 0..3 {
74            g.add_edge(i, i + 1).unwrap();
75        }
76        assert_eq!(count_reachable(&g).unwrap(), vec![4, 4, 4, 4]);
77    }
78
79    #[test]
80    fn undirected_two_components() {
81        // {0,1,2} and {3,4}: each vertex reaches its component.
82        let mut g = Graph::with_vertices(5);
83        g.add_edge(0, 1).unwrap();
84        g.add_edge(1, 2).unwrap();
85        g.add_edge(3, 4).unwrap();
86        assert_eq!(count_reachable(&g).unwrap(), vec![3, 3, 3, 2, 2]);
87    }
88
89    #[test]
90    fn directed_chain_each_only_reaches_downstream() {
91        // 0 -> 1 -> 2 -> 3.
92        let mut g = Graph::new(4, true).unwrap();
93        g.add_edge(0, 1).unwrap();
94        g.add_edge(1, 2).unwrap();
95        g.add_edge(2, 3).unwrap();
96        assert_eq!(count_reachable(&g).unwrap(), vec![4, 3, 2, 1]);
97    }
98
99    #[test]
100    fn directed_cycle_all_reach_all() {
101        // 0 -> 1 -> 2 -> 0: each vertex reaches all 3.
102        let mut g = Graph::new(3, true).unwrap();
103        g.add_edge(0, 1).unwrap();
104        g.add_edge(1, 2).unwrap();
105        g.add_edge(2, 0).unwrap();
106        assert_eq!(count_reachable(&g).unwrap(), vec![3, 3, 3]);
107    }
108
109    #[test]
110    fn self_loop_does_not_inflate_count() {
111        let mut g = Graph::with_vertices(2);
112        g.add_edge(0, 0).unwrap();
113        g.add_edge(0, 1).unwrap();
114        assert_eq!(count_reachable(&g).unwrap(), vec![2, 2]);
115    }
116}
rust_igraph/algorithms/connectivity/reachability.rs

rust_igraph/algorithms/connectivity/
reachability.rs
