05 · Graphs: reachable is not ready

A graph consists of vertices and edges connecting them. Direction matters: “ingest must precede validate” is not interchangeable with its reverse. Two questions about that graph require different meanings of “next”: BFS asks what is closest by edge count; dependency ordering asks what has no unfinished prerequisite. Both can use a queue. The queue alone does not make the algorithms equivalent.

Representation is part of the interface

In the BFS example, a dictionary maps each node to its outgoing neighbors. An edge a -> b allows a traversal from a to b. A node appearing only as a neighbor is a valid sink with no outgoing edges. The graph is finite, node IDs are hashable, and the source must occur as a key or a neighbor. Empty input has no valid source.

An adjacency list uses O(V+E) storage; an adjacency matrix uses O(V²) slots even for a sparse graph. A tree can be treated as a graph with no cycles and one unique undirected path between any pair of nodes, but an arbitrary directed graph does not inherit those properties. Keep a visited structure rather than trusting a visually tree-shaped example.

Breadth-first search: finalize on discovery

Set the source distance to zero. The FIFO queue processes all nodes at distance d before nodes at distance d+1. When discovering an unseen neighbor, assign one more than the current distance and enqueue it immediately. Marking it now—not when removing it later—prevents many parents from queuing the same node.

from collections import deque
 
 
def bfs_distances(graph, source):
    nodes = set(graph)
    for neighbors in graph.values():
        nodes.update(neighbors)
    if source not in nodes:
        raise ValueError("unknown source")
    distance = {source: 0}
    parent = {source: None}
    queue = deque([source])
    while queue:
        u = queue.popleft()
        for v in graph.get(u, ()):
            if v not in distance:
                distance[v] = distance[u] + 1
                parent[v] = u
                queue.append(v)
    return distance, parent
 
 
graph = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": ["a"], "z": []}
distance, parent = bfs_distances(graph, "a")
assert distance == {"a": 0, "b": 1, "c": 1, "d": 2}
assert "z" not in distance
assert parent["d"] == "b"  # adjacency order breaks equal-length ties
assert bfs_distances({"a": ["b"]}, "b")[0] == {"b": 0}

After visiting a, the queue holds b, c, both one hop away. Visiting b discovers d at distance two. Visiting c cannot improve it to one hop; it would merely find another two-hop route. The first discovery is shortest because any shorter path would have a predecessor in an earlier completed layer.

MIT's official BFS lecture notes develop adjacency representations, level sets and shortest paths. The important qualification is unweighted shortest paths, or equal positive edge costs. An edge with weight 100 is still one hop; BFS cannot minimize arbitrary weighted travel time. DFS can discover reachability, and exhaustive path enumeration could find a shortest path, but ordinary DFS discovery order does not provide BFS's shortest-hop guarantee.

Our implementation scans all graph entries to validate the source, then processes reachable nodes and their edges. Under bounded-cost hashing the total upper bound is O(V+E) time and O(V) auxiliary space. Neighbor collections must be reusable finite collections, not exhausted generators. Duplicate edges add scan work but do not duplicate discoveries.

Dependency ordering: every predecessor must finish

For the notebook, represent prerequisites[job] as a set of jobs that must finish before it. This is the convention of Python's official graphlib.TopologicalSorter, not the outgoing-neighbor representation above. Mistaking one convention for the other can return a reversed yet plausible schedule.

Kahn's algorithm counts remaining prerequisites, enqueues zero-count jobs, emits one, and reduces each dependent job's count. A job becomes ready only at zero. If unfinished jobs remain but none is ready, following predecessors within that finite remainder must eventually revisit a node: a directed cycle blocks completion.

from collections import deque
from graphlib import TopologicalSorter, CycleError
from itertools import permutations
 
 
def dependency_order(prerequisites):
    nodes = set(prerequisites)
    for deps in prerequisites.values():
        nodes.update(deps)
    outgoing = {node: [] for node in nodes}
    remaining = {node: 0 for node in nodes}
    for job, deps in prerequisites.items():
        for dep in set(deps):
            outgoing[dep].append(job)
            remaining[job] += 1
    ready = deque(node for node in nodes if remaining[node] == 0)
    result = []
    while ready:
        job = ready.popleft()
        result.append(job)
        for successor in outgoing[job]:
            remaining[successor] -= 1
            if remaining[successor] == 0:
                ready.append(successor)
    if len(result) != len(nodes):
        raise ValueError("cyclic prerequisites")
    return result
 
 
def valid_order(order, deps):
    positions = {x: i for i, x in enumerate(order)}
    nodes = set(deps).union(*(set(d) for d in deps.values()))
    return (len(order) == len(nodes) == len(positions)
            and set(order) == nodes
            and all(positions[p] < positions[job]
                    for job, ps in deps.items() for p in ps))
 
assert valid_order(dependency_order({"publish": {"validate"}, "validate": {"ingest"}}),
                   {"publish": {"validate"}, "validate": {"ingest"}})
assert dependency_order({}) == []
 
# All directed graphs on three named vertices, including self-loops.
edges = [(u, v) for u in range(3) for v in range(3)]
for mask in range(1 << len(edges)):
    deps = {v: set() for v in range(3)}
    for bit, (u, v) in enumerate(edges):
        if mask & (1 << bit):
            deps[v].add(u)
    possible = any(valid_order(order, deps) for order in permutations(range(3)))
    try:
        order = dependency_order(deps)
    except ValueError:
        assert not possible
    else:
        assert possible and valid_order(order, deps)
    try:
        library_order = list(TopologicalSorter(deps).static_order())
    except CycleError:
        assert not possible
    else:
        assert possible and valid_order(library_order, deps)

Notice what we test: validity, not exact order. Independent jobs may appear in either order. Our ready collection begins from a set, so tie order is not promised across runs. For reproducibility with string job IDs, use a heap of ready IDs and sorted successor processing if needed; this adds ordering overhead and a requirement that the keys be comparable.

O(V+E) time follows from processing each node once and each distinct dependency once, plus reading the input. O(V+E) auxiliary storage holds the reverse edges and counts. Emitting an order is not executing a schedule: real failures, retries and concurrency require a separate state machine. Never mark a job complete merely because it was returned as ready.

Exercises

1. Add parent-pointer path reconstruction to BFS. What does a missing destination mean?
2. Why is “reachable from ingest” insufficient to say that publish is ready?
3. Should a prerequisite that was omitted as a key be accepted? Contrast this lesson's graph utility with a production job catalog.

Exit artifact: shortest-hop distances, a valid dependency order or cycle rejection, and a documented edge convention. These tests exhaust graphs with three vertices, not all possible graphs.

Next: Dynamic programming as a state argument.