On this page

Graph Algorithms in the Real World

Why this exists

The previous thirteen lessons built a toolbox: BFS, DFS, topological sort, shortest paths, union-find, spanning trees, SCCs, flows and 2-SAT. This lesson is the payoff. It walks through systems you use every day and shows the exact algorithm inside each one, why that algorithm was chosen, and where the textbook version had to be bent to survive production.

The point is not trivia. Recognizing "this is reachability", "this is a cycle check" or "this is NP-complete in general, so we need a heuristic or a restriction" lets you reuse fifty years of results instead of inventing a worse version. Interviewers probe exactly this: "How does a package manager decide install order?" "How does a database notice a deadlock?" Each has a crisp graph answer.

We go deep on two systems, with full code: PageRank, the eigenvector computation that launched Google (Brin and Page, 1998), and deadlock detection, the cycle search every relational database runs on its lock table. Then we survey routing protocols (Dijkstra and Bellman–Ford running on every router on the internet), dependency resolution (topological sort, and why version selection is NP-complete), build systems, social graphs, graph databases, garbage collectors, knowledge graphs, fraud detection, map routing and the Git commit graph.

Pattern triggers

If the system needs to…It is really…Algorithm
Rank nodes by how much "endorsement" flows into themThe stationary distribution of a random walkPageRank by power iteration
Compute routes when every router knows the whole topologySingle-source shortest paths per routerDijkstra (OSPF, IS-IS)
Compute routes when routers only talk to neighboursDistributed relaxationBellman–Ford (RIP); path vector (BGP)
Install packages or run build steps in a valid orderLinear extension of a DAGTopological sort (Kahn or DFS)
Choose package versions satisfying constraintsBoolean satisfiabilitySAT / backtracking (NP-complete in general)
Rebuild only what changedReachability from changed nodes in the reverse dependency DAG, then topological orderDFS/BFS + topological sort
Suggest "people you may know"Two-hop neighbourhoodBFS to depth 2, rank by common neighbours
Find tightly knit groupsModularity maximizationLouvain / Leiden, label propagation
Free memory nobody can reachReachability from rootsMark = DFS/BFS; copying GC = BFS (Cheney)
Notice that transactions are stuck foreverCycle in a wait-for graphDFS with colours
Group accounts that share devices, cards or addressesConnected componentsUnion-find
Answer "is this route faster" on a continental road map in millisecondsShortest paths with preprocessingA*, ALT, contraction hierarchies
Find the common base of two Git branchesLowest common ancestors in a DAGTwo-sided ancestor walk

The meta-trigger: whenever entities point at other entities and the question is about reachability, ordering, cycles, cost of the best route, or influence flowing along links, you are holding a graph algorithm. The engineering is in scale (billions of edges), dynamism (the graph changes while you compute) and distribution (no machine sees the whole graph).

Intuition & first principles

PageRank: votes that are weighted by the voter

A naive way to rank web pages is to count in-links. It is easy to game: create a thousand junk pages linking to yours. Brin and Page's fix was recursive: a link from an important page should count more than a link from an unimportant one, and a page that links to a hundred others should pass on less to each than a page that links to one. Formally, with pages, the number of links on page , and the set of pages linking to :

The recursion has a beautiful reading, the random surfer model. A surfer starts on a random page. At each step, with probability (the damping factor, 0.85 in the original paper) they click a uniformly random link on the current page; with probability they get bored and jump to a uniformly random page. is the long-run fraction of time the surfer spends on page . The jump term does real work: without it, a surfer would get trapped in a group of pages with no links out (a "rank sink"), and the ranks would not be well defined.

Two practical details complete the model. Dangling pages (no out-links: PDFs, images, dead ends) would leak probability; the standard fix is to treat them as linking to every page, so their rank is spread uniformly. And the formula above sums to 1, which makes PR a probability distribution; the 1998 paper writes the jump term as rather than , which scales every rank by and changes nothing about the ordering.

In matrix form, let be the column-stochastic matrix with if links to (and for every if is dangling). The Google matrix is , and the PageRank vector is the with , : the principal eigenvector. Power iteration just applies repeatedly, , which costs one pass over the edges per iteration.

Deadlock: waiting in a circle

Transaction holds a lock on row A and wants row B. holds B and wants A. Neither can proceed, and neither will release what it holds until it proceeds. Draw an edge whenever is waiting for a lock that holds: the wait-for graph. A deadlock is a cycle in that graph. Detection is cycle detection, exactly the white/grey/black DFS from the DFS lesson; resolution is choosing a victim on the cycle to abort, which deletes its outgoing and incoming edges and breaks the cycle.

Mechanics

PageRank by hand

Four pages: A links to B and C; B links to C; C links to A; D links to C. Nobody links to D.

flowchart LR
    A["A (0.3725)"] --> B["B (0.1958)"]
    A --> C["C (0.3941)"]
    B --> C
    C --> A
    D["D (0.0375)"] --> C

Start from the uniform vector and apply the update with , so the jump term is . For iteration 1: (only A links to B, and A has two links); .

The trace below was computed by the implementation in this lesson (values rounded to 4 places; "L1 change" is ):

Iteration ABCDL1 change
00.25000.25000.25000.2500—
10.25000.14380.56880.03750.6375
20.52090.14380.29780.03750.5419
30.29060.25890.41300.03750.4606
40.38850.16100.41300.03750.1958
50.38850.20260.37140.03750.0832
60.35320.20260.40670.03750.0707
100.37510.19490.39250.03750.0092
200.37250.19580.39420.03750.000057
47 (converged)0.3725270.1958240.3941490.0375

Observations worth keeping:

  • D sits at exactly from iteration 1 onward: with no in-links, it only receives the random jump.
  • C wins: it collects all of B's vote, half of A's, and all of D's.
  • A is second with one in-link, because it comes from C, the most important page, which has only one out-link.
  • The values oscillate early (A jumps from 0.25 to 0.52 and back to 0.29) because rank sloshes around the cycle A → C → A, then damps out. The L1 change shrinks by a factor of about 0.6 per iteration on average and never by less than a factor of , as the correctness section proves. Reaching an L1 change below took 37 iterations; below , 47.
  • The converged vector matches a direct linear solve of to six decimals.

Deadlock detection by hand

A lock manager keeps, for each lock, its holder and a queue of waiters. Turning that into a wait-for graph is mechanical: for every waiter, add an edge to every transaction holding a conflicting lock. Suppose:

TransactionHoldsWaits forEdge(s)
T1row Arow B (held by T2)T1 → T2
T2row Brow C (held by T3)T2 → T3
T3row Crow A (held by T1)T3 → T1
T4—row A (held by T1)T4 → T1
flowchart LR
    T4["T4"] --> T1["T1 (holds A)"]
    T1 -->|"wants B"| T2["T2 (holds B)"]
    T2 -->|"wants C"| T3["T3 (holds C)"]
    T3 -->|"wants A"| T1

DFS with colours (white = unvisited, grey = on the current path, black = finished), visiting transactions in id order:

StepActionPath (grey, in order)BlackFinding
1visit T1T1—
2follow T1 → T2, visit T2T1, T2—
3follow T2 → T3, visit T3T1, T2, T3—
4follow T3 → T1: T1 is greyT1, T2, T3—back edge: cycle T1 → T2 → T3 → T1
5choose victim: youngest on the cycle, T3; abort it——edges T2 → T3 and T3 → T1 removed
6rerun: T1 → T2, T2 has no out-edges; T4 → T1 (black)—T2, T1, T4no cycle

T4 is waiting but not deadlocked: once T3 aborts, T2, then T1, then T4 can proceed. Being blocked is not being deadlocked; only a cycle is.

In OSPF (RFC 2328) each router originates a link-state advertisement listing its neighbours and link costs, and floods it to every router in the area. Once flooding settles, every router holds an identical link-state database: the whole weighted graph. Each router then runs Dijkstra rooted at itself and installs, for each destination, the first hop of the shortest path. IS-IS, which most large ISP backbones use internally, does the same with a different packet format.

flowchart LR
    R1["R1"] ---|"10"| R2["R2"]
    R1 ---|"1"| R3["R3"]
    R2 ---|"2"| R3
    R2 ---|"1"| R4["R4"]
    R3 ---|"7"| R5["R5"]
    R4 ---|"3"| R5

Dijkstra from R1 (verified by script):

StepSettledist R2dist R3dist R4dist R5
0R1 (0)101∞∞
1R3 (1)31∞8
2R2 (3)3148
3R4 (4)3147
4R5 (7)3147

R1's forwarding table sends traffic for every destination to R3 first: R2 at cost 3 (not via the direct cost-10 link), R3 at 1, R4 at 4, R5 at 7 via R3 → R2 → R4 → R5 (not via the direct R3–R5 link of cost 7, which would total 8). When two paths tie, OSPF can split traffic across them (equal-cost multipath, ECMP). The network layer page covers the packet-level side.

Distance-vector routing and count-to-infinity

RIP (RFC 2453) routers know only their neighbours. Every 30 seconds each router sends neighbours its whole table of (destination, distance) pairs; a router that hears "I can reach X at distance " from neighbour over a link of cost updates its own entry if is better, or if is its current next hop for X. This is distributed Bellman–Ford: after rounds with no failures, every router knows the best route using at most hops.

Good news travels fast; bad news travels slowly. Take a line A — B — C, every link cost 1, destination C. Normally B is at distance 1 (direct) and A at 2 (via B). Now the B–C link fails. B no longer has a direct route, but A is still advertising "C at distance 2", so B concludes it can reach C via A at distance 3, not realizing A's route goes through B itself. A then hears B's 3 and moves to 4, and so on. Simulated synchronously (RIP uses 16 as "infinity"):

RoundA's distance (next hop)B's distance (next hop)
0 (link fails)2 (B)1 (C), now invalid
12 (B)3 (A)
24 (B)3 (A)
34 (B)5 (A)
46 (B)5 (A)
………
1314 (B)15 (A)
1416, unreachable15 (A)
1516, unreachable16, unreachable

Fifteen rounds of 30 seconds is over seven minutes of traffic looping between A and B. This is the count-to-infinity problem, and it is why RIP caps the metric at 15 hops: a small infinity bounds how long the counting takes, at the cost of limiting network diameter. Split horizon with poisoned reverse fixes this two-node case: A advertises C to B as "unreachable", because A's route to C goes through B. The same simulation with poisoned reverse converges in 2 rounds. It does not fix loops of three or more routers; for those, routers add hold-down timers and triggered updates, and EIGRP replaces the whole scheme with Garcia-Luna-Aceves' DUAL algorithm, which guarantees loop freedom.

BGP (RFC 4271), which glues the internet's autonomous systems together, is a path-vector protocol: instead of a distance, each advertisement carries the full list of ASes the route traverses (the AS_PATH). A router rejects any route that already contains its own AS number, which kills count-to-infinity loops outright. But BGP does not pick shortest paths; it picks routes by policy (business relationships first, then path length, then tie-breakers). Griffin, Shepherd and Wilfong showed (2002) that with arbitrary policies BGP may oscillate forever, and that deciding whether a stable routing exists is NP-complete. The Gao–Rexford conditions (customer routes preferred over peer and provider routes, and no "valley" paths) are the commercial convention that keeps real BGP convergent. See the BGP page.

The ladder: brute force → better → optimal

Most systems here pick from a ladder of algorithms. Two of the most important ladders:

Ranking (PageRank)

Rung 1: solve the linear system. by Gaussian elimination: time and memory. Fine for ; for pages the matrix alone would need entries.

Rung 2: power iteration. One sparse matrix–vector product per iteration, for links, and memory for two vectors plus the edge list. The number of iterations depends only on and the tolerance, not on : the error shrinks by at least a factor per step, so at most iterations, about 113 for and , and usually far fewer.

Rung 3: distributed and approximate. At web scale the edge list does not fit on one machine. Pregel (Malewicz et al., SIGMOD 2010), Google's "think like a vertex" framework, used PageRank as its flagship example: each vertex sends to its neighbours in a superstep, then sums what it receives. Apache Giraph and Spark GraphX follow the same model. For personalized PageRank (jump to a specific user's pages rather than uniformly), local "push" algorithms (Andersen, Chung and Lang, 2006) and Monte Carlo random walks touch only the neighbourhood of the source, which is what recommendation systems such as Twitter's "Who to Follow" built on.

Route finding on road maps

Rung 1: Dijkstra. per query. On a continental road graph (the full USA graph from the 9th DIMACS Implementation Challenge has about 24 million nodes and 58 million edges) a single query settles millions of nodes and takes on the order of seconds: too slow for a service answering thousands of requests per second.

Rung 2: bidirectional Dijkstra and A*. Searching from both ends roughly halves the explored area. A* (Hart, Nilsson and Raphael, 1968) adds a heuristic lower bound on remaining distance; straight-line distance divided by maximum speed is valid but weak on roads. ALT (Goldberg and Harrelson, 2005) precomputes distances to a handful of landmarks and uses the triangle inequality for much tighter bounds.

Rung 3: contraction hierarchies. Preprocess once (Geisberger, Sanders, Schultes and Delling, 2008): order nodes by "importance", contract them one at a time, and whenever removing node would destroy a shortest path , add a shortcut edge . A query then runs bidirectional Dijkstra that only ever moves upward in the order, and settles a few hundred nodes instead of millions, answering continental queries in well under a millisecond. OSRM, the open-source routing engine behind many OpenStreetMap services, uses contraction hierarchies (and a multi-level partition variant that handles traffic updates better). The preprocessing must be redone when weights change, which is why traffic-aware systems favour customizable variants (Delling et al.'s Customizable Route Planning).

SystemBrute forceBetterOptimal in practice
Ranking pagesDense linear solve, Power iteration, Distributed power iteration; local push for personalized PageRank
Road routingDijkstra per query, millions of settled nodesBidirectional, A*, ALTContraction hierarchies: hundreds of settled nodes per query
Network routingFlood every packetDistance vector (Bellman–Ford), slow convergenceLink state (Dijkstra) inside a domain; path vector (BGP) between domains
DeadlocksTimeouts on every lock waitPeriodic wait-for-graph DFSDetect on wait (InnoDB) or after a short timeout (PostgreSQL); prevention by lock ordering where possible
Garbage collectionReference counting (misses cycles)Stop-the-world mark–sweepGenerational, concurrent tri-colour marking
Package versionsTry every combinationBacktracking with heuristicsCDCL SAT solvers / PubGrub with conflict learning; or restrict the problem (Go's MVS)

Correctness

PageRank converges, and to a unique answer

Existence and uniqueness. With the dangling fix, is column-stochastic (every column sums to 1), and so is . Every entry of is at least . By the Perron–Frobenius theorem, a positive column-stochastic matrix has eigenvalue 1 with a one-dimensional eigenspace spanned by a positive vector, and every other eigenvalue has modulus less than 1. Normalized to sum to 1, that vector is PageRank. This is why the damping factor is not decoration: with the matrix can be reducible and the "answer" can be non-unique or zero on most pages.

Geometric convergence. Let be probability vectors. Then , because the jump term contributes . A column-stochastic matrix does not increase the L1 norm: . Hence

so is a contraction with factor in L1, and by the Banach fixed-point theorem power iteration converges from any starting distribution with . In terms of eigenvalues: the second eigenvalue of has modulus at most (Haveliwala and Kamvar, 2003).

What the stopping rule guarantees. We stop when . By the triangle inequality and the contraction, , so . With and the true error is below . The code's assertion against the exact solution to is therefore comfortably safe.

A cycle in the wait-for graph is exactly a deadlock

Assume the standard model: each lock is held exclusively, a waiting transaction waits for all the holders it conflicts with (the "AND" model), and a transaction releases locks only when it finishes.

Cycle implies deadlock. Every transaction on a cycle is waiting for the next to finish. None of them can finish first, because each needs its successor to finish first. Without outside intervention (an abort), none ever runs again.

Deadlock implies cycle. Suppose a set of transactions is deadlocked: none will ever proceed. Each waits for some holder, and that holder must itself be stuck (otherwise it would finish and release), so it is also in . Every vertex of has an out-edge into ; walking out-edges in a finite set must eventually revisit a vertex, which closes a cycle.

With shared locks and multi-unit resources, a cycle is necessary but not sufficient (some holder might finish via another path), and detection needs the general reduction algorithm on the resource-allocation graph (Holt, 1972); with "OR" waits (any one of several resources will do), the condition becomes a knot rather than a cycle. Database lock managers use the AND model, which is why a cycle check is enough.

Mark phase marks exactly the live objects

Define live = reachable from a root by following pointers. Marking is BFS or DFS from all roots at once, so by the standard search invariant (every marked object was reached along a pointer path; every object reachable from a marked object is eventually marked) it marks exactly the reachable set, in . Unreachable objects can never be touched again by the program, which has no way to name them, so freeing them is safe.

For concurrent marking (the collector runs while the program mutates pointers), the invariant becomes the tri-colour invariant of Dijkstra, Lamport, Martin, Scholten and Steffens (1978): white = not yet seen, grey = seen but children not scanned, black = scanned. The danger is the program storing a pointer to a white object into a black one and erasing the last other path to it; the collector would never revisit the black object and would free a live object. Write barriers prevent this by shading the target grey (Dijkstra-style insertion barrier) or by preserving the old pointer target (Yuasa-style deletion barrier, a "snapshot at the beginning"). Go's collector uses a hybrid of the two.

Distance vector: why bad news is slow

Bellman–Ford's invariant is "after rounds, every advertised distance is the length of a real path of at most hops, and is optimal among those". A link failure breaks the first half: B still holds A's advertisement "2", but A's path went through the dead link. The protocol keeps relaxing using distances that no longer correspond to real paths, so each round can only add the link cost; values climb until they reach the infinity sentinel. Path vector repairs the invariant by carrying the path itself, so a router can see its own name in a route and discard it.

Complexity

SystemGraph size in practiceAlgorithmTimeMemory
PageRank– edges (web), – (product graphs)Power iteration, –Two rank vectors + edges; distributed by vertex partition
OSPF / IS-IS SPFhundreds to a few thousand routers per areaDijkstra with a heap per LSA changeLink-state database
RIP hops diameterDistributed Bellman–Fordup to diameter rounds, plus count-to-infinityOne table per router
Install order– packagesKahn
Version resolutionsameSAT / backtrackingexponential worst casesolver state
Incremental build– targetsReverse reachability + topological orderDAG + cache
Friend-of-friendaverage degree in the hundreds2-hop BFS per query, about edge reads at candidate counter
Triangle counting+ edgesDegree-ordered node iterator
Community detection– nodesLouvainroughly per pass, few passes in practice
GC marklive heapDFS/BFS from rootsmark bits + mark stack
Deadlock checkactive transactionsDFS for transactions, wait edgescolours + stack
Road routing (CH)– nodesBidirectional upward Dijkstrasub-millisecond query, minutes of preprocessinggraph + shortcuts
Git merge-base– commitsTwo-colour walk with generation numbersproportional to commits between tips and basecommit-graph file

Constants matter in two places. PageRank at scale is memory-bandwidth-bound: each iteration streams the edge list, and rank[source] is a cache miss per edge unless vertices are reordered for locality. GC marking is pointer chasing, the worst access pattern for caches, so collectors prefetch from the mark stack and mark in parallel.

Implementation

PageRank by power iteration

Same graph and expected values as the trace, plus a dangling-node graph (, where page 2 has no out-links) whose exact answer, from a linear solve, is . Each block asserts convergence within 100 iterations, ranks summing to 1, and agreement with the exact values to .

def pagerank(n: int, edges: list[tuple[int, int]], d: float = 0.85,
             tol: float = 1e-10, max_iter: int = 100) -> tuple[list[float], int]:
    """Power iteration. Dangling pages spread their rank uniformly.
    Returns (ranks, iterations). Raises if it does not converge."""
    out_deg = [0] * n
    for u, _ in edges:
        out_deg[u] += 1
    r = [1.0 / n] * n
    for it in range(1, max_iter + 1):
        dangling = sum(r[u] for u in range(n) if out_deg[u] == 0)
        base = (1.0 - d) / n + d * dangling / n
        nr = [base] * n
        for u, v in edges:
            nr[v] += d * r[u] / out_deg[u]
        delta = sum(abs(a - b) for a, b in zip(nr, r))
        r = nr
        if delta < tol:
            return r, it
    raise RuntimeError("PageRank did not converge")


if __name__ == "__main__":
    A, B, C, D = range(4)
    ranks, iters = pagerank(4, [(A, B), (A, C), (B, C), (C, A), (D, C)])
    expected = [0.372527, 0.195824, 0.394149, 0.0375]
    assert iters <= 100
    assert abs(sum(ranks) - 1.0) < 1e-9
    assert all(abs(x - y) < 1e-6 for x, y in zip(ranks, expected))
    assert sorted(range(4), key=lambda i: -ranks[i]) == [C, A, B, D]

    ranks2, iters2 = pagerank(3, [(0, 1), (1, 2)])
    assert iters2 <= 100 and abs(sum(ranks2) - 1.0) < 1e-9
    assert all(abs(x - y) < 1e-6 for x, y in zip(ranks2, [0.184417, 0.341171, 0.474412]))
    print(f"PageRank converged in {iters} iterations:", [round(x, 6) for x in ranks])
public class PageRankDemo {
    record Result(double[] ranks, int iterations) {}

    static Result pagerank(int n, int[][] edges, double d, double tol, int maxIter) {
        int[] outDeg = new int[n];
        for (int[] e : edges) outDeg[e[0]]++;
        double[] r = new double[n];
        java.util.Arrays.fill(r, 1.0 / n);
        for (int it = 1; it <= maxIter; it++) {
            double dangling = 0;
            for (int u = 0; u < n; u++) if (outDeg[u] == 0) dangling += r[u];
            double base = (1.0 - d) / n + d * dangling / n;
            double[] nr = new double[n];
            java.util.Arrays.fill(nr, base);
            for (int[] e : edges) nr[e[1]] += d * r[e[0]] / outDeg[e[0]];
            double delta = 0;
            for (int i = 0; i < n; i++) delta += Math.abs(nr[i] - r[i]);
            r = nr;
            if (delta < tol) return new Result(r, it);
        }
        throw new IllegalStateException("PageRank did not converge");
    }

    static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }

    static void checkClose(double[] got, double[] want) {
        double sum = 0;
        for (int i = 0; i < got.length; i++) {
            check(Math.abs(got[i] - want[i]) < 1e-6, "rank " + i + " = " + got[i]);
            sum += got[i];
        }
        check(Math.abs(sum - 1.0) < 1e-9, "sum");
    }

    public static void main(String[] args) {
        final int A = 0, B = 1, C = 2, D = 3;
        Result res = pagerank(4, new int[][]{{A, B}, {A, C}, {B, C}, {C, A}, {D, C}}, 0.85, 1e-10, 100);
        check(res.iterations() <= 100, "iterations");
        checkClose(res.ranks(), new double[]{0.372527, 0.195824, 0.394149, 0.0375});
        double[] r = res.ranks();
        check(r[C] > r[A] && r[A] > r[B] && r[B] > r[D], "order");

        Result res2 = pagerank(3, new int[][]{{0, 1}, {1, 2}}, 0.85, 1e-10, 100);
        check(res2.iterations() <= 100, "iterations dangling");
        checkClose(res2.ranks(), new double[]{0.184417, 0.341171, 0.474412});
        System.out.println("PageRank converged in " + res.iterations() + " iterations");
    }
}
#include <cmath>
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

struct PageRankResult { std::vector<double> ranks; int iterations; };

PageRankResult pagerank(int n, const std::vector<std::pair<int, int>>& edges,
                        double d = 0.85, double tol = 1e-10, int max_iter = 100) {
    std::vector<int> out_deg(n, 0);
    for (auto [u, v] : edges) ++out_deg[u];
    std::vector<double> r(n, 1.0 / n);
    for (int it = 1; it <= max_iter; ++it) {
        double dangling = 0;
        for (int u = 0; u < n; ++u) if (out_deg[u] == 0) dangling += r[u];
        std::vector<double> nr(n, (1.0 - d) / n + d * dangling / n);
        for (auto [u, v] : edges) nr[v] += d * r[u] / out_deg[u];
        double delta = 0;
        for (int i = 0; i < n; ++i) delta += std::fabs(nr[i] - r[i]);
        r = std::move(nr);
        if (delta < tol) return {r, it};
    }
    throw std::runtime_error("PageRank did not converge");
}

void check(bool ok, const std::string& msg) { if (!ok) throw std::runtime_error(msg); }

void check_close(const std::vector<double>& got, const std::vector<double>& want) {
    double sum = 0;
    for (size_t i = 0; i < got.size(); ++i) {
        check(std::fabs(got[i] - want[i]) < 1e-6, "rank " + std::to_string(i));
        sum += got[i];
    }
    check(std::fabs(sum - 1.0) < 1e-9, "sum");
}

int main() {
    enum { A, B, C, D };
    auto res = pagerank(4, {{A, B}, {A, C}, {B, C}, {C, A}, {D, C}});
    check(res.iterations <= 100, "iterations");
    check_close(res.ranks, {0.372527, 0.195824, 0.394149, 0.0375});
    const auto& r = res.ranks;
    check(r[C] > r[A] && r[A] > r[B] && r[B] > r[D], "order");

    auto res2 = pagerank(3, {{0, 1}, {1, 2}});
    check(res2.iterations <= 100, "iterations dangling");
    check_close(res2.ranks, {0.184417, 0.341171, 0.474412});
    std::cout << "PageRank converged in " << res.iterations << " iterations\n";
}
function pagerank(n: number, edges: [number, number][], d = 0.85, tol = 1e-10, maxIter = 100):
    { ranks: number[]; iterations: number } {
  const outDeg = new Array<number>(n).fill(0);
  for (const [u] of edges) outDeg[u]++;
  let r = new Array<number>(n).fill(1 / n);
  for (let it = 1; it <= maxIter; it++) {
    let dangling = 0;
    for (let u = 0; u < n; u++) if (outDeg[u] === 0) dangling += r[u];
    const nr = new Array<number>(n).fill((1 - d) / n + (d * dangling) / n);
    for (const [u, v] of edges) nr[v] += (d * r[u]) / outDeg[u];
    let delta = 0;
    for (let i = 0; i < n; i++) delta += Math.abs(nr[i] - r[i]);
    r = nr;
    if (delta < tol) return { ranks: r, iterations: it };
  }
  throw new Error("PageRank did not converge");
}

function check(ok: boolean, msg: string): void {
  if (!ok) throw new Error(msg);
}

function checkClose(got: number[], want: number[]): void {
  got.forEach((x, i) => check(Math.abs(x - want[i]) < 1e-6, `rank ${i} = ${x}`));
  check(Math.abs(got.reduce((a, b) => a + b, 0) - 1) < 1e-9, "sum");
}

const [A, B, C, D] = [0, 1, 2, 3];
const res = pagerank(4, [[A, B], [A, C], [B, C], [C, A], [D, C]]);
check(res.iterations <= 100, "iterations");
checkClose(res.ranks, [0.372527, 0.195824, 0.394149, 0.0375]);
const r = res.ranks;
check(r[C] > r[A] && r[A] > r[B] && r[B] > r[D], "order");

const res2 = pagerank(3, [[0, 1], [1, 2]]);
check(res2.iterations <= 100, "iterations dangling");
checkClose(res2.ranks, [0.184417, 0.341171, 0.474412]);
console.log(`PageRank converged in ${res.iterations} iterations`);

Wait-for-graph deadlock detector

find_cycle runs an iterative white/grey/black DFS in increasing transaction id order and returns the first cycle found, rotated to start at its smallest id so that every language prints the same thing. resolve repeatedly finds a cycle, aborts the youngest transaction on it (largest id, a common policy because it has usually done the least work), and removes it from the graph. Tests: the four-transaction example above, two independent cycles, and a graph with waiting but no deadlock.

def find_cycle(wait_for: dict[int, list[int]]) -> list[int] | None:
    """Return one cycle (rotated to start at its smallest id) or None."""
    nodes = sorted(set(wait_for) | {v for vs in wait_for.values() for v in vs})
    WHITE, GREY, BLACK = 0, 1, 2
    colour = {v: WHITE for v in nodes}
    for s in nodes:
        if colour[s] != WHITE:
            continue
        colour[s] = GREY
        path = [s]                       # grey vertices, in DFS order
        iters = [0]                      # next out-edge index for each path vertex
        while path:
            u = path[-1]
            out = wait_for.get(u, [])
            if iters[-1] < len(out):
                w = out[iters[-1]]
                iters[-1] += 1
                if colour[w] == GREY:    # back edge: the cycle is path[w..u]
                    cycle = path[path.index(w):]
                    k = cycle.index(min(cycle))
                    return cycle[k:] + cycle[:k]
                if colour[w] == WHITE:
                    colour[w] = GREY
                    path.append(w)
                    iters.append(0)
            else:
                colour[u] = BLACK
                path.pop()
                iters.pop()
    return None


def resolve(wait_for: dict[int, list[int]]) -> list[int]:
    """Abort the youngest transaction on each cycle until none remain. Returns victims."""
    g = {u: list(vs) for u, vs in wait_for.items()}
    victims = []
    while (cycle := find_cycle(g)) is not None:
        victim = max(cycle)
        victims.append(victim)
        g.pop(victim, None)
        for u in g:
            g[u] = [v for v in g[u] if v != victim]
    return victims


if __name__ == "__main__":
    example = {1: [2], 2: [3], 3: [1], 4: [1]}
    assert find_cycle(example) == [1, 2, 3]
    assert resolve(example) == [3]

    two_cycles = {1: [2], 2: [1], 3: [4], 4: [5], 5: [3]}
    assert find_cycle(two_cycles) == [1, 2]
    assert sorted(resolve(two_cycles)) == [2, 5]

    waiting_only = {1: [2], 2: [3], 4: [3]}
    assert find_cycle(waiting_only) is None and resolve(waiting_only) == []

    multi_holder = {1: [2, 3], 3: [4], 4: [1]}   # T1 waits for two shared-lock holders
    assert find_cycle(multi_holder) == [1, 3, 4]
    print("deadlock detector: all tests passed")
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import java.util.TreeSet;

public class DeadlockDemo {
    static List<Integer> findCycle(Map<Integer, List<Integer>> waitFor) {
        TreeSet<Integer> nodes = new TreeSet<>(waitFor.keySet());
        for (List<Integer> vs : waitFor.values()) nodes.addAll(vs);
        Map<Integer, Integer> colour = new HashMap<>();   // 0 white, 1 grey, 2 black
        for (int v : nodes) colour.put(v, 0);
        for (int s : nodes) {
            if (colour.get(s) != 0) continue;
            colour.put(s, 1);
            List<Integer> path = new ArrayList<>(List.of(s));
            List<Integer> iters = new ArrayList<>(List.of(0));
            while (!path.isEmpty()) {
                int top = path.size() - 1, u = path.get(top);
                List<Integer> out = waitFor.getOrDefault(u, List.of());
                if (iters.get(top) < out.size()) {
                    int w = out.get(iters.get(top));
                    iters.set(top, iters.get(top) + 1);
                    if (colour.get(w) == 1) {
                        List<Integer> cycle = new ArrayList<>(path.subList(path.indexOf(w), path.size()));
                        Collections.rotate(cycle, -cycle.indexOf(Collections.min(cycle)));
                        return cycle;
                    }
                    if (colour.get(w) == 0) { colour.put(w, 1); path.add(w); iters.add(0); }
                } else {
                    colour.put(u, 2);
                    path.remove(top);
                    iters.remove(top);
                }
            }
        }
        return null;
    }

    static List<Integer> resolve(Map<Integer, List<Integer>> waitFor) {
        Map<Integer, List<Integer>> g = new TreeMap<>();
        waitFor.forEach((u, vs) -> g.put(u, new ArrayList<>(vs)));
        List<Integer> victims = new ArrayList<>();
        List<Integer> cycle;
        while ((cycle = findCycle(g)) != null) {
            int victim = Collections.max(cycle);
            victims.add(victim);
            g.remove(victim);
            for (List<Integer> vs : g.values()) vs.removeIf(v -> v == victim);
        }
        return victims;
    }

    static Map<Integer, List<Integer>> graph(int[][] edges) {
        Map<Integer, List<Integer>> g = new TreeMap<>();
        for (int[] e : edges) g.computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);
        return g;
    }

    static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }

    public static void main(String[] args) {
        var example = graph(new int[][]{{1, 2}, {2, 3}, {3, 1}, {4, 1}});
        check(List.of(1, 2, 3).equals(findCycle(example)), "example cycle");
        check(List.of(3).equals(resolve(example)), "example victims");

        var two = graph(new int[][]{{1, 2}, {2, 1}, {3, 4}, {4, 5}, {5, 3}});
        check(List.of(1, 2).equals(findCycle(two)), "two cycles");
        List<Integer> v = resolve(two);
        Collections.sort(v);
        check(List.of(2, 5).equals(v), "two victims");

        var waiting = graph(new int[][]{{1, 2}, {2, 3}, {4, 3}});
        check(findCycle(waiting) == null && resolve(waiting).isEmpty(), "no deadlock");

        var multi = graph(new int[][]{{1, 2}, {1, 3}, {3, 4}, {4, 1}});
        check(List.of(1, 3, 4).equals(findCycle(multi)), "multi holder");
        System.out.println("deadlock detector: all tests passed");
    }
}
#include <algorithm>
#include <iostream>
#include <map>
#include <optional>
#include <set>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

using WaitFor = std::map<int, std::vector<int>>;

std::optional<std::vector<int>> find_cycle(const WaitFor& g) {
    std::set<int> nodes;
    for (const auto& [u, vs] : g) { nodes.insert(u); nodes.insert(vs.begin(), vs.end()); }
    std::map<int, int> colour;  // 0 white, 1 grey, 2 black
    for (int v : nodes) colour[v] = 0;
    static const std::vector<int> none;
    for (int s : nodes) {
        if (colour[s] != 0) continue;
        colour[s] = 1;
        std::vector<int> path{s};
        std::vector<size_t> iters{0};
        while (!path.empty()) {
            int u = path.back();
            auto it = g.find(u);
            const auto& out = it == g.end() ? none : it->second;
            if (iters.back() < out.size()) {
                int w = out[iters.back()++];
                if (colour[w] == 1) {
                    std::vector<int> cycle(std::find(path.begin(), path.end(), w), path.end());
                    std::rotate(cycle.begin(), std::min_element(cycle.begin(), cycle.end()), cycle.end());
                    return cycle;
                }
                if (colour[w] == 0) { colour[w] = 1; path.push_back(w); iters.push_back(0); }
            } else {
                colour[u] = 2;
                path.pop_back();
                iters.pop_back();
            }
        }
    }
    return std::nullopt;
}

std::vector<int> resolve(WaitFor g) {
    std::vector<int> victims;
    while (auto cycle = find_cycle(g)) {
        int victim = *std::max_element(cycle->begin(), cycle->end());
        victims.push_back(victim);
        g.erase(victim);
        for (auto& [u, vs] : g) vs.erase(std::remove(vs.begin(), vs.end(), victim), vs.end());
    }
    return victims;
}

WaitFor graph(const std::vector<std::pair<int, int>>& edges) {
    WaitFor g;
    for (auto [u, v] : edges) g[u].push_back(v);
    return g;
}

void check(bool ok, const std::string& msg) { if (!ok) throw std::runtime_error(msg); }

int main() {
    auto example = graph({{1, 2}, {2, 3}, {3, 1}, {4, 1}});
    auto c = find_cycle(example);
    check(c && *c == std::vector<int>{1, 2, 3}, "example cycle");
    check(resolve(example) == std::vector<int>{3}, "example victims");

    auto two = graph({{1, 2}, {2, 1}, {3, 4}, {4, 5}, {5, 3}});
    c = find_cycle(two);
    check(c && *c == std::vector<int>{1, 2}, "two cycles");
    auto v = resolve(two);
    std::sort(v.begin(), v.end());
    check(v == std::vector<int>{2, 5}, "two victims");

    auto waiting = graph({{1, 2}, {2, 3}, {4, 3}});
    check(!find_cycle(waiting) && resolve(waiting).empty(), "no deadlock");

    auto multi = graph({{1, 2}, {1, 3}, {3, 4}, {4, 1}});
    c = find_cycle(multi);
    check(c && *c == std::vector<int>{1, 3, 4}, "multi holder");
    std::cout << "deadlock detector: all tests passed\n";
}
type WaitFor = Map<number, number[]>;

function findCycle(g: WaitFor): number[] | null {
  const all = new Set<number>();
  for (const [u, vs] of g) { all.add(u); vs.forEach((v) => all.add(v)); }
  const nodes = [...all].sort((a, b) => a - b);
  const colour = new Map<number, number>(nodes.map((v) => [v, 0])); // 0 white, 1 grey, 2 black
  for (const s of nodes) {
    if (colour.get(s) !== 0) continue;
    colour.set(s, 1);
    const path = [s];
    const iters = [0];
    while (path.length > 0) {
      const top = path.length - 1, u = path[top];
      const out = g.get(u) ?? [];
      if (iters[top] < out.length) {
        const w = out[iters[top]++];
        if (colour.get(w) === 1) {
          const cycle = path.slice(path.indexOf(w));
          const k = cycle.indexOf(Math.min(...cycle));
          return [...cycle.slice(k), ...cycle.slice(0, k)];
        }
        if (colour.get(w) === 0) { colour.set(w, 1); path.push(w); iters.push(0); }
      } else {
        colour.set(u, 2);
        path.pop();
        iters.pop();
      }
    }
  }
  return null;
}

function resolve(waitFor: WaitFor): number[] {
  const g: WaitFor = new Map([...waitFor].map(([u, vs]) => [u, [...vs]]));
  const victims: number[] = [];
  let cycle: number[] | null;
  while ((cycle = findCycle(g)) !== null) {
    const victim = Math.max(...cycle);
    victims.push(victim);
    g.delete(victim);
    for (const [u, vs] of g) g.set(u, vs.filter((v) => v !== victim));
  }
  return victims;
}

function graph(edges: [number, number][]): WaitFor {
  const g: WaitFor = new Map();
  for (const [u, v] of edges) {
    if (!g.has(u)) g.set(u, []);
    g.get(u)!.push(v);
  }
  return g;
}

function check(ok: boolean, msg: string): void {
  if (!ok) throw new Error(msg);
}
const eq = (a: number[] | null, b: number[]): boolean =>
  a !== null && a.length === b.length && a.every((x, i) => x === b[i]);

const example = graph([[1, 2], [2, 3], [3, 1], [4, 1]]);
check(eq(findCycle(example), [1, 2, 3]), "example cycle");
check(eq(resolve(example), [3]), "example victims");

const two = graph([[1, 2], [2, 1], [3, 4], [4, 5], [5, 3]]);
check(eq(findCycle(two), [1, 2]), "two cycles");
check(eq(resolve(two).sort((a, b) => a - b), [2, 5]), "two victims");

const waiting = graph([[1, 2], [2, 3], [4, 3]]);
check(findCycle(waiting) === null && resolve(waiting).length === 0, "no deadlock");

const multi = graph([[1, 2], [1, 3], [3, 4], [4, 1]]);
check(eq(findCycle(multi), [1, 3, 4]), "multi holder");
console.log("deadlock detector: all tests passed");

Variant: count-to-infinity, simulated

The table in the mechanics section came from this simulation. It models synchronous rounds: every router advertises its current table, then every router recomputes from what it heard.

INF = 16  # RIP's "infinity"


def simulate(poisoned_reverse: bool) -> list[tuple[int, int, int]]:
    """Line A - B - C, all costs 1, destination C. Link B-C has just failed."""
    dist = {"A": 2, "B": 1}
    next_hop = {"A": "B", "B": "C"}
    neighbours = {"A": ["B"], "B": ["A"]}          # B-C is gone
    rows = [(0, dist["A"], dist["B"])]
    for rnd in range(1, 50):
        heard = {}
        for u in dist:
            for v in neighbours[u]:
                poisoned = poisoned_reverse and next_hop[u] == v
                heard[(u, v)] = INF if poisoned else dist[u]
        new_dist, new_hop = {}, {}
        for u in dist:
            best, hop = INF, None
            for v in neighbours[u]:
                cost = min(INF, 1 + heard[(v, u)])
                if cost < best:
                    best, hop = cost, v
            new_dist[u], new_hop[u] = best, hop
        dist, next_hop = new_dist, new_hop
        rows.append((rnd, dist["A"], dist["B"]))
        if dist["A"] == INF and dist["B"] == INF:
            break
    return rows


if __name__ == "__main__":
    plain = simulate(False)
    assert plain[1] == (1, 2, 3) and plain[2] == (2, 4, 3)
    assert plain[-1] == (15, 16, 16) and len(plain) == 16       # 15 rounds to give up
    poisoned = simulate(True)
    assert poisoned == [(0, 2, 1), (1, 2, 16), (2, 16, 16)]     # 2 rounds
    print("count-to-infinity:", len(plain) - 1, "rounds; poisoned reverse:", len(poisoned) - 1)

Variant: mark phase of a tracing garbage collector

def mark(heap: dict[str, list[str]], roots: list[str]) -> set[str]:
    """Iterative DFS from the roots. Returns the set of live objects."""
    live: set[str] = set()
    stack = list(roots)                   # the "mark stack"
    while stack:
        obj = stack.pop()
        if obj in live:
            continue
        live.add(obj)
        stack.extend(p for p in heap.get(obj, []) if p not in live)
    return live


def sweep(heap: dict[str, list[str]], live: set[str]) -> list[str]:
    return sorted(obj for obj in heap if obj not in live)


def refcounts(heap: dict[str, list[str]]) -> dict[str, int]:
    rc = {obj: 0 for obj in heap}
    for ptrs in heap.values():
        for p in ptrs:
            rc[p] += 1
    return rc


if __name__ == "__main__":
    heap = {"a": ["b"], "b": ["c"], "c": ["a"],     # live cycle, reachable from the root a
            "d": ["e"], "e": ["d"],                 # garbage cycle
            "f": []}                                # garbage, no references
    live = mark(heap, roots=["a"])
    assert live == {"a", "b", "c"}
    assert sweep(heap, live) == ["d", "e", "f"]
    rc = refcounts(heap)
    # Reference counting alone would free only f: d and e keep each other at count 1.
    assert [o for o in sorted(heap) if rc[o] == 0] == ["f"]
    print("mark-sweep frees", sweep(heap, live))

Variant: merge-base in a commit DAG

def ancestors(parents: dict[str, list[str]], c: str) -> set[str]:
    """All ancestors of c, including c itself."""
    seen, stack = {c}, [c]
    while stack:
        for p in parents.get(stack.pop(), []):
            if p not in seen:
                seen.add(p)
                stack.append(p)
    return seen


def merge_bases(parents: dict[str, list[str]], a: str, b: str) -> list[str]:
    """Best common ancestors: common ancestors that are not ancestors of another common ancestor."""
    common = ancestors(parents, a) & ancestors(parents, b)
    dominated: set[str] = set()
    for c in common:
        for p in parents.get(c, []):
            dominated |= ancestors(parents, p)
    return sorted(common - dominated)


if __name__ == "__main__":
    # main: A - B - C - D ; feature branched at B: B - E - F
    linear = {"B": ["A"], "C": ["B"], "D": ["C"], "E": ["B"], "F": ["E"]}
    assert merge_bases(linear, "D", "F") == ["B"]
    assert merge_bases(linear, "D", "C") == ["C"]          # fast-forward case
    # criss-cross: B and C both branch from A, then each side merges the other
    criss = {"B": ["A"], "C": ["A"], "M1": ["B", "C"], "M2": ["C", "B"]}
    assert merge_bases(criss, "M1", "M2") == ["B", "C"]    # two best common ancestors
    print("merge-base ok")

Variant: a tiny backtracking version resolver

Real resolvers are far more sophisticated, but the shape is this: pick a package with a pending constraint, try its newest allowed version, add that version's constraints, recurse, and back up on conflict.

Index = dict[str, dict[int, dict[str, set[int]]]]   # package -> version -> {dep: allowed versions}


def resolve(index: Index, root: dict[str, set[int]]) -> dict[str, int] | None:
    def solve(chosen: dict[str, int], constraints: dict[str, set[int]]) -> dict[str, int] | None:
        pending = sorted(p for p in constraints if p not in chosen)
        if not pending:
            return chosen
        pkg = pending[0]
        for ver in sorted(constraints[pkg] & index[pkg].keys(), reverse=True):  # newest first
            merged = dict(constraints)
            ok = True
            for dep, allowed in index[pkg][ver].items():
                narrowed = merged.get(dep, allowed) & allowed
                if not narrowed or (dep in chosen and chosen[dep] not in narrowed):
                    ok = False
                    break
                merged[dep] = narrowed
            if ok:
                result = solve({**chosen, pkg: ver}, merged)
                if result is not None:
                    return result
        return None                                   # every version conflicts: backtrack

    return solve({}, {p: set(v) for p, v in root.items()})


if __name__ == "__main__":
    index: Index = {
        "liba": {2: {"util": {2}}, 1: {"util": {1, 2}}},
        "libb": {2: {"util": {1}}, 1: {"util": {1, 2}}},
        "util": {1: {}, 2: {}},
    }
    # newest liba forces util 2, which rules out libb 2: the resolver settles on libb 1
    assert resolve(index, {"liba": {1, 2}, "libb": {1, 2}}) == {"liba": 2, "libb": 1, "util": 2}
    # pinning libb to 2 forces util 1, which forces liba back to 1
    assert resolve(index, {"liba": {1, 2}, "libb": {2}}) == {"liba": 1, "libb": 2, "util": 1}
    conflict: Index = {"x": {1: {"util": {1}}}, "y": {1: {"util": {2}}}, "util": {1: {}, 2: {}}}
    assert resolve(conflict, {"x": {1}, "y": {1}}) is None
    print("resolver ok")

Variant: triangle counting and clustering coefficient

def count_triangles(n: int, edges: list[tuple[int, int]]) -> int:
    """Orient each edge from lower to higher (degree, id) rank; count each triangle once."""
    deg = [0] * n
    for u, v in edges:
        deg[u] += 1
        deg[v] += 1
    rank = {v: (deg[v], v) for v in range(n)}
    out: list[set[int]] = [set() for _ in range(n)]
    for u, v in edges:
        if rank[u] < rank[v]:
            out[u].add(v)
        else:
            out[v].add(u)
    return sum(len(out[u] & out[v]) for u in range(n) for v in out[u])


def local_clustering(n: int, edges: list[tuple[int, int]]) -> list[float]:
    adj: list[set[int]] = [set() for _ in range(n)]
    for u, v in edges:
        adj[u].add(v)
        adj[v].add(u)
    res = []
    for v in range(n):
        k = len(adj[v])
        links = sum(1 for a in adj[v] for b in adj[v] if a < b and b in adj[a])
        res.append(links / (k * (k - 1) / 2) if k > 1 else 0.0)
    return res


if __name__ == "__main__":
    social = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 4), (4, 5), (3, 5), (5, 6)]
    assert count_triangles(7, social) == 3            # {0,1,2}, {1,2,3}, {3,4,5}
    cc = local_clustering(7, social)
    assert cc[0] == 1.0 and abs(cc[3] - 1 / 3) < 1e-12 and cc[6] == 0.0
    print("triangles:", count_triangles(7, social))

Real-world uses

The rest of the map:

Dependency resolution and package managers

Two separate problems hide inside "install this package". Ordering is easy: once the set of packages is fixed, install dependencies before dependents, which is a topological sort of the dependency DAG; a cycle means no valid order exists, and package systems either reject it or break it with special rules.

Selection is hard: choosing which version of each package to install. In general it is NP-complete. Mancinelli, Boender, Di Cosmo, Vouillon, Durak, Leroy and Treinen proved in 2006 that deciding whether a single Debian package is installable is NP-complete, by encoding 3-SAT as packages with dependencies and conflicts. OPIUM (Tucker, Shuffelton, Jhala and Lerner, ICSE 2007) showed that handing the problem to a SAT/pseudo-boolean solver gives complete, optimal answers where apt's heuristics sometimes failed. Russ Cox's essay "Version SAT" (2016) explains the reduction in engineer's terms and identifies the ingredients that make it hard: a package can depend on specific versions of other packages, and two versions of one package cannot be installed together. Remove either ingredient and the problem gets easier: npm traditionally allows several versions of a package to coexist in nested node_modules, trading disk space and duplicate code for an easy resolution problem, and Go's minimal version selection (2018) allows only "at least version X" constraints and picks the minimum version that satisfies them all, which is a simple graph traversal rather than a search.

In practice: libsolv (used by openSUSE's zypper, Fedora's dnf and conda through libmamba) is a dedicated SAT solver; Dart's pub introduced PubGrub (Natalie Weizenbaum, 2018), a conflict-driven algorithm with human-readable explanations of failure, also used by Python's uv; pip's resolver (since 20.3) is a backtracking search; Cargo uses backtracking with heuristics. The small resolver above shows the backtracking shape; PubGrub and CDCL add learning: when a conflict is found, record the combination that caused it so the search never tries it again. This is the SAT-solver relative of the 2-SAT lesson.

Build systems and incremental computation

A build is a DAG of targets. Make (Stuart Feldman, Bell Labs, 1976) reads rules, builds the dependency graph, and rebuilds a target if any prerequisite has a newer modification time, visiting targets in a topological order by DFS. Incremental builds are reverse reachability: the set of targets to rebuild is everything reachable from the changed files in the reversed DAG, processed in topological order. Bazel and Buck replace timestamps with content hashes, so a target whose inputs hash the same is fetched from a (possibly remote) cache instead of rebuilt, and "Build Systems à la Carte" (Mokhov, Mitchell and Peyton Jones, ICFP 2018) shows that build systems differ along exactly two axes: the scheduler (in what order to visit the graph) and the rebuilder (how to decide a node is stale). Spreadsheets are the same structure with cells as nodes, and a circular reference is a cycle error. See also the monorepo page for build graphs at repository scale.

Social graphs

  • Friend-of-friend. "People you may know" starts with the 2-hop neighbourhood: BFS to depth 2, then rank candidates by the number of common friends (or a weighted variant such as Adamic–Adar). With an average degree of 200, the 2-hop frontier is up to 40,000 edge reads per user, which is why these systems precompute or sample rather than run BFS on demand, and why they sit on graph-aware stores like Facebook's TAO (Bronson et al., USENIX ATC 2013). LinkedIn's "2nd" and "3rd" degree labels are BFS levels.
  • Six degrees. Milgram's 1967 letter-forwarding experiment suggested chains of about six; Watts and Strogatz (Nature, 1998) explained why: a mostly local graph with a few random long-range edges has both high clustering and short paths, the small-world property. Measured on the 2011 Facebook graph (721 million users), the average distance was 4.74 (Backstrom, Boldi, Rosa, Ugander and Vigna, 2012), and Facebook reported 4.57 in 2016 ("three and a half degrees of separation", counting intermediaries rather than hops). These studies estimated distances with probabilistic counters (HyperANF), cousins of Bloom filters.
  • Community detection. Partition the graph so that edges inside groups are denser than chance, measured by modularity (Newman and Girvan, 2004). The Louvain method (Blondel, Guillaume, Lambiotte and Lefebvre, 2008) alternates two phases: move each node to the neighbouring community that most increases modularity until nothing improves, then collapse each community into a single node and repeat on the smaller graph. The Leiden algorithm (Traag, Waltman and van Eck, 2019) fixes Louvain's tendency to produce internally disconnected communities.
  • Triangle counting. The number of triangles, and the clustering coefficient (the fraction of a node's neighbour pairs that are themselves connected), measure how cliquish a network is. Spam and fake accounts tend to have unusually low clustering because their contacts do not know each other, which is why triangle counts appear as features in abuse detection. The degree-ordered algorithm above runs in .

Graph databases

When the questions are "who is connected to whom, within hops, through which relationships", a graph database stores adjacency directly so a traversal step is a pointer dereference rather than an index lookup and join. Neo4j calls this index-free adjacency; query languages such as Cypher and Gremlin compile variable-length path patterns into BFS/DFS with filters. The graph databases page covers the storage and query engine side; the algorithms inside (shortest path, PageRank, Louvain, connected components) are the ones in this module, often shipped as a built-in library.

Garbage collection

Every tracing collector, from McCarthy's original Lisp mark–sweep (1960) to the JVM's G1 and ZGC and Go's concurrent collector, starts by computing reachability from the roots (thread stacks, registers, globals). Mark–sweep uses DFS with an explicit mark stack. Cheney's copying collector (1970) is BFS: it copies roots into the empty half of the heap, then scans the copied objects left to right, copying each object they point to onto the end. The to-space itself is the BFS queue, so it needs no extra memory. Generational collectors trace only the young generation most of the time, treating a remembered set of old-to-young pointers as extra roots. Reference counting (CPython, Swift) frees objects immediately when their count drops to zero but cannot free cycles; CPython adds a cycle-detecting collector for exactly the "d ↔ e" case in the variant above. The memory allocators page and runtime internals cover the allocation side.

Deadlock detection in practice

PostgreSQL waits deadlock_timeout (1 second by default) before running its detector, betting that most lock waits resolve on their own and the DFS is not worth running on every wait; when it finds a cycle it aborts one transaction with an error. MySQL's InnoDB checks immediately when a transaction blocks (configurable with innodb_deadlock_detect) and rolls back the transaction it judges smallest by rows modified. Distributed databases cannot see one global wait-for graph; Chandy, Misra and Haas's edge-chasing algorithm (1983) sends probe messages along wait edges and declares deadlock when a probe returns to its sender. Many systems avoid detection altogether: wait-die and wound-wait (Rosenkrantz, Stearns and Lewis, 1978) use transaction timestamps so that waits only ever go from older to younger (or the reverse), which makes cycles impossible. Lock ordering in application code (always lock accounts in id order) is the same idea: if every wait edge goes "upward" in a total order, the wait-for graph is a DAG. More in the deadlocks page.

Knowledge graphs

A knowledge graph stores facts as labelled edges (subject, predicate, object): (Paris, capital_of, France). Google introduced its Knowledge Graph in 2012; Wikidata is the largest open one. SPARQL property paths (:parent+ = one or more parent edges) are regular path queries: BFS over the product of the graph and a small automaton. Personalized PageRank from the query entities is a classic baseline for entity ranking.

Fraud rings

A fraud ring is a set of accounts controlled by one actor, and they give themselves away by sharing things: devices, phone numbers, card numbers, shipping addresses, IP ranges. Build a graph with accounts and identifiers as nodes; union-find over shared identifiers groups accounts into connected components, and components that are unusually large or dense are flagged for review. Money laundering detection looks for cycles in transaction graphs (money leaving and returning through intermediaries), and PageRank variants that propagate "trust" from known-good seeds (TrustRank, Gyöngyi, Garcia-Molina and Pedersen, 2004) are standard features.

Maps and navigation

Covered in the ladder: Dijkstra is the correctness baseline; A*, ALT and contraction hierarchies make it fast enough to serve. Real systems add turn costs (road segments as nodes, allowed turns as edges) and time-dependent weights for traffic. The geometric side, snapping GPS points to roads and finding nearby candidates, uses the structures in spatial indexing.

Git's commit graph

A Git repository is a DAG of commits, each pointing at its parents (see Git internals). Many everyday commands are graph algorithms:

  • git merge-base A B returns the best common ancestors: common ancestors of A and B that are not ancestors of another common ancestor. In a tree this is the unique lowest common ancestor; in a DAG there can be several, as the criss-cross test above shows. Git's recursive merge strategy handled that case by first merging the merge bases into a virtual ancestor; the newer ort strategy keeps the same idea. The implementation walks backward from both tips at once, painting commits with "reachable from A" and "reachable from B" flags, and uses generation numbers stored in the commit-graph file (Git 2.18 and later) to stop early instead of walking all history.
  • git log A..B lists commits reachable from B but not from A: a set difference of two reachability searches.
  • git bisect is binary search on a DAG: pick a commit that splits the remaining candidates roughly in half by reachability, test it, discard half.
  • git gc and git prune delete objects unreachable from any ref or reflog: the garbage-collection mark phase, applied to version control.

Pitfalls & edge cases

  • Dangling nodes in PageRank. Forgetting them makes ranks sum to less than 1 and leak away over iterations. Redistribute their mass uniformly (or to a personalization vector) every iteration.
  • Normalizing PageRank. The 1998 paper's form sums to , the modern form sums to 1. Mixing the two across components of a system gives ranks off by a factor of .
  • Convergence tests on rank changes, not on rank order. Orders can stabilize long before values do, or flip between two nearly tied pages for many iterations. Decide which one the product needs.
  • Treating blocked as deadlocked. A transaction waiting on a chain that ends in a running transaction is not deadlocked. Only cycles count; aborting non-cycle waiters destroys throughput.
  • Victim selection that starves. If the same transaction is always the youngest on a cycle and gets aborted and retried, it can starve. Real systems age transactions, keep the original timestamp across retries (as wound-wait does), or weigh work done.
  • Count-to-infinity in custom gossip protocols. Any system that propagates "distance to X" hop by hop (service meshes, overlay networks, gossip protocols) can reproduce RIP's problem. Carry the path, a sequence number (as AODV and Babel do), or a bounded infinity.
  • Topological sort with cycles. Kahn's algorithm silently outputs fewer than nodes when there is a cycle. Always check the count, and report the cycle (with the DFS cycle finder above) instead of a truncated order.
  • "Latest version" is not always solvable. Resolvers that greedily take the newest version of everything without backtracking fail on inputs a backtracking resolver handles, as the second resolver test shows.
  • GC roots you forgot. Missing a root (a pointer held only in a register, a native handle) frees a live object: the worst kind of bug. Conservative collectors treat anything that looks like a pointer as one for this reason.

Variations

  • HITS (Kleinberg, 1999) computes query-dependent hub and authority scores from the principal eigenvectors of and .
  • Personalized PageRank and TrustRank change the jump distribution from uniform to a seed set; they power "related items", trust propagation and many fraud features.
  • Betweenness centrality (Brandes' algorithm, unweighted) counts shortest paths through a node, useful for finding bottlenecks.

Practice ladder

Problems 1–12 are LeetCode problems that are small versions of the systems above; 13–15 are implementation exercises. Problem statements are paraphrased in my own words; follow the links for the formal versions.

1. Keys and Rooms (LeetCode 841) — Rooms contain keys to other rooms; starting from room 0, can you enter every room? This is the GC mark phase: reachability from a root.

Hint

DFS or BFS from room 0, marking visited rooms; compare the count with the number of rooms.

Solution
def can_visit_all_rooms(rooms: list[list[int]]) -> bool:
    seen = {0}
    stack = [0]
    while stack:
        for key in rooms[stack.pop()]:
            if key not in seen:
                seen.add(key)
                stack.append(key)
    return len(seen) == len(rooms)


assert can_visit_all_rooms([[1], [2], [3], []]) is True
assert can_visit_all_rooms([[1, 3], [3, 0, 1], [2], [0]]) is False   # room 2 unreachable

: every room and key is processed once.

2. Get Watched Videos by Your Friends (LeetCode 1311) — Collect videos watched by people at exactly distance from you in a friendship graph, sorted by frequency. Friend-of-friend queries as BFS levels.

Hint

BFS level by level, stopping at level ; count videos with a hash map; sort by (count, name).

3. Course Schedule (LeetCode 207) — Decide whether prerequisite rules allow finishing all courses. A package manager's cycle check, or a deadlock detector on a static graph.

Hint

Kahn's algorithm: repeatedly take courses with no remaining prerequisites; if you take fewer than , there is a cycle.

Solution
from collections import deque


def can_finish(n: int, prereqs: list[list[int]]) -> bool:
    adj: list[list[int]] = [[] for _ in range(n)]
    indeg = [0] * n
    for course, pre in prereqs:
        adj[pre].append(course)
        indeg[course] += 1
    q = deque(v for v in range(n) if indeg[v] == 0)
    taken = 0
    while q:
        u = q.popleft()
        taken += 1
        for w in adj[u]:
            indeg[w] -= 1
            if indeg[w] == 0:
                q.append(w)
    return taken == n


assert can_finish(2, [[1, 0]]) is True
assert can_finish(2, [[1, 0], [0, 1]]) is False
assert can_finish(4, [[1, 0], [2, 1], [3, 2], [1, 3]]) is False

.

4. Course Schedule II (LeetCode 210) — Output a valid order, or nothing if impossible. Exactly an install order.

Hint

The same Kahn loop, appending each dequeued course to the answer; return an empty list if the answer is short.

5. Find All Possible Recipes from Given Supplies (LeetCode 2115) — Recipes need ingredients, some of which are other recipes; given basic supplies, which recipes can be made? Build-system logic: a target is buildable when all its inputs are.

Hint

Kahn's algorithm over ingredients → recipes, seeded with the supplies; recipes in a cycle never reach in-degree 0.

6. Network Delay Time (LeetCode 743) — A signal spreads from one node over weighted directed links; how long until all nodes have it? One OSPF SPF run.

Hint

Dijkstra from the source; the answer is the maximum distance, or if some node is unreachable.

Solution
import heapq


def network_delay_time(times: list[list[int]], n: int, k: int) -> int:
    adj: dict[int, list[tuple[int, int]]] = {v: [] for v in range(1, n + 1)}
    for u, v, w in times:
        adj[u].append((v, w))
    dist: dict[int, int] = {}
    pq = [(0, k)]
    while pq:
        d, u = heapq.heappop(pq)
        if u in dist:
            continue
        dist[u] = d
        for v, w in adj[u]:
            if v not in dist:
                heapq.heappush(pq, (d + w, v))
    return max(dist.values()) if len(dist) == n else -1


# the OSPF example from this lesson, as directed links both ways, numbered R1..R5 -> 1..5
links = [(1, 2, 10), (1, 3, 1), (2, 3, 2), (2, 4, 1), (3, 5, 7), (4, 5, 3)]
times = [[u, v, w] for u, v, w in links] + [[v, u, w] for u, v, w in links]
assert network_delay_time(times, 5, 1) == 7
assert network_delay_time([[1, 2, 1]], 2, 2) == -1

.

7. Cheapest Flights Within K Stops (LeetCode 787) — Cheapest route with at most intermediate stops. Bellman–Ford limited to rounds, which is precisely what rounds of distance-vector exchange compute.

Hint

Run relaxation rounds, each reading from a copy of the previous round's distances so a single round cannot chain several edges.

Solution
def find_cheapest_price(n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:
    INF = float("inf")
    dist = [INF] * n
    dist[src] = 0
    for _ in range(k + 1):                  # round i = routes with at most i edges
        prev = dist[:]                      # what neighbours advertised last round
        for u, v, w in flights:
            if prev[u] + w < dist[v]:
                dist[v] = prev[u] + w
    return -1 if dist[dst] == INF else int(dist[dst])


fl = [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]]
assert find_cheapest_price(4, fl, 0, 3, 1) == 700
assert find_cheapest_price(4, fl, 0, 3, 2) == 400
assert find_cheapest_price(3, [[0, 1, 100], [1, 2, 100], [0, 2, 500]], 0, 2, 0) == 500

time, memory.

8. Find Eventual Safe States (LeetCode 802) — Nodes from which every path ends at a terminal node. The complement is every node that can reach a cycle: processes that can get dragged into a deadlock.

Hint

Three-colour DFS: a node is safe iff it finishes black without ever touching a grey node. Or run Kahn on the reversed graph from the terminal nodes.

9. Accounts Merge (LeetCode 721) — Merge account records that share any email address. Fraud-ring grouping by shared identifiers.

Hint

Union-find over emails (or accounts); group by root; sort each group.

10. Lowest Common Ancestor of a Binary Tree (LeetCode 236) — The tree version of git merge-base. Teaches the base case before the DAG generalization in the variant above.

Hint

Recursive: return the node if it is one of the targets; if both subtrees return non-null, the current node is the LCA.

11. Minimum Degree of a Connected Trio in a Graph (LeetCode 1761) — Among all triangles, minimize the number of edges leaving the triangle. Triangle enumeration, the core of clustering-coefficient computation.

Hint

For each edge and each common neighbour , the trio degree is . Adjacency as a matrix or bitsets for .

Solution
def min_trio_degree(n: int, edges: list[list[int]]) -> int:
    adj = [set() for _ in range(n + 1)]
    for u, v in edges:
        adj[u].add(v)
        adj[v].add(u)
    best = float("inf")
    for u, v in edges:
        for w in adj[u] & adj[v]:
            best = min(best, len(adj[u]) + len(adj[v]) + len(adj[w]) - 6)
    return -1 if best == float("inf") else int(best)


assert min_trio_degree(6, [[1, 2], [1, 3], [3, 2], [4, 1], [5, 2], [3, 6]]) == 3
assert min_trio_degree(7, [[1, 3], [4, 1], [4, 3], [2, 5], [5, 6], [6, 7], [7, 5], [2, 6]]) == 0
assert min_trio_degree(3, [[1, 2], [2, 3]]) == -1

with hash sets; bounded by if you only intersect from the lower-degree endpoint.

12. Sort Items by Groups Respecting Dependencies (LeetCode 1203) — Order items so that dependencies come first and items of the same group are contiguous. A two-level build graph: modules, and files inside modules.

Hint

Give ungrouped items their own singleton groups. Topologically sort the groups (edges from inter-group dependencies), then topologically sort items inside each group; any cycle at either level means no answer.

13. Implementation: PageRank on a real web graph. Download the SNAP web-Google dataset (about 875,000 pages and 5 million links), store it as compressed sparse rows, and run the power iteration above. Measure iterations to , time per iteration, and how much reordering vertices by in-degree changes the time. Then add a personalization vector and compare the top-10 pages for two different seeds.

Hint

Use NumPy: build CSR arrays, then each iteration is np.add.at or a sparse matrix–vector product (scipy.sparse). Expect tens of iterations and well under a second per iteration on a laptop.

14. Implementation: a distance-vector simulator. Extend the count-to-infinity variant to an arbitrary topology with asynchronous, randomly ordered updates. Add split horizon, poisoned reverse and triggered updates, and find a three-router loop where poisoned reverse alone still counts to infinity. Compare against the network layer page's description of RIP.

Hint

A triangle A–B–C with a stub D behind C: when C–D fails, A and B can each believe the other still reaches D. Log every advertisement to see the loop.

15. Implementation: a mini make. Parse a file of target: dep1 dep2 rules, detect cycles (print the cycle with the DFS finder), compute the set of stale targets given a list of changed files (reverse reachability), and print the rebuild order (topological sort restricted to that set). Stretch goal: run independent targets in parallel with a worker pool, Kahn-style, as make -j does. The topological sort lesson has the ordering half.

Hint

Keep both the forward graph (target → deps) and the reverse graph (dep → targets). Stale set = BFS from changed files over the reverse graph. Order = Kahn over the induced subgraph.

Common mistakes & interview follow-ups

  • "How would you compute PageRank for a billion pages?" Power iteration over a partitioned edge list (Pregel/Spark style): each superstep, vertices send rank/out-degree along edges, receivers sum. Discuss dangling mass (a global aggregate per step), convergence checks (another aggregate), and stragglers. Mention that iterations do not grow with .
  • "Why 0.85?" Higher follows links more faithfully but converges more slowly (error bound ) and is more sensitive to graph changes; lower washes out the link signal. It was an empirical choice, not a derived constant.
  • "How do you stop link spam?" TrustRank-style seeding from vetted pages, discounting links within one site, and detecting dense link farms by their odd degree and triangle statistics.
  • "OSPF or RIP for a large network, and why?" OSPF: link state converges quickly and has no count-to-infinity, at the cost of flooding and memory for the full map; areas keep that bounded. RIP's 15-hop limit and slow convergence restrict it to small networks.
  • "Why doesn't BGP just use Dijkstra?" No AS will share its full internal topology or let others choose its routes; BGP must express policy (who pays whom), and it scales by exchanging only reachability with paths. The path also gives loop detection.
  • "Your package manager hangs on resolution. Why?" Version selection is NP-complete in general; a backtracking resolver can explore exponentially many combinations. Remedies: better heuristics, conflict learning (PubGrub/CDCL), tighter constraints, lockfiles that skip resolution, or a restricted model (minimal version selection).
  • "How does the database pick which transaction to abort?" It finds a cycle in the wait-for graph and picks a victim by policy: youngest, least work done, or fewest locks. Follow-up: how do you avoid starvation? Keep the original timestamp across retries.

Quick quiz

1. In the four-page example, why is D's PageRank exactly , and what would change if D linked to nobody instead of to C?

Answer

D has no in-links, so it only receives the random-jump share . If D linked to nobody, it would be dangling: its rank would be spread uniformly over all four pages each iteration instead of going to C. D's own rank would rise slightly, because it would receive part of its own mass back, and C's would fall.

2. Prove in two lines that power iteration on the Google matrix converges for any starting distribution.

Answer

For probability vectors : because the jump terms cancel, and for column-stochastic . So is a contraction with factor in L1, and Banach's fixed-point theorem gives geometric convergence to the unique fixed point.

3. A–B–C in a line, link B–C fails, RIP without split horizon. Why does B think it can still reach C, and roughly how long until both routers give up?

Answer

A still advertises "C at distance 2", and B cannot tell that A's route goes through B. Distances climb by about 2 every 2 rounds until hitting 16; the simulation takes 15 rounds, which at RIP's 30-second update interval is over 7 minutes without triggered updates.

4. A transaction is blocked waiting for a lock. Is it deadlocked? What do you check?

Answer

Not necessarily. Follow wait-for edges from it: it is deadlocked only if it lies on a cycle (in the AND model). If its chain ends at a transaction that is running, it will eventually proceed.

5. Why can git merge-base return two commits, when "lowest common ancestor" in a tree is always unique?

Answer

The commit graph is a DAG, not a tree: a commit can have several parents. In a criss-cross history, two common ancestors can each fail to be an ancestor of the other, so both are "best".

Further reading / sources

  • Sergey Brin and Lawrence Page, "The anatomy of a large-scale hypertextual Web search engine", Computer Networks and ISDN Systems 30(1–7), 1998; Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, "The PageRank citation ranking: bringing order to the Web", Stanford technical report, 1999.
  • Amy N. Langville and Carl D. Meyer, Google's PageRank and Beyond: The Science of Search Engine Rankings, Princeton University Press, 2006 (dangling nodes, convergence, the Google matrix); Taher Haveliwala and Sepandar Kamvar, "The second eigenvalue of the Google matrix", Stanford technical report, 2003.
  • Grzegorz Malewicz et al., "Pregel: a system for large-scale graph processing", SIGMOD 2010.
  • J. Moy, RFC 2328 "OSPF Version 2" (1998); G. Malkin, RFC 2453 "RIP Version 2" (1998); Y. Rekhter, T. Li, S. Hares, RFC 4271 "A Border Gateway Protocol 4 (BGP-4)" (2006); Timothy G. Griffin, F. Bruce Shepherd, Gordon Wilfong, "The stable paths problem and interdomain routing", IEEE/ACM Transactions on Networking 10(2), 2002; James Kurose and Keith Ross, Computer Networking: A Top-Down Approach, chapter 5 "The Network Layer: Control Plane".
  • Fabio Mancinelli et al., "Managing the complexity of large free and open source package-based software distributions", ASE 2006; Chris Tucker, David Shuffelton, Ranjit Jhala, Sorin Lerner, "OPIUM: Optimal Package Install/Uninstall Manager", ICSE 2007; Russ Cox, "Version SAT", 2016, and "Minimal Version Selection", 2018.
  • Andrey Mokhov, Neil Mitchell, Simon Peyton Jones, "Build systems à la carte", ICFP 2018; Stuart I. Feldman, "Make — a program for maintaining computer programs", Software: Practice and Experience 9(4), 1979.
  • Vincent D. Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre, "Fast unfolding of communities in large networks", Journal of Statistical Mechanics, 2008; V. A. Traag, L. Waltman, N. J. van Eck, "From Louvain to Leiden: guaranteeing well-connected communities", Scientific Reports 9, 2019; Duncan J. Watts and Steven H. Strogatz, "Collective dynamics of 'small-world' networks", Nature 393, 1998; Lars Backstrom et al., "Four degrees of separation", WebSci 2012.
  • Richard Jones, Antony Hosking, Eliot Moss, The Garbage Collection Handbook, 2nd ed., 2023, chapters 2 "Mark-sweep garbage collection", 4 "Copying garbage collection" and 15 "Concurrent garbage collection"; C. J. Cheney, "A nonrecursive list compacting algorithm", Communications of the ACM 13(11), 1970; Edsger W. Dijkstra et al., "On-the-fly garbage collection: an exercise in cooperation", Communications of the ACM 21(11), 1978.
  • Abraham Silberschatz, Peter Galvin, Greg Gagne, Operating System Concepts, chapter 8 "Deadlocks" (wait-for graphs, detection); K. Mani Chandy, Jayadev Misra, Laura Haas, "Distributed deadlock detection", ACM Transactions on Computer Systems 1(2), 1983; the PostgreSQL documentation for deadlock_timeout and the MySQL documentation "Deadlock Detection".
  • Robert Geisberger, Peter Sanders, Dominik Schultes, Daniel Delling, "Contraction hierarchies: faster and simpler hierarchical routing in road networks", WEA 2008; Andrew V. Goldberg and Chris Harrelson, "Computing the shortest path: A* search meets graph theory", SODA 2005; Hannah Bast et al., "Route planning in transportation networks", 2016 survey (arXiv:1504.05140).
  • The Git documentation for git merge-base, and Derrick Stolee's blog series on the commit-graph file and generation numbers.

Previous lesson: 2-SAT, Graph Coloring & Other Classic Graph Problems · Next lesson: Capstone

Related: Module 4 overview · Shortest Paths · Topological Sort · Graph Databases · Deadlocks · BGP · Network Layer · LCA & Binary Lifting · Course home