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 ). We also want to be able to check if pair of vertices is adjacent. Note that is exactly the same as , 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 . 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 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 where to the set .

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++) {
    adj[i] = 0;
}

This is how we can set that vertices are adjacent:

adj[sidx(1, 5)] = 1

The test for adjacency is analogous.