[mkgmap-dev] Diagnostic warnings for dead-end oneway highway=service

Fri Jan 3 21:29:20 GMT 2014

On Fri, Jan 03, 2014 at 03:29:22PM +0100, Gerd Petermann wrote:
>okay, thinking again about endlessly traveling in a loop I guess it is 
>a special form of a deadend when there is no other exit ;-)

Right, that was what I had in mind. Generally, if the routing graph is 
not strongly connected (it is not forming a single strongly connected 
component) it should be a sign of invalid oneways. When there are no 
oneway=* attributes, the routing graph will trivially be strongly 
connected (you can get from anywhere to anywhere, because you can 
traverse the edges in both directions).

A special case is when there are multiple routing islands even when 
ignoring the oneway=* attributes. Within a map tile, we can legitimately 
have multiple routing islands, for example if no ferry connection has 
been mapped to an island, or when some ways in the tile are connected by 
ways in adjacent tile(s).

We should only complain when the introduction of oneway=yes "splits" a 
routing island.  

There is an efficient algorithm for computing the strongly connected 
components of a directed graph: 
http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

Perhaps we could invoke the algorithm in two passes:

(1) on the undirected graph of roads (hard-wiring oneway=no)
Each strongly connected component (SCC) would be a routing island.
(2) for each SCC from step 1 that contains oneway=yes attributes:
If the SCC would be split, list the oneway=yes ways (or some of them).

	Marko