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
_______________________________________________
mkgmap-dev mailing list
[email protected]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
