The Strahler number

A few days ago, I was browsing Wikipedia and came across an article on the Strahler number, which measures the branching of a tree. The mathematical kind of tree, not the kind that grows in the ground (although I suppose it would work for that, too).

The number originally came from hydrology and was used to describe systems of rivers and streams. At its source, a stream has a Strahler number of 1: it is a first order stream. When two streams of order n join together, the combined stream has order n+1. If two streams of different order join, the combined stream has the same order as the bigger one.

The Amazon has a Strahler number of 12 at its mouth. The Mississippi is a 10.

This approach can also be used by a compiler to calculate the number of registers needed to evaluate an arithmetic expression tree without spilling any (which is why I thought this was interesting).

Imagine we are adding two subexpressions; the left expression takes three registers and the right expression takes four. We only need four registers to evaluate the combined expression, since we can evaluate the right expression first, store the result in one register, and use the other three to evaluate the left expression. However, if both sub-expressions require four registers to evaluate, we need a fifth register to evaluate the combined expression.

Of course things get more complicated when you have acyclic graphs instead of trees, but this is still a useful metric in a register allocator. Mainly, I just appreciate the beauty of a mathematical concept that applies to completely different fields like this.