[mkgmap-dev] Routing graph analysis

Sat Mar 16 20:44:12 GMT 2013

Hi Gerd,

>>I wrote some months ago about a possible project to highlight 
>>dead-ends on the map, but nobody replied. I think it should be a set 
>>of 'dead-end layers', one for each mode of routing. Then you could 
>>easily survey all those nearby suspectable cases when going for a walk 
>>or a bicycle trip.
>>
>>Pedestrians can use steps, cannot legally use highway=cycleway. For 
>>bicycles it is vice versa. Both can use paths and most ways except 
>>motorways. Cars can use all ways except those meant for bicycles and 
>>pedestrians. There are really multiple routing graphs to consider if 
>>you want to check for dead-ends properly.
>
>I agree that it would be better to check each road network separately, 
>but I don't think that mkgmap is the right program for this. Maybe you 
>can use different styles for that?

Yes, I guess it would call for a separate preprocessor tool.

It is a bit like programming language compilers and static analysis 
tools. Compilers can generate warnings for some things, especially when 
you crank up the optimization level, but their main purpose is to 
translate the code, not to find all errors.

The same goes for mkgmap; it can only detect 'easy' errors as a 
byproduct of the map-making. In this case, it can detect easy cases of 
unconnected roads or dead-end oneways, but it cannot possibly analyze 
the full routing graph.

>On the other hand, I think the dead end check that is implemented now 
>is  incorrect because it doesn't report all "individual oneway roads 
>that go nowhere" as documented.
>
>I did not find a simple way to fix that in the existing routine, but it
>can be done in the StyledConverter, because it is very similar to the 
>check for unconnected roads implemented with r2530.

I think that a stand-alone routing graph analysis tool could be useful, 
for flagging dead ends, computing routing islands, and computing 
strongly connected components in the routing graph (to flag 'trap' 
areas, which you can only enter but not exit, or vice versa). It might 
even consider turn restrictions. (I do not think that we currently 
complain about a T crossing where the vertical line of the T is an 
oneway pointing down, and there are turn restrictions from both arms of 
the T, prohibiting a turn to the downward-pointing way.)

The tool would input the OSM data and a list of way tags that are to be 
considered when building the routing graph. The oneway tag would not be 
hardwired; it could be dropped for pedestrians, for example. I think 
that the 'routing style language' could be a subset of the mkgmap style 
language.

Based on the tool output, the map translation toolchain could add new 
pseudo tags, such as routing:bicycle=deadend or 
routing:motorcar:island=1, which could then be highlighted by custom map 
translation or rendering styles.  This would not be limited to mkgmap; 
it could also be used for (say) OsmAndMapCreator, or for visualization 
in JOSM.

	Marko