Module import_graph 

Shared structural-import-graph kernel.

Builds the directed file→file import graph from the imports table and computes strongly-connected components. Reused by the architecture analyses that reason over structure rather than history (dependency-cycles, and the reachability-based metrics).

The SCC routine is a hand-rolled iterative Tarjan (Tarjan 1972). Iterative, not recursive, because a long import chain (a 50k-file monorepo can have deep transitive use paths) would overflow the call stack with the recursive formulation. The analysis crate deliberately avoids petgraph (its optional 0.8 dep conflicts with leiden-rs), and unsafe is forbidden workspace-wide — so this is a plain Vec-based adjacency walk.

Structs

GraphMetrics

Repo-level structural metrics derived from one SCC + reachability pass. The single source of truth shared by architecture-metrics (HEAD) and architecture-trend (sampled history) so the two can never disagree on propagation cost or cycle structure.

ImportGraph

The directed structural import graph. Nodes are repo-relative paths: every live Tier-1 source file, plus any resolved import endpoint. A file that neither imports nor is imported is still a node (a singleton with empty adjacency), so isolated files are counted in n. Edges are src → target (“src imports target”).

Reach

Per-node transitive reachability counts over the import graph.

ReachIndex

Transitive-reachability index for pairwise “is there a dependency path between these two files?” queries. Built on the SCC condensation so cycles collapse to a point; the forward reach-sets stay sparse for real import graphs (no N×N matrix).

Functions

build_import_graph

Build the directed import graph over every live Tier-1 source file. Nodes are seeded from complexity_metrics (one row per parsed source file, isolated files included) and edges from the resolved rows in the imports table (target_path IS NOT NULL). Seeding from all source files — not just resolved endpoints — keeps a file that neither imports nor is imported in n, so propagation_cost and cycle share are computed over the full component set (per MacCormack/Lakos). Parallel edges are deduped and self-loops dropped — neither affects reachability or SCC membership, and removing them keeps the adjacency tight.

build_import_graph_from_edges

Build the directed import graph from an in-memory (src, target) edge list alone — the zero-seed case of build_import_graph_seeded, so nodes are exactly the resolved edge endpoints. Used where the node set is intended to be edge-derived (e.g. the change-set projection’s cycle check, which only reasons over SCCs of size ≥ 2 that singletons never enter).

build_import_graph_seeded

Build the directed import graph over seed_nodes ∪ edge-endpoints. Seed nodes are interned first, so a seed file with no edges becomes a singleton (empty-adjacency) node counted in n — isolated source files that neither import nor are imported still participate in the propagation_cost and cycle-share denominators. Edges use the same parallel-edge dedup + self-loop drop as build_import_graph; the adjacency is sized after all interning, so singletons get empty vecs.

graph_metrics

Compute GraphMetrics for graph. Empty graph → all zeros.

reach_index

Build a ReachIndex for pairwise connectivity queries. Same forward-closure construction as reachability, but retains the reach-sets instead of collapsing them to counts.

reachability

Compute per-node visibility fan-in / fan-out over the directed import graph, given its SCCs (from tarjan_scc).

tarjan_scc

Strongly-connected components of a directed graph via iterative Tarjan. Each returned Vec is the node ids of one SCC. A singleton component is a node on no cycle; a component of size ≥ 2 is a dependency cycle (tangle).

topo_levels

Per-node topological layer of the import graph: the longest path (in the SCC condensation) from a source to the node’s SCC. Cycle members share their SCC’s level.