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

Mon Jan 6 19:02:57 GMT 2014

Hi Marko,

before I retired I worked for a company that develops tools around the 
(job) scheduling tools in IT centers. One typilcal problem in this area is a 
loop of dependencies (job a depends on b, b on c, c on d, .. , x on y; y on b)
which may result in deadlocks.
In such a loop it is not possible to say which dependency is wrong,
you can only list the elements of the loop and an expert has to say
where the loop has to be split. 
Still our customers asked for a tool to show THE wrong depency.
Your email reminded me a bit on this ;-)

In the OSM case, maybe it is a way that is missing and not a 
wrong oneway tag. I think someone has to visit the place to find out.

Another question is what we can do with such "wrong" data in the map 
produced by mkgmap. 

Gerd

> Date: Mon, 6 Jan 2014 19:07:32 +0200
> From: marko.makela at iki.fi
> To: mkgmap-dev at lists.mkgmap.org.uk
> Subject: Re: [mkgmap-dev] Diagnostic warnings for dead-end oneway highway=service
> 
> 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
> _______________________________________________
> mkgmap-dev mailing list
> mkgmap-dev at lists.mkgmap.org.uk
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.mkgmap.org.uk/pipermail/mkgmap-dev/attachments/20140106/5ec13584/attachment.html>