Yesterday I accomplished challenge #266 on /r/dailyprogrammer, which is about node degrees. I solved it with a normal adjacency matrix first, but after having read a bit more about simple graphs, I wanted to optimise the amount of information stored.

Given that we have got n nodes, the normal adjacency matrix as shown above consists of n² elements. However, we don’t need that many because a simple graph has got two interesting characteristics:

• the principal axis consist of 0s *(see blue boxes)*

• the matrix is mirrored

We could store the information (true/false or 1/0) in a smaller matrix or a list. I chose a list with ((n² – n) / 2 =** m + 1**) elements. Since lists start with index 0, the last index would be m.

The adjacency matrix can be regarded as a two-dimensional array with n elements that contain n elements each.

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++){
if (i == j) continue; // ignore blue/empty fields
// field[3, 4] would be 7
// field[4, 3] would be (m - 2), which is 7 as well
}
}

What’s the relation between the indices of the adjacency matrix and numbers in the fields, which themselves represent the indices of our BitArray?

Each field can be accessed by two numbers a and b, with a > b:

**((a² – a) / 2) – (a – b)**.

Assuming we have two pairs of connected nodes: (1, 3) and (10, 4), their relating index in the BitArray would be:

• ((3² – 3) / 2) – (3 – 1) = 1

• ((10² – 10) / 2) – (10 – 4) = 39

So in C# we would implement it this way:

int n = 10; // number of nodes
BitArray nodes = new BitArray(n, false);
int a = 1;
int b = 3;
// higher number
int h = a > b ? a : b;
nodes.Set((h * h - h) / 2 - Math.Abs(a - b)), true);