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

Mon Jan 6 17:07:32 GMT 2014

On Sun, Jan 05, 2014 at 08:25:12AM -0800, GerdP wrote:
>The question is:
>If you get a list of oneway road (parts) which create routing islands, 
>is it really the only conclusion that these oneways are wrong?

I cannot think of any other conclusion in the practice. See below for a 
somewhat artificial example.

Before I left the academic world 10 years ago, I implemented Tarjan's 
algorithm for strongly connected components in a model checker tool. It 
was applied to the graph of reachable states (reachability graph) of the 
modelled system, which would typically be a high-level model of a 
distributed system or protocol.

A desired property of any distributed algorithm is that its state 
diagram is strongly connected, that is, you can get from any valid state 
to any other valid state by performing a number of possible actions.  

When the reachability graph of a distributed system is not strongly 
connected, it usually means that one or more actors (processes, threads, 
whatever) are stuck. The system as a whole might not be in a deadlock, 
if some processes can keep doing something.

There is a class of distributed algorithms called self-stabilizing 
algorithms. They have the additional property that you can get from any 
state (including invalid states) to the valid states. In the 
reachability graph of this kind of a distributed algorithm you would 
have a very large number of initial states (all possible states of the 
distributed system), and there would a strongly connected component of 
the valid states.

Now, let me get back to the OSM domain. I guess we could think of a 
restricted area that only defines oneway exits to the public road 
network, but the entry roads are well-kept secrets (maybe enforced by 
law). If the road network within the restricted area is mapped, then it 
would form its own strongly connected component from which you can get 
to the strongly connected component of the public road network, but not 
vice versa. (By definition, the graph of strongly connected components 
is acyclic.)

	Marko