Function reachability
pub fn reachability(adj: &[Vec<usize>], sccs: &[Vec<usize>]) -> ReachExpand description
Compute per-node visibility fan-in / fan-out over the directed
import graph, given its SCCs (from tarjan_scc).
Method (Baldwin, MacCormack & Rusnak 2014, “Hidden Structure”):
condense the graph to its SCC DAG, then propagate reach-sets in
Tarjan’s emission order (which is reverse-topological — a component
is emitted only after every component it can reach). Each node’s
vfo is the total size of the SCCs reachable from its SCC; vfi is
the total size of the SCCs that can reach it. Self is included
(the visibility matrix is reflexive). Propagation cost — the metric
“a change to a random file can reach X% of the system” — is
sum(vfo) / n² = mean(vfi) / n.
Reach-sets are kept on the condensation and stay sparse for real import graphs; dense pathological graphs trade memory for the exact count (no N×N matrix is ever materialised).