[patch] Add a check for loops in directional waterways

[TrickyFoxy]

One of the frequent problems in Maproulette to fix problems with waterways in Russia is their cycling. Probably due to the fact that no editor highlights such situations.

​https://maproulette.org/browse/projects/42201

Moreover, the situations may not be much more obvious. (see gif)

[gaben]

Somewhat related to #17533. Probably needs pathfinding?

[gaben]

I wrote a loop detector for waterways, probably usable for the road network as well. Currently testing it, working fine, but the performance is not acceptable yet.

[gaben]

work in progress patch: the algorithm is correct but insanely slow on a large dataset

[gaben]

Good news! The performance issue is fixed. Just got it working in a country-size drainage network. I'll clean up, annotate the code and attach the patch in a few days.

[gaben]

stable version, added tests

[gaben]

Please review the patch.

In very large drainage networks (~1M graphs, country size), sometimes it's prone to StackOverflowError because of deep recursive calls. Increasing the stack size seems to remediate the problem. Also, I encountered it only on Java 8 and 11 but not on 17.

[taylor.smock]

@gaben: Can you not move stuff around so much? I'd also prefer to avoid losing inline comments (specifically stuff like /* directed */ -- it is useless with modern IDEs, but not everyone is going to be looking at the code in an IDE).

As a heads up, GerdP is troubleshooting a different problem with NodeGraph (see #22614) which can cause JOSM to freeze, so I'd strongly prefer to avoid a bunch of changes there right now.

For the SOE, I'm going to guess that the graph.addAll(buildGraph(referrer)); call is the cause, so you can probably trigger the SOE by finding the waterway with the most ways and running the validator on that.

If you want to try to fix it, something like the following would work:

    private Collection<Way> buildGraph(Way way) {
        if (visitedWays.contains(way))
            return Collections.emptySet();

        final Set<Way> graph = new HashSet<>();

        final Deque<Way> unprocessed = new ArrayDeque<>();
        unprocessed.add(way);
        while (!unprocessed.isEmpty()) {
            Way current = unprocessed.pop();
            if (!visitedWays.contains(current)) {
                visitedWays.add(current);
                for (Node node : current.getNodes()) {
                    // this checks to see if the node is referred to by at least 2 ways. One of which is current.
                    if (node.isReferredByWays(2)) {
                        Collection<Way> referrers = node.referrers(Way.class)
                                .filter(this::isPrimitiveUsable)
                                .filter(candidate -> candidate != current)
                                .collect(Collectors.toSet());

                        graph.addAll(referrers);
                        unprocessed.addAll(referrers);
                    }
                }
            }
        }
        return graph;
    }

I'll note that passes your current tests. If something is wrong from a logic perspective, please add a test so that when we do get an SOE, we fix it properly. :)

EDIT: NVM. I got some data downloaded, and it actually occurred in strongConnect.
EDIT2: The test should also be highlighting the problematic ways not the nodes of the way.

[gaben]

Replying to taylor.smock:

@gaben: Can you not move stuff around so much? I'd also prefer to avoid losing inline comments (specifically stuff like /* directed */ -- it is useless with modern IDEs, but not everyone is going to be looking at the code in an IDE).

In most places, these inline comments are missing.

I restructured the file because it wasn't up to the standards I've seen in JOSM: missing documentation, typos and messed up order. Do you want a new ticket for that?

As a heads up, GerdP is troubleshooting a different problem with NodeGraph (see #22614) which can cause JOSM to freeze, so I'd strongly prefer to avoid a bunch of changes there right now.

I'm already subscribed to that ticket. Not sure let's ask GerdP.

For the SOE, I'm going to guess that the graph.addAll(buildGraph(referrer)); call is the cause, so you can probably trigger the SOE by finding the waterway with the most ways and running the validator on that.

Thanks, I'll investigate once I have time (>2 weeks from now).

EDIT2: The test should also be highlighting the problematic ways not the nodes of the way.

It's a workaround. If the validation would highlight the ways, clicking on the error message would "hide" the actual problem. Imagine many kilometers long ways where everything is highlighted although the problem is only in a small area and hard to spot. Zoom into the problem wouldn't help. Probably I can attach an example.

The best would be if JOSM could highlight way segments where the two end nodes are not consecutive.

[taylor.smock]

Replying to gaben:

In most places, these inline comments are missing.

I restructured the file because it wasn't up to the standards I've seen in JOSM: missing documentation, typos and messed up order. Do you want a new ticket for that?

I don't mind the added documentation, its just that any patches that depend upon the current order won't apply cleanly in the future, and since we have another ticket where someone is actively looking at that code, I don't want to mess them up.

For the SOE, I'm going to guess that the graph.addAll(buildGraph(referrer)); call is the cause, so you can probably trigger the SOE by finding the waterway with the most ways and running the validator on that.

Thanks, I'll investigate once I have time (>2 weeks from now).

Like I noted in my first edit, it was actually in the Tarjan#strongConnect method, unless you were running into the SOE where I initially guessed. The strongConnect method will have an SOE when there are a large number of nodes.

EDIT2: The test should also be highlighting the problematic ways not the nodes of the way.

It's a workaround. If the validation would highlight the ways, clicking on the error message would "hide" the actual problem. Imagine many kilometers long ways where everything is highlighted although the problem is only in a small area and hard to spot. Zoom into the problem wouldn't help. Probably I can attach an example.
The best would be if JOSM could highlight way segments where the two end nodes are not consecutive.

I think we do that with highlightWaySegments (from TestError.Builder). You just have to decide which segments to highlight. A naive approach would be to highlight any waysegment where it is connected to another way.
There is also a highlightNodePairs method which might be better.

[GerdP]

Replying to gaben:

As a heads up, GerdP is troubleshooting a different problem with NodeGraph (see #22614) which can cause JOSM to freeze, so I'd strongly prefer to avoid a bunch of changes there right now.

I'm already subscribed to that ticket. Not sure let's ask GerdP.

I've only a minimal patch right now to implement the check for max. two terminal nodes. Nobody should wait for me, I am not very active reg. coding. I'd be happy if someone could implement the use of a ProgressMonitor.

[taylor.smock]

Ticket retargeted after milestone closed

[gaben]

A short status update: two weeks ago I got it working without exceptions with the recursive Tarjan algorithm present in the patch. The performance is even better, but as a byproduct, fewer nodes get highlighted in red, which makes the visual presentation less useful. Still thinking of a solution.

[GerdP]

Just a remark: I often add waterway=ditch without knowing the correct direction. Sometimes I still don't know it after survey, since in my area there might be no movement in the water. So, I'd suggest to exclude waterway=ditch from this test or at least allow to do that with a preference.

[gaben]

Hmm, what about decreasing the severity to warning for ditches?

Anyway, I'm planning a plugin with waterway direction autofix capability and probably I'll need some help. Algorithm-wise something like detailed in ​this journal.

[taylor.smock]

Ticket retargeted after milestone closed

[taylor.smock]

Ticket retargeted after milestone closed

[taylor.smock]

Moving WIP patch off of milestone.

[gaben]

Yeah, good idea. In the last days I got it working properly, but now there is a new issue.
How would you like to see the results? There are a few options:

• highlight the connection nodes only (current state)
• highlight way segments (I'm not sure if possible with latest JOSM)
• highlight all nodes along the cycle

[taylor.smock]

Replying to gaben:

• highlight the connection nodes only (current state)
• highlight way segments (I'm not sure if possible with latest JOSM)

This is possible. See TestError.Builder#highlightWaySegments​.

• highlight all nodes along the cycle

I'd strongly prefer highlighting the way segments -- I think it will be vastly more understandable than having a bunch of nodes highlighted on the problematic way.

[gaben]

Replying to taylor.smock:

This is possible. See TestError.Builder#highlightWaySegments​.

You are right, I was mistaken by the WaySegment description ("A segment consisting of 2 consecutive nodes out of a way.").

A short update on the patch. I got the algorithm working without limitations (no more stack overflow error), performance is even better, runtime is comparable to Crossing ways test. One thing remains for now, the configuration as requested by @GerdP in comment:17.

[gaben]

Please review the code :)

[taylor.smock]

Some quick comments on the code:

• private static List<String> directionalWaterways; where it is then set in public void startTest(...) doesn't make sense. It should probably be non-static.
• >=0 if the node is found or: JavaDoc doesn't like >. Use >. This is due to JavaDoc interpreting HTML.
• public static final class Tarjan: Is this supposed to be usable for other classes? If so, maybe it should be in its own file.

I haven't run it yet, and I do want to prior to applying it, but I have no significant object at this time.

[gaben]

Oops, yep. I was working on the patch late evenings, maybe I need to get some rest. I'm in CET...

For the last one, where should I put the file? Ideally I'd put all the algorithms like this one in a common folder.

[taylor.smock]

Ticket retargeted after milestone closed

[taylor.smock]

Ticket retargeted after milestone closed

[taylor.smock]

Ticket retargeted after milestone closed

[taylor.smock]

Ticket retargeted after milestone deleted

[gaben]

Crated a PR on GH: ​pull/128.

[gaben]

The patch on GH is ready for review.

[taylor.smock]

Ticket retargeted after milestone deleted

[taylor.smock]

Ticket retargeted after milestone closed

[gaben]

So is there any objection on the patch? Please find the latest iteration on GitHub.

(@GerdP if you are interested, it's also accessible via ​https://patch-diff.githubusercontent.com/raw/JOSM/josm/pull/128.patch)

[GerdP]

Thanks, gaben. I just tried to apply 128.patch on clean r18934, but I get a strange error message:

C:\josm\core>svn patch c:\Users\Gerd\Downloads\128.patch
U         src\org\openstreetmap\josm\data\osm\NodeGraph.java
U         src\org\openstreetmap\josm\data\validation\OsmValidator.java
A         src\org\openstreetmap\josm\data\validation\tests\CycleDetector.java
A         test\data\CycleDetector_test_wikipedia.osm
A         test\unit\org\openstreetmap\josm\data\validation\tests\CycleDetectorTest.java
U         test\unit\org\openstreetmap\josm\data\validation\tests\CycleDetectorTest.java
U         src\org\openstreetmap\josm\data\validation\OsmValidator.java
U         src\org\openstreetmap\josm\data\validation\tests\CycleDetector.java
U         src\org\openstreetmap\josm\data\osm\NodeGraph.java
A         src\org\openstreetmap\josm\data\validation\algos
A         src\org\openstreetmap\josm\data\validation\algos\Tarjan.java
A         src\org\openstreetmap\josm\data\validation\algos\package-info.java
U         src\org\openstreetmap\josm\data\validation\tests\CycleDetector.java
U         src\org\openstreetmap\josm\data\osm\NodeGraph.java
U         src\org\openstreetmap\josm\data\osm\NodeGraph.java
U         src\org\openstreetmap\josm\data\validation\algos\Tarjan.java
U         src\org\openstreetmap\josm\data\validation\algos\package-info.java
svn: E720003: Can't open 'C:\josm\core\test\data\regress\21881\svn-2811B0B6': Das System kann den angegebenen Pfad nicht finden.

The patch is loaded with extra data from git so I really have no idea where this comes from.

[gaben]

There is a new regression folder 21881, maybe you need to create it manually before applying the patch, which is strange.

[GerdP]

If I got that right the patch changes the same file multiple times. Maybe one of the changes requires a unixoid system?

[gaben]

I learnt something, there is a difference between patch and diff. The patch contains all the commits by commit, the diff is only diff.

Please try the ​diff or if it still doesn't work, I uploaded the changes in SVN format: 21881_github.patch​.

Replying to GerdP:

Maybe one of the changes requires a unixoid system?

I think you only need git, and the issue is that SVN and Git use different patch format.

[GerdP]

OK, that worked. I'll have a closer look tomorrow. Quick question: Why do you remove the comments in NodeGraph which explain the meaning of a parameter like false or true?

[gaben]

See IntelliJ's ​inlay hints. If there is a comment, I cannot see the real parameter name from the method. Imagine the parameter gets reworded, and the comment remains there. Having a hardcoded comment can create misleading assumptions (happened before).

[gaben]

reupload with all the files

[GerdP]

I have attached an example which shows why I am afraid of this test.
One error has 202 highlighted nodes and it's almost impossible to understand why there's an error.

I think the water in this area simply has no fixed flow direction. Sometimes rain water goes into the nearby river Hunte, sometimes water from the Hunte goes into these waterways, so the data might even be correct and we simply have no good tagging to describe this situation.

By the way: I worked for a company which made (and probably still makes) a good money with a graphical tool that shows dependency graphs in networks as defined in job schedulers (where a job X has to wait for the completion of one or more other jobs before it can be started as they produce or update input for X)
These dependency graphs also can have loops (circular dependencies) and these loops where feared by the operators as it is very hard to tell which dependency is wrong and the next nightly batch production was blocked until a solution was found. Can cost milions if the wrong dependency is removed and important jobs are executed with incomplete or out-agaed input.
I remember the typical question was: Which job is responsible for the loop? And the answer was: All!

So, back to the waterways: In complex situations like in my example in can be vey difficult to find the set of ways which have to be reversed, and neither the error message nor the hilited nodes give much help.

[gaben]

I still think it's a useful warning, let me think about the problem. I see the issue in the sample file.

One solution could be color coded highlight (starting with one color and blending to different one, for example), because the graph gives the order in which we could clearly see the cycle.

[GerdP]

It gives you the order but you can't say which part is wrong, can you? There is no first or known good element in such a loop.

[GerdP]

With my sample: When I select way ​https://www.osm.org/way/1059889368 and run a partial validation, why does it report the loop in the east?

[gaben]

Replying to GerdP:

With my sample: When I select way ​https://www.osm.org/way/1059889368 and run a partial validation, why does it report the loop in the east?

In case of partial validation, the graph building starts from the selected way(s). They'll create at least one graph, then all issues within these are highlighted, no matter which way is selected.

In this example the ​way/1059889368 is part of a bigger graph, that's why you see the error in the east.

It can be improved, e.g. report only if the selected way is part of an issue.

[GerdP]

It can be improved, e.g. report only if the selected way is part of an issue.

Yes, that would happen with my patch 23397-beta2.patch for #23397 if the created TestError contains the proper primitives.

[gaben]

After applying ticket:23397:23397-beta2.patch​, the partial validation no longer works for this test :/

[GerdP]

Why not?

[gaben]

I haven't checked yet, but my suspicion is that the patch in #23397 is looking for the selected way among the errors, but this test is highlighting way segments, not ways, therefore being removed.

[GerdP]

That's why I wrote that the test has to create the proper list of primitives. The highlighted elements are only for rendering and zooming.

[GerdP]

Lookking at the patch I would expect that the filtering works, means, when my example way is selected the error message for the loop is correctly removed as the way is not in possibleCycle. Isn't it?

[gaben]

Sorry, I meant to say nodes.

Yes, the filtering works. The issue is that the CycleDetector is working on nodes entirely; possibleCycle contains nodes. If you want to apply #23397, I have to rewrite this part too :(

[GerdP]

Ah, now I understand. Well, the test is about waterways, so I think it should blame ways. That said I agree that the filtering in #23397 relies on assumptions like this. I have to check all java tests before applying that.

[gaben]

I fixed the test primitive issue for #23397, but with a serious performance penalty, unfortunately. It is 2-4 times slower due to a second run, where the nodes are backtracked to parent ways. I'm still trying to minimize the impact. Probably there are ways I couldn't think of yet :)

[gaben]

Performance penalty is now under 5%, I love programming.

@GerdP, you can check the new patch via the old urls.

Edit: there is one more issue with the highlight, which is visible in the example dataset between ​node/9737844597 and ​node/9737844598.

[GerdP]

Yes, that gap looks strange. I've tested with your patch and the one for #23397.
When I select way 1059889389 and run validator a lot of segments in the north are highlighted. When I double click on the error only way 1059889389 is selected.
I would expect that any way that is part of the cycle is selected. Also, when I click on a way that is highlighted, it should enable the "Lookup" icon in the validator tree.
And of course the question is why way 1059889389 is considered to be part of the cycle.

[taylor.smock]

Ticket retargeted after milestone closed

[gaben]

Good catch, thank you! That way (1059889389) is reported because one of the end nodes is part of a cycle. Fixed locally.

I'll look into the highlight issue from comment:59 in the following days.

[taylor.smock]

Ticket retargeted after milestone closed

[taylor.smock]

Ticket retargeted after milestone closed

[taylor.smock]

Ticket retargeted after milestone closed

[gaben]

@GerdP, could you please have a look again on the latest version of the patch? I think all the issues have been fixed for now. (It's available in the usual way, see the diff link in comment:42.)

[GerdP]

I've downloaded it. Ping again if you don't get feedback within 5 days.

[GerdP]

Seems to work quite well now. I've found one special case in the area around ​https://www.osm.org/way/1187387723
Is this really an error or should fairway be removed from the default list for directionalWaterways?
The wiki says "Create a simple linear way, in the direction of flow if relevant, and add waterway=fairway".

[gaben]

Thanks for reviewing! Good point, fairway doesn't make sense. Also after looking at the list, tidal_channel neither, from the wiki:

bi-directional flow of salty water which depends on the tides

Diff link in comment:42 contains these findings (it is auto-updating the content after I push commits to the GitHub PR).

[GerdP]

I also found tidal_channel suspicious but the wiki states "The direction of the way should be towards the sea (i.e. the direction of water flow at low tide)."

[gaben]

Hmm okay. JOSM and also iD shows the direction of tidal_channels. Added back for now.

[gaben]

Is there anything else to do?

[GerdP]

I just checked the code coverage and it seems that isConsecutive() always returns true. Do you have an example where this test is needed?

[gaben]

Analysis: the graphMap is an adjacency list representation of the underlying waterway node data (this is important). E.g. from 21881_not_consecutive.osm​:

n6855025171 -> {n6855025169, n9044997814},
n9044997814 -> {n6855025171, n9044997815}

which means ​node/6855025171 connects to the next two nodes (there is a Y intersection).

The isConsecutive() asks if the node order is 6855025171 -> 9044997814 on ​way/732065019. Answer is no, but why is it asking this exactly?

Because all the information we have is that these 4 nodes create a cycle: {6855025171, 9044997814, 9044997815, 6855025172} and we trying to create a graph for the error highlighting with the following code:

// build new graph exclusively from SCC nodes
for (Node node : nodes) {
    for (Node successor : graphMap.get(node)) {
        // check for outbound nodes
        if (nodes.contains(successor)) {
            pairs.add(new Pair<>(node, successor));
        }
    }
}

Among the others here we get the pair {n6855025171, n9044997814}, and since both nodes are part of w732065019 and w732065020 we need to test both. It's aligning only on w732065020, hence the isConsecutive() returns false for the other.

Generally it's not causing an issue, but this time there is an error in the dataset.

[GerdP]

In 19062/josm:

fix #21881: Add a check for loops in directional waterways
Patch by gaben, slightly modified

• implements Tarjan algorithm to find strongly connected components
• new preference validator.CycleDetector.directionalWaterways contains the list of waterway values which should be checked

[GerdP]

Thanks for the example, I've added a reduced version as 2nd unit test.

[gaben]

Oops, the HistoryLoadTask.java modifications from #23645 slipped in the commit r19062.

[GerdP]

In 19063/josm:

see #21881: revert unintended change for different ticket

[gaben]

Thank you! Wiki updated https://josm.openstreetmap.de/wiki/Help/Preferences/Validator?action=diff&version=68

[GerdP]

Unit test WaySegmentTest fails because of the changed message text. I think I just change the expected text?

test/unit/org/openstreetmap/josm/data/osm/WaySegmentTest.java

@@ -36 +36 @@
         assertEquals(WaySegment.forNodePair(w, n1, n4).getLowerIndex(), 4);
         assertEquals(WaySegment.forNodePair(w, n4, n1).getLowerIndex(), 5);
         IllegalArgumentException iae = assertThrows(IllegalArgumentException.class, () -> WaySegment.forNodePair(w, n3, n4));
-        assertEquals("Node pair is not part of way!", iae.getMessage());
+        assertEquals("The node pair is not consecutive part of the way!", iae.getMessage());
     }
 }

[GerdP]

In 19064/josm:

see #21881 Add a check for loops in directional waterways

• fix @since xxx
• adapt unit test

[gaben]

Replying to GerdP:

Unit test WaySegmentTest fails because of the changed message text. I think I just change the expected text?

One more place needs to be updated to stay consistent. Sorry, I missed that :(

src/org/openstreetmap/josm/data/osm/IWaySegment.java

@@ -107 +107 @@
             }
             endIndex--;
         }
-        throw new IllegalArgumentException("Node pair is not part of way!");
+        throw new IllegalArgumentException("The node pair is not consecutive part of the way!");
     }
 
     /**

[GerdP]

Thinking again about it I prefer the old message as it matches the javadoc and easier to understand. What was the reason to change it?

[gaben]

The message misled me multiple times in the past few years when encountered this IAE.

It said Node pair is not part of way!, which turns out is not always true. In the above example (comment:74) the two nodes are part of the way, just not consecutive in the way direction, which is a requirement for creating WaySegment as it iterates node by node.

If needed, the javadoc can be adjusted as well to reflect the usage.

[GerdP]

Ah, I always understand "Node pair" as synonym for way segment. So maybe "Node pair is not a segment of the way!"

[GerdP]

suggested text in message and javadoc

[GerdP]

I think the code in WaySegment.forNodePair() is wrong. Have a way w with nodes n1,n2,n3 and call
WaySegment.forNodePair(w, n2, n1)
I think this should throw the exception?

[GerdP]

add check to make sure that forNodePair doesn't return WaySegment with index -1

[GerdP]

In 19065/josm:

see #21881 Add a check for loops in directional waterways
Fix code in WaySegment and IWaySegment

• change text in Exception to "Node pair is not a single segment of the way!" and move it to constant IWaySegment.NOT_A_SEGMENT
• fix error in WaySegment.forNodePair and IWaySegment.forNodePair
• add unit test for further invalid node pairs

[gaben]

Yesterday I got busy with my microcontroller, but checked just now, and I see the -1 is coming from lastIndexOf() function. How has nobody caught it up until now? :)

[GerdP]

Probably because all places where the method was called iterated over the way nodes.