Reconstructing FSMA 204 Trace Chains with NetworkX

The standard-library engine in the One-Up, One-Back Chain Reconstruction guide models a lot lineage with plain adjacency dictionaries. Once the graph grows past a few hundred lots — or once you want centrality, shortest-path, or connected-component analysis for a recall drill — a purpose-built graph library earns its dependency. This guide shows how to reconstruct the same one-up/one-back lineage as a NetworkX DiGraph, run ancestors() and descendants() to answer the two regulatory questions, and use weakly-connected-component analysis to catch the single most common structural defect: a sub-chain that is disconnected from the lot you are actually recalling.

The task is specific and easy to get subtly wrong. A lot lineage is directed, and the direction encodes regulatory meaning: an edge points from an immediate previous source to its immediate subsequent recipient, in the direction product physically moves. Get that direction backward and nx.descendants() will faithfully return the ancestors — a silent error that produces a plausible-looking but inverted recall scope. This guide walks the correct construction, a reproduction of the reversed-edge bug, the fix, and the assertions that prove the graph is right before anyone acts on it.

Root Cause: Why NetworkX Reconstruction Goes Wrong

Two failure modes account for nearly every incorrect NetworkX lineage. The first is edge direction. NetworkX defines descendants(G, n) as every node reachable from n by following edges forward, and ancestors(G, n) as every node that can reach n. That maps cleanly onto FSMA 204 only if you add each edge as add_edge(previous_source, subsequent_recipient). Teams that think in terms of “who did this lot come from” often add the edge the other way, and then descendants and ancestors quietly swap. Because both return non-empty, sensible-looking sets, the mistake survives casual inspection and only surfaces when a recall pulls the wrong products.

The second failure mode is disconnection. Reconstruction ingests thousands of overlapping one-up/one-back records, and if one facility’s shipping event is missing, its lots form an island — a weakly-connected component with no path to or from the suspect lot. A traversal rooted at the suspect lot will simply never visit that island, so the recall silently omits it. NetworkX makes this defect observable: a healthy reconstruction around a single recall should be one weakly-connected component, and number_weakly_connected_components greater than one is a direct signal that the chain has fractured. The diagram below shows the shape we are reconstructing — ancestors feeding a suspect lot, descendants leaving it, and a disconnected orphan component that must be detected rather than traversed past.

Figure — DiGraph closure and a disconnected component:

Minimal Reproducible Example

The reproduction below builds a lineage from a realistic list of one-up/one-back KDE edges, but adds each edge in physical-intuition order — recipient first — which reverses direction. It also includes the SPN-2200 → SPN-2205 handoff that belongs to an unrelated lot with no connection to the recalled SAL-3300, standing in for a fractured chain.

import networkx as nx

# (previous_source_tlc, subsequent_recipient_tlc, cte_type)
kde_edges = [
    ("ROM-1007", "SAL-3300", "Transformation"),
    ("ROM-1009", "SAL-3300", "Transformation"),
    ("SAL-3300", "SAL-3300-D1", "Shipping"),
    ("SAL-3300", "SAL-3300-R2", "Shipping"),
    ("SPN-2200", "SPN-2205", "Receiving"),  # unrelated island
]

g = nx.DiGraph()
for source, recipient, cte in kde_edges:
    # BUG: edge added recipient -> source, inverting the lineage
    g.add_edge(recipient, source, cte_type=cte)

# Expect the finished shipments; get the field lots instead.
print("descendants:", nx.descendants(g, "SAL-3300"))
# -> {'ROM-1007', 'ROM-1009'}  (wrong: these are ancestors)
print("components:", nx.number_weakly_connected_components(g))
# -> 2  (the SPN island is present but never traversed from SAL-3300)

The bug is invisible to a smoke test: nx.descendants(g, "SAL-3300") returns a non-empty set of real lot codes, so nothing throws. But those codes are the upstream field lots, not the downstream shipments a recall must pull. Acting on this graph would recall the wrong direction of the supply chain entirely.

Fix Implementation

The fix is to add every edge in regulatory direction — previous source to subsequent recipient — and to make the disconnected-component check an explicit gate rather than an afterthought. Wrapping construction in a small function keeps the direction contract in one auditable place.

import logging

import networkx as nx

logger = logging.getLogger("fsma204.nx_reconstruction")


def build_lineage(kde_edges: list[tuple[str, str, str]]) -> nx.DiGraph:
    """Build a lot lineage DiGraph from one-up/one-back KDE edges.

    Each edge points previous_source -> subsequent_recipient, so
    nx.descendants() returns the one-forward closure and
    nx.ancestors() returns the one-back closure.
    """
    g = nx.DiGraph()
    for source, recipient, cte in kde_edges:
        g.add_edge(source, recipient, cte_type=cte)  # correct direction
    if not nx.is_directed_acyclic_graph(g):
        cycle = nx.find_cycle(g)
        logger.error("LINEAGE_CYCLE | edges=%s", cycle)
        raise ValueError(f"Lineage contains a cycle: {cycle}")
    return g


def recall_scope(g: nx.DiGraph, suspect_tlc: str) -> dict[str, object]:
    """Return the one-back and one-forward closure for a suspect lot,
    plus any lots stranded in a disconnected component."""
    forward = nx.descendants(g, suspect_tlc)   # where product went
    backward = nx.ancestors(g, suspect_tlc)    # where product came from
    connected = forward | backward | {suspect_tlc}
    stranded = set(g.nodes) - connected
    if stranded:
        logger.warning("DISCONNECTED_LOTS | suspect=%s | stranded=%s",
                       suspect_tlc, sorted(stranded))
    return {
        "suspect": suspect_tlc,
        "descendants": sorted(forward),
        "ancestors": sorted(backward),
        "stranded": sorted(stranded),
    }

With edges in the correct direction, nx.descendants(g, "SAL-3300") now returns {"SAL-3300-D1", "SAL-3300-R2"} — the finished shipments — and nx.ancestors(g, "SAL-3300") returns {"ROM-1007", "ROM-1009"} — the field lots. The recall_scope helper additionally subtracts the connected closure from the full node set, so the SPN-2200/SPN-2205 island surfaces in stranded instead of being silently skipped. A stranded lot is not automatically part of the recall, but it must be reviewed: it usually means a missing edge, and the Fallback Routing Logic decides whether to widen the scope until the gap is explained.

Verification Steps

Prove the graph before trusting it. The assertions below lock the node and edge counts, confirm the closure direction, and verify that a path exists from a field lot all the way to a retail shipment.

edges = [
    ("ROM-1007", "SAL-3300", "Transformation"),
    ("ROM-1009", "SAL-3300", "Transformation"),
    ("SAL-3300", "SAL-3300-D1", "Shipping"),
    ("SAL-3300", "SAL-3300-R2", "Shipping"),
    ("SPN-2200", "SPN-2205", "Receiving"),
]
g = build_lineage(edges)

# Structure: 7 distinct lots, 5 recorded handoffs.
assert g.number_of_nodes() == 7, g.number_of_nodes()
assert g.number_of_edges() == 5, g.number_of_edges()

# Direction: descendants are downstream, ancestors upstream.
assert nx.descendants(g, "SAL-3300") == {"SAL-3300-D1", "SAL-3300-R2"}
assert nx.ancestors(g, "SAL-3300") == {"ROM-1007", "ROM-1009"}

# End-to-end reachability from field lot to retail shipment.
assert nx.has_path(g, "ROM-1007", "SAL-3300-R2")

# Fracture detection: the SPN island is stranded, not traversed.
scope = recall_scope(g, "SAL-3300")
assert scope["stranded"] == ["SPN-2200", "SPN-2205"]
assert nx.number_weakly_connected_components(g) == 2
print("lineage verified:", scope)

Every assertion is a compliance guarantee, not a style check. The node and edge counts catch duplicate or dropped records; the direction assertions catch the reversed-edge bug; has_path proves the suspect lot’s contamination can actually reach the finished good; and the stranded-set assertion proves the disconnected component was detected rather than quietly omitted from the recall. Wiring these into the mock-drill suite means a reversed or fractured graph fails the build instead of the outbreak.

Related Edge Cases

• A lot with no ancestors or descendants. If both nx.ancestors and nx.descendants return empty sets for a committed lot, it was added as an isolated node — usually because both linkage KDEs were blank. Treat it exactly like a stranded lot and chase the missing edge.
• Self-loops from duplicated lot codes. If the same traceability lot code is reused for two unrelated lots, build_lineage may raise on the resulting cycle. Namespace lot codes by assigning facility before ingestion so SAL-3300 from two packers never collides.
• Multiple suspect lots in one recall. For a broad outbreak, take the union of descendants across every suspect lot rather than reconstructing each separately, so shared downstream shipments are counted once and no descendant is missed.

Frequently Asked Questions

Related

• One-Up, One-Back Chain Reconstruction for FSMA 204 — the parent guide with the standard-library graph model and the KDE contract behind every edge.
• Resolving orphaned receiving events in recall queries — the root-cause detail behind a stranded receiving lot with no matching shipper.
• Fallback Routing Logic — decides how to respond when a disconnected component leaves a real gap.
• FSMA 204 architecture reference — the CTE and KDE definitions that determine each edge’s direction.

Up: One-Up, One-Back Chain Reconstruction — this guide expresses the parent’s directed-graph model with a NetworkX DiGraph.