Shader Gradient

It took me a while to grasp how gradients in Cg/HLSL work. For some reason, all the tutorials I watched/read do not teach you the basics, or at least, they do not tell you why they suddenly do this and that, and magic gradients happen.

The following is not a tutorial since I’m just a beginner. I’d like to share what I learnt in a way how I am learning. There is a logical structure, and once I got it, it all makes sense. To be honest, I’m not that interested in the visual output but in the algorithms. I don’t know if everything I’m writing here is correct but when I spot an error, I’ll edit this post.

Continue reading Shader Gradient

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-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?

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