Adjacency list - mapping of coordinates to a single dimensional array

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 $x < y$. 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 $x < y < N$ 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++) {
    adj[i] = 0;
}

This is how we can set that vertices $(1, 5)$ are adjacent:

adj[sidx(1, 5)] = 1

The test for adjacency is analogous.