Lab 01 — A LangGraph-Faithful StateGraph Engine From Scratch

Phase 18 · Lab 01 · Phase README · Warmup

The problem

The thing that separates someone who uses LangGraph from someone trusted to own it is understanding its execution model — and that model is not "a chain of function calls," it's a Pregel / Bulk-Synchronous-Parallel (BSP) message-passing graph that runs in discrete super-steps. Build a faithful miniature of StateGraph so the model is muscle memory: channels with reducers, nodes, normal + conditional edges, compile, and invoke/stream driven by the super-step loop.

What you build

PieceWhat it does
last_value / add_messages / addreducers — how a node's write combines with the channel (overwrite / append / accumulate)
StateGraph(channels)the graph: add_node, add_edge, add_conditional_edges, set_entry_point
compile() → CompiledGraphvalidate (entry exists, no dead-ends) and freeze into a runnable
invoke / streamthe super-step loop: run active nodes → merge writes via reducers → follow edges → repeat, guarded by recursion_limit

File map

FileRole
lab.pyyour implementation (fill the # TODOs)
solution.pyreference + a main() that builds a ReAct agent as a StateGraph and shows reducers + the recursion guard
test_lab.py18 tests: reducers, validation, linear/conditional/cyclic execution, streaming, determinism
requirements.txtpytest only

Run it

pytest test_lab.py -v
LAB_MODULE=solution pytest test_lab.py -v
python solution.py

Success criteria

  • You can explain the super-step (Pregel/BSP) model: active nodes see the same state, writes merge via reducers, then edges compute the next active set.
  • Your add_messages accumulates and last_value overwrites — and you can say why two writers on one channel need a merge reducer.
  • Conditional edges branch via a router; a cycle hits recursion_limit.
  • invoke and stream agree (invoke is stream consumed to the end).
  • All 18 tests pass under both lab and solution.

How this maps to the real stack

This is the engine underneath langgraph.graph.StateGraph. In real LangGraph:

from typing import Annotated, TypedDict
from langgraph.graph import StateGraph, START, END
from langgraph.graph.message import add_messages

class State(TypedDict):
    messages: Annotated[list, add_messages]   # your add_messages reducer

g = StateGraph(State)
g.add_node("agent", call_model)
g.add_node("tools", run_tools)
g.add_edge(START, "agent")
g.add_conditional_edges("agent", should_continue, {"tools": "tools", "end": END})
g.add_edge("tools", "agent")
app = g.compile()          # + checkpointer in Lab 02

Your channels dict is real LangGraph's Annotated TypedDict; your super-step loop is its Pregel engine; your recursion_limit is the real one (default 25). What you didn't build here — persistence, streaming token mode, subgraphs — layers on top of exactly this loop (Labs 02 & 03).

Limits. Real LangGraph adds async, true-parallel node execution, richer stream modes, typed state validation, and the LangGraph Platform runtime. The execution model is what you built.

Extensions (your own machine)

  • Add fan-out/fan-in: let a node have multiple successor edges (parallel branches) and prove the reducer merges their writes in one super-step.
  • Add a stream_mode="values" (full state per step) alongside the "updates" mode.
  • Rebuild the same ReAct graph in real LangGraph and diff the behavior against your engine.

Interview / resume signal

"Reimplemented LangGraph's StateGraph from scratch — the Pregel/BSP super-step engine with channel reducers, conditional edges, and a recursion guard — so I can explain and debug its execution model (why reducers exist, how loops/branches work, concurrent writes) rather than just call its API."