Final report: via points support landed in Gnome Maps!

This is my final report for Google Summer of Code 2014. I'm a bit on late but, since in the last weeks I was in a hard review state, I decided to write the wrap up post just when my changes to Gnome Maps were committed.

By the way, finishing GSOC does not mean that my contribution finished, indeed I'm planning to continue contributing on this project as I have free time.

Results achieved

Gnome Maps finally supports via points. All my code was committed to the master branch and considering that we've got a code freeze exception, I'm really happy to announce that it will be in Gnome 3.14!

Finally via points!

Turn point marker bubble appears on instruction selection

In details:

• It's possible to add and remove via points. All the points that compose the query have a marker, that can be drag.
• On instruction selection, a turn point is showed on the map and a bubble with the instruction appears.
• There are information about the estimated time to reach the final destination and the distance of the routing, moreover every instruction has info about its length.
• There are new icons for destinations (thanks to Andreas Nilsson).
• A spinner is showed on route loading (thank to Jonas Danielsson).

The main thing I dropped has been via points reordering. The GTK drag and drop library is not simple as it seems, so I planned to add this feature in the next release.

Acknowledgement

I really would like to thank you all the Gnome Maps team, in details:

• Mattias Bengtsson for mentoring me
• Jonas Danielsson, Damiàn Nohales and Zeeshan Ali for reviewing my code
• Andreas Nilsson for design, mockup and graphics

By the way, I could never forget the nights spent coding during GUADEC with Rishi Raj Singh and Mattias.

Lot of fun at GUADEC!

Last week was the GUADEC week!
It has been a great experience and it has been wonderful to meet a lot of Gnome developers, contributors and enthusiasts!

Here you are my summary of the week:

Good

• Strasbourg is a wonderful city
• Keynotes, talks and AGM
• Lightning talks
• Maps BoF and nights reviewing code
• Volunteering for helping organizers
• Coffee breaks
• The lunch at the canteen during core days
• Orangerie park and Bartholdi restaurant
• and most of all... Gnome people!

Bad

• Strasbourg is an expensive city
• At pre-registration party that were not a lot of drinks and food
• Nobody was at the FEC before pre-registration party
• The info-desk was not in the hall
• No lunch provided during BoF

A really happy person at GUADEC '14 :)

Thanks a lot to Gnome Foundation for having
sponsored the really happy person! :)

Just two days to GUADEC

Tomorrow I'm going to leave for Strasbourg and starting the next day I will attend GUADEC '14.
As Gnome intern, I'm going to give a lightning talk on Sunday starting at 5pm (UTC/GMT +2 hours).

I would like to thank the Gnome Foundation for sponsor my accommodation.
Can't wait for meeting developers and having interesting lectures!

report #4: GraphHopper alternatives working, now working on maps

Overview

It passed another month since my last post. The alternatives algorithm on GraphHopper is now finally working and now I'm back working on Gnome Maps.

In the meanwhile at my university, I attended the International Summer School on Software Engineering (more info here). The school this year was really interesting and I had some really impressive lectures that opened my mind.

GraphHopper alternatives algorithm status

As I wrote in my last post I had to consider similarity and optimality for selecting good alternatives.

I implemented both the measures and now the algorithm avoids to select a path that is too similar to another one or it's too far from the optimal one.

Then I started writing an optimized version of the algorithm for having better performance (although the old one was not so poor).

Now when calculating the best path the algorithm search also the best plateaux (more info about the algo here). The regression testing went fine and I also discovered that the code would working fine when Contraction Hierarchies is activated!

Peter Karich gave me another hint for making the algorithm even more faster, this is pure research on routing algorithms and it could have really interesting results. Sadly, there isn't a lot of time for doing it inside this GSOC, so I'm planning to do it as a future work.

Gnome maps via points handling status

Some weeks ago, I made a video of Gnome Maps working well with via points. That code seems really good to me, but I didn't considered the sidebar (was not finished yet).

When sidebar was pushed on repo, I realize that I had to make a good number of fix. Now it works and soon I will attach a new patch to the Bugzilla issue (here).

TODO GraphHopper

1. Change alternatives goodness function. (done!)
2. Optimize code. (done!)
3. Test activating Contraction Hierarchies. (done!)
4. Test on real environments.

TODO Gnome Maps

1. Fix the sidebar for working with via points. (review should come soon)
2. Clicking on an instruction should show the point in the map.
3. Adding a plus button to add via points and a minus buttons for removing them.
4. Make possible to reorder via points.
5. Add some markers for each via points. (partially done)
6. Make via points draggable. (partially done)
7. Make possible to add via points by clicking on the route. (partially done)

By the way -13 to GUADEC !

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!

report #2: via points working with basic interaction

Overview

Since last report I worked on adding via points support to maps.
I updated the interface with GraphHopper and now it can manage also via points. You can have a demo in the below video.

I forgot to record some interactions but the new markers are already draggable and selectable.
I was waiting for the markers bubble that will based on GtkPopover and the sidebar baseline, so I started studying the best solution for the alternative paths problem.

New sidebar mockups

Some of you remember that in my last post I also talked about the new sidebar, for those of you that are impatient Andreas made some fresh mockups.

Sidebar and new interactions mockups

The idea is that with the drag and drop on the map, users will allowed to add, remove and move points, but they could do the same also with the new sidebar. Moreover the sidebar will allow users to sort the points.

Studying best solution for supporting alternative paths.

In the last days I'm working also on alternative paths. GraphHopper currently is missing this feature. First of all I had some lectures about road network algorithms (Dijkstra, A*, Arc Flags, Highway Hierarchies and Contraction Hierarchies). Thanks Peter Karich for support
I also investigated on some solutions for the alternative paths problem. I need some more time but today the options are:

• k-shortest path
• pareto optimality
• penalty approach
• plateau method

Next days schedule

I'm going to spend next days studying which of the options it's most suitable for solving alternative paths problem.

report #1: first two weeks

Welcome to my first report on my work for GSOC 2014 for Gnome!

Overview

I'm going to add via points and alternative paths support to maps (see the good news).
As my main target, I'm going first to focus on via points, my plans are:

1. Change the GraphHopper interface.
2. Add new markers for start, via and end points. The new markers will be selectable and draggable and the route path will change while dragging them. Design will come up in the next days.
3. Finish the work on the new sidebar (still in the work in progress branch).

I already have some mockups for the sidebar and I'll post new markers mockups as soon as they're available. Thanks Andreas!

Sidebar mockups

 After completing via points, I'll focus on alternative paths (plans to come).

Code base

First of all, I had a look to the branch wip/routing2 on which I'll base my code. Despite it's still a work in progress, you can already successfully calculate and show the path between two locations. Thanks Mattias!
I also tested that actually Champlain allows to select and drag markers with few lines of code.

A good news for gnome maps user

I'm going to add alternative paths to maps!
As you maybe know, the maps routing feature is based on GraphHopper.
After a chat with Peter Karich, GH main developer, I discovered that via points is already in GH and it will need at most some optimization. This is a really good news because I'll have time to work also on alternative paths (that needs more work on GH).

User location bubble bug fixed

I also worked for fixing a small bug related to the user location bubble that couldn't be closed.

This bubble should be closeable

Next days schedule

My plan for next few days are:

1. Change the GraphHopper interface for allowing via points in the query.
2. Create some example for testing the code.
3. Show via point in the map, creating new markers draggable and selectable.