Writing a Graph Down

Last timeThings and the Links Between Them

There are two ways to store a graph, a table of every pair or a list of neighbours per point, and the density of the graph decides which one is right.

Two arrangements

A graph on paper is a drawing, and a drawing is not a thing a machine can walk

over. There are two standard ways to write one down, and nearly every real

system uses one of them.

The first is a square table with a row and a column for every point. The cell

where row $u$ meets column $v$ records whether there is a link from $u$ to

$v$ , as a yes or no, or as the cost when the links carry one. The second is a

list for every point, holding the points it is linked to and nothing else.

Both hold the same graph. They cost wildly different amounts, and they make

different questions cheap, so the choice is a real one.

FIG 1The same six point graph, as a table

	a	b	c	d	e	f
a	0	1	1	0	0	0
b	1	0	0	1	0	0
c	1	0	0	1	0	0
d	0	1	1	0	1	0
e	0	0	0	1	0	1
f	0	0	0	0	1	0

Thirty six cells holding seven links, each recorded twice because the graph is undirected. The two marked cells are the row for a, which says a is linked to b and to c. Twenty two of the thirty six cells record that no link exists, and in a realistic graph that proportion is far worse.

What the table costs

The table has $n^2$ cells and it has them whatever the graph looks like. An

empty graph on a thousand points takes a million cells. A graph with two links

takes a million cells. The memory is decided by the number of points alone,

which is the whole problem with it.

In exchange, one question becomes instant: is there a link from $u$ to $v$ .

Look at one cell. No searching, no following, one fetch. That is a genuinely

valuable property for some work, and it is worth being clear about which work.

FIG 2What each arrangement costs to store

: the number of points
: the number of links

The neighbour lists need one slot per point to find its list, plus one entry per link at each of its two ends. The table ignores m entirely, which is why it is ruinous on a sparse graph and perfectly reasonable on a dense one.

What the lists cost

The neighbour lists cost $n + 2m$ entries, so a graph with a million points

and three million links takes seven million entries rather than a thousand

thousand million cells. That is the difference between fitting in memory and

not, and it is why this is the normal representation.

The question the lists answer cheaply is: what is next to this point. Go to

the point's list and read it. The cost is the length of that list, which is

the number of neighbours it actually has, so reading every neighbour of every

point costs $2m$ in total rather than $n^2$ .

The question they answer badly is the one the table is good at. Asking whether

$u$ links to $v$ means searching $u$ 's list, which costs as long as the list.

The lesson stops here

2 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents