Tuesday, May 7, 2013

Routing things and stuff

Unfortunately I'm pretty bad at mathematics, but there's one thing that makes me wish I would know more about it: programming (of course). People who don't know a lot about programming always think that you have to be a mathematics-pro if you want to program: that's not true at all! Of course it highly depends on the things you want to create, but for things like a "normal" Android app you barely have to do any math.

For more sophisticated stuff you'll probably need to do some calculations sooner or later though. The first time I worked for indoo.rs (actually, my first job as a developer ever) I had the pleasure to implement a routing algorithm. A what!? I had absolutely no clue about that stuff when I started working for them. However, I wanted to do my job as good as I can and started reading Wikipedia articles in both German and English to get an idea about how routing algorithms (and in this case A*) work and how to implement them.

What I want to share with you today is an implementation of some routing algorithm I implemented a few days ago. It's a mixture of everything I still remembered from a few years back when I had to implement routing for indoo.rs. I think it's best described as a depth-first, kind-of-dijkstra thing.

The challenge in my case was that I had to implement an algorithm which routes between... things. Of course I can't go into detail about what the "things" are, but it comes down to this: the algorithm had to find a path between points, which are no points in the common sense (they have no coordinates or similar, just a name and connections to other points). So, to be very specific, the points were simply represented by a String, and I knew which point is connected to another point. Of course that means we can't use a full-blown A* algorithm, because it needs some kind of heuristic (for example the distance between two points) - which I didn't have.

So here it is. Let's call it EinStern, okay?


If there's any question or problem using this I'd love to help you in the comments.