Adjacency Matrix for Simple Graphs

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.

adjacency_matrix_01

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.

Adjacency matrix relating to the BitArray

The adjacency matrix can be regarded as a two-dimentional 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?

Adjacency matrix

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);