Chapter Eight · Graphs

Graphs

Things and the connections between them: the shape underneath routers, package managers, build pipelines and every object graph a garbage collector walks. Five topics choose how to store a graph, visit it, order it, find the cheapest path through it, and ask what keeps it connected.

5 topics

A build that fails only when parallelism is switched on. An install that stalls for two minutes before downloading anything. A route planner that sends a van down a road that looks short on the map. A network that stays up until one particular cable is cut. Each of these is a graph problem, and each has a known answer with a known price, once someone draws the nodes and the edges.

This chapter teaches that drawing and what follows from it. It starts with the modelling decisions, what a node is, what an edge is, which way it points, and how the whole thing sits in memory, because those set every later cost. It then visits a graph in the two basic orders, breadth-first and depth-first, and uses the second to order a graph of tasks: the topological sort behind every build, install and pipeline, and the critical path that sets how fast any of them can possibly run.

The last two topics add weights. Dijkstra's algorithm finds the cheapest path as long as no edge is negative, and the spanning tree finds the cheapest network that still connects everything, which turns out to be the most fragile network there is. No running example appears here: routers, packages and pipelines are smaller and clearer than any library search service.

Five questions, five algorithms, one graph

Fewest hops from here to there→Breadth-first search: O(n + e)

Is there a cycle, and what is reachable→Depth-first search: O(n + e)

In what order can these tasks run→Topological sort: O(n + e)

Cheapest path when edges have costs→Dijkstra: O((n + e) log n)

Cheapest links that connect everything→Kruskal or Prim: O(e log e)