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.