On Mon, Dec 30, 2013 at 01:25:34PM -0800, GerdP wrote:

I think the dead-end test can be done in StyledConverter. The test is quite similar to the one that is done in findUnconnectedRoads().

This sounds reasonable to me. The sooner the validation checks are done, the better, because we will have a more direct connection to the style language and the OSM data. This is the direction that mkgmap has been following recently, thanks to you and WanMil. Unfortunately I cannot spend much time in coding (I get too much of it at my day job). I can volunteer to test patches and do some analysis on the output. Best regards, Marko

Hi Gerd,

okay, I'll have a look at it during the next days.

Thanks! BTW, the diagnostics is not completely useless as it is now; it does include labels, which (when present) will identify the ways. But, in addition to normally unnamed highway=service, there could be some ways that are accidentally left unnamed, such as when splitting a way to a dual carriageway near a junction (Y-shaped). Then, both "oneway arms" of the "Y" could accidentally point to the same direction, which would trigger a warning. Marko

On Thu, Jan 02, 2014 at 04:27:23PM +0100, Gerd Petermann wrote:

attached is a patch for the high-prec-coord branch to perform the dead-end-check in StyledConverter. I did not remove the original code, so both tests are performed now. I think this helps to find differences.

Thanks! This looks verbose enough for my taste: 2014/01/02 19:42:16 WARNING (StyledConverter): 63240004.osm.pbf: Oneway road 55835321 with tags [oneway=yes,mkgmap:street=Pentinkaarre,name=Pentinkaarre,mkgmap:label:1=Pentinkaarre,highway=living_street,surface=paved] goes to nowhere at http://www.openstreetmap.org/?mlat=62.262185&mlon=24.710546&zoom=17 Maybe you could filter out the generated mkgmap:* tags, but I am OK with it. I guess that the logging output is too verbose to be read directly by a human anyway (without any searching or filtering, that is). This way is (was) P-shaped. The oneway=yes would be OK for the D-shaped loop of the P, but not for the 'foot'. I fixed this particular error, but left others there, so that we can do more cross-checking with subsequent patches. I got 23 Oneway warnings with your branch+patch, and 13 with trunk. The differences are as follows, after filtering out timestamps and sorting both outputs: * Different coordinates for the 13 old messages (as expected; this is thanks to the higher precision) * 'Extra' warning for the ways: 55835321 23152992 64148077 167346021 * 'Missing' warning for the ways: 200035193 220389737 25455464 42191422 53197410 131648853 50118184 The 'missing' warnings could be because the ways are connected to other ways for which map is not being generated, such as a highway=service,oneway=yes leading to a highway=service,oneway=yes,tunnel=yes,... that is omitted from the map. IMO the 'missing' warnings should be emitted; we should be checking that the generated map makes sense.

Please note that both checks will not recognize restriction relations which prohibit to enter or leave a oneway.

Right. Ignorance is bliss. :) A related note with oneways is that some mappers seem to generate redundant turn restrictions for oneways. For example, they would add a relation that prevents turning against the oneway from a motorway_link to the motorway lane. I wonder if we should emit warnings for such redundant relations? Best regards, Marko

On Thu, Jan 02, 2014 at 11:19:06AM -0800, GerdP wrote:

Hi Marko,

please check:

Marko Mäkelä wrote

...

* Different coordinates for the 13 old messages (as expected; this is thanks to the higher precision)

I don't yet see a reason for different coordinates. Did you really compare the output one program execution? Or did you use a different program for the "old" messages?

I did 2 comparisons with the output from 2 runs: With mkgmap/trunk r2916 With mkgmap/branches/high-prec-coord r2930 and your patch First, I compared the output of trunk to the output of branch, using the finland.osm.pbf from Geofabrik dated today, 02:16 UTC. There were 2 differences: (a) Variation of the coordinates in the 13 old-style messages (b) Addition of 10 new-style messages This was to be expected. What was not expected was the difference 13 vs. 10. To diagnose it, I performed another comparison within the output of the patched branch. Many of the "old" messages had direct counterparts in the "new" messages, but some "new" messages for "old" messages were missing, and some were extra (only "new" message for the way, no "old" one). In my previous message, I listed the OSM way IDs for both cases. I fixed one error (for one extra "new" message) in the OSM database, but I left the others intact, so that we will have some errors in the next finland.osm.pbf to check against. Marko

Hi Marko, found a few special cases: 1) the new dead-end-check is done before merging roads, so sometimes the reported way ids in the old RouteNode check refer to merged roads. When you want to compare results you should use --x-no-mergeroads so that you see the correct way ids. 2) The new check did not ignore points that lie on the boundary, only those that were outside of the tile boundary 3) The new check did not recognize P-shaped oneways as self-connecting. 4) The new check used a different (wrong) interpretation of the meaning of the LEVEL parameter in --report-dead-ends=LEVEL option. Attached is a new version of the patch. One possible problem case in the new check: If a oneway X is connected to a way Y that has just one (or more) identical points, the dead-end-check for X will say that the way is not a dead end, but later the way Y will be deleted with a corresponding warning and the old dead-end-check reports the dead-end for way X. I think this is okay as long as you see the warning for way Y. Ciao, Gerd

Date: Thu, 2 Jan 2014 11:59:27 -0800 From: gpetermann_muenchen@hotmail.com To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] Diagnostic warnings for dead-end oneway highway=service

Hi Marko,

okay, thanks for the explanation. I'll look at the differences tomorrow.

Gerd

Marko Mäkelä wrote

...

On Thu, Jan 02, 2014 at 11:19:06AM -0800, GerdP wrote:

...

Hi Marko,

please check:

Marko Mäkelä wrote

...

* Different coordinates for the 13 old messages (as expected; this is thanks to the higher precision)

I don't yet see a reason for different coordinates. Did you really compare the output one program execution? Or did you use a different program for the "old" messages?

I did 2 comparisons with the output from 2 runs:

With mkgmap/trunk r2916 With mkgmap/branches/high-prec-coord r2930 and your patch

First, I compared the output of trunk to the output of branch, using the finland.osm.pbf from Geofabrik dated today, 02:16 UTC.

There were 2 differences:

(a) Variation of the coordinates in the 13 old-style messages (b) Addition of 10 new-style messages

This was to be expected.

What was not expected was the difference 13 vs. 10. To diagnose it, I performed another comparison within the output of the patched branch. Many of the "old" messages had direct counterparts in the "new" messages, but some "new" messages for "old" messages were missing, and some were extra (only "new" message for the way, no "old" one).

In my previous message, I listed the OSM way IDs for both cases. I fixed one error (for one extra "new" message) in the OSM database, but I left the others intact, so that we will have some errors in the next finland.osm.pbf to check against.

Marko _______________________________________________ mkgmap-dev mailing list

...

mkgmap-dev@.org

...

http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

-- View this message in context: http://gis.19327.n5.nabble.com/Diagnostic-warnings-for-dead-end-oneway-highw... Sent from the Mkgmap Development mailing list archive at Nabble.com. _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

Hi Marko, reg. p-shaped: The error was not in the foot, but in the other end. My understanding is that that you can travel in that loop like in a roundabout, so it is not a dead end. OK? Gerd

...

3) The new check did not recognize P-shaped oneways as self-connecting.

This was not a bug in the new check, but a bug in the old check!

I agree that by definition, looped ways cannot be dead ends.

For the purpose of detecting dead ends, we could ignore non-branching loops formed by a sequence of ways. Actually, it does not matter if the non-branching loops are oneway!

If there is no non-looped way connected to both ends of the "foot" of the P, then the foot of the P forms a dead-end oneway. That is, a P-shaped oneway should be treated just like an I-shaped oneway that is obtained by removing the looped part.

Maybe you could use this idea to improve dead-end checks? Note that a roundabout does not count as a non-branching loop, unless it is connected to a single oneway flare road only.

...

Attached is a new version of the patch.

Thanks, I will try it later for today's data. I already ran trunk and the previous patch on the data.

...

I think this is okay as long as you see the warning for way Y.

Me too, it is OK to be silent about some part of an error scenario, as long as some of the connected ways get flagged. I usually download a region around the problematic spot in order to figure out what the intention is and how it should be fixed.

Marko _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

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_algori... 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

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

On Mon, Jan 06, 2014 at 08:02:57PM +0100, Gerd Petermann wrote:

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 ;-)

Yeah. :) By the way, I was wondering how you have so much expertise and energy to work on this. (I cannot code anything big on spare time, because my brain needs a break after working on complex coding problems at the day job.) Now I got the answer. Nice to see that active OSM development is not only for students and young people. Your example is very similar to using a model checker. For a safety property violation (say, an assertion on the global state, or a check for a system-wide deadlock) the model checker would give you a (shortest) path of actions leading from the start to the error. For a liveness property violation, the counterexample would be a path to a non-progressing loop, plus the loop itself.

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.

Right. The "global" check could at most say "something might be wrong", and human intervention would be required. In my experience, even for "local" errors it is useful to look at the surroundings, to see if the JOSM Validator reports any errors nearby.

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

One option could be to emit a warning, saying that we are going to strip oneway=* from way X in order to avoid a potential problem. This could be enabled by --report-dead-ends=3 if we want this to be optional. Also, what would the Garmin routing algorithms (different versions of Mapsource etc.) do with such data? For example, can the routing get stuck if a P-shaped oneway (with no junctions to other roads, besides from the foot of the P) is the closest way to the starting point or the destination point? Does it matter if the P is split into "foot" and "loop" parts in the Garmin map? Marko

Hi Marko,

With the newer patch and the data from last night, the new check did not report any issues that were missed by the old check. The new check failed to report these ways that were flagged by the old check in trunk: 200035193,220389737,25455464,42191422,53197410,131648853,50118184

Strange, after sorting I don't see a single difference for finland. Please check: When I split latest finland.osm.pbf with max-nodes=1000000 these ways are all close to tile boundaries Results with my tiles: 200035193,42191422: not reported 220389737,25455464,53197410,131648853,50118184: reported by both checks Please post one of your tiles (the input file) with a difference. Attached is also the style that I use to test the dead-end-check. Gerd

Hi Marko, I was able to reproduce your results. You don't use parameter --x-no-mergeroads in your script as I recommended. The merge algo doesn't look at the tag mkgmap:dead-end-check, so it may merge a way with that tag into a way without it. I did not change that in RoadMerger because we want to replace the old code. I think it looks good, I just have to add code for the p-shaped oneways. By the way: Why do you use --overlap=10000 for splitter? Is the keep-complete option not working for you? Gerd

Date: Sat, 4 Jan 2014 13:05:17 +0200 From: marko.makela@iki.fi To: mkgmap-dev@lists.mkgmap.org.uk Subject: Re: [mkgmap-dev] Diagnostic warnings for dead-end oneway highway=service

Hi Gerd,

...

...

With the newer patch and the data from last night, the new check did not report any issues that were missed by the old check. The new check failed to report these ways that were flagged by the old check in trunk: 200035193,220389737,25455464,42191422,53197410,131648853,50118184

Strange, after sorting I don't see a single difference for finland.

I am using manually assigned tiles. My scripts are at http://www.polkupyoraily.net/osm/ with the most important ones being http://www.polkupyoraily.net/osm/files/areas.list http://www.polkupyoraily.net/osm/files/osm2img.sh

...

Please post one of your tiles (the input file) with a difference.

There are two tiles with one message (nowhere near the tile borders):

63240004: 2822016,956256 to 2916352,1172416 # : 60.553894,20.519027 to 62.578125,25.157318

2014/01/03 23:34:09 WARNING (RouteNode): 63240004.osm.pbf: Oneway road (http://www.openstreetmap.org/browse/way/131648853) goes nowhere at http://www.openstreetmap.org/?mlat=61.498772&mlon=23.777456&zoom=17

63240010: 3014656,1111040 to 3067072,1409024 # : 64.687500,23.840332 to 65.812225,30.234375

2014/01/03 23:35:00 WARNING (RouteNode): 63240010.osm.pbf: Oneway road (http://www.openstreetmap.org/browse/way/50118184) goes nowhere at http://www.openstreetmap.org/?mlat=65.011645&mlon=25.467852&zoom=17

Most messages are for this tile:

63240002: 2784459,1093376 to 2822016,1195648 # : 59.748008,23.461304 to 60.553894,25.655823

2014/01/03 23:34:24 WARNING (RouteNode): 63240002.osm.pbf: Oneway road (http://www.openstreetmap.org/browse/way/25455464) goes nowhere at http://www.openstreetmap.org/?mlat=60.172919&mlon=24.947340&zoom=17 2014/01/03 23:34:25 WARNING (RouteNode): 63240002.osm.pbf: Oneway road (http://www.openstreetmap.org/browse/way/42191422) goes nowhere at http://www.openstreetmap.org/?mlat=60.212344&mlon=25.084937&zoom=17 2014/01/03 23:34:25 WARNING (RouteNode): 63240002.osm.pbf: Oneway road (http://www.openstreetmap.org/browse/way/53197410) goes nowhere at http://www.openstreetmap.org/?mlat=60.212325&mlon=25.084907&zoom=17 2014/01/03 23:34:25 WARNING (RouteNode): 63240002.osm.pbf: Oneway road (http://www.openstreetmap.org/browse/way/200035193) goes nowhere at http://www.openstreetmap.org/?mlat=60.203610&mlon=24.659707&zoom=17 2014/01/03 23:34:25 WARNING (RouteNode): 63240002.osm.pbf: Oneway road (http://www.openstreetmap.org/browse/way/220389737) goes nowhere at http://www.openstreetmap.org/?mlat=60.176588&mlon=24.807431&zoom=17

AFAICT, none of these are near the tile boundaries. The min/max lat is between 60.17 and 60.22 (well within 59.748..60.553) and the min/max lon is between 24.65 and 25.085 (inside 23.46..25.65).

...

Attached is also the style that I use to test the dead-end-check.

I am using the default style. That could explain the difference, because the default style is omitting some tunnels from the map.

Marko _______________________________________________ mkgmap-dev mailing list mkgmap-dev@lists.mkgmap.org.uk http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

On Sat, Jan 04, 2014 at 09:43:32PM +0200, Marko Mäkelä wrote:

On Sat, Jan 04, 2014 at 02:05:11PM +0100, Gerd Petermann wrote:

...

You don't use parameter --x-no-mergeroads in your script as I recommended.

Ah, sorry, I forgot that piece of your advice :(

OK, now I think I understand this (without trying that option yet; I think that merging roads is generally a good idea, even with this bug being present). Many of the warnings that I get are for situations like this: -------------->================>F where ----> is the oneway that I get a warning for, and ====> is another oneway that ends in a fixme=continue or similar. I guess that the two ways get merged, but tags are not being merged, or the flag to suppress dead-end checks gets discarded. Marko

Hi Marko, okay, let me know if the patch works for you. Gerd Marko Mäkelä wrote

Hi Gerd,

...

...

I figured out that it would be nice to display all tags of the dead-end oneway, like we do in MultiPolygonRelation, so that my mkgmap wrapper script could filter out any oneway warnings for highway=service.

I am not sure if I got that right. If you want to suppress the dead-end-check for all ways with specific tags, you can do it in the style (add the tag mkgmap:dead-end-check=false to the way)

I do not want to suppress dead-end-checks altogether. I do it on a case-by-case basis, either by adding fixme=continue to the endpoint (this will set mkgmap:dead-end-check=false on the way; I wrote the code to do that), or by filtering out messages.

Here is a slightly different example:

... Motorway exit 67 (http://www.openstreetmap.org/?mlat=60.47712&mlon=26.27170&zoom=17) has no motorway!

This is for node 1909615887. The message fails to mention the tags of the attached way 181498435 (highway=construction, construction=motorway, ...).

I have a file that I pass to "grep -vf" for suppressing known warnings. I would not want to add a suppression for this message as it is now, because it would remain suppressed after the construction is completed and the way gets tagged highway=motorway. If my suppression regexp were something like

Motorway exit 67 .*mlat=60\.47712&mlon=26\.27170.*highway=construction

then it would no longer suppress the warning if the way is changed to highway=motorway and some map editor breaks something. (Even better than coordinates would be the ID of the highway=motorway_exit node.)

Marko _______________________________________________ mkgmap-dev mailing list

mkgmap-dev@.org

http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

-- View this message in context: http://gis.19327.n5.nabble.com/Diagnostic-warnings-for-dead-end-oneway-highw... Sent from the Mkgmap Development mailing list archive at Nabble.com.