<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 12pt;
font-family:Calibri
}
--></style></head>
<body class='hmmessage'><div dir='ltr'>Hi Marko,<br><br>before I retired I worked for a company that develops tools around the <br>(job) scheduling tools in IT centers. One typilcal problem in this area is a <br>loop of dependencies (job a depends on b, b on c, c on d, .. , x on y; y on b)<br>which may result in deadlocks.<br>In such a loop it is not possible to say which dependency is wrong,<br>you can only list the elements of the loop and an expert has to say<br>where the loop has to be split. <br>Still our customers asked for a tool to show THE wrong depency.<br>Your email reminded me a bit on this ;-)<br><br>In the OSM case, maybe it is a way that is missing and not a <br>wrong oneway tag. I think someone has to visit the place to find out.<br><br>Another question is what we can do with such "wrong" data in the map <br>produced by mkgmap. <br><br>Gerd<br><br><div>> Date: Mon, 6 Jan 2014 19:07:32 +0200<br>> From: marko.makela@iki.fi<br>> To: mkgmap-dev@lists.mkgmap.org.uk<br>> Subject: Re: [mkgmap-dev] Diagnostic warnings for dead-end oneway highway=service<br>> <br>> On Sun, Jan 05, 2014 at 08:25:12AM -0800, GerdP wrote:<br>> >The question is:<br>> >If you get a list of oneway road (parts) which create routing islands, <br>> >is it really the only conclusion that these oneways are wrong?<br>> <br>> I cannot think of any other conclusion in the practice. See below for a <br>> somewhat artificial example.<br>> <br>> Before I left the academic world 10 years ago, I implemented Tarjan's <br>> algorithm for strongly connected components in a model checker tool. It <br>> was applied to the graph of reachable states (reachability graph) of the <br>> modelled system, which would typically be a high-level model of a <br>> distributed system or protocol.<br>> <br>> A desired property of any distributed algorithm is that its state <br>> diagram is strongly connected, that is, you can get from any valid state <br>> to any other valid state by performing a number of possible actions. <br>> <br>> When the reachability graph of a distributed system is not strongly <br>> connected, it usually means that one or more actors (processes, threads, <br>> whatever) are stuck. The system as a whole might not be in a deadlock, <br>> if some processes can keep doing something.<br>> <br>> There is a class of distributed algorithms called self-stabilizing <br>> algorithms. They have the additional property that you can get from any <br>> state (including invalid states) to the valid states. In the <br>> reachability graph of this kind of a distributed algorithm you would <br>> have a very large number of initial states (all possible states of the <br>> distributed system), and there would a strongly connected component of <br>> the valid states.<br>> <br>> Now, let me get back to the OSM domain. I guess we could think of a <br>> restricted area that only defines oneway exits to the public road <br>> network, but the entry roads are well-kept secrets (maybe enforced by <br>> law). If the road network within the restricted area is mapped, then it <br>> would form its own strongly connected component from which you can get <br>> to the strongly connected component of the public road network, but not <br>> vice versa. (By definition, the graph of strongly connected components <br>> is acyclic.)<br>> <br>> Marko<br>> _______________________________________________<br>> mkgmap-dev mailing list<br>> mkgmap-dev@lists.mkgmap.org.uk<br>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev<br></div> </div></body>
</html>