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.