Adjacency list - mapping of coordinates to a single dimensional array
Post
Cancel

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:

$\begin{matrix} y = 2: & \text{1 entry} \\ y = 3: & \text{2 entries} \\ y = 4: & \text{3 entries} \\ \ldots \\ y = N-1: & N-2 \text{ entries} \end{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:

1 2 3 4 5 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:

1 2 3 4 5 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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 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:

1 2 3 4 5 6 7 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:

1 adj[sidx(1, 5)] = 1 

The test for adjacency is analogous.