Graphs, BFS and DFS, from first idea to production

You type pip install and a few seconds later forty packages are on your disk, each installed after the packages it needs. A map app finds the fastest way home through thousands of junctions. PostgreSQL notices that two transactions are each waiting for the other and kills one of them about a second later. None of these programs knows anything about packages, roads or transactions in particular. They all reduce the problem to dots and lines and walk it with one of a handful of algorithms.

That model is a graph, and the walks are mostly two: breadth-first search (BFS), which spreads out in rings, and depth-first search (DFS), which follows one route as far as it goes before backing up. Almost everything else in this article is one of those two with a small twist: a queue swapped for a heap, a counter added to each node, a colour remembered per node.

By the end you’ll be able to store a graph in Python, find shortest paths, count connected groups, detect cycles, order tasks by their dependencies, and explain why Dijkstra’s algorithm breaks on negative edges. You’ll also see where graphs sit inside real backends: permission hierarchies, dependency checks, record merges and deadlocks, with code from ezychat.io and from this site. Start at Beginner if “node” and “edge” are new words. If you’ve written a BFS before, skip to Intermediate and try the demos.

Beginner: dots, lines and a dict of lists

What is a graph?

A graph is a set of things and the connections between some pairs of them. The things are nodes (also called vertices) and the connections are edges. That’s the whole definition. What makes it useful is how many problems already have this shape:

• People and friendships. Each person is a node; two friends share an edge. “Is Dina a friend of a friend of Ali?” is a graph question.
• Cities and roads. Each city is a node; each road is an edge, with a distance on it. “What’s the shortest drive from Penang to Melaka?” is a graph question.
• Tasks and dependencies. Each task is a node; an arrow from A to B means “A must happen before B”. “In what order can I do these?” is a graph question.

Two counts come up constantly, so they get letters: V is the number of nodes and E the number of edges. The top graph above has V = 4 and E = 4.

Directed or undirected, weighted or not

Two questions classify almost every graph you’ll meet.

Does an edge have a direction? Friendship is mutual: if Ali is Ben’s friend, Ben is Ali’s. That’s an undirected graph. “Follows” on a social network isn’t mutual, and neither is “must happen before”. Those are directed graphs, and their edges are drawn as arrows. In a directed graph, the number of arrows coming into a node is its in-degree and the number going out is its out-degree. In an undirected graph there’s just the degree, the number of edges touching the node.

Does an edge carry a number? A road has a length, a flight has a price, a network link has a delay. That number is a weight, and a graph with them is weighted. If every edge counts the same, the graph is unweighted, and “shortest path” just means “fewest edges”.

A few more words you’ll need. A path is a sequence of nodes where each consecutive pair is joined by an edge. A cycle is a path that comes back to where it started. A graph is connected if there’s a path between every pair of nodes; if not, it splits into separate connected components. A directed graph with no cycles has its own name, a DAG (directed acyclic graph), and it’s the shape of every build system and task scheduler. A tree is a connected graph with no cycles at all: a folder hierarchy, an org chart, a comment thread.

Storing a graph in Python: a dict of lists

The most common way to store a graph is an adjacency list: for each node, the list of its neighbours. In Python that’s a dictionary from node to list, which is exactly the structure the hash maps article spends its time on. Finding a node’s neighbours is one dictionary lookup.

friends = {}

def add_friendship(a, b):
    friends.setdefault(a, []).append(b)   # undirected: store the edge both ways
    friends.setdefault(b, []).append(a)

for a, b in [("ali", "ben"), ("ali", "chen"), ("ben", "chen"), ("chen", "dina"), ("eli", "fatin")]:
    add_friendship(a, b)

print(friends["chen"])
print(len(friends["chen"]), "friends")
print("dina" in friends["ali"])
print(sorted(friends))
# ['ali', 'ben', 'dina']
# 3 friends
# False
# ['ali', 'ben', 'chen', 'dina', 'eli', 'fatin']

Notice that an undirected edge is stored twice, once in each direction. Forgetting the second append is the most common bug in hand-built graphs: everything looks fine until a search from the other end can’t find its way back.

Weighted and directed graphs are small variations. For weights, store a dictionary of neighbour to weight instead of a list. For direction, store the edge only once, from its source.

roads = {                       # weighted, undirected: city -> {neighbour: km}
    "KL":     {"Ipoh": 205, "Melaka": 145},
    "Ipoh":   {"KL": 205, "Penang": 165},
    "Melaka": {"KL": 145, "JB": 225},
    "Penang": {"Ipoh": 165},
    "JB":     {"Melaka": 225},
}
print(roads["KL"]["Melaka"], "km")

steps = {                       # directed: task -> the tasks that must wait for it
    "write code":  ["run tests"],
    "run tests":   ["build image"],
    "build image": ["deploy"],
    "migrate db":  ["deploy"],
    "deploy":      [],
}
print(steps["run tests"])
print([t for t, after in steps.items() if "deploy" in after])
# 145 km
# ['build image']
# ['build image', 'migrate db']

(The distances are rounded and only there to give the edges numbers.) Look at the last line. Asking “what does run tests lead to?” is one lookup, but asking “what leads into deploy?” meant scanning every list. A directed adjacency list answers questions in the direction it was built. If you need both directions often, build a second dictionary with every edge reversed. That trick comes back in Advanced, and in a real codebase in the production section.

The other option: an adjacency matrix

An adjacency matrix is a V × V grid where row a, column b holds 1 (or the weight) if there’s an edge from a to b, and 0 otherwise.

names = ["ali", "ben", "chen", "dina", "eli", "fatin"]
index = {name: i for i, name in enumerate(names)}
matrix = [[0] * len(names) for _ in names]
for a, b in [("ali", "ben"), ("ali", "chen"), ("ben", "chen"), ("chen", "dina"), ("eli", "fatin")]:
    matrix[index[a]][index[b]] = matrix[index[b]][index[a]] = 1

for name, row in zip(names, matrix):
    print(f"{name:>5}", row)
print(matrix[index["chen"]][index["dina"]] == 1)   # one jump, no searching
#   ali [0, 1, 1, 0, 0, 0]
#   ben [1, 0, 1, 0, 0, 0]
#  chen [1, 1, 0, 1, 0, 0]
#  dina [0, 0, 1, 0, 0, 0]
#   eli [0, 0, 0, 0, 0, 1]
# fatin [0, 0, 0, 0, 1, 0]
# True

The matrix answers “are these two connected?” with a single index, and the list has to scan a neighbour list (or use a set instead of a list). But the matrix pays for every possible pair, connected or not. Real graphs are almost always sparse: each node connects to a handful of others, not to most of them. Here’s what that costs, measured with tracemalloc on my laptop for 10,000 people with about five friends each:

import random, tracemalloc

random.seed(7)
n, per_node = 10_000, 5                      # 10,000 people, about 5 friends each
edges = [(random.randrange(n), random.randrange(n)) for _ in range(n * per_node // 2)]

tracemalloc.start()
adj = {v: [] for v in range(n)}
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)
list_bytes = tracemalloc.get_traced_memory()[0]
tracemalloc.stop()

tracemalloc.start()
matrix = [bytearray(n) for _ in range(n)]     # one byte per pair, the cheapest matrix
for a, b in edges:
    matrix[a][b] = matrix[b][a] = 1
matrix_bytes = tracemalloc.get_traced_memory()[0]
tracemalloc.stop()

print(f"adjacency list:   {list_bytes / 2**20:6.1f} MiB")
print(f"adjacency matrix: {matrix_bytes / 2**20:6.1f} MiB")
print(f"cells in use: {sum(len(v) for v in adj.values()) / n**2:.3%}")
# adjacency list:      1.6 MiB
# adjacency matrix:   96.0 MiB
# cells in use: 0.050%

Sixty times the memory, and 99.95% of the matrix is zeros. Double the people and the list doubles while the matrix quadruples. My rule: use an adjacency list unless the graph is small and dense. Matrices earn their place in a few spots: graphs of a few hundred nodes where most pairs are connected, algorithms that are naturally written over a matrix (Floyd-Warshall for all-pairs shortest paths), and maths, where the matrix is the object (PageRank in Expert is matrix multiplication in disguise).

There’s a third representation you’ve already used without the name: a plain edge list, [("ali", "ben"), ...]. It’s how graphs arrive from files, APIs and database tables. You usually convert it to an adjacency list straight away, which is the first exercise.

def build_graph(nodes, edges, directed=False):
    graph = {v: [] for v in nodes}          # every node gets a list, even with no edges
    for a, b in edges:
        graph[a].append(b)
        if not directed:
            graph[b].append(a)
    return graph

g = build_graph("ABCDE", [("A", "B"), ("B", "C"), ("A", "C")])
print(g)
print(build_graph("ABC", [("A", "B"), ("B", "C")], directed=True))
# {'A': ['B', 'C'], 'B': ['A', 'C'], 'C': ['B', 'A'], 'D': [], 'E': []}
# {'A': ['B'], 'B': ['C'], 'C': []}

def find_judge(n, trust):
    trusted_by = [0] * (n + 1)              # in-degree
    trusts = [0] * (n + 1)                  # out-degree
    for a, b in trust:
        trusts[a] += 1
        trusted_by[b] += 1
    for person in range(1, n + 1):
        if trusted_by[person] == n - 1 and trusts[person] == 0:
            return person
    return -1

print(find_judge(3, [(1, 3), (2, 3)]))
print(find_judge(3, [(1, 3), (2, 3), (3, 1)]))
print(find_judge(1, []))
# 3
# -1
# 1

Intermediate: BFS, DFS and the problems they solve

Every graph algorithm in this section has the same skeleton. Keep a frontier of nodes you know about but haven’t explored. Take one out, look at its neighbours, add the new ones to the frontier, and remember which nodes you’ve already seen so you never add them twice. The only real choice is which node you take out next. Take the oldest and you get BFS. Take the newest and you get DFS.

BFS: explore in rings with a queue

Breadth-first search takes the oldest node first, which means it uses a queue: first in, first out. Starting from Ali, it visits all of Ali’s friends, then all of their friends, then the next ring out. Edward F. Moore described it in 1959 as a way to find the shortest path through a maze, and it’s still the right tool for that.

from collections import deque

friends = {
    "ali": ["ben", "chen"], "ben": ["ali", "chen", "eli"], "chen": ["ali", "ben", "dina"],
    "dina": ["chen", "fatin"], "eli": ["ben", "fatin"], "fatin": ["dina", "eli", "gita"],
    "gita": ["fatin"],
}

def bfs(graph, start):
    dist = {start: 0}                  # doubles as the visited set
    queue = deque([start])
    while queue:
        node = queue.popleft()         # oldest first: nearest first
        for nxt in graph[node]:
            if nxt not in dist:        # mark when queued, not when popped
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist

print(bfs(friends, "ali"))
# {'ali': 0, 'ben': 1, 'chen': 1, 'eli': 2, 'dina': 2, 'fatin': 3, 'gita': 4}

The output is a map of hop distances: Gita is four handshakes from Ali. Two details decide whether a BFS is correct and fast.

Mark nodes when you queue them, not when you pop them. If you wait until the pop, the same node can be queued several times by different neighbours before its first copy comes out. The answer stays right but the queue fills with duplicates; on a dense graph it can hold close to E entries instead of V.

Use collections.deque, not a list. list.pop(0) shifts every remaining item one place left, so it costs O(n). deque.popleft() is O(1). Measured on my laptop:

import time
from collections import deque

n = 100_000
items = list(range(n))
start = time.perf_counter()
while items:
    items.pop(0)                 # shifts every remaining item left by one
list_s = time.perf_counter() - start

items = deque(range(n))
start = time.perf_counter()
while items:
    items.popleft()              # moves one pointer
deque_s = time.perf_counter() - start
print(f"list.pop(0): {list_s * 1000:.0f} ms   deque.popleft(): {deque_s * 1000:.1f} ms")
# list.pop(0): 840 ms   deque.popleft(): 4.3 ms

About two hundred times slower for 100,000 items, and the gap keeps growing, because the list version is quadratic. A BFS written with queue.pop(0) passes every small test and then crawls.

Why BFS finds the shortest path

In an unweighted graph, BFS reaches every node by a path with the fewest possible edges. The argument is short. The queue always holds nodes at distance d followed by nodes at distance d + 1, never anything else, because a node at distance d can only add neighbours at distance d + 1. So BFS finishes every node at distance 1 before it touches distance 2, and the first time it reaches a node is by a shortest route.

To get the path itself and not only its length, remember for each node how you first reached it: its parent. When you reach the goal, follow parents back to the start and reverse.

from collections import deque

def shortest_path(graph, start, goal):
    parent = {start: None}             # how we first reached each node
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            path = []
            while node is not None:    # walk the parent links back to the start
                path.append(node)
                node = parent[node]
            return path[::-1]
        for nxt in graph[node]:
            if nxt not in parent:
                parent[nxt] = node
                queue.append(nxt)
    return None                        # goal not reachable

print(shortest_path(friends, "ali", "gita"))
print(shortest_path(friends, "dina", "eli"))
print(shortest_path({"a": [], "b": []}, "a", "b"))
# ['ali', 'ben', 'eli', 'fatin', 'gita']
# ['dina', 'fatin', 'eli']
# None

The parent dictionary does two jobs: it’s the visited set and the breadcrumb trail. That pairing is so common that it’s worth making the default; a separate visited set next to a parent map is usually a sign that one of them is redundant.

DFS: go deep with recursion or a stack

Depth-first search takes the newest node first. It follows one neighbour, then that neighbour’s first neighbour, and so on until it hits a dead end, then backs up to the most recent place with an unexplored option. Written recursively, the call stack does the remembering:

def dfs(graph, start):
    visited, order = set(), []
    def visit(node):
        visited.add(node)
        order.append(node)
        for nxt in graph[node]:
            if nxt not in visited:
                visit(nxt)             # go deep before trying the next neighbour
    visit(start)
    return order

def dfs_stack(graph, start):
    visited, order = set(), []
    stack = [start]
    while stack:
        node = stack.pop()             # newest first: keep going deeper
        if node in visited:
            continue                   # pushed twice, already handled
        visited.add(node)
        order.append(node)
        for nxt in reversed(graph[node]):   # reversed, so the first neighbour pops first
            if nxt not in visited:
                stack.append(nxt)
    return order

print(dfs(friends, "ali"))
print(dfs_stack(friends, "ali"))
# ['ali', 'ben', 'chen', 'dina', 'fatin', 'eli', 'gita']
# ['ali', 'ben', 'chen', 'dina', 'fatin', 'eli', 'gita']

Same order both ways. The stack version marks nodes when they’re popped and skips stale copies, which is what makes its order match the recursive one. If you mark on push instead (the BFS habit), you still visit everything, but in a slightly different order that isn’t a true depth-first order, and that matters for the algorithms below that depend on when a node finishes.

Compare the order with BFS. BFS from Ali visited ben, chen, then eli and dina (distance 2). DFS went ali, ben, chen, dina, fatin: one long chain, as far as it could go. DFS paths are valid paths, but nothing makes them short.

That’s easier to see than to read. In the maze below, step through BFS and watch the numbered cells spread out in rings from S. Then switch to DFS on the same walls and watch it pick a direction and keep going.

On the default walls BFS expands 46 cells and returns the 16-move shortest path. DFS gets to the goal sooner, after 27 cells, but by a 26-move route, because it prefers going up and commits to the first corridor it finds. Neither is “faster” in general. BFS is guaranteed shortest in hops. DFS uses less memory on wide graphs (its frontier is one path plus the siblings along it, while BFS holds an entire ring), and its structure, entering and finishing nodes in nested order, is what cycle detection and topological sort are built on.

The visited set, and what happens without it

Forget the visited check and BFS runs forever on any graph with a cycle. Here it is with a safety cap, so the program actually stops:

from collections import deque

loop = {"a": ["b"], "b": ["c"], "c": ["a"]}      # a -> b -> c -> a

def bfs_forgetful(graph, start, max_steps=10):
    queue, seen_order = deque([start]), []
    while queue and len(seen_order) < max_steps:  # the cap is the only thing that stops it
        node = queue.popleft()
        seen_order.append(node)
        queue.extend(graph[node])                 # no visited check
    return seen_order

print(bfs_forgetful(loop, "a"))

square = {"a": ["b", "c"], "b": ["a", "d"], "c": ["a", "d"], "d": ["b", "c"]}
print(len(bfs_forgetful(square, "a", max_steps=1000)), "pops for a 4-node graph, and the queue still isn't empty")
# ['a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', 'a']
# 1000 pops for a 4-node graph, and the queue still isn't empty

A three-node loop goes round forever. The four-node square is worse: every undirected edge is a two-node cycle (a to b and straight back), so the queue doubles in size every ring. Undirected graphs always need the visited set, even when they “have no cycles”, because every edge is a way back.

The visited set is the reason graph traversal is cheap. Each node is added to the frontier at most once, and each node’s neighbour list is read at most once.

What BFS and DFS cost: O(V + E)

Count the work. Every node enters and leaves the frontier once: that’s V operations. When a node leaves, its neighbour list is scanned once. Across the whole run, that’s the sum of all neighbour-list lengths, which is E for a directed graph and 2E for an undirected one (each edge appears in two lists). Each neighbour check is one set lookup, O(1) on average. Total: O(V + E) time. The visited set and frontier hold at most V entries: O(V) extra space.

O(V + E) is “linear in the size of the graph”: the cost of reading the input once. You can’t do fundamentally better, since you have to look at the graph to search it. Here’s the edge count on random graphs, timed on my laptop:

import random, time
from collections import deque

def bfs_count(graph, start):
    seen = {start}
    queue = deque([start])
    edge_checks = 0
    while queue:
        v = queue.popleft()
        for nxt in graph[v]:
            edge_checks += 1
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)
    return len(seen), edge_checks

random.seed(1)
for n in (100_000, 200_000, 400_000):
    graph = {v: [] for v in range(n)}
    for _ in range(3 * n):                     # E = 3V undirected edges
        a, b = random.randrange(n), random.randrange(n)
        graph[a].append(b)
        graph[b].append(a)
    start = time.perf_counter()
    nodes, checks = bfs_count(graph, 0)
    ms = (time.perf_counter() - start) * 1000
    print(f"V={n:>7,}  reached {nodes:>7,}  edge checks {checks:>9,}  {ms:6.0f} ms")
# V=100,000  reached  99,733  edge checks   600,000     129 ms
# V=200,000  reached 199,471  edge checks 1,199,990     357 ms
# V=400,000  reached 399,011  edge checks 2,399,988     824 ms

The work doubles exactly with the graph: 2E edge checks, every time. The clock grows a little faster than double, because a bigger graph fits worse in the CPU’s caches and every hop to a random neighbour is a likely cache miss. That gap between “operations” and “time” is the honest caveat on every Big-O claim: the count is exact, the constant isn’t.

Connected components: how many separate groups?

To count groups, start a traversal from every node that hasn’t been visited yet. Each new start is a new component.

def components(graph):
    seen, groups = set(), []
    for start in graph:                # try every node as a starting point
        if start in seen:
            continue
        group, stack = [], [start]
        seen.add(start)
        while stack:
            node = stack.pop()
            group.append(node)
            for nxt in graph[node]:
                if nxt not in seen:
                    seen.add(nxt)
                    stack.append(nxt)
        groups.append(sorted(group))
    return groups

people = {
    "ali": ["ben"], "ben": ["ali", "chen"], "chen": ["ben"],
    "dina": ["eli"], "eli": ["dina"],
    "fatin": [],
}
print(components(people))
# [['ali', 'ben', 'chen'], ['dina', 'eli'], ['fatin']]

Still O(V + E) in total, not once per component: the seen set is shared across all the starts, so every node is explored exactly once. This traversal marks on push, which is fine here because the order inside a group doesn’t matter. Use whichever search you like for components; I’d default to an explicit stack, for a reason that shows up in Advanced (recursion depth).

Grids are graphs

A grid of cells is a graph where each cell is a node and the edges go to its up, down, left and right neighbours. You never build an adjacency list; you compute neighbours on the fly. Number of islands is connected components on that implicit graph: count the land cells that start a new flood.

from collections import deque

def neighbours(grid, r, c):
    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):   # up, down, left, right
        nr, nc = r + dr, c + dc
        if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]):
            yield nr, nc

def count_islands(grid):
    seen = set()
    islands = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == "1" and (r, c) not in seen:
                islands += 1                       # a new island: flood all of it
                seen.add((r, c))
                queue = deque([(r, c)])
                while queue:
                    cell = queue.popleft()
                    for nr, nc in neighbours(grid, *cell):
                        if grid[nr][nc] == "1" and (nr, nc) not in seen:
                            seen.add((nr, nc))
                            queue.append((nr, nc))
    return islands

sea = [
    "11000",
    "11010",
    "00011",
    "10000",
]
print(count_islands(sea))

def flood_fill(image, r, c, colour):
    old = image[r][c]
    if old == colour:
        return image                               # nothing to do, and no infinite loop
    stack = [(r, c)]
    while stack:
        r, c = stack.pop()
        if image[r][c] != old:
            continue
        image[r][c] = colour                       # recolouring doubles as "visited"
        stack.extend(neighbours(image, r, c))
    return image

pic = [[1, 1, 0], [1, 0, 0], [1, 1, 1]]
print(flood_fill(pic, 0, 0, 7))
# 3
# [[7, 7, 0], [7, 0, 0], [7, 7, 7]]

Flood fill is the paint bucket in an image editor: recolour every cell connected to the clicked one. It needs no visited set, because recolouring a cell is marking it. The early return when the new colour equals the old one isn’t a micro-optimization. Without it, a recoloured cell still matches old, so the fill keeps re-adding the same cells and never ends.

Cycles in an undirected graph

In an undirected graph, a traversal finds a cycle when it reaches a node it has already seen by some route other than the edge it just walked. The “other than” matters: every undirected edge leads straight back to where you came from, and that’s not a cycle.

def has_cycle_undirected(graph):
    seen = set()
    for start in graph:
        if start in seen:
            continue
        seen.add(start)
        stack = [(start, None)]                 # (node, the node we came from)
        while stack:
            node, came_from = stack.pop()
            for nxt in graph[node]:
                if nxt == came_from:
                    continue                    # the edge we just walked, not a loop
                if nxt in seen:
                    return True                 # reached an old node another way
                seen.add(nxt)
                stack.append((nxt, node))
    return False

line = {"a": ["b"], "b": ["a", "c"], "c": ["b"]}
triangle = {"a": ["b", "c"], "b": ["a", "c"], "c": ["a", "b"]}
print(has_cycle_undirected(line), has_cycle_undirected(triangle))
# False True

(This skips the edge back to the parent by node, so it treats two parallel edges between the same pair as one. For simple graphs that’s what you want. Union-find, in Advanced, is the other standard tool here and handles a stream of edges more naturally.)

Cycles in a directed graph: three colours

Directed graphs need more care. In the diamond on the left below, d is reached twice, through b and through c, but there’s no cycle: arrows only point downward. “Reached a seen node” isn’t enough. What signals a cycle is reaching a node that is still on the current DFS path, because that means you can follow arrows from it, down to where you are, and back to it.

So DFS tracks three states per node: white (not started), grey (started, still on the path, some neighbours unexplored) and black (finished: every route out of it has been explored). An edge to a black node is harmless. An edge to a grey node is a back edge, and a back edge means a cycle.

WHITE, GREY, BLACK = 0, 1, 2       # not started, on the current path, finished

def find_cycle(graph):
    colour = {v: WHITE for v in graph}
    path = []
    def visit(node):
        colour[node] = GREY
        path.append(node)
        for nxt in graph[node]:
            if colour[nxt] == GREY:                 # back on our own path: a cycle
                return path[path.index(nxt):] + [nxt]
            if colour[nxt] == WHITE:
                found = visit(nxt)
                if found:
                    return found
        colour[node] = BLACK                        # every route from here is done
        path.pop()
        return None
    for v in graph:
        if colour[v] == WHITE:
            found = visit(v)
            if found:
                return found
    return None

diamond = {"a": ["b", "c"], "b": ["d"], "c": ["d"], "d": []}    # d reached twice, no cycle
looped = {"a": ["b"], "b": ["c"], "c": ["d", "a"], "d": []}
print(find_cycle(diamond))
print(find_cycle(looped))
# None
# ['a', 'b', 'c', 'a']

Returning the cycle instead of True costs one slice and makes the error message useful. “Your build has a cycle” is a bad error. “a needs b needs c needs a” tells someone which line to delete.

Topological sort: an order where every arrow points forward

Given tasks and “must happen before” arrows, a topological order is a list of all the tasks in which every arrow points forward: each task comes after everything it depends on. It exists exactly when the graph has no cycles, which makes topological sort a cycle detector and a scheduler at once.

Kahn’s algorithm (Arthur Kahn, 1962) is the intuitive version. Count each node’s in-degree: how many things must happen before it. Everything at zero is ready. Take a ready node, put it in the output, and subtract one from each node it points to. Anything that reaches zero becomes ready. Repeat.

from collections import deque

# task -> the tasks that can only start after it
deploy = {
    "write code": ["run tests"],
    "run tests": ["build image"],
    "migrate db": ["deploy"],
    "build image": ["deploy"],
    "deploy": ["smoke test"],
    "smoke test": [],
}

def kahn(graph):
    indegree = {v: 0 for v in graph}
    for v in graph:
        for nxt in graph[v]:
            indegree[nxt] += 1                    # how many things must happen first
    ready = deque(v for v in graph if indegree[v] == 0)
    order = []
    while ready:
        v = ready.popleft()
        order.append(v)
        for nxt in graph[v]:
            indegree[nxt] -= 1                    # one prerequisite done
            if indegree[nxt] == 0:
                ready.append(nxt)
    if len(order) < len(graph):
        stuck = sorted(v for v in graph if indegree[v] > 0)
        raise ValueError(f"cycle: these never became ready: {stuck}")
    return order

print(kahn(deploy))
deploy["smoke test"].append("write code")         # now everything waits on everything
try:
    kahn(deploy)
except ValueError as e:
    print(e)
# ['write code', 'migrate db', 'run tests', 'build image', 'deploy', 'smoke test']
# cycle: these never became ready: ['build image', 'deploy', 'run tests', 'smoke test', 'write code']

If there’s a cycle, the nodes on it wait for each other forever, their counts never reach zero, and the ready queue empties early. That’s the detection: fewer nodes out than went in. Notice what Kahn’s algorithm reports, though: everything that’s stuck, not the cycle itself. Nodes downstream of a cycle are stuck too, without being part of it. Watch that happen below. The graph is a simplified slice of this site’s own study links (an arrow means “read this first”):

With the extra arrow, Big-O, Hash maps and Graphs come out and then the queue is empty. Two pointers and Sliding window wait for each other. Rate limiter isn’t in the loop at all; it’s stuck behind it. When you need the actual loop for an error message, run the three-colour DFS on the stuck nodes.

The DFS version of topological sort uses finishing order. A node finishes (turns black) only after everything reachable from it has finished. So if you append each node to a list as it finishes, every node appears after everything that depends on it, and reversing the list gives a valid order. Python’s standard library also has one, graphlib.TopologicalSorter (since 3.9), which takes the arrows the other way round: each node maps to the nodes it depends on.

deploy = {
    "write code": ["run tests"],
    "run tests": ["build image"],
    "migrate db": ["deploy"],
    "build image": ["deploy"],
    "deploy": ["smoke test"],
    "smoke test": [],
}

def topo_dfs(graph):
    done, order = set(), []
    def visit(v):
        done.add(v)
        for nxt in graph[v]:
            if nxt not in done:
                visit(nxt)
        order.append(v)            # appended only after everything that depends on it
    for v in graph:
        if v not in done:
            visit(v)
    return order[::-1]             # reverse postorder

print(topo_dfs(deploy))

from graphlib import TopologicalSorter, CycleError

# graphlib wants the other direction: node -> the nodes it depends on
needs = {"run tests": {"write code"}, "build image": {"run tests"},
         "deploy": {"build image", "migrate db"}, "smoke test": {"deploy"}}
print(list(TopologicalSorter(needs).static_order()))
needs["write code"] = {"smoke test"}
try:
    list(TopologicalSorter(needs).static_order())
except CycleError as e:
    print("CycleError:", e.args[1])
# ['migrate db', 'write code', 'run tests', 'build image', 'deploy', 'smoke test']
# ['write code', 'migrate db', 'run tests', 'build image', 'deploy', 'smoke test']
# CycleError: ['run tests', 'build image', 'deploy', 'smoke test', 'write code', 'run tests']

Three different valid orders for the same graph. Topological orders are rarely unique: migrate db can go anywhere before deploy. If you need a deterministic order (for a reproducible build, or a test that compares output), break ties explicitly, for example by sorting the ready queue. topo_dfs above skips the grey check for brevity, so on a cyclic graph it returns an order without complaint; combine it with the three colours when the input isn’t trusted. graphlib checks for you and reports the cycle itself, which is why I’d reach for it whenever I don’t need to step through the algorithm.

Which one do I pick? Kahn’s when I want waves: everything in the ready queue at the same moment can run in parallel, which is exactly what a build or task scheduler needs (there’s an exercise on this in Expert). DFS when I’m already doing a DFS for another reason. graphlib for everything else. It even has a prepare() / get_ready() / done() interface built for running tasks in parallel.

Bipartite: can the nodes be split into two sides?

A graph is bipartite if its nodes can be coloured with two colours so that every edge joins different colours: students and courses, buyers and products, two teams where nobody wants a rival on their own side. BFS checks it in one pass. Colour the start 0, every neighbour 1, their neighbours 0, and so on. If an edge ever joins two nodes of the same colour, it’s impossible.

from collections import deque

def two_colour(graph):
    side = {}
    for start in graph:
        if start in side:
            continue
        side[start] = 0
        queue = deque([start])
        while queue:
            v = queue.popleft()
            for nxt in graph[v]:
                if nxt not in side:
                    side[nxt] = 1 - side[v]          # neighbours go on the other side
                    queue.append(nxt)
                elif side[nxt] == side[v]:
                    return None                      # an edge inside one side: impossible
    return side

square = {"a": ["b", "d"], "b": ["a", "c"], "c": ["b", "d"], "d": ["c", "a"]}
triangle = {"a": ["b", "c"], "b": ["a", "c"], "c": ["a", "b"]}
print(two_colour(square))
print(two_colour(triangle))
# {'a': 0, 'b': 1, 'd': 1, 'c': 0}
# None

A graph is bipartite exactly when it has no cycle of odd length. The square (length 4) splits fine; the triangle (length 3) can’t. The colouring is also the proof: when the function returns a dictionary, you can check every edge against it.

from collections import deque

def course_order(n, prerequisites):
    after = [[] for _ in range(n)]        # course -> courses that need it
    indegree = [0] * n
    for course, needs in prerequisites:
        after[needs].append(course)
        indegree[course] += 1
    ready = deque(c for c in range(n) if indegree[c] == 0)
    order = []
    while ready:
        c = ready.popleft()
        order.append(c)
        for nxt in after[c]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                ready.append(nxt)
    return order if len(order) == n else []

print(course_order(2, [(1, 0)]))
print(course_order(4, [(1, 0), (2, 0), (3, 1), (3, 2)]))
print(course_order(2, [(1, 0), (0, 1)]))
print(course_order(3, []))
# [0, 1]
# [0, 1, 2, 3]
# []
# [0, 1, 2]

from collections import defaultdict, deque

def ladder_length(begin, end, words):
    words = set(words)
    if end not in words:
        return 0
    # Bucket words by pattern: "hot" sits in "*ot", "h*t" and "ho*".
    buckets = defaultdict(list)
    for w in words | {begin}:
        for i in range(len(w)):
            buckets[w[:i] + "*" + w[i + 1:]].append(w)
    seen = {begin}
    queue = deque([(begin, 1)])
    while queue:
        word, length = queue.popleft()
        if word == end:
            return length
        for i in range(len(word)):
            for nxt in buckets[word[:i] + "*" + word[i + 1:]]:
                if nxt not in seen:
                    seen.add(nxt)
                    queue.append((nxt, length + 1))
    return 0

words = ["hot", "dot", "dog", "lot", "log", "cog"]
print(ladder_length("hit", "cog", words))
print(ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log"]))
# 5
# 0

from collections import deque

def minutes_to_rot(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))       # every rotten orange starts at minute 0
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue:
        r, c, t = queue.popleft()
        minutes = max(minutes, t)
        for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2               # rotting it is marking it visited
                fresh -= 1
                queue.append((nr, nc, t + 1))
    return minutes if fresh == 0 else -1

print(minutes_to_rot([[2, 1, 1], [1, 1, 0], [0, 1, 1]]))
print(minutes_to_rot([[2, 1, 1], [0, 1, 1], [1, 0, 1]]))
print(minutes_to_rot([[0, 2]]))
# 4
# -1
# 0

from collections import deque

class Node:
    def __init__(self, val, neighbors=None):
        self.val = val
        self.neighbors = neighbors or []

def clone_graph(node):
    if node is None:
        return None
    copies = {node: Node(node.val)}       # original -> its copy; also the visited set
    queue = deque([node])
    while queue:
        cur = queue.popleft()
        for nb in cur.neighbors:
            if nb not in copies:
                copies[nb] = Node(nb.val)
                queue.append(nb)
            copies[cur].neighbors.append(copies[nb])
    return copies[node]

# The square 1-2-3-4-1.
a, b, c, d = Node(1), Node(2), Node(3), Node(4)
a.neighbors, b.neighbors, c.neighbors, d.neighbors = [b, d], [a, c], [b, d], [c, a]
copy = clone_graph(a)
print(copy.val, [n.val for n in copy.neighbors], copy is a)
print(copy.neighbors[0].neighbors[0] is copy)     # the copy points at the copy, not the original
# 1 [2, 4] False
# True

Advanced: weights, merges, deep recursion and graphs you never build

Dijkstra: shortest paths when edges have weights

BFS counts edges. On a road map, three short roads can beat one long one, so “fewest edges” is the wrong question. Dijkstra’s algorithm (Edsger Dijkstra, 1959) answers the right one for graphs whose weights are zero or positive. It’s BFS with the queue replaced by a priority queue: instead of the oldest node, always expand the node with the smallest known distance so far.

import heapq

roads = {
    "KL":     {"Ipoh": 205, "Melaka": 145, "Kuantan": 250},
    "Ipoh":   {"KL": 205, "Penang": 165},
    "Melaka": {"KL": 145, "JB": 225},
    "Kuantan": {"KL": 250, "JB": 320},
    "Penang": {"Ipoh": 165},
    "JB":     {"Melaka": 225, "Kuantan": 320},
}

def dijkstra(graph, start):
    dist = {start: 0}
    parent = {start: None}
    heap = [(0, start)]                    # (distance so far, node), smallest first
    done = set()
    while heap:
        d, node = heapq.heappop(heap)
        if node in done:
            continue                       # a stale, longer entry: skip it
        done.add(node)                     # d is now final for this node
        for nxt, km in graph[node].items():
            new = d + km
            if new < dist.get(nxt, float("inf")):
                dist[nxt] = new
                parent[nxt] = node
                heapq.heappush(heap, (new, nxt))
    return dist, parent

dist, parent = dijkstra(roads, "Penang")
print(dist)
node, path = "JB", []
while node:
    path.append(node)
    node = parent[node]
print(" -> ".join(reversed(path)), dist["JB"], "km")
# {'Penang': 0, 'Ipoh': 165, 'KL': 370, 'Melaka': 515, 'Kuantan': 620, 'JB': 740}
# Penang -> Ipoh -> KL -> Melaka -> JB 740 km

heapq is a binary heap: push and pop cost O(log n). Python’s heap has no “decrease this key” operation, so when a shorter route to a node turns up, the code pushes a second entry and skips the stale one when it surfaces (the done check). That’s called lazy deletion, and it’s how almost everyone writes Dijkstra in Python. The heap can hold up to E entries, so the cost is O((V + E) log V): every edge may cause one push, every push and pop is a logarithm. The heaps article covers the heap itself, and the tip below links to it.

Why Dijkstra fails on negative edges

Dijkstra’s correctness rests on one claim: when a node comes off the heap with distance d, no later discovery can beat d. With non-negative weights that’s true. Any other route to the node goes through something still on the heap, which is already at least d away, and adding edges can only make it longer. A negative edge breaks the claim: a route through a far-away node can come back cheaper.

import heapq

def dijkstra(graph, start):
    dist, done, heap = {start: 0}, set(), [(0, start)]
    while heap:
        d, node = heapq.heappop(heap)
        if node in done:
            continue
        done.add(node)
        for nxt, w in graph[node].items():
            if nxt not in done and d + w < dist.get(nxt, float("inf")):
                dist[nxt] = d + w
                heapq.heappush(heap, (d + w, nxt))
    return dist

def bellman_ford(graph, start):
    dist = {v: float("inf") for v in graph}
    dist[start] = 0
    for _ in range(len(graph) - 1):         # V - 1 rounds of relaxing every edge
        for v in graph:
            for nxt, w in graph[v].items():
                if dist[v] + w < dist[nxt]:
                    dist[nxt] = dist[v] + w
    for v in graph:                          # one more round: any improvement means a negative cycle
        for nxt, w in graph[v].items():
            if dist[v] + w < dist[nxt]:
                raise ValueError("negative cycle")
    return dist

# A cashback that makes the long way cheaper.
g = {"S": {"A": 2, "B": 5}, "A": {"C": 2}, "B": {"A": -4}, "C": {}}
print("dijkstra:    ", dijkstra(g, "S"))
print("bellman-ford:", bellman_ford(g, "S"))
# dijkstra:     {'S': 0, 'A': 2, 'B': 5, 'C': 4}
# bellman-ford: {'S': 0, 'A': 1, 'B': 5, 'C': 3}

Dijkstra didn’t crash. It returned wrong numbers with total confidence, which is the worst kind of failure. Bellman-Ford is the standard fix: relax every edge V − 1 times, because a shortest path without cycles has at most V − 1 edges. It costs O(V × E) instead of O((V + E) log V), and it can detect a negative cycle (a loop whose total weight is negative, where “shortest” stops meaning anything because you can go round forever). In practice, negative weights mostly appear when a graph models money or log-probabilities; currency arbitrage detection is literally a search for a negative cycle.

Union-find: who is in the same group?

Sometimes the graph arrives as a stream of “these two belong together” facts, and the only question you ever ask is “are x and y in the same group?” Re-running BFS after every new edge would cost O(V + E) each time. A disjoint-set union, or union-find, answers both operations in almost constant time.

Each group is a tree of parent pointers. Every element points at a parent; the root points at itself and is the group’s representative. find(x) climbs to the root. union(a, b) finds both roots and, if they differ, points one at the other.

class DisjointSet:
    def __init__(self):
        self.parent = {}
        self.rank = {}

    def find(self, x):
        self.parent.setdefault(x, x)
        self.rank.setdefault(x, 0)
        root = x
        while self.parent[root] != root:       # climb to the representative
            root = self.parent[root]
        while self.parent[x] != root:          # path compression: point everyone at it
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                       # already one group: this edge closes a cycle
        if self.rank[ra] < self.rank[rb]:      # union by rank: short tree under tall tree
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

ds = DisjointSet()
for a, b in [("ali", "ben"), ("chen", "dina"), ("ben", "dina"), ("eli", "fatin")]:
    ds.union(a, b)
print(ds.find("ali") == ds.find("chen"), ds.find("ali") == ds.find("eli"))
print(ds.union("ali", "chen"))                 # same group already
groups = {}
for person in ds.parent:
    groups.setdefault(ds.find(person), []).append(person)
print(sorted(groups.values()))
# True False
# False
# [['ali', 'ben', 'chen', 'dina'], ['eli', 'fatin']]

Two tricks make it fast, and they’re the whole point. Union by rank always hangs the shorter tree under the taller one, so trees stay shallow (the height is at most log₂ V). Path compression makes every node visited by find point straight at the root, so the next find from any of them is one hop.

Here’s how much each trick buys, counting parent hops on the worst input for the naive version (a long chain built one union at a time), measured on my laptop:

import random, time

def run(n, compress, by_rank, ops):
    parent = list(range(n))
    rank = [0] * n
    hops = 0
    def find(x):
        nonlocal hops
        root = x
        while parent[root] != root:
            root = parent[root]
            hops += 1
        if compress:
            while parent[x] != root:
                parent[x], x = root, parent[x]
        return root
    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb:
            return
        if by_rank:
            if rank[ra] < rank[rb]:
                ra, rb = rb, ra
            parent[rb] = ra
            if rank[ra] == rank[rb]:
                rank[ra] += 1
        else:
            parent[ra] = rb            # naive: whatever order the call came in
    start = time.perf_counter()
    for kind, a, b in ops:
        if kind == "u":
            union(a, b)
        else:
            find(a)
    return hops, time.perf_counter() - start

n = 5_000
random.seed(3)
# Worst case for the naive version: union(0,1), union(0,2), ... builds one long chain.
ops = [("u", 0, i) for i in range(1, n)] + [("f", random.randrange(n), 0) for _ in range(n)]
for name, c, r in [("naive", False, False), ("rank only", False, True),
                   ("compression only", True, False), ("both", True, True)]:
    hops, s = run(n, c, r, ops)
    print(f"{name:<17} {hops:>12,} parent hops  {s * 1000:8.1f} ms")
# naive               24,900,614 parent hops    1006.4 ms
# rank only                4,998 parent hops       1.7 ms
# compression only        19,991 parent hops       2.7 ms
# both                     4,998 parent hops       2.0 ms

Five thousand elements and the naive version already does 25 million hops: the chain makes every operation O(n), so the whole run is O(n²). Either trick alone fixes this input. Together they give a guarantee for every input: Robert Tarjan proved in 1975 that m operations cost O(m α(n)), where α is the inverse Ackermann function, which is at most 4 for any n you could store in this universe. People call it “effectively constant”, and that’s fair.

Union-find is the engine of Kruskal’s algorithm for minimum spanning trees (sort edges by weight, add each one unless it joins two nodes already in the same group), of “accounts merge” style problems, and of anything that groups records as evidence arrives. It has one big limitation: it can only merge. There is no efficient “split this group again”. When groups must also come apart, you’re back to storing the edges and re-running a traversal, or to much more complex dynamic-connectivity structures. The production section has a real merge with exactly this one-way shape.

Python’s recursion limit, and turning DFS into a loop

Recursive DFS is the clearest way to write it, and in Python it has a hard ceiling. CPython limits how deep recursion goes, by default to 1,000 frames, and a DFS down a long path needs one frame per node on the path.

import sys

print(sys.getrecursionlimit())

chain = {i: [i + 1] for i in range(5_000)}       # 0 -> 1 -> 2 -> ... -> 5000
chain[5_000] = []

def topo_recursive(graph):
    done, order = set(), []
    def visit(v):
        done.add(v)
        for nxt in graph[v]:
            if nxt not in done:
                visit(nxt)
        order.append(v)
    for v in graph:
        if v not in done:
            visit(v)
    return order[::-1]

try:
    topo_recursive(chain)
except RecursionError as e:
    print("RecursionError:", e)

def topo_iterative(graph):
    done, order = set(), []
    for root in graph:
        if root in done:
            continue
        done.add(root)
        stack = [(root, iter(graph[root]))]       # a node and where we are in its neighbours
        while stack:
            v, neighbours = stack[-1]
            for nxt in neighbours:
                if nxt not in done:
                    done.add(nxt)
                    stack.append((nxt, iter(graph[nxt])))
                    break                         # descend; resume v's iterator later
            else:
                stack.pop()                       # all neighbours finished: v is finished
                order.append(v)
    return order[::-1]

order = topo_iterative(chain)
print(len(order), order[:3], order[-1])
# 1000
# RecursionError: maximum recursion depth exceeded
# 5001 [0, 1, 2] 5000

A dependency chain 5,000 long is not exotic: a linked list of records, a long comment thread, a big package tree. You can raise the limit with sys.setrecursionlimit, but that only moves the ceiling, and set it too high and the interpreter can crash outright instead of raising a clean error. Convert to an explicit stack whenever the depth depends on the data.

The conversion has one subtlety. For a simple “visit everything” DFS, pushing neighbours on a list is enough (you saw dfs_stack in Intermediate). But topological sort and cycle detection need to know when a node finishes, after all its neighbours. The trick above is to push a (node, iterator over its neighbours) pair. Each pass resumes the iterator where it left off; when it’s exhausted, the node is finished. That’s precisely what the recursive version’s call stack was storing: which node, and how far through its loop it had got. Airflow’s DAG cycle check, which you’ll see in Expert, uses the same explicit-stack idea.

Implicit graphs: states as nodes

Some of the most useful graphs are never stored. The nodes are states of a puzzle or a system, and the edges are the moves between them, generated on demand. A combination lock with four wheels has 10,000 states, and each one has eight neighbours (turn any wheel one click either way). “Fewest turns to open it, avoiding some forbidden combinations” is a BFS over that graph:

from collections import deque

def turns(code):
    """Every combination one wheel-click away: 8 neighbours, generated on demand."""
    for i in range(4):
        d = int(code[i])
        for step in (1, -1):
            yield code[:i] + str((d + step) % 10) + code[i + 1:]

def open_lock(deadends, target):
    blocked = set(deadends)
    if "0000" in blocked:
        return -1
    seen = {"0000"}
    queue = deque([("0000", 0)])
    while queue:
        code, moves = queue.popleft()
        if code == target:
            return moves, len(seen)
        for nxt in turns(code):
            if nxt not in seen and nxt not in blocked:
                seen.add(nxt)
                queue.append((nxt, moves + 1))
    return -1

print(open_lock(["0201", "0101", "0102", "1212", "2002"], "0202"))
print(open_lock([], "5555"))
# (6, 1506)
# (20, 10000)

The neighbour function replaced the adjacency list. Everything else is the BFS you already know. This is how you think about puzzles (sliding tiles, Rubik’s cube), about state machines (is this order state reachable from that one?), about word ladders, and about model checking, where tools explore every reachable state of a concurrent program looking for a bad one. The catch is size: implicit graphs are often astronomically large, and the visited set is what runs out first. The second call above had to see all 10,000 states to reach a target 20 moves away.

Bidirectional BFS: search from both ends

When you know both the start and the goal, you can run two BFS searches, one from each end, and stop when they meet. If each node has b neighbours and the answer is d moves away, one search sees about bᵈ states; two searches that meet in the middle each go d/2 deep, for about 2 × b^(d/2). With exponents, halving the depth is an enormous saving. Counting the codes each method looks at:

from collections import deque

def turns(code):
    for i in range(len(code)):
        d = int(code[i])
        for step in (1, -1):
            yield code[:i] + str((d + step) % 10) + code[i + 1:]

def one_way(start, goal):
    seen = {start}
    queue = deque([(start, 0)])
    while queue:
        code, moves = queue.popleft()
        if code == goal:
            return moves, len(seen)
        for nxt in turns(code):
            if nxt not in seen:
                seen.add(nxt)
                queue.append((nxt, moves + 1))

def two_way(start, goal):
    if start == goal:
        return 0, 1
    dist_a, dist_b = {start: 0}, {goal: 0}
    front_a, front_b = [start], [goal]
    while front_a and front_b:
        if len(front_a) > len(front_b):            # always grow the smaller side
            front_a, front_b, dist_a, dist_b = front_b, front_a, dist_b, dist_a
        next_front, best = [], None
        for code in front_a:                       # expand one whole level
            for nxt in turns(code):
                if nxt in dist_b:                  # the two searches touched
                    total = dist_a[code] + 1 + dist_b[nxt]
                    best = total if best is None else min(best, total)
                if nxt not in dist_a:
                    dist_a[nxt] = dist_a[code] + 1
                    next_front.append(nxt)
        if best is not None:
            return best, len(dist_a) + len(dist_b)
        front_a = next_front

for start, goal in (("0000", "2222"), ("0000", "5555"), ("000000", "222222"), ("000000", "333333")):
    (m1, s1), (m2, s2) = one_way(start, goal), two_way(start, goal)
    assert m1 == m2                                # same answer, different amount of work
    print(f"{start} -> {goal}: {m1:>2} moves; one-way saw {s1:>7,} codes, bidirectional {s2:>6,}")
# 0000 -> 2222:  8 moves; one-way saw   3,467 codes, bidirectional    642
# 0000 -> 5555: 20 moves; one-way saw  10,000 codes, bidirectional 11,286
# 000000 -> 222222: 12 moves; one-way saw 275,502 codes, bidirectional 17,822
# 000000 -> 333333: 18 moves; one-way saw 848,606 codes, bidirectional 135,566

Look at the second line, because it’s the honest one. When the target is as far away as anything in a small graph, both methods end up seeing everything, and bidirectional search is slightly worse: each side counts some codes the other also saw. The win appears when the graph is much bigger than the part you need, as with six wheels: 15 times fewer codes for a 12-move answer. Two implementation details matter. Expand a whole level before checking for the meeting, and take the minimum over that level; stopping at the first touch can return a path one move too long. And always grow the smaller frontier, which keeps the two halves balanced when one side branches more than the other.

Reversing the edges: who depends on me?

Earlier, “what leads into deploy?” needed a scan of every list. When you ask that kind of question often, build the reverse graph once: the same nodes with every edge flipped. Then “what depends on X, directly or indirectly?” is an ordinary BFS on the reverse graph.

from collections import deque

# page -> the records it is built from
built_from = {
    "home": ["product:7", "banner"],
    "product page": ["product:7", "price:7"],
    "category page": ["product page", "product:9"],
    "sitemap": ["category page"],
}

def reverse(graph):
    rev = {}
    for v, outs in graph.items():
        rev.setdefault(v, [])
        for w in outs:
            rev.setdefault(w, []).append(v)    # flip every edge
    return rev

used_by = reverse(built_from)

def affected(changed):
    seen, queue = {changed}, deque([changed])
    while queue:
        for page in used_by[queue.popleft()]:
            if page not in seen:
                seen.add(page)
                queue.append(page)
    return sorted(seen - {changed})

print(used_by["price:7"])
print(affected("price:7"))
print(affected("banner"))
# ['product page']
# ['category page', 'product page', 'sitemap']
# ['home']

Change a price and three cached pages are stale, including the sitemap, two hops away. This is how incremental builds decide what to rebuild after a file changes, how spreadsheets decide which cells to recalculate, and how a cache with derived entries decides what to throw away.

import heapq

def network_delay(times, n, k):
    graph = {v: [] for v in range(1, n + 1)}
    for u, v, w in times:
        graph[u].append((v, w))
    dist = {}
    heap = [(0, k)]
    while heap:
        d, node = heapq.heappop(heap)
        if node in dist:
            continue                       # first pop is the shortest
        dist[node] = d
        for nxt, w in graph[node]:
            if nxt not in dist:
                heapq.heappush(heap, (d + w, nxt))
    return max(dist.values()) if len(dist) == n else -1

print(network_delay([(2, 1, 1), (2, 3, 1), (3, 4, 1)], 4, 2))
print(network_delay([(1, 2, 1)], 2, 2))
print(network_delay([(1, 2, 4), (1, 3, 1), (3, 2, 1)], 3, 1))
# 2
# -1
# 2

def redundant_connection(edges):
    parent = list(range(len(edges) + 1))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path halving: a cheaper form of compression
            x = parent[x]
        return x
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra == rb:
            return [a, b]                  # both ends already connected: this edge makes the loop
        parent[ra] = rb
    return None

print(redundant_connection([(1, 2), (1, 3), (2, 3)]))
print(redundant_connection([(1, 2), (2, 3), (3, 4), (1, 4), (1, 5)]))
# [2, 3]
# [1, 4]

Expert: graphs inside backend systems

At this level the algorithms are the easy part. The questions are about what the graph means in a running system: who builds it, how big it gets, what happens when it changes underneath you, and where it should be stored.

Dependency resolution: package managers and build systems

A package manager resolving dependencies does two separate graph jobs, and only one of them is easy.

The easy one is ordering. Once the exact versions are chosen, installing them is a topological sort: install each package after the packages it needs. Build systems are the same shape with files instead of packages. Make, Bazel and their relatives model targets as nodes and “needs” as edges, build in topological order, and run independent targets in parallel (Kahn’s waves). An incremental build is the reverse-graph trick from Advanced: from the files that changed, walk the reverse edges and rebuild only what’s reachable.

The hard job is choosing versions. “A needs B at least 2.0, C needs B below 2.0, and both A and C are needed” is a constraint problem, not a traversal. Russ Cox showed in 2016 (“Version SAT”) that dependency resolution with version ranges and conflicts is NP-complete: any SAT problem can be encoded as a set of packages. Real resolvers survive with heuristics and backtracking. pip has used a backtracking resolver by default since version 20.3 in 2020. Go took the other road and changed the rules so the problem becomes easy: minimal version selection picks the lowest version that satisfies every stated minimum, which a simple graph walk can compute. When a design review proposes “just resolve the dependency graph”, ask which of the two problems they mean.

DAG schedulers: Airflow and Celery canvas

Workflow tools turn a DAG into running work. In Apache Airflow, a DAG is a Python file declaring tasks and their order (extract >> transform >> load). The scheduler runs a task once everything upstream of it has succeeded, which is Kahn’s algorithm spread over time. Airflow refuses to load a DAG with a cycle: check_cycle raises AirflowDagCycleException. In Airflow 2.2.1 it’s an iterative DFS with exactly the three colours from Intermediate, trimmed here:

CYCLE_NEW = 0
CYCLE_IN_PROGRESS = 1
CYCLE_DONE = 2

def check_cycle(dag: "DAG") -> None:
    """Check to see if there are any cycles in the DAG.

    :raises AirflowDagCycleException: If cycle is found in the DAG.
    """
    # default of int is 0 which corresponds to CYCLE_NEW
    visited = defaultdict(int)
    path_stack = deque()
    ...
        for adjacent_task in current_task.get_direct_relative_ids():
            if visited[adjacent_task] == CYCLE_IN_PROGRESS:
                msg = f"Cycle detected in DAG. Faulty task: {task_id}"
                raise AirflowDagCycleException(msg)

CYCLE_IN_PROGRESS is grey, CYCLE_DONE is black, and an explicit path_stack replaces recursion, so a DAG with thousands of tasks can’t hit the recursion limit.

Celery’s canvas builds DAGs out of three primitives: a chain runs tasks one after another, each receiving the previous result; a group runs tasks in parallel; a chord is a group plus a callback that runs once every member of the group has finished. That’s fan-out and fan-in, the two shapes every DAG is built from. This runs in-process with eager mode, no broker needed (Celery 5.6.3):

from celery import Celery, chain, chord, group

app = Celery("demo")
app.conf.task_always_eager = True          # run in-process, no broker, for the demo

@app.task
def fetch(source):
    return f"rows from {source}"

@app.task
def merge(parts):
    return f"report built from {len(parts)} sources"

@app.task
def email(report):
    return f"sent: {report}"

# fan out to three fetches, fan in to merge, then email
flow = chain(chord(group(fetch.s(s) for s in ("crm", "billing", "inbox")), merge.s()), email.s())
print(flow.apply().get())
# sent: report built from 3 sources

The graph is the easy part of a scheduler. The hard parts are what a node does when it fails halfway: retry it (so it had better be idempotent), skip everything downstream, or run a compensating task. A chord’s callback waits on every member, so one member that never finishes holds up the whole fan-in. That’s a timeout question, not a graph one, and it’s where most production incidents in DAG schedulers live.

Deadlock detection: the wait-for graph

A deadlock is a cycle in a graph. Transaction A holds a lock that B wants, and B holds a lock that A wants. Draw an arrow from each transaction to the one it’s waiting for, and a deadlock is exactly a cycle in that wait-for graph.

PostgreSQL detects this and breaks it. The documentation says it plainly: “PostgreSQL automatically detects deadlock situations and resolves them by aborting one of the transactions involved, allowing the other(s) to complete. (Exactly which transaction will be aborted is difficult to predict and should not be relied upon.)” The lock manager’s README in the source tree describes the graph: “There is a graph edge leading from process A to process B if A waits for B, ie, A is waiting for some lock and B holds a conflicting lock”, and a deadlock exists when “the WFG contains a cycle.”

The detector doesn’t run on every wait. Building and searching the graph is expensive, so a process that can’t get a lock goes to sleep, and only if it’s still waiting after deadlock_timeout (default one second) does it run the check. Here’s a real deadlock, on a local PostgreSQL 14 with two threads:

import threading, time
import psycopg

DSN = "host=/tmp port=5541 user=postgres dbname=postgres"
with psycopg.connect(DSN, autocommit=True) as c:
    c.execute("DROP TABLE IF EXISTS wallets")
    c.execute("CREATE TABLE wallets (id int PRIMARY KEY, balance int)")
    c.execute("INSERT INTO wallets VALUES (1, 100), (2, 100)")

def transfer(name, first, second, results):
    with psycopg.connect(DSN) as conn:
        try:
            conn.execute("UPDATE wallets SET balance = balance - 10 WHERE id = %s", (first,))
            time.sleep(0.5)                          # let the other transaction take its first lock
            conn.execute("UPDATE wallets SET balance = balance + 10 WHERE id = %s", (second,))
            conn.commit()
            results[name] = "committed"
        except psycopg.errors.DeadlockDetected as e:
            results[name] = f"{e.sqlstate} {e.diag.message_primary}\n{e.diag.message_detail}"

results = {}
start = time.perf_counter()
a = threading.Thread(target=transfer, args=("A: 1 then 2", 1, 2, results))
b = threading.Thread(target=transfer, args=("B: 2 then 1", 2, 1, results))
a.start(); b.start(); a.join(); b.join()
for name in sorted(results):
    print(name, "->", results[name])
print(f"resolved after {time.perf_counter() - start:.1f} s")
# A: 1 then 2 -> committed
# B: 2 then 1 -> 40P01 deadlock detected
# Process 37313 waits for ShareLock on transaction 740; blocked by process 37312.
# Process 37312 waits for ShareLock on transaction 741; blocked by process 37313.
# resolved after 1.5 s

The DETAIL line is the cycle: 37313 waits for 37312, which waits for 37313. And the 1.5 seconds is the half-second sleep plus the one-second deadlock_timeout before anyone looked. Change thread B to lock row 1 first, like A, and the same run prints two committed lines after 1.0 s: B simply waits its turn, because a wait-for graph where every transaction takes locks in the same global order can’t contain a cycle. The documentation calls this “the best defense against deadlocks”: acquire locks “on multiple objects in a consistent order”. That sentence is topological sorting applied to resources, and you’ll see it three times in ezychat below.

Hierarchies in SQL: recursive CTEs or a graph database?

Org charts, folder trees, category trees and comment threads are graphs stored in tables, usually as a parent_id column. SQL walks them with a recursive common table expression: a starting row, plus a query that joins one more level onto what’s been found so far, repeated until nothing new appears. It’s BFS written in SQL. SQLite supports it, so this runs from Python’s standard library:

import sqlite3

db = sqlite3.connect(":memory:")
db.executescript("""
CREATE TABLE units (id TEXT PRIMARY KEY, parent_id TEXT, name TEXT);
INSERT INTO units VALUES
  ('org',   NULL,    'Head office'),
  ('kl',    'org',   'KL branch'),
  ('pg',    'org',   'Penang branch'),
  ('sales', 'kl',    'KL sales team'),
  ('svc',   'kl',    'KL service team'),
  ('night', 'svc',   'Night shift');
""")

# Everything under the KL branch, with how deep it sits.
rows = db.execute("""
WITH RECURSIVE below(id, name, depth) AS (
    SELECT id, name, 0 FROM units WHERE id = 'kl'          -- the starting row
    UNION ALL
    SELECT u.id, u.name, b.depth + 1                       -- one more level down
    FROM units u JOIN below b ON u.parent_id = b.id
)
SELECT name, depth FROM below ORDER BY depth, name
""").fetchall()
for name, depth in rows:
    print("  " * depth + name)

# A bad row that makes a loop: Head office's parent is now the night shift.
db.execute("UPDATE units SET parent_id = 'night' WHERE id = 'org'")
rows = db.execute("""
WITH RECURSIVE below(id, depth, trail) AS (
    SELECT id, 0, '/' || id || '/' FROM units WHERE id = 'kl'
    UNION ALL
    SELECT u.id, b.depth + 1, b.trail || u.id || '/'
    FROM units u JOIN below b ON u.parent_id = b.id
    WHERE b.trail NOT LIKE '%/' || u.id || '/%'            -- the visited set, carried in the row
)
SELECT max(depth), count(*) FROM below
""").fetchone()
print(rows)

runaway = db.execute("""
WITH RECURSIVE below(id) AS (
    SELECT id FROM units WHERE id = 'kl'
    UNION ALL
    SELECT u.id FROM units u JOIN below b ON u.parent_id = b.id
)
SELECT count(*) FROM (SELECT * FROM below LIMIT 10000)
""").fetchone()[0]
print(runaway, "rows, and only the LIMIT stopped it")
# KL branch
#   KL sales team
#   KL service team
#     Night shift
# (4, 6)
# 10000 rows, and only the LIMIT stopped it

The last query is the forgetful BFS from Intermediate again, in SQL. A recursive CTE has no visited set unless you carry one in the row (the trail column), so one bad parent_id turns a hierarchy query into an infinite one. PostgreSQL 14 added a CYCLE clause that does the bookkeeping for you. Whatever the database, a tree stored as parent_id should either reject cycles on write or guard every recursive read.

Other ways to store a tree trade write cost for read cost. A materialized path stores each row’s full path from the root (org.kl.svc.night), so “everything under KL” is a prefix match an index can serve, at the price of rewriting paths when a subtree moves. PostgreSQL’s ltree extension is a materialized path with operators and index support, and it’s what ezychat uses. Closure tables store every ancestor and descendant pair explicitly: fast reads, more rows.

And graph databases? Neo4j and its relatives store adjacency directly, so a query like “friends of friends who like this product, up to four hops” is a short pattern instead of a stack of joins, and each hop follows a pointer rather than an index lookup. My opinion: for trees and shallow hierarchies, which is most of what a typical backend has, a relational database with a recursive CTE, a path column or a closure table is enough, and one fewer database to run is worth a lot. A graph database starts paying for itself when the core queries are multi-hop, variable-depth and over a large, densely connected graph: fraud rings, recommendations, network topology.

PageRank in one paragraph

PageRank (Sergey Brin and Larry Page, 1998) scores pages by imagining a random surfer: at each step, with probability 0.85 they follow a random link from the current page, and otherwise they jump to a random page anywhere. A page’s score is the fraction of time the surfer spends there in the long run, so a page matters if pages that matter link to it. Computing it is repeated rounds of “each page shares its score among its out-links” until the numbers settle, which is a matrix times a vector, over and over:

def pagerank(links, damping=0.85, rounds=50):
    pages = list(links)
    rank = {p: 1 / len(pages) for p in pages}
    for _ in range(rounds):
        new = {p: (1 - damping) / len(pages) for p in pages}
        for page, outs in links.items():
            targets = outs or pages                  # a page with no links shares with everyone
            for t in targets:
                new[t] += damping * rank[page] / len(targets)
        rank = new
    return rank

links = {"home": ["docs", "blog"], "docs": ["home"], "blog": ["home", "docs"], "old post": ["blog"]}
for page, score in sorted(pagerank(links).items(), key=lambda kv: -kv[1]):
    print(f"{page:<9} {score:.3f}")
# home      0.407
# docs      0.313
# blog      0.242
# old post  0.038

“old post” links out but nothing links to it, so it keeps only the random-jump share. The same idea, importance flowing along edges, ranks accounts in social graphs and spots suspicious clusters in payment networks.

Why social graphs need special storage at scale

A social network’s graph is huge, constantly changing, read far more than written, and queried with a small, fixed set of questions: who are this user’s friends, did this person like that post, how many likes does it have. Facebook’s answer is documented in the USENIX ATC 2013 paper “TAO: Facebook’s Distributed Data Store for the Social Graph” (Bronson and others). TAO models everything as objects (users, posts, places) and typed associations between them (friend, liked, authored), stored as per-object lists of edges. It’s “a geographically distributed data store that provides efficient and timely access to the social graph” using “a fixed set of queries”, and the paper reports it handling “a billion reads and millions of writes each second”. Underneath, the data lives in sharded MySQL, with a large graph-aware caching layer in front that serves the adjacency lists.

The lesson I take from it is the same as the one from the adjacency matrix in Beginner, at planetary scale: store what the queries need, in the shape they need it. TAO doesn’t run arbitrary graph traversals. It serves adjacency lists, fast, and lets the application compose them. Twitter’s FlockDB, open-sourced in 2010, made a similar choice for follower lists: a sharded store of edges on top of MySQL, optimized for huge adjacency lists and set operations on them, not for deep traversal.

The adversarial cases are the hubs. A celebrity’s follower list has tens of millions of entries, so “fan out a post to every follower” or “intersect two users’ friend lists” can’t be one in-memory loop. Systems split hub lists across shards, precompute counts, and treat high-degree nodes differently from ordinary ones. Degree distribution, not node count, is usually what breaks a graph system first.

Graphs in a design review

When a design contains a graph, these are the questions I ask:

1. Is it really a tree, a DAG or a general graph? Each allows simpler storage and queries than the next. Say which, and say what enforces it.
2. Who prevents cycles, and when? At write time (a check, a constraint, a validator at import) is far cheaper than discovering a loop at read time.
3. How deep and how wide can it get? Depth decides recursion limits and query cost; the biggest degree decides memory and fan-out.
4. Which direction do the queries go? If you need “who depends on me” as often as “what do I depend on”, store or index both directions.
5. What happens to in-flight work when the graph changes? A DAG edited while it runs, a subtree moved while permissions are evaluated, a merge while someone reads the old id.
6. If there are locks, in what order are they taken? One global order, written down, is the cheapest deadlock prevention there is.

def find_deadlock(waits_for):
    """waits_for: transaction -> the transactions holding locks it wants. Returns one cycle or None."""
    WHITE, GREY, BLACK = 0, 1, 2
    colour = {t: WHITE for t in waits_for}
    for blockers in waits_for.values():
        for b in blockers:
            colour.setdefault(b, WHITE)          # a holder that waits for nothing is still a node
    for root in list(colour):
        if colour[root] != WHITE:
            continue
        path = [root]
        colour[root] = GREY
        stack = [iter(waits_for.get(root, ()))]
        while stack:
            for nxt in stack[-1]:
                if colour[nxt] == GREY:
                    return path[path.index(nxt):] + [nxt]
                if colour[nxt] == WHITE:
                    colour[nxt] = GREY
                    path.append(nxt)
                    stack.append(iter(waits_for.get(nxt, ())))
                    break
            else:
                colour[path.pop()] = BLACK
                stack.pop()
    return None

print(find_deadlock({"T1": ["T2"], "T2": ["T3"], "T3": []}))
print(find_deadlock({"T1": ["T2"], "T2": ["T3"], "T3": ["T1"], "T4": ["T1"]}))
print(find_deadlock({"T1": ["T2", "T3"], "T3": ["T4"], "T4": ["T3"]}))
# None
# ['T1', 'T2', 'T3', 'T1']
# ['T3', 'T4', 'T3']

def build_plan(needs, seconds):
    """needs: task -> tasks it depends on. Returns waves of tasks that can run together,
    and the wall-clock time with unlimited workers (the critical path)."""
    tasks = set(needs) | {d for ds in needs.values() for d in ds}
    remaining = {t: set(needs.get(t, ())) for t in tasks}
    finish = {}
    waves = []
    while remaining:
        wave = sorted(t for t, deps in remaining.items() if not deps)
        if not wave:
            raise ValueError(f"cycle among {sorted(remaining)}")
        for t in wave:
            finish[t] = seconds[t] + max((finish[d] for d in needs.get(t, ())), default=0)
            del remaining[t]
        for deps in remaining.values():
            deps.difference_update(wave)
        waves.append(wave)
    return waves, max(finish.values())

needs = {
    "test": {"compile"}, "lint": set(), "compile": {"deps"},
    "image": {"compile"}, "deploy": {"test", "image", "lint"},
}
seconds = {"deps": 40, "compile": 90, "lint": 20, "test": 120, "image": 60, "deploy": 30}
waves, total = build_plan(needs, seconds)
print(waves)
print(total, "s with enough workers;", sum(seconds.values()), "s one at a time")
# [['deps', 'lint'], ['compile'], ['image', 'test'], ['deploy']]
# 280 s with enough workers; 360 s one at a time

In production: graphs hiding in a multi-tenant backend

I’m the primary engineer of ezychat.io, a multi-tenant platform where AI and staff answer customers on WhatsApp, Instagram, Messenger and web chat. It’s Python (FastAPI and Celery) on PostgreSQL and Redis. Before writing this section I searched the backend for graph code: BFS and DFS, deque traversals, graphlib, recursive CTEs, union-find. There is no general-purpose graph library in it and no hand-written BFS. What there is, is graphs in disguise: a tree that permissions flow down, a dependency graph between product modules, merge chains between duplicate contacts, threads of comments, and a lock order that keeps the database’s wait-for graph acyclic. Every excerpt below is trimmed from the real code.

Permissions flow down a tree, stored as ltree paths

An organization in ezychat has a hierarchy of units: branches, departments and teams. The model keeps both a parent_id and a materialized path:

class OrgUnit(Base):
    __tablename__ = "org_units"
    __table_args__ = (UniqueConstraint("org_id", "parent_id", "name"),)
    ...
    parent_id: Mapped[uuid.UUID | None] = mapped_column(
        ForeignKey("org_units.id", ondelete="CASCADE")
    )
    kind: Mapped[str] = mapped_column(String(20))  # branch | department | team
    name: Mapped[str] = mapped_column(String(200))
    path: Mapped[str] = mapped_column(Ltree())

The path column is PostgreSQL’s ltree, indexed with GiST in migration 0003 (CREATE INDEX IF NOT EXISTS ix_org_units_path ON org_units USING GIST (path)). A role can be assigned at a unit, and it covers everything below that unit. When the permission snapshot for a user is built, “everything below” is one query using ltree’s descendant operator, <@:

_DESCENDANTS_SQL = text(
    "SELECT child.id FROM org_units parent "
    "JOIN org_units child ON child.path <@ parent.path "
    "WHERE parent.id = :unit_id"
)
...
    for unit_id, codes in by_scope.items():
        descendants = (
            (await session.execute(_DESCENDANTS_SQL, {"unit_id": unit_id})).scalars().all()
        )
        for did in descendants:
            scoped.setdefault(str(did), set()).update(codes)

That’s a subtree traversal with no traversal in sight. The path is the precomputed answer to “who are my ancestors?”, so “who are my descendants?” becomes “whose path starts with mine?”, which the GiST index can serve. To check the behaviour, I ran the same join against a toy table on a local PostgreSQL 14 (the real paths use each unit’s UUID in hex as the label, not a name):

import psycopg

with psycopg.connect("host=/tmp port=5541 user=postgres dbname=postgres", autocommit=True) as db:
    db.execute("CREATE EXTENSION IF NOT EXISTS ltree")
    db.execute("DROP TABLE IF EXISTS org_units")
    db.execute("CREATE TABLE org_units (id text PRIMARY KEY, parent_id text, path ltree)")
    db.execute("CREATE INDEX ON org_units USING GIST (path)")
    db.execute("""INSERT INTO org_units VALUES
        ('kl',    NULL, 'kl'),
        ('pg',    NULL, 'pg'),
        ('sales', 'kl', 'kl.sales'),
        ('svc',   'kl', 'kl.svc'),
        ('night', 'svc', 'kl.svc.night')""")
    rows = db.execute("""
        SELECT child.id FROM org_units parent
        JOIN org_units child ON child.path <@ parent.path
        WHERE parent.id = %s ORDER BY child.path""", ("kl",)).fetchall()
    print([r[0] for r in rows])
    print(db.execute("SELECT 'kl.svc.night'::ltree <@ 'kl'::ltree, 'pg'::ltree <@ 'kl'::ltree").fetchone())
# ['kl', 'sales', 'svc', 'night']
# (True, False)

The unit itself counts as its own descendant (<@ is “is a descendant of, or equal to”), which is what a permission scope wants: a role at the KL branch covers the KL branch too. The cost of a materialized path is on writes. Moving a team rewrites its path, and the docstring of the function that does it spells out why that’s more than a cosmetic change:

async def _place(
    session: AsyncSession, org_id: uuid.UUID, unit: OrgUnit, branch_id: uuid.UUID | None
) -> None:
    """Put a team under a branch, or back at the top of the org.

    The team becomes a child of the branch's unit, which is what the hierarchy
    was built for: permission scopes cover a unit's descendants, so a role
    scoped to the branch now covers this team too. That is a permission change,
    which is why every caller bumps the org's permission version.
    """
    if branch_id is None:
        unit.parent_id = None
        unit.path = unit.id.hex
        return
    branch_unit = await _branch_unit(session, org_id, branch_id)
    unit.parent_id = branch_unit.id
    unit.path = f"{branch_unit.path}.{unit.id.hex}"

Two graph lessons in a dozen lines. Editing an edge in a tree changes the answer to every reachability question below it, so anything derived from reachability has to be invalidated: the callers bump the org’s permission version (the snapshot carries it as pv) and invalidate the org’s cache. And the path is rebuilt from the new parent’s path in one assignment. In this router _place is only called on teams, when one is created or moved. Moving a unit that has children of its own would also mean rewriting every descendant’s path, which is the materialized-path trade-off from Expert.

Why ltree instead of a recursive CTE? Permission checks run on every request, and a prefix match on an indexed column is cheaper and more predictable than a recursive query whose cost grows with depth. The hierarchy is shallow and changes rarely: the profile where a materialized path wins.

A dependency graph between product modules

ezychat is sold as modules (booking, leads, commerce, deal rooms, marketing, documents) that an organization switches on and off. Some modules can’t work without others, so the catalog declares a dependency graph:

    # Modules this one cannot work without. Deal Rooms writes leads and reads
    # the lead panel; ordering quotes from the catalogue. Both dependencies
    # were deliberate and neither was written down, so nothing stopped an org
    # enabling deal rooms with leads off and getting a module that half-works
    # in ways no error names.
    requires: tuple[str, ...] = ()

The code that consumes it is a small graph toolkit. Unknown nodes are rejected at import. Self-loops (a cycle of length one) are rejected in the constructor, with the comment “a module requiring itself would make itself impossible to enable”. And the reverse adjacency is precomputed, exactly the “who depends on me?” trick from Advanced:

# module key -> the modules that cannot run without it, for the disable guard.
DEPENDANTS: dict[str, tuple[str, ...]] = {
    module.key: tuple(other.key for other in MODULES if module.key in other.requires)
    for module in MODULES
}

Enabling a module checks its out-edges (are all my requirements on?), and disabling one checks its in-edges via DEPENDANTS (is anything that needs me still on?). Both look only one hop away, and that’s enough. The rule “every enabled module has all its direct requirements enabled” is checked at every change, so if it held before the change it holds after, and following it hop by hop means every indirect requirement is enabled too. Maintaining an invariant locally gives you the transitive guarantee for free. This is a pattern I like a lot: it replaces a graph traversal at read time with a one-hop check at write time.

Today the graph has no edges at all. Every module’s requires is empty. Deal Rooms “carried one until 2026-09-19”, and the comment on it explains why it was removed: the lead_id column “has always been nullable”, the create form never asked for one, and “every read of a linked lead sits inside a null check”. Marketing’s empty tuple is “Empty, and deliberately so”, because forcing a CRM on someone who only wants to schedule posts “is how this module loses the customer it exists to attract”. I find that the most useful kind of graph code: the machinery is there and tested, and the people who declare edges have to argue for each one in writing.

The validator catches self-loops but not longer cycles. Two modules that required each other could never be enabled one at a time, since each would refuse while the other was off. With zero edges that’s theoretical, and it’s an easy gap to close. It’s the first exercise below.

Contact merges are union-find with a depth of one

The same customer often shows up as two contacts: one from WhatsApp, one from an Instagram comment. When the platform has proof they’re one person, it merges them. The handbook states the rule: “Nothing is deleted. Every table referencing contacts is repointed to the surviving contact.” The loser becomes a tombstone that points at the survivor through merged_into_id:

    survivor, loser = _choose_survivor(contact_a, contact_b)

    for _table, statement in _repoint_statements(org_id, survivor.id, loser.id):
        session.execute(statement)

    _backfill_survivor_fields(survivor, loser)

    # Not deleted. Everything the loser held has just moved, so the row now
    # carries nothing but its own identity — kept as a tombstone so an id held
    # outside this database still resolves to the person who absorbed it, and
    # so the unmerge has something to reverse onto.
    loser.merged_into_id = survivor.id

Look at it as a graph. merged_into_id is a parent pointer. A live contact has none: it’s a root. A merge links one root under another: that’s union. And resolving an old id to the person it now belongs to is find. The merge refuses anything that isn’t a root:

    if _resolve_head(contact_a) is not None or _resolve_head(contact_b) is not None:
        logger.warning("merge_contacts: refusing to merge a tombstone for org %s", org_id)
        return None

The interesting part is how deep the trees can get. Textbook union-find lets chains grow and fixes them lazily with path compression during find. ezychat flattens them eagerly during union. The merge registry, which lists every table a merge has to repoint, includes the contacts table itself:

    Repoint(
        "contacts",
        "merged_into_id",
        "Merge chains. If A was merged into B and B is then merged into C, A's "
        "tombstone has to follow, or an external system holding A's id resolves "
        "to a contact that no longer represents anybody.",
    ),

So when B merges into C, every tombstone pointing at B is repointed to C in the same transaction. Every tree has depth at most one, and find is always a single hop. Here’s the shape as a small model (not the real code, which runs SQL):

created = {"A": 3, "B": 2, "C": 1, "D": 4}       # contact -> created_at (smaller is older)
merged_into = {c: None for c in created}         # None means a live contact: a root

def merge(x, y):
    if merged_into[x] or merged_into[y]:
        return None                              # never merge a tombstone
    survivor, loser = sorted((x, y), key=created.get)   # the older record survives
    for c, target in merged_into.items():
        if target == loser:
            merged_into[c] = survivor            # "A's tombstone has to follow"
    merged_into[loser] = survivor
    return survivor

def resolve(c):
    return merged_into[c] or c                   # one hop, always

print(merge("A", "B"))                           # B is older, so B survives
print(merge("B", "C"))                           # C is older again
print(merged_into)
print({c: resolve(c) for c in created})
print(merge("A", "D"))                           # A is a tombstone now: refused
# B
# C
# {'A': 'C', 'B': 'C', 'C': None, 'D': None}
# {'A': 'C', 'B': 'C', 'C': 'C', 'D': 'D'}
# None

In textbook terms this is closer to the old “quick-find” variant: unions do more work (an UPDATE ... WHERE merged_into_id = :loser over the loser’s tombstones) so that finds do almost none. For a database that’s the right way round. Merges are rare, the update is one indexed statement, and resolving an id happens on reads, where a single hop means a single join instead of a loop. And the survivor isn’t chosen by rank but by age: “Earlier created_at survives; an exact tie breaks deterministically on the lower str(id).” Deterministic choice matters more than balanced trees when the trees are never deeper than one.

The docstring also keeps an “unmerge” possible (“so the unmerge has something to reverse onto”), which is the one thing union-find structures can’t do cheaply. Keeping the tombstone row and its identity is what makes it possible at all.

Comment threads, and the parent that wasn’t a comment

Comments on a Facebook or Instagram post form a tree: replies point at the comment they answer. ezychat groups them into threads keyed by the root comment, and a reply is filed by looking up the thread whose root is its parent_id. A docstring in the webhook parser records a bug in exactly that edge:

def _parent_comment_id(value: dict[str, Any], post_id: str) -> str | None:
    """The parent *comment* this one replies to, or None if it is top-level.

    **Facebook always sends `parent_id`.** On a top-level comment it is the
    post id; only on a genuine reply does it name another comment. Read
    literally — as "present only for replies", which is what this file used to
    say — every root comment took the reply path, and the first one on a post
    synthesized a placeholder thread keyed on the post id that every later
    top-level comment then nested under. Two strangers commenting on the same
    post arrived in the inbox as one conversation, the second appearing to
    answer the first. Present since comment ingestion was written; found on
    2026-09-02 by reading a real thread beside the Facebook post it came from.
    ...
    """
    parent_id = value.get("parent_id")
    if not parent_id or parent_id == post_id:
        return None
    return parent_id

In graph terms, an edge pointed at a node of the wrong kind. The post is the real root of the tree, but it wasn’t a comment, so treating it as one made every top-level comment a reply to a shared placeholder and merged separate trees into one. Graph code tends to assume every edge connects two nodes of the same type; data from outside rarely promises that.

The same file handles the other classic problem of building a tree from a stream: a child arriving before its parent. Its comment says “a reply can in rare cases arrive before its root comment”, and instead of dropping the reply, the code synthesizes a placeholder thread for the missing root and files the reply under it. Any time you build a tree from events, decide in advance what happens to an orphan.

Lock order: keeping the wait-for graph acyclic

Three places in ezychat write down the order in which they take row locks, for the reason in Expert. The wallet code:

    # Lock order: wallet first, then the held requests — always. The credit
    # path arrives already holding the wallet lock (re-locking is a no-op),
    # but the stuck-hold sweep calls in cold; without this line it would
    # take the request locks first and then meet a concurrent top-up coming
    # the other way around — wallet held, waiting on requests — which is a
    # deadlock Postgres resolves by killing one of a sweep and a payment.
    await _locked_wallet(session, org_id)

A batch upsert that sorts its rows first, because the order of rows in one statement is the order their locks are taken:

        # In key order: two passes upserting overlapping phrases in different
        # orders would lock the same rows in opposite orders and deadlock.
        for (side, phrase), (nothing, tagged) in sorted(counts.items())

And closing a support case, whose docstring says “The room’s state row is locked first, because a scoring pass holds it and then writes the case: taking the two the other way round could deadlock.”

Sorting by key before locking is the general version. If every transaction takes locks in ascending key order, a wait-for edge can only ever point from a transaction holding smaller keys toward one holding larger ones, and a cycle would need an edge pointing back down. That’s the argument behind topological order, used as a prevention rule.

Prevention can’t cover everything, and the booking code is the honest counterpart. Two concurrent bookings of the same resource can make PostgreSQL’s own exclusion-constraint check wait on each other, and the module docstring says that wait “ends one of two ways: the deadlock detector kills one side (SQLSTATE 40P01), or lock_timeout (core/db.py) elapses first”. Both are treated as what they mean to the customer:

# Two ways the database says "somebody else has this row, and you are not
# getting it": the deadlock detector picked you as the victim, or your
# `lock_timeout` (core/db.py) elapsed while the winner held the lock. Both
# mean the same thing to a customer, and neither is an error on our side.
_LOST_RACE_SQLSTATES = frozenset({"40P01", "55P03"})

The customer sees “just taken” instead of an error page. That’s the full deadlock story from Expert, in production: prevent cycles where you control the order, and where you can’t, let the detector break them and treat the victim as an ordinary lost race.

This site’s study graph

The articles on this site form a graph too. Each post’s frontmatter lists prerequisites and uses, and the site’s connections() function in src/lib/posts.js computes the reverse edges (“next”, “used in”) by scanning every post. The build fails if an edge points at a post that doesn’t exist, which is the same “unknown node” check ezychat’s module catalog does. Nothing checks for cycles, so I ran one against the real frontmatter, including this article’s:

import json, pathlib, re, sys
from graphlib import TopologicalSorter

blog = pathlib.Path(sys.argv[1] if len(sys.argv) > 1 else "src/content/blog")

def field(text, name):
    m = re.search(rf"^{name}:\s*(.+)$", text, re.M)
    return m.group(1).strip() if m else None

needs, order, section = {}, {}, {}
for f in sorted(blog.glob("*.md*")):
    front = f.read_text().split("---")[1]
    slug = f.stem
    deps = set()
    for key in ("prerequisites", "uses"):
        raw = field(front, key)
        deps |= set(json.loads(raw)) if raw else set()
    needs[slug] = deps
    section[slug] = field(front, "section")
    order[slug] = int(field(front, "order") or 0)

print(sum(map(len, needs.values())), "edges between", len(needs), "posts")
print(list(TopologicalSorter(needs).static_order()))

# Does each section's hand-written `order` respect the edges inside that section?
for post, deps in needs.items():
    for dep in deps:
        if section[dep] == section[post] and order[dep] >= order[post]:
            print("out of order:", dep, "->", post)
print("checked")
# 14 edges between 11 posts
# ['big-o-complexity', 'pin-your-llm-model-ids', 'hash-maps', 'caching-system-design', 'graphs-bfs-dfs', 'idempotency-and-retries', 'two-pointers', 'no-lost-turns-ai-reply-pipeline', 'sliding-window', 'rate-limiter-system-design', 'congestive-collapse-admission-control']
# checked

No cycle, and the hand-numbered study order inside each section never puts a post before something it builds on. It’s a small graph, but it’s the same check a build system or a package manager runs: does an order exist where every arrow points forward?

from graphlib import CycleError, TopologicalSorter

def validate_requirements(requires):
    """requires: module key -> the module keys it cannot work without."""
    keys = set(requires)
    for key, deps in requires.items():
        unknown = set(deps) - keys
        if unknown:
            raise ValueError(f"module {key!r} requires unknown module(s) {sorted(unknown)}")
    try:
        return list(TopologicalSorter(requires).static_order())   # a safe enable order
    except CycleError as e:
        raise ValueError(f"modules require each other in a loop: {' -> '.join(e.args[1])}") from None

print(validate_requirements({"booking": (), "leads": (), "deal_rooms": ("leads",)}))
try:
    validate_requirements({"leads": ("deal_rooms",), "deal_rooms": ("leads",)})
except ValueError as e:
    print(e)
# ['booking', 'leads', 'deal_rooms']
# modules require each other in a loop: leads -> deal_rooms -> leads