Over the last weekend I was at the Barcamp Oldenburg. Since one of the first things I learned at this Barcamp was that not even among technically inclined people everyone knows what a Barcamp is let me give a ultra-rapid introduction.
In the last two blog post we learned how to use -semirings to implement several different algorithms, with just 7 lines of code and the right instantiation for a class. Among others, I showed you how to compute the length of the shortest paths between two nodes of a graph. In the last blog post I presented a way to represent every path between two nodes using regular expressions. In this blog post it is the time to combine both. We will construct a new -semiring and use our, by now, well known algorithm to get every path that exhibits a specific property.
In the last blog post I showed you what you can do with just implementing the interface for a -semiring and than using the matrix over that semiring. Up until now, we can compute the transitive connection relation, the length of the shortest path, the maximum throughput between two nodes and the reliability on the most reliable path. But what we can’t do right now is producing the path(s) that instantiate these properties. So this is exactly what I will show you in this post.
After in the last blog post I described some algebraic structures and already said I would like to show case how to solve some very different problems with those. I think it’s now time to go into that. I start with something which is more or less a reiteration of a fantastic blog post by Russell O’Conner on mostly graph problems. I will layout the problems a little differently and hope to convey the ideas behind the post to a wider audience. I will also omit some stuff and maybe come back to that in a later post. But now without further ado let’s get started.
Lately, for reasons which slip my mind right now, I had to review some old library code I wrote. And as always when you review code you wrote a while ago, you think “How could I have ever thought this was good code?” Usually this is because the code contains more hacks than clean code or because you can’t even understand what that piece of code does. In this case I was quite ok with that, but could have hit myself hard for not recognising a general pattern of all distinct cases I programmed back then. This prompted me to go to:
I can’t really show you the difference in 1. because I wrote the code for a project I was hired for and it’s not really open source but I decided to make a series of blog post about 2. I hope you like it.