Today I was asked via IRC about how to implement adjacency list in C. My idea and implementation will be shown below.

Suppose that we want to keep adjacency information of $N$ vertices (numbers from the set $[0, N-1]$). We also want to be able to check if pair of vertices $(x, y)$ is adjacent. Note that $(5, 3)$ is exactly the same as $(3, 5)$, so we may perform optimization here by assuming that always $% $. This way, our adjacency matrix starts to be a triangular matrix.

Let’s count the total number of entries in our matrix:

So the total number of entries is a sum of series $1 + 2 + ... + N-2$. Let’s then define a helper function sr(N) which will calculate the sum of natural numbers between 1 and N:

int sr(int N)
{
// sum of numbers 1..N
return N * (N+1) / 2;
}


The next thing is to define a function $idx: \mathbb{Z}^2 \rightarrow \mathbb{Z}$ which will map 2D coordinates into a single array index. We may use the previous observation of relation between value of y and the number of entries:

int idx(int x, int y)
{
// convert triangular matrix indices into array index
return sr(y-1) + x;
}


This will uniquely map every pair $(x, y)$ where $% $ to the set $[0, N-1]$.

We may also like to have some helper, so we don’t have to keep an eye on ordering of x and y:

int sidx(int x, int y)
{
// wrapper around idx(x, y) which swaps coordinates if needed
if (x == y) {
// error
return -1;
}

if (x > y) {
return idx(y, x);
} else {
return idx(x, y);
}
}


Finally, this is how we allocate our adjacency array:

int Nx = sr(N-1);
char *adj = (char *)malloc(Nx * sizeof(char *));

// zero everything
for (int i = 0; i < Nx; i++) {

This is how we can set that vertices $(1, 5)$ are adjacent:
adj[sidx(1, 5)] = 1