Skip to main content

reachability

Function reachability 

pub fn reachability(adj: &[Vec<usize>], sccs: &[Vec<usize>]) -> Reach
Expand 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).