Graphs and how to store them

Six vertices joined by seven edges, stored twice. Watch each edge set two cells of a grid and add a node to two lists.

⋯12static void push_arc(struct enode **list, int u, int v)13{14    struct enode *e = malloc(sizeof *e);15    if (e == NULL)16        exit(1);17    e->to = v;18    e->next = list[u];19    list[u] = e;20}21 22static void add_edge(int adj[V][V], struct enode **list, int u, int v)23{24    adj[u][v] = 1;25    adj[v][u] = 1;26    push_arc(list, u, v);27    push_arc(list, v, u);28}29 30int main(void)31{32    const int edges[E][2] = { { 4, 5 }, { 3, 4 }, { 2, 4 }, { 1, 3 }, { 1, 2 }, { 0, 2 }, { 0, 1 } };33    int adj[V][V] = { { 0 } };34    struct enode *list[V] = { NULL };35    for (int i = 0; i < E; i++)36        add_edge(adj, list, edges[i][0], edges[i][1]);37#ifdef EXTRA_U38    add_edge(adj, list, EXTRA_U, EXTRA_V);39#endif40    for (int u = 0; u < V; u++) {41        for (int v = 0; v < V; v++)42            printf("%d ", adj[u][v]);43        printf("|");44        int degree = 0;45        for (const struct enode *p = list[u]; p != NULL; p = p->next) {46            printf(" %d", p->to);47            degree++;48        }49        printf("  (degree %d)\n", degree);50    }

Vertices and edges

A graph is a set of vertices joined by edges. A road map is a graph: the junctions are vertices, the roads edges. This one has V = 6 vertices and E = 7 edges, 0–1, 0–2, 1–2, 1–3, 2–4, 3–4 and 4–5: a triangle, a square and a tail.

• In an undirected graph an edge goes both ways. In a directed graph each edge is an arc from one vertex to another, like a one-way street.
• In a weighted graph each edge carries a number: a length, a cost, a time.
• The degree of a vertex is the number of edges at it. Vertex 4 has degree 3. Each edge has two ends, so the degrees add up to 2E: here 2 + 3 + 3 + 2 + 3 + 1 = 14.
• A path is a sequence of vertices, each joined to the next, such as 0, 2, 4, 5. A cycle is a path that returns to its start, such as 1, 2, 4, 3, 1.
• A graph is connected when there is a path between every two vertices.

The code and its cost

The adjacency matrix

The first store is a V × V grid of int cells. Cell adj[u][v] is 1 when u and v are joined and 0 when they are not:

int adj[V][V] = { { 0 } };

add_edge stores an undirected edge in both directions, so the matrix is symmetric across its diagonal:

adj[u][v] = 1;
adj[v][u] = 1;

An undirected edge is stored twice, in row u and in row v. Testing for an edge reads one cell, one step. Listing the neighbours of u reads the whole of row u, V cells, whatever the degree. The matrix takes V² cells, joined or not: 36 ints, 144 bytes, in main’s frame.

Adjacency lists

The second store gives each vertex a list of its neighbours, as a linked list of nodes:

struct enode {
    int to;
    struct enode *next;
};

struct enode *list[V] = { NULL };

A node holds one neighbour, 16 bytes: an int, 4 bytes of padding and a pointer. push_arc puts a new node on the front of a list, and add_edge calls it twice, once for each end:

push_arc(list, u, v);
push_arc(list, v, u);

An undirected edge again takes two entries, one node in each list: 7 edges make 14 nodes. The program adds the edges from the last back to the first, so pushing on the front leaves every list in ascending order. Listing u’s neighbours follows u’s list, as many steps as its degree. Testing for an edge u–v walks u’s list, also up to its degree.

The printed table

The program prints each vertex’s matrix row, then its list and its degree:

0 1 1 0 0 0 | 1 2  (degree 2)
1 0 1 1 0 0 | 0 2 3  (degree 3)
1 1 0 0 1 0 | 0 1 4  (degree 3)
0 1 0 0 1 0 | 1 4  (degree 2)
0 0 1 1 0 1 | 2 3 5  (degree 3)
0 0 0 0 1 0 | 4  (degree 1)

Vertex 5 is in only one list, 4’s.

Space and steps

Here the matrix is the smaller store: 144 bytes against 14 blocks of 32 bytes, 448 bytes of heap, as malloc gives each 16-byte node.

Sparse and dense

A graph is sparse when E is close to V, and dense when E is close to V(V − 1)/2, every pair joined. Road maps and social networks are sparse: a junction meets a few roads, whatever the size of the map. For them the lists win: their space grows with the edges, the matrix’s with the square of the vertices. A small dense graph suits the matrix, with its one-step edge test.

The matrix is the adjacency matrix of linear algebra, where its powers count paths. Packed into arrays, adjacency lists become the compressed-row form of a sparse matrix.

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic graph.c -o graph
./graph
gcc -std=c11 -Wall -Wextra -pedantic -DEXTRA_U=0 -DEXTRA_V=5 graph.c -o graph
./graph

The second build adds the edge 0–5: two more cells turn to 1, and 5 and 0 join the fronts of lists 0 and 5.

Worked example

A road map. A map with 1,000,000 junctions and 2,500,000 roads. As a matrix: 10¹² cells, 125 GB even at one bit a cell. As lists: 5,000,000 nodes, about 160 MB in the 32-byte blocks malloc gives them (80 MB of node data), and 8 MB of heads.

This graph. With V = 6 the matrix is 144 bytes and the lists 448 bytes of heap: the matrix is not always the bigger store.

Arcs. In a directed graph with arcs 0 → 1 and 1 → 2, each arc sets one cell and adds one node: adj[0][1] and adj[1][2], a 1 in list 0 and a 2 in list 1. The matrix is no longer symmetric.

Three checks. Which list holds vertex 5? (Only 4’s.) How many steps to list the neighbours of 4 in each store? (6 matrix cells; 3 list nodes.) A graph on 10 vertices with every pair joined: how many list nodes? (90.)

Where it’s used

Maps and transport. Road and rail networks are sparse graphs, kept as adjacency lists for route planning.

Social networks. People are vertices and friendships edges; each person’s list holds their friends.

Dependencies. Tasks that must wait for other tasks form a directed graph, such as files that must be compiled before others.

Circuits and the web. Components joined by wires, and pages joined by links, are graphs.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.