Over a million developers have joined DZone.

Graph Optimization in Physical Space: Calculating Several Alternative Roads to Rome

DZone's Guide to

Graph Optimization in Physical Space: Calculating Several Alternative Roads to Rome

Using the GraphHopper software to analyze different ways to create and analyze routes to major European cities.

· Big Data Zone
Free Resource

See how the beta release of Kubernetes on DC/OS 1.10 delivers the most robust platform for building & operating data-intensive, containerized apps. Register now for tech preview.

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 used "fastest car" with a starting point at Rome — see the original image from the project:

Roads to Rome. Attribution: Moovel Lab and OpenStreetMap

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:

Northern part of Italy. Starting exploration in Rome

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 colors for different road speeds:


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



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

Full SPT of Italy starting in Rome.

As well as for Germany and France:

Full SPT of Germany starting in Berlin.
Full SPT of France starting in Paris.

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 Do Shortest Path Trees Have 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:


New Mesosphere DC/OS 1.10: Production-proven reliability, security & scalability for fast-data, modern apps. Register now for a live demo.

java ,spatial

Published at DZone with permission of Peter Karussell. See the original article here.

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}