Storing a graph

Below are the streets of central Almaty as an adjacency matrix: a row and a column are an intersection, a dot is a stretch of street between two intersections. There are 7909 intersections, 62,552,281 cells in the matrix, and 20,778 dots: 0.03% of the matrix is filled. Switch the order of the vertices: it decides where these dots fall, although the graph is one and the same.

In a random order the dots are scattered over the whole matrix. In the file’s order they huddle near the diagonal: OpenStreetMap writes the intersections of one street next to each other. If the intersections are ordered along a Hilbert curve, which goes round the map in squares, the dots gather into a narrow band: intersections that are neighbours on the map get close numbers. For a computer this is not just pretty: a vertex’s neighbours end up close in memory too, and a graph traversal misses the cache less often.

The idea

A graph is vertices and edges, but a program needs not a picture but answers to questions: who are the neighbours of vertex v, is there an edge between u and v, go over all the edges. Each form of a graph makes some questions cheap and others expensive, and spends different amounts of memory on it.

Let there be n vertices and m edges. Here are the four main forms on a small piece of the same map, fourteen intersections near Republic Square. Tap the intersections:

• Adjacency matrix: an n × n table with a one wherever there is an edge. “Is there an edge u–v” is one access. But going over a vertex’s neighbours means going through its whole row of n cells, and the memory needed is n² cells whatever the number of edges.
• Adjacency lists: each vertex has a list of neighbours. Going over the neighbours costs as much as there are of them, memory is O(n + m). Checking an edge means running through the list of the smaller vertex.
• Edge list: just the pairs (u, v), the way a graph lies in a file. Convenient for going over all the edges or sorting them by weight, as in Kruskal’s algorithm. Finding a vertex’s neighbours means going over all the edges.
• CSR (compressed sparse row): the same lists, but laid out one after another in one array targets, with an array start saying where each vertex’s list begins. Two dense arrays instead of thousands of small lists: less memory on bookkeeping fields, and neighbours lie in a row. This is how graph libraries and the scenes of this catalogue store graphs, and sparse matrices in numerical libraries are built the same way.

Code

All four forms for the streets of Almaty, and how much they take if a vertex number is four bytes:

The matrix of bits is 7.8 megabytes, the matrix of bytes 62.5 megabytes, and CSR 115 kilobytes: 68 times less than even the bit matrix. The reason is that roads are a sparse graph: an intersection has from one to five neighbours, and there are about as many edges as vertices, not n². Almost all real large graphs are like this: roads, links, dependencies, friends. A matrix pays off only for dense graphs, with edges of order n², and for algorithms that look at all pairs of vertices anyway, like Floyd–Warshall.

Traversal: square against line

Going breadth first through a graph stored as a matrix means looking at the whole row of each vertex: n² steps, however many edges there are. With lists or CSR it is n + m. A benchmark on growing pieces of the same graph:

The matrix has slope 2: double the graph and the time grows fourfold, and on all 7909 intersections a traversal over the matrix in Go takes tens of times longer than over the lists. In Go CSR and the lists run almost level: the graph is still too small for cache misses to show, and CSR wins on graphs of millions of vertices, where dense arrays save both memory and trips to it. In Python CSR, on the contrary, is almost twice as slow: the slice targets[a:b] copies the neighbours into a new list, while the adjacency lists have it ready. One more reason to measure in your own language.

What costs what

The forms can and should be combined. If “is there an edge” is asked often and a matrix does not fit, a hash set of pairs is kept beside the lists; this is how the first problem of the article is solved. CSR is awkward to change, so a graph is assembled in lists or an edge list and then turned into CSR once and only read after that.

And do not forget the order of the vertices. A numbering in which neighbours on the map are neighbours in the array too makes every traversal faster, although the asymptotics do not change. Curves that number the plane this way are the subject of the article on Hilbert curves.

Problems

In the first the graph is too big for a matrix, while the questions are exactly the ones a matrix answers best of all. In the second the right form turns going over pairs of neighbours into an almost linear count of triangles; among the tests are the imports of the Go standard library and of this site’s modules.