Suppose you have a couple graphs, represented by adjacency matrices (A and B) whose cells represent travel times or distances or some other notion of cost. Assuming their dimensions are compatible, and that the columns of A correspond to the same nodes as the rows of B, then
A ⌊.+ B
will produce a new adjacency matrix (call it C) where each c_ij is the minimum traversal cost from node i to node j. For example, if A represented driving times from all cities in NY state to all airports in NY, and B represented direct flight times from all NY airports to all CA airports, then our result would be the minimum travel time (ignoring parking and security) between any NY town and any CA airport.
The sequence `⌊.+` is an inner product chosen specifically to achieve this effect, with addition where multiplication would normally be, and ⌊ (min) where multiplication would normally be.
Notice that it took me longer to give this under-caffeinated explanation of what is going on than to write the code.
Yes, multiplying graph adjacency matrices over a min-tropical semiring produces shortest paths. APL supports this syntactically, but how does it function in the real world? What if the matrices are extremely sparse, like almost all real world graphs are? Syntax is the easy the problem. The hard problem is having very sparse graphs with billions of nodes and many billions of edges. How is a square matrix going to deal with that? Sparse and hypersparse graph computing is hard, which is not syntactically relevant.
Python does not have this terse a syntax, but it gets very close with multiple bindings to the SuiteSparse GraphBLAS Hypersparse graph processing libraries, which intrinsically supports sparse graphs and a very large number of operators, including the tropical min/max ones. Suitesparse doesn't provide syntax (that's the easy part), it provides the hard part, sparse and hypersparse data structures and very complex dynamic, parallel graph processing optimizations including JIT compilation of GPU accelerated operations.
Here's a notebook that shows your shortest path example using Python and the GraphBLAS. While it's a trivial example, it can scale the the largest graphs possible to use today using SuiteSparse:
NB: I should clarify I'm not advocating for Python's syntax in particular vs APL, I'm saying that syntax is not the hard part of any particular problem, especially when it comes to sparse graphs. There are also other binding to GraphBLAS like Julia that are quite nice. I do appreciate that APL does elgantly permit the notion of graph operations with linear algebra.
Sorry but to me this looks like a cool language to play code golf, but a terrible language to use in production.
It feels like obfuscating your own source code.
> The sequence `⌊.+` is an inner product chosen specifically to achieve this effect, with addition where multiplication would normally be, and ⌊ (min) where multiplication would normally be.
Sorry, it is early for me too. I am wondering if there is a mistake here. Do you mean that addition is where multiplication would be and min is where addition would be?
Hm wait floyd-warshall is subtly different from regular matrix multiplication with (+, *) replaced with (min, +).
We're accumulating into the existing matrix so the order of loop iteration matters, it has to be {k, i, j}. As such I'm not sure how
C_ij := \min_k (A_ik + B_kj)
would work to give all pairs shortest path, since in floyd-warshal the results of C[i][j] at iteration k depend on C[i*][j*] for k-1 being computed, which is not true for the above where C_ij can be computed independently of all others.
It seems like it _is_ possible to easily express APSP via an inner product with (min, +), but it's less efficient than floyd warshal. Whereas floyd warshall asks "What's the shortest path from i to j using vertices in {1..k}", if you instead ask "what's the shortest path from i to j of length at most k" and then use repeated-squaring you can get the answer in n^3 lg(n). See
The sequence `⌊.+` is an inner product chosen specifically to achieve this effect, with addition where multiplication would normally be, and ⌊ (min) where multiplication would normally be.
Notice that it took me longer to give this under-caffeinated explanation of what is going on than to write the code.