One-Up, One-Back Chain Reconstruction for FSMA 204

FSMA 204 does not ask any single facility to know the entire journey of a food. It asks each facility to record two adjacent facts about every regulated lot: the immediate previous source it came from, and the immediate subsequent recipient it went to. The regulatory bet is that if every node in the supply chain records its one-up and one-back links faithfully, an investigator can stitch those overlapping fragments into a complete lineage during an outbreak. This page owns the reconstruction step of that bet — the algorithm that takes a pile of Critical Tracking Event records, each carrying only its local neighbors, and reassembles the full directed graph for a suspect lot. It is scoped to the Recall Simulation & FDA 24-Hour Response work, and it depends directly on the Critical Tracking Events model that defines which KDEs each event must carry.

The triggering requirement is Subpart S itself. A shipping facility records an immediate subsequent recipient under § 1.1340; the receiving facility on the other end records an immediate previous source under § 1.1345. Those two records describe the same physical handoff from opposite ends, and reconstruction is the act of proving they agree. When they do, one directed edge joins two lots. When they disagree — a receiving event that names a source lot no shipping event ever produced, or a transformation that consumes a lot with no upstream origin — reconstruction surfaces a gap that must be resolved before a recall scope can be trusted. This page defines how to model CTE events as a directed graph, how to traverse it forward and backward to answer “where did this lot go” and “where did this lot come from,” and how to detect the cycles and broken links that signal corrupt lineage. The narrower how-to guides — reconstructing trace chains with NetworkX and resolving orphaned receiving events — build on the model established here.

Modeling CTE Events as a Directed Graph

The natural data structure for one-up/one-back reconstruction is a directed graph whose nodes are traceability lot codes and whose edges are custody handoffs. An edge points from a source lot to a recipient lot in the direction physical product moves. A Shipping event contributes a forward edge from the shipped lot to the recipient’s lot; a Receiving event contributes the mirror-image edge from its declared previous source to the received lot. Because both ends of a handoff record the same edge from their own vantage point, the graph is deliberately over-specified — and that redundancy is exactly what makes gap detection possible. If only one side of an edge exists, the link is broken and the chain has a hole.

Transformation events are where the topology stops being a simple chain. A Transformation — dicing, blending, repacking — consumes one or more input lots and emits a new output lot with a freshly assigned traceability lot code under § 1.1350. In graph terms it is a fan-in followed by a fan-out: several ancestor lots converge on the transformation node, and one or more descendant lots leave it. This is why a naive linear walk is insufficient. Reconstruction must handle branching in both directions, which is precisely what a general directed-graph traversal gives you. An adjacency dictionary mapping each lot to the set of lots directly downstream (and a parallel reverse map upstream) is enough to model the entire structure; a library such as networkx formalizes the same idea with a DiGraph, but the algorithm does not require it, and the implementation below stays on the standard library.

Two traversals answer the two regulatory questions. A forward breadth-first walk from a suspect lot over the downstream adjacency map yields every lot that could have received contaminated product — the descendants, or the one-forward closure. A backward walk over the upstream map yields every lot that could have been the origin — the ancestors, or the one-back closure. Recall scoping unions the two: the ancestors tell you where to look for the root cause, and the descendants tell you which finished goods to pull from shelves. The diagram below shows a single lot moving through the canonical CTE sequence, with the one-forward and one-back edges that reconstruction reassembles.

Figure — one-up/one-back edges across a lot lineage:

One-Up / One-Back KDE Mapping

Reconstruction only works if the edge-defining KDEs are present and consistent on both sides of every handoff. The table below maps the fields the graph builder reads, the direction each contributes, and the Subpart S source that mandates it. The previous_source_reference and subsequent_recipient_reference are the load-bearing linkage KDEs — everything else is node attribution that lets an investigator interpret an edge once it is drawn.

A record missing its linkage KDE does not merely lack an attribute — it fails to place an edge, which leaves a lot stranded as an isolated node. That is the difference between an incomplete field and a broken chain, and reconstruction must treat the two distinctly. A stranded node is reported as a gap so an operator can chase the missing counterpart record rather than silently accepting a truncated lineage as complete.

Production Reconstruction Engine

The implementation has two layers. A pydantic v2 TraceEvent model validates each CTE record and normalizes its linkage KDEs into immutable tuples, so a single malformed event never corrupts the graph. A LotLineageGraph then ingests validated events into forward and reverse adjacency maps and exposes the four operations reconstruction needs: forward closure (descendants), backward closure (ancestors), gap detection, and cycle detection. The traversal is plain breadth-first search over standard-library dictionaries — deterministic, allocation-light, and trivially testable. A networkx DiGraph would model the same structure, and the companion NetworkX guide shows that route, but the core engine deliberately carries no third-party graph dependency.

from __future__ import annotations

import logging
from collections import defaultdict, deque
from datetime import datetime
from decimal import Decimal
from enum import Enum

from pydantic import BaseModel, ConfigDict, Field, field_validator

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


class CTEType(str, Enum):
    HARVESTING = "Harvesting"
    COOLING = "Cooling"
    INITIAL_PACKING = "Initial Packing"
    SHIPPING = "Shipping"
    RECEIVING = "Receiving"
    TRANSFORMATION = "Transformation"


class TraceEvent(BaseModel):
    """One validated Critical Tracking Event with its linkage KDEs."""

    model_config = ConfigDict(strict=True, frozen=True)

    event_id: str = Field(..., min_length=1)
    traceability_lot_code: str = Field(..., min_length=1, max_length=50)
    cte_type: CTEType
    location_id: str = Field(..., min_length=1)
    event_timestamp: datetime
    quantity: Decimal = Field(..., gt=0)
    unit_of_measure: str
    # one-back KDE: source lot(s) consumed/received by this event
    previous_source_reference: tuple[str, ...] = ()
    # one-forward KDE: recipient/output lot(s) leaving this event
    subsequent_recipient_reference: tuple[str, ...] = ()

    @field_validator("event_timestamp")
    @classmethod
    def require_tz(cls, v: datetime) -> datetime:
        if v.tzinfo is None:
            raise ValueError("event_timestamp must be timezone-aware ISO 8601")
        return v


class LotLineageGraph:
    """Directed lot graph reconstructed from one-up/one-back KDEs."""

    def __init__(self) -> None:
        self._forward: dict[str, set[str]] = defaultdict(set)
        self._backward: dict[str, set[str]] = defaultdict(set)
        self._nodes: set[str] = set()

    def add_event(self, event: TraceEvent) -> None:
        tlc = event.traceability_lot_code
        self._nodes.add(tlc)
        # one-back: source -> this lot
        for src in event.previous_source_reference:
            self._forward[src].add(tlc)
            self._backward[tlc].add(src)
        # one-forward: this lot -> recipient/output lot
        for dst in event.subsequent_recipient_reference:
            self._forward[tlc].add(dst)
            self._backward[dst].add(tlc)

    def _closure(self, start: str, adjacency: dict[str, set[str]]) -> set[str]:
        seen: set[str] = set()
        queue: deque[str] = deque([start])
        while queue:
            node = queue.popleft()
            for nxt in adjacency.get(node, set()):
                if nxt not in seen:
                    seen.add(nxt)
                    queue.append(nxt)
        return seen

    def descendants(self, tlc: str) -> set[str]:
        """One-forward closure: every lot downstream of tlc."""
        return self._closure(tlc, self._forward)

    def ancestors(self, tlc: str) -> set[str]:
        """One-back closure: every lot upstream of tlc."""
        return self._closure(tlc, self._backward)

    def find_gaps(self) -> list[str]:
        """Lots referenced by an edge but with no committed event node."""
        referenced: set[str] = set(self._backward)
        for targets in self._forward.values():
            referenced |= targets
        return sorted(referenced - self._nodes)

    def find_cycles(self) -> list[list[str]]:
        """Detect directed cycles; a valid lineage must be acyclic."""
        color: dict[str, int] = {n: 0 for n in self._nodes}  # 0=white 1=grey 2=black
        cycles: list[list[str]] = []
        path: list[str] = []

        def visit(node: str) -> None:
            color[node] = 1
            path.append(node)
            for nxt in self._forward.get(node, set()):
                if nxt not in color:  # gap node, not committed; skip
                    continue
                if color[nxt] == 1:
                    cycles.append(path[path.index(nxt):] + [nxt])
                elif color[nxt] == 0:
                    visit(nxt)
            path.pop()
            color[node] = 2

        for n in self._nodes:
            if color[n] == 0:
                visit(n)
        return cycles

    def reconstruct(self, tlc: str) -> dict[str, object]:
        if tlc not in self._nodes:
            logger.error("RECONSTRUCT_MISS | tlc=%s has no committed event", tlc)
            raise KeyError(f"No committed event for lot {tlc}")
        gaps = self.find_gaps()
        report: dict[str, object] = {
            "root_tlc": tlc,
            "ancestors": sorted(self.ancestors(tlc)),
            "descendants": sorted(self.descendants(tlc)),
            "gaps": gaps,
            "cycles": self.find_cycles(),
        }
        if gaps:
            logger.warning("TRACE_GAP | root=%s | broken_links=%s", tlc, gaps)
        return report

A short driver shows the shape of a reconstructed recall scope. The events below describe romaine lot ROM-1007 shipped to a processor, received, transformed into salad lot SAL-3300, and shipped onward — the exact one-up/one-back overlap Subpart S is built around.

from datetime import datetime, timezone


def _demo() -> None:
    logging.basicConfig(level=logging.INFO)
    graph = LotLineageGraph()
    events = [
        TraceEvent(
            event_id="E1", traceability_lot_code="ROM-1007",
            cte_type=CTEType.SHIPPING, location_id="0614141000012",
            event_timestamp=datetime(2026, 2, 3, 14, 0, tzinfo=timezone.utc),
            quantity=Decimal("40"), unit_of_measure="case",
            subsequent_recipient_reference=("ROM-1007",),
        ),
        TraceEvent(
            event_id="E2", traceability_lot_code="ROM-1007",
            cte_type=CTEType.RECEIVING, location_id="0614141000029",
            event_timestamp=datetime(2026, 2, 4, 9, 30, tzinfo=timezone.utc),
            quantity=Decimal("40"), unit_of_measure="case",
            previous_source_reference=("ROM-1007",),
        ),
        TraceEvent(
            event_id="E3", traceability_lot_code="SAL-3300",
            cte_type=CTEType.TRANSFORMATION, location_id="0614141000029",
            event_timestamp=datetime(2026, 2, 4, 16, 0, tzinfo=timezone.utc),
            quantity=Decimal("900"), unit_of_measure="ea",
            previous_source_reference=("ROM-1007",),
            subsequent_recipient_reference=("SAL-3300",),
        ),
    ]
    for event in events:
        graph.add_event(event)

    print(graph.reconstruct("ROM-1007"))


if __name__ == "__main__":
    _demo()

Running the driver prints the ancestors and descendants of ROM-1007 and confirms no gaps or cycles: the romaine lot has SAL-3300 among its descendants, so a contamination signal on the romaine correctly expands to the finished salad. The reverse walk from SAL-3300 would return ROM-1007 as an ancestor, which is how an investigator working backward from a sick-consumer product reaches the field lot.

Error Handling and Broken-Link Strategy

Reconstruction fails in three characteristic ways, and each has a distinct signal. A gap is a lot referenced by an edge whose counterpart event was never committed — a receiving event that names source ROM-1007 when no shipping event ever produced it. find_gaps returns these as dangling references, and they are the most common real-world defect because they arise whenever one side of a handoff is late, quarantined, or filed under a mismatched lot code. A gap is not a reason to fail the whole reconstruction; it is a reason to widen the scope conservatively and flag the missing counterpart for follow-up. The dedicated guide on resolving orphaned receiving events walks the root causes and the reconciliation join that closes them.

A cycle is structurally impossible in a valid lineage — product cannot be its own ancestor — so any cycle find_cycles reports is proof of corrupt data: a duplicated lot code reused across unrelated lots, or a reversed edge where a receiving event was recorded as a shipping event. Cycles must halt automated scope expansion, because a traversal over a cyclic graph will either loop or silently conflate two distinct lots into one recall. The engine surfaces the offending cycle path so an operator can identify the duplicated code. A stranded node is a committed lot with no edges at all, usually because both its linkage KDEs were empty; it is reconstruction’s signal that the record was persisted but never wired into the chain.

When a reconstruction cannot be completed because a required upstream record is genuinely absent — not merely late — the recall query must not return a falsely narrow scope. That decision belongs to the Fallback Routing Logic, which decides whether to expand the recall to a conservative superset (every lot handled at the affected location in the window), divert the query to manual investigation, or hold it pending the missing record. Reconstruction’s job is to detect and report the break precisely; the routing layer decides what a responsible response to that break looks like. This division keeps the graph algorithm pure and testable while the compliance judgment lives in one auditable place.

Integration with the Recall Pillar

This engine is the reconstruction stage inside the parent Recall Simulation & FDA 24-Hour Response workflow. Upstream, validated CTE records arrive already conforming to the KDE contract enforced during ingestion — the same Schema Validation Rules gate that guarantees each event_timestamp is timezone-aware and each linkage KDE is well-formed before it ever reaches the graph. Reconstruction therefore assumes clean nodes and concentrates entirely on the edges between them. Downstream, the ancestor and descendant sets it produces feed lot-level recall scoping and the sortable-spreadsheet export the FDA request demands within 24 hours.

The reconstruction output also composes with the broader compliance model documented in the FSMA 204 architecture reference. Because the graph is built purely from linkage KDEs cited to specific Subpart S sections, a reconstructed lineage is directly defensible: every edge traces to a § 1.1340 subsequent-recipient record or a § 1.1345 previous-source record, and every gap names the exact section whose counterpart record is missing. That traceability is what turns a graph traversal into an audit artifact rather than an internal convenience.

Operational Notes

Run reconstruction as an on-demand query against the committed ledger, not as a standing service — it is invoked when a recall is declared or a drill is scheduled, and it should read a consistent snapshot so the graph does not shift mid-traversal. Recommended runtime and dependencies:

• Python 3.10+ (the code uses from __future__ import annotations, PEP 604 unions, and list[...] / dict[...] generics).
• pydantic ≥ 2.5 for the v2 field_validator and ConfigDict API. Never mix in the v1 validator decorator.
• networkx ≥ 3.2 is optional and only needed for the companion NetworkX guide; the core engine here is standard-library only.

Set a LEDGER_SNAPSHOT source (a read replica or a point-in-time export) and a RECALL_WINDOW bound so traversal is scoped to the relevant date range rather than the entire historical graph. Log every reconstruction with the root lot code, the ancestor and descendant counts, and any gaps or cycles found, so a drill produces the same audit trail as a live recall. For the two procedural deep-dives that extend this model, see reconstructing trace chains with NetworkX and resolving orphaned receiving events in recall queries.

Frequently Asked Questions

Related

• Reconstructing trace chains with NetworkX — the same directed-graph model expressed with a DiGraph and built-in ancestors/descendants helpers.
• Resolving orphaned receiving events in recall queries — root-cause and reconciliation for the most common broken-link defect.
• Fallback Routing Logic — decides how a recall query responds when reconstruction reports an unresolved gap.
• Schema Validation Rules — the ingestion gate that guarantees clean nodes before they reach this graph.
• FSMA 204 architecture reference — the CTE and KDE model whose linkage fields define every edge here.

Up: Recall Simulation & FDA 24-Hour Response — reconstruction is the stage that turns validated CTE records into the lot graph a recall scope is drawn from.