Graphs & dependency plans
Represent work that depends on other work, and discover when the plan is impossible.
BY THE END, YOU CAN
- Represent vertices and directed edges
- Explain breadth-first traversal and topological order
- Detect cycles in dependency workflows
Diagram description: fetch → build; fetch → test; build → deploy; test → deploy; a → b (cycle: fail early); b → a
Relationships are data too
A graph consists of vertices and edges.
In a job workflow, each vertex is a job and an edge means one job must finish before another can begin. Choose and document the edge direction: 'A points to B' might mean A unlocks B or A depends on B, and those conventions are opposites. An adjacency list stores neighbors for each vertex.
Graphs also model package dependencies, service calls, build systems, and organizational ownership. Their usefulness comes from making relationships explicit enough to analyze.
Traversal answers a particular question
Breadth-first search explores vertices in increasing number of edges from a starting point and finds shortest paths in an unweighted graph.
A visited set prevents repeated exploration and infinite loops in cyclic graphs. Depth-first traversal explores one branch before returning. Neither traversal alone gives every possible dependency schedule.
For prerequisite work, a topological order places prerequisites before dependents. Such an order exists only for a directed acyclic graph, and multiple valid orders may exist when independent jobs can run in any order.
An impossible plan should fail early
Python's TopologicalSorter accepts a mapping from each node to its predecessors.
The example says publish depends on render, and render depends on fetch. A cycle such as fetch depending on publish has no valid starting point. Detect this when accepting the workflow instead of leaving jobs waiting forever.
Also distinguish a valid dependency graph from successful execution: a prerequisite can fail at runtime. Relay needs a policy for dependent jobs when an ancestor fails, such as cancellation or a visible blocked state.
from graphlib import TopologicalSorter
plan = {"fetch": [], "render": ["fetch"], "publish": ["render"]}
print(list(TopologicalSorter(plan).static_order()))COMMON FAILURE MODE
Confusing 'the graph has a valid order' with 'all jobs will succeed.' Dependency failure still needs a runtime policy.
TRY IT YOURSELF
Draw dependencies for fetch → render → publish and fetch → archive. List two valid schedules, then introduce a cycle and explain why execution cannot start safely.
Make the call in the laboratory.
The two-question checkpoint, your notes, and your saved progress are in the laboratory. Free, with no account.
Open in the laboratory ↗CONNECT IT TO RELAY
Let Relay validate a small dependency workflow. Reject cycles and define what 'blocked by failed prerequisite' means.