Module graph_inference 

DSFB-Debug: service-call graph auto-inference (no_std).

Why auto-inference matters

causality::attribute_root_causes (paper §10) requires a service dependency graph as input. Earlier versions made the graph an operator-supplied prerequisite: a deployment couldn’t run root-cause attribution until a human curated the parent→child service map. This module removes that prerequisite by recovering the graph directly from observed span parent-child links in the trace stream.

Algorithm — Tarjan’s SCC

Tarjan’s strongly-connected-components algorithm (Tarjan 1972, “Depth-first search and linear graph algorithms”, SIAM J. Comput. 1(2):146-160) handles cyclic dependency structures (e.g.\ mutual-recursion service pairs). Each SCC contracts to a single supernode; the resulting DAG is the service dependency graph that causality::attribute_root_causes consumes.

Determinism (Theorem 9 preserved)

The entire graph-walk is a pure function of the input edges. Tarjan’s algorithm is deterministic given a fixed input ordering; the caller’s responsibility is to pass ServiceEdge slices in canonical order (lexicographic sort on (parent_service_idx, child_service_idx) is sufficient).

Input shape

ServiceEdge { parent_service_idx, child_service_idx } — indices into a caller-managed signal_names table. The minimal Jaeger / OTLP span shape suffices: service_name, span_id, parent_span_id map to ServiceEdges via a one-pass scan over the span list.

Structs

ServiceEdge

One observed parent->child invocation between services. parent_service_idx and child_service_idx are indices into a caller-managed signal_names table.

Functions

infer_service_graph_from_observed

Infer a parent->child service edge list from raw observation pairs.

tarjan_scc

Strongly-connected-component count via Tarjan’s algorithm. Returns the SCC ID per node into scc_id_out (length must be >= num_services), and the total SCC count.