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 exibits 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 the most reliable path. But what we can’t do right now is producing the path(s) that instatiate these properties. So this is exactly what I will show you in this post.
After in the last blog post I described some algebraic strutures 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:
- Rewrite the code in the more general way, reducing the code size by 30% and increasing the speed on two cases and
- Go into research mode for finding even better patterns of generalisation.
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 decieded to make a series of blog post about 2. I hope you like it.
For the last 10 years now I am a Apple user. Nevertheless I really like Linux and that’s not only on servers and in embedded devices but for the Desktop. I actually don’t see Linux fitting on the Desktop of anybody who is not tech savvy even though Ubuntu is not that bad. But for so called power users Linux actually is a very valid Desktop environment. So as a second Workspace I have VMWare Linux instance running on my machine almost 24-7. And since I have been asked now at least one to many times how my “strange” Desktop Environment is configured. I’d like to share that with you.