report #3: first implementation of alternatives on GraphHopper, going on on gnome maps

Overview 

First of all I would like to say sorry for not blogging in the last month.
I had to do a lot of not gsoc stuff, but this is not a good excuse... so just sorry and let's start with the report! :)

Interface with GraphHopper now supports viapoints

I created a patch for supporting viapoints in maps. The patch is now in review. You can have more info here.

Dependency fixed

I have been a bit stucked in Maps because I was waiting for two jobs to get done: first implementation of sidebar and new markers.
In these weeks Mattias and Damiàn made a great work and both jobs are now in review (more info on bugzilla here and here and on Damiàn blog).

New markers by Damiàn Nohales

New sidebar by Mattias Bengtsson

GraphHopper best approach for alternative paths issue

In my last report I said I was studying the best algorithm for solving alternative paths problem. You can have a good overview of my research here and below a short resume:

• k-shortest path: not feasible
• pareto optimality: not feasible
• penalty approach: good option for simple Dijkstra-like algorithms. It adds an overhead to the computation (for updating penalties). So if there will be time, it will be implemented just for this category of algorithms.
• plateau method: best option for bidirection Dijkstra-like algorithms. This algo should not create a lot of problems when activating Contraction Hierarchies but I'll know more about this later after some tests.

Together with Peter Karich, I decided to start working on the plateau method.

GraphHopper: implementing alternatives paths

I wrote a first implementation of plateau method and two small unit tests. The algo was working fine in these tests, so I decide to test in a real world environment.... and I had some troubles.
After a bit, I realize that I have to work on the goodness function.
In detail, I should consider two more conditions for selecting a good alternative: similarity and optimality rate.

Red alternative is good
Yellow one not too much

What's next? (Gnome maps)

1. Fix the sidebar for working with viapoints.
2. Add the feature to add, remove and sort viapoints directly from the sidebar.
3. New turning point markers on the map.

What's next? (GraphHopper)

1. Change alternatives goodness function.
2. Optimize code (Peter gave to me a good hint).
3. Test activating Contraction Hierarchies (crossing fingers mode ON XD ).

Going to GUADEC!

I'm really excited to announce that I got accomodation sponsorship from GUADEC travel committee and I've already booked flight tickets for being in Strasbourg!