Modelling With Graphs

A graph is a set of things and the connections between them. Once a problem is drawn that way, a whole toolbox applies to it unchanged: the search that finds a route between two cities also finds the order in which to build a project, and the list of services that go down when the database does. The algorithms in the rest of this chapter never ask what the things are. They ask only which things connect.

That makes the modelling step the one with the consequences. What counts as a node, what counts as an edge, which way the edge points, what its weight means and how the whole structure sits in memory are all decided before any algorithm runs, and each decision sets a cost the algorithm cannot undo.

Nodes, Edges, Direction and Weight

A node is one thing: a router, a package, a web page, a person. An edge connects two nodes. It can be two-way, like a cable or a friendship, where A connected to B means B connected to A. Or it can be one-way, like "package A depends on package B" or "page A links to page B", where the reverse is a different claim that may be false. An edge can also carry a weight, a number that says what crossing it costs: kilometres, milliseconds, money.

The figure draws the same five nodes three times. On the left the edges have no direction. In the middle each one is an arrow. On the right each carries a weight. Every algorithm in this chapter reads one of those three pictures, and feeding it the wrong one gives a confident, wrong answer.

Two familiar structures are special cases. A tree, from Chapter 6, is a connected graph with no cycles, so there is exactly one path between any two of its nodes. A linked list is a tree with a single branch. The graph in the figure is neither: D can be reached from A through B or through C, and that second route is what makes it a graph.

Graphs in Systems You Already Run

Routers and the links between them form a weighted graph, with latency or link cost as the weight. A project's dependencies form a directed graph, and it stops being a tree the moment two packages share a third. Calls between services form a directed graph whose reversed edges answer "who breaks if this fails". Hyperlinks form the directed graph a crawler walks. The objects inside a running program, each holding references to others, form the graph that Chapter 4's garbage collector traverses. Foreign keys between database tables form one too.

Naming the graph is the step that unlocks the rest of the chapter. "Which services fail if the auth service fails" becomes reachability over reversed edges. "In what order do we deploy" becomes a topological sort. "What is the cheapest path between two data centres" becomes a shortest-path problem. None of those questions needs new code once the nodes and edges are written down.

The Adjacency Matrix

The first way to store a graph is a table with one row and one column per node, holding a mark wherever an edge exists. Asking "is there an edge from A to B" is a single lookup. It pays in memory: the table has n² cells whatever the number of edges, and listing one node's neighbours means scanning its whole row of n cells, most of them empty.

For five nodes that is 25 cells, and nobody cares. For a million nodes it is a trillion cells, which comes to 125 gigabytes even packed at one bit per cell. A social network or a road map with a million nodes has perhaps ten edges per node, so almost every one of those trillion cells would hold a zero.

The Adjacency List

The second way stores, for each node, the list of its neighbours. Memory grows with the number of nodes plus the number of edges, not with the square of the nodes. Visiting a node's neighbours costs its degree, the number of edges it has, and a node with three neighbours costs three steps. Testing for one particular edge means searching that node's list, or keeping a set of neighbours per node to make the test constant time on average.

A million nodes with ten edges each is 10 million list entries, about 80 megabytes at 8 bytes per entry, against 125 gigabytes for the matrix. Nearly every graph a working engineer meets is sparse like this, with far fewer edges than n², so the adjacency list is the default and the matrix is kept for small or dense graphs.

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D"],
    "D": ["E"],
    "E": [],
}

In Python the adjacency list is usually a dictionary, as above: each key is a node and its value is the list of nodes it points to. A has two neighbours, B and C; B and C both point to D; D points to E; E points nowhere. Five nodes and five edges take five dictionary entries holding five neighbours in total.

Graphs That Are Never Stored

Some graphs are far too large to write down. The positions of a sudoku, the states of a sliding puzzle and the configurations a model checker explores are all nodes, and an edge joins two of them when one move turns the first into the second. Nobody stores those edges. A function computes a node's neighbours from a rule at the moment the search asks for them, and Chapter 9's backtracking search walks such a graph.

The traversals in the next topic work on these implicit graphs unchanged, because all they ever ask is "what are the neighbours of this node". The only thing kept in memory is the set of nodes already visited, which on a well-pruned search is a vanishing fraction of the whole graph.

What the Representation Costs

A graph built from Python objects that hold references to each other is natural to write and slow to walk. Following an edge is a pointer chase: the next node's address is known only after the current node has been read, so the processor cannot fetch ahead, and each hop is a likely cache miss of about 100 nanoseconds on Chapter 4's ladder. Chapter 5 found the same problem in linked lists. A million edges followed that way can spend a tenth of a second in misses alone.

The packed alternative stores the graph in two flat arrays. One holds every neighbour list back to back. The other holds offsets, one per node, saying where that node's run of neighbours starts. In the figure, A's neighbours sit at positions 0 and 1 of the neighbour array, because A's offset is 0 and B's is 2. A walk over this layout reads memory in order, the processor's prefetcher streams it at memory bandwidth, and large graphs that are read far more often than they change are laid out this way in graph libraries.

The choice follows the dominant operation, as Chapter 5 showed for containers. If the question is mostly "is there an edge", a matrix or a set per node answers it. If it is mostly "visit every neighbour", a list answers it, and a packed list answers it at the speed of the memory bus. The Big-O is the same for both lists; the cache lines are not.