Algebraic Path Finding | Iago Leal


Consider a graph with weights on its edges. Like the one in the
figure, for example. One way to represent this graph is via an adjacency
matrix A whose component A(s, t) is the weight of the edge between
nodes s and t. Notice that since there may not be edges
between all vertices (after all, what’s the fun in a complete graph?),
A is a partial function. We can solve
this by adjoining a value infty to the
possible weights and assigning it as the weight of the non-existent
edges. In case this solution seems like a dirty trick to you, a
possibility is to think of this process as the same as returning a
Maybe value to make a partial function total, with infty playing the role of
Nothing.

Given this graph, a common question to ask is what are best ways to
travel between its vertices. That is, if you want to go from node s to node t,
which sequence of edges should you choose? If you’ve read what I have been writing about dynamic
programming
, you are probably already smelling the sweet scent of
value functions and Bellman equations in the air.

Let mathcal{S} be the (finite) set
of nodes in the graph, and let’s define V
colon mathcal{S}times mathcal{S}to (-infty, infty]
as the
value function which tells us the length of the shortest path between
two vertices. With a bit of dynamic programming, we can find out that
V satisfies a Bellman equation:


begin{aligned}
V(s, s) &= 0 \
V(s, t) &= min_{q in mathcal{S}}, A(s, q) + V(q, t), ; forall
s ne t.
end{aligned}

The first line is the base case for the recursion and represents the
0-step paths. It costs nothing to just stay where you are, but it is in
turn impossible to reach any other vertex in zero steps. This may seem
really simple, but let’s nevertheless define a matrix I to represent this 0-step reachability
relation. Why we want to do that will soon be clear.


I(s, t) = begin{cases}
0 ,& s = t \
infty ,& s ne t.
end{cases}

We can use I to write the recurrence
more compactly:


V(s, t) = min left{ I(s, t),, min_{q in mathcal{S}} A(s, q) +
V(q, t) right}

What the above equation means is that the minimal distance between
two vertices is the shortest among staying in the vertex (an empty path)
and recursively following the shortest path with at least one edge.

Every problem is linear if you squint hard
enough

The equation above is indeed rather ugly. However, by looking at it
with care, one can the structure unveiling. First, the term


min_{q in mathcal{S}}, A(s, q) + V(q, t)

looks a lot like some kind of composition where we aggregate over the
middle index q. Even more: if you
squint your eyes enough, it looks a lot like the formula for matrix
multiplication.

Well, let’s try to discover where this idea takes us. Even if it is
just for the sake of abstract nonsense, it could be interesting. In
general, when talking about real numbers, we use the usual arithmetic
structure with addition and multiplication. Today we’re going to be
eccentric and define a new kind of addition and multiplication:


begin{aligned}
a oplus b &= min{a,, b}, \
a otimes b &= a + b, \
mathbf{0} &= infty, \
mathbf{1} &= 0.
end{aligned}

So, what is happening here? The thing is: the real numbers extended
with infty satisfy all the axioms for
a Semiring
structure
if we take sum to be min
and product to be +. This is called the
min-plus or Tropical
semiring
and, surprisingly, satisfies a lot of the axioms we expect
from a sum and product The main difference is that instead of having
inverses, oplus is idempotent.

Before further exploring the properties of the Tropical semiring, or
of semirings in general, let’s take advantage of our new notation to
rewrite the ugly equation


V(s, t) = I(s, t) oplus bigoplus_{q in mathcal{S}} A(s, q) otimes
V(q, t)

into the much more elegant (and index-free!) matrix format


V = I oplus (A otimes V).

By now, the choice of the letter I
for the 0-step becomes clear: it is the identity matrix in the Tropical
algebra!

What is cool is that in this form, finding the shortest path becomes
the same as solving a linear system. Can we transfer the methods from
classical linear algebra to this semiring setting? Unfortunately the
answer is in general negative… This is why we will have to require a
further piece of structure from our semirings: a closure
operator
denoted ^* which
returns the fixed point of the mapping x
mapsto mathbf{1} oplus a otimes x
, that is, we require
that

x^* = mathbf{1} oplus a otimes x^* =
mathbf{1} oplus x^star otimes a.

Now, you may call me a cheater since this is the scalar version of
the shortest path equation. Nevertheless, we will see that while such an
operator tends to be pretty simple to define for the scalar field, it is
also the missing piece for solving the Algebraic Path
Problem
. That is, an algorithm capable of solving the Bellman
equation in a way that is polymorphic on the semiring.

Alright, that was a pretty mathematical introduction. It’s far from
time for this post to become more computational. Let’s take the above
discussion to Haskell land by defining a Semiring
class.

Wikipedia
article on the topic
.

The Tropical Semiring
and Shortest Paths

One can think of a semiring as a structure with an operation for
combining two values (otimes) and
another for aggregating values (oplus). Since the min-plus semiring was our
choice for intuition, let’s start the implementation with it.

Regular
Language
.

The semiring instance is straighforward, since the constructors
closely resemble the class methods. We will only implement a couple
simplifications in order to not get expressions with redundant
parts.

defined for
calculus expressions on another post
. All of them are some kind of
“realizations of typeclass”.

The usefulness of this interpreter comes from the fact that it
commutes with the matrix operations. Thus, whenever we want to perform
many queries in a same graph with idempotent aggregations (such as
shortest paths, largest paths, most reliable paths, widest paths etc.),
we may first calculate the regular expressions representing these paths
and then collapse them separately for each semiring.

Classical Matrix Inversion

To wrap up this post, let’s take a look at a semiring that is not
idempotent: the classical field structure on the real/complex numbers.
Or, to be technicality accurate, one of these fields complete with an
extra point to amount for the non-invertibility of zero.

Source link