Team OSRM is happy to announce a new data analysis feature for OpenStreetmap data based on OSRMs great routing capabilities. Over the past weeks, we at Team OSRM received a number of complaints that a certain part of the road network was not route-able and were asked for help. We observed that some of these error were not caused by obviously invalid tagging, but by connectivity issues such as unconnected islands of the road network, sources and sinks. Think of the latter two as one-ways where you can drive in but not out, and vice-versa. There are in fact 1,074,201 such way segments today.

For the impatient: head to OSRMs demo site and activate the ‘small components’ layer or use the routing view of Geofabriks great OSM Inspector to see the visualization.

Big thanks go to Geofabrik for hosting the tile layer that we use.

Strongly connected components

One assumption in reality is that the road network is a strongly connected component. It is a technical term, but in essence it means that you should be able to go from one intersection of the road network to every other intersection [*]. Especially, you should not get stuck in a street that you can’t get out of.

We implemented a standard algorithm for this problem, known as Tarjan’s SCC algorithm to automatically detect all ways that have these problems each time we update our routing data.

Right now, there are about a million way segments planet-wide that bear connectivity issues. While this number seems large at first, about 60% of these problems shall be fixable by editing a single segment only.

What kind of problems are visualized?

The following list will show you the problems that will be detected:

Unconnected islands

Here, we have a road that looks like a car could drive on it, but it is unconnected to the rest of the road network. Most probably, it is missing a tag that indicates access rules.

Sources and Sinks

Here, a one-way street just ends. Any car that enters this street would be trapped according to the data. This can be caused by faulty tags or perhaps also by missing data. It may be an indicator that there is a street missing.

Here we have a source of traffic. How should a car ever get to the upper-left corner if traffic always goes in the other direction?

False Positives?

There is a limited number of false positives. Either there is an accidental problem in our parsing or on purpose. Most notably, piers. Most ferry connections go through piers although the ferry carries cars. And in the early days of OSRM we allowed them to connect continental main land and islands in the sea.

And of course, someone might have just already fixed the problem. * * * # Links:

• OSRM Demo Site: http://map.project-osrm.org/
• OSRM Bug Tracker: https://github.com/DennisOSRM/Project-OSRM/issues
• Small Components on OSM Inspector: http://tools.geofabrik.de/osmi/?view=routing

---

[*] Technical Note: we implemented an iterative version of the seminal algorithm.