A few of my favorite things

The Tropical (min-plus) semiring is one of my favorite examples of how changing one’s perspective can make difficult problems much simpler.¹ In this semiring, instead of using the usual addition and multiplication, we replace them with minimum and addition, so, for instance, \( 1 \oplus 2 = 1 \) and \( 3 \otimes 2 = 5 \). I’ve written and presented about this before.

Links from the farm

Recently, someone on the APL Farm posted an excellent article by sigfpe (AKA Dan Piponi), which prompted me to post a different article where they work with the min-+ semiring. I also posted this article by Russell O’Connor, which is one of my all-time favorites. In it, there’s an example where the distances between nodes in a graph gets turned into a Tropical matrix, and algorithms for computing shortest distances become iterated linear algebra over this different semiring. And then I wanted to work in APL instead of Haskell…

An open dialogue

After a bit of head scratching, I realized that Dyalog APL is really good for manipulating matrices over the min-+ semiring. Taking exampleGraph2 from O’Connor’s blog post, and letting \( 10^{20} \) stand in for \( \infty \)²:

inf←1e20
dist←6 6⍴0 7 9 inf inf 14 7 0 10 15 inf inf 9 10 0 11 inf 2 inf 15 11 0 6 inf inf inf inf 6 0 9 14 inf 2 inf 9 0

we have the following distance matrix

      dist
0.0E0  7.0E0  9.0E0  1.0E20 1E20 1.4E1
7.0E0  0.0E0  1.0E1  1.5E1  1E20 1.0E20
9.0E0  1.0E1  0.0E0  1.1E1  1E20 2.0E0
1.0E20 1.5E1  1.1E1  0.0E0  6E0  1.0E20
1.0E20 1.0E20 1.0E20 6.0E0  0E0  9.0E0
1.4E1  1.0E20 2.0E0  1.0E20 9E0  0.0E0

With this matrix, representing distances between vertices in our graph, we can use the APL matrix product operator . with different operations to perform our calculations; instead of + and × for addition and multiplication, we turn to ⌊ (min) and +; then dist ⌊.+ dist gives us the two-hop distances:

      dist ⌊.+ dist
 0  7  9 20 23 11
 7  0 10 15 21 12
 9 10  0 11 11  2
20 15 11  0  6 13
23 21 11  6  0  9
11 12  2 13  9  0

We can make this more succinct with ⍨, telling the interpreter to apply our function with dist as both arguments:

      ⌊.+⍨ dist
 0  7  9 20 23 11
 7  0 10 15 21 12
 9 10  0 11 11  2
20 15 11  0  6 13
23 21 11  6  0  9
11 12  2 13  9  0

I was very excited that I could write down the steps of the Gauss-Jordan-Floyd-Warshall-Kleene algorithm in so few characters! Moreover, iterating that step until convergence is similarly succinct using the power operator ⍣; we can keep running ⌊.+ until the output matches (≡) the input:

      ⌊.+⍨⍣≡dist
 0  7  9 20 20 11
 7  0 10 15 21 12
 9 10  0 11 11  2
20 15 11  0  6 13
20 21 11  6  0  9
11 12  2 13  9  0

Imagine my surprise when I searched for “distance” in Iverson’s notation as a tool of thought:

and if p gives distances from a source to transhipment points and q gives distances from the transhipment points to the destination, then p⌊.+q gives the minimum distance possible.