Alternative Roads to Rome

The roads to rome project from Moovel Labs is a nice visualization of the possibilities with GraphHopper. And it is only the start. While investigating and debugging the quality of alternative routes – a new feature from GraphHopper – we stumbled over the necessity to do a very similar visualizations. The visualization of the so called shortest path tree.

What is a shortest path tree?

The shortest path tree (SPT) contains the ‘best ways’ from a root location to any other point in the network. ‘Best way’ can mean for example the ‘shortest’, ‘fastest’ or the ‘most beautiful’ path. The SPT is unique for each root location and transportation mode (e.g. “car”). It is easy to calculate with the Dijkstra algorithm, but it is hard to make it working on large networks such as the European road network. GraphHopper can do this.

The people from the Moovel lab project e.g. used ‘fastest car’ with a starting point at Rome – see here the original image from the project:

We can create similar – but easier to gather – visualizations with our MiniGraphUI, a very simplistic Java Swing UI built just for development a few years ago:

Shortest Path Tree Visualizations

For the visualization we made the line thickness dependent on the number of reachable leafs of the SPT. Let us change the transportantion mode to ‘walking’ instead of car (ferries included but not visualized):

A further step to make the visualization more powerful is to use different colours for different road speeds:

Alternatively, we can colour-encode the distance from the origin Rome:

 

 

 

 

 

Of course the flag colours green, white and red must be tried too, click to zoom 🙂

As well as for Germany and France:

All images are via OpenStreetMap (c) contributors.

Many changes would be possible to make the visualizations better looking like with a background map or better colours, but we left this task to the reader, just showing the possibilities here.

When ‘time’ is used as the ‘distance measure’ as in our examples, then these visualizations are the so called isochrone maps – see our Isochrone API for this task.

Create your own shortest path trees

Although the visualizations from Moovel are also done with GraphHopper, within the MiniGraphUI we have direct access to all the underlying graph properties, so that a SPT through full Germany with millions of nodes takes only half a minute to draw on an aged laptop after importing the data which took under 10 minutes for Italy. We can even zoom in and out. For larger areas probably some further speed tuning could be necessary. You can download GraphHopper here then replace the MiniGraphUI with this snippet, specify your OSM file, then edit config.properties and set prepare.chWeighting=no and finally run:

./graphhopper.sh clean
./graphhopper.sh miniui your-area.pbf

And we could do animations like done in an older post here or compare with old versions of OSM.

What have shortest path trees to do with alternative route finding?

As we mentioned in the intro we have stumbled over the necessity to visualize the SPT to improve the quality of alternative path search. The work for this is currently still under development.

These SPTs can be made from any origin A (‘source SPT’) as well as towards any destination B (‘sink SPT’). And with the help of those two SPTs we can find out ‘overlapping areas’ in the middle. These areas are called plateaus – if we use a bidirectional Dijkstra and extend the normal finish condition to actually make these two Dijkstras really overlap each other. And the larger these plateaus are, the better is the alternative. For example, the best path is also the best alternative with a 100% overlapping path reaching from A to B in the source SPT and backward from B-A in the sink SPT. Apart from the optimal path, these plateaus are often not too large and we need to use other properties to select good alternatives. This can be done for example with a property called ‘sharing’ which calculates the distance an alternative route shares with the best one. After several necessary tweaks with the help of zoomable and debuggable visualizations like this one:

we got surprisingly good alternatives e.g. from Rome to Perugia: