OpenStreetMap

Tiny SCCs all over the world

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

Unconnected Island

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

Sink 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.

Source

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?

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:


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

Discussion

Comment from maning on 9 October 2012 at 09:32

Great! Any plans for a worldwide coverage?

Comment from AMosm on 9 October 2012 at 10:50

A (oneway) highway(=service) starting/ending in a node amenity=parking + parking=underground or amenity=parking_entrance IS a source/end and perhaps should not be extra marked as unconnected. Example: http://www.openstreetmap.org/browse/way/134837754

Comment from DennisL on 9 October 2012 at 11:38

It has world-wide coverage. The renderer seems a bit over-whelmed at the moment.

Comment from Pink Duck on 9 October 2012 at 14:10

There seems to be a large number of highlighted segments that are attached to highway=service closed-ways with area=yes. The routing does not seem able to use highway=track, tracktype=grade1.

Comment from dcp on 9 October 2012 at 16:16

Great work, lads (and Ladies if any are involved). I have a street connected to an area=yes; highway=residential which is connected to a street. All have the same name. Is this an mapping error or a false positive?

Comment from DennisL on 9 October 2012 at 17:11

Thanks!

Areas are not routed through (yet).

Comment from Zverik on 9 October 2012 at 17:19

Dennis, is it possible to create such component maps not only for all highways, but for highways with level >= residential/unclassified, highway >= tertiary etc?

In Russia we have such validator http://peirce.gis-lab.info/qa/RU/routing-map , but it is not scalable :(

Comment from DennisL on 9 October 2012 at 18:14

Well, yes and no. At the moment our capacity is rather limited. But we may implement that feature in the future.

Comment from Pierre-Alain Dorange on 9 October 2012 at 20:17

I try optimize data for routing in my local city (their was small components signaled) but majority its was false positive for me : generally real noexit road (tagged noexit=yes). It the old town at Cognac (France) we got many of those noexit street, because the city is old and some street are strange and because some street has become “pedestrian only” so side street became “noexit”…

Do OSRM small component miss “noexit” tag or do i miss someting ?

Comment from DennisL on 9 October 2012 at 20:19

Do you have an example to look at?

Comment from amm on 10 October 2012 at 00:54

What happens to cars that enter into a oneway street that has noexit? Either you are allowed to drive in both directions (in which case the oneway tag would be wrong), there is a valid exit, or you are not allowed to drive into that road at all. (Or the traffic planner in your city is mad and/or has a hatred for cars… ;-))

Comment from harendra_7 on 10 October 2012 at 05:48

Satellite images are not enough clear in some areas to draw and connect the roads.

Comment from malenki on 17 October 2012 at 20:53

I found a bug which isn’t marked with the new feature, yay! ;) See http://osrm.at/1xY

Comment from DennisL on 23 October 2012 at 12:16

Malenki, this is not an error that get’s visualized in the layer. if you move the markers along then you see that everything is connected, but there is a detour. The problem is not reachability but the detour.

Comment from Pierre-Alain Dorange on 23 October 2012 at 17:13

@DennisL, my example are my town where i live : Cognac, France. I got lot of small island error here : http://tools.geofabrik.de/osmi/?view=routing&lon=-0.32778&lat=45.69423&zoom=17

It was mostly related to street that end on “pedestrian-only” streets. I tag tham “noexit=yes” bit there were reported as “island”, i probably miss something ? I re-inspect and one street was probably bad tagged (i change that just now) but the others seems OK for me.

Comment from DennisL on 24 October 2012 at 08:08

@Pierre-Alain Dorange, your examples are pretty obvious. One-way streets either start or end at ways where car traffic is not allowed.

Comment from mcld on 28 October 2012 at 09:48

Dennis, this visualisation is SUPER-helpful! It led me to fix many wonky things: streets mis-labeled as footways, oneways going the wrong way, etc.

(Some things are unfixable, such as one-way roads leading into carpark buildings. It might be good to ignore sources/sinks that terminate it building entrances etc?)

I guess the computation is heavy, but are you planning to have the data refreshed? I have been hacking away at various patches, and it will be hard to remember what has been fixed and what hasn’t.

Comment from DennisL on 28 October 2012 at 11:35

@mlcd Thanks for your comments. The layer is updated daily (with a few exceptions).

Log in to leave a comment