nx_dep_graph.nx

nx_dep_graph.nx -- V2.0 P-8: directed dependency graph + Tarjan SCC. Sovereign port of Tarjan's 1972 strongly-connected-components algorithm (Robert Tarjan, "Depth-first search and linear graph algorithms", SIAM J. Computing, 1972). Linear-time O(V+E) cycle detection across the substrate artifact graph. COMPOSES (per "avoid duplicate primitives" cardinal): nx_syscalls.sys_mmap (per-instance buffer allocation) COMPOSED BY: wiki/nx_pipeline_walker (V2.0 P-8.5; queued -- populates graph from extractor_nx import lists) wiki/nx_pipeline_route (V3+ /wiki/pipeline/graph view) wiki/nx_artifact_store (V3+ MEANINGFUL refinement: artifact with resolved imports + reverse-deps is more MEANINGFUL than orphans) V2.0 P-8 SCOPE: - NxDepGraph: parallel-pool adjacency list (from_rowid -> list of to_rowid) - nx_dep_graph_add_edge: caller-driven population - nx_dep_graph_tarjan_scc: iterative Tarjan SCC (NO recursion; substrate- friendly; bounded stack budget per NX_DEPG_MAX_STACK) - Per-rowid SCC ID assignment (scc_id[rowid] = scc index 0..N-1) - Accessors: deps / reverse-deps / scc-of / scc-size / cycle-detection V3+ SCOPE (TODO): - Topological sort within DAG (sccs treated as supernodes) - Critical-path computation (longest dep chain) - Pretty-printed graphviz / mermaid emit - Per-SCC quarantine recommendation (cycle = MEANINGFUL refinement blocker per V2_0_PIPELINE_BOOTSTRAP §2.2) REFERENCE: Tarjan 1972 -- the original DFS-based algorithm. Substrate implementation uses explicit work-stack + index/lowlink arrays (no recursive function calls). Status: V2.0 P-8. 2026-05-27.