Refactor / rewrite WayConnectionTypeCalculator?

[matthijs]

While working on #19633, I dug around in WayConnectionTypeCalculator to understand how it works. I have not prior experience with the JOSM codebase, but this particular bit of code looks quite complex and took me the better part of a day to understand. Even though the problem it solves is also not quite trivial, I have the suspicion that the code could be made significantly simpler, probably by rewriting it from scratch. It looks like this code has evolved over time to add more complexity, but is now a collection of special cases and global variables, making it hard to see how everything interacts.

I won't have time right now to actually attempt this, but I wanted to maybe spark discussion and at least write down some of my thoughts somewhere.

One thing that was particularly confusing is the overloading of the "forward" and "backward" terms. These mean two things:

• The "forward" and "backward" roles in a relation limit the given ways to only be used in the indicated direction.
• In the code, these are used (e.g. in lastForwardWay or isOnewayLoopForwardPart to indicate the forward and backward direction of the entire route.

Using different terminology for the second one would make the code easier to understand. I could not come up with some good terms, but I'll use "non-reverse" and "reverse" direction below to at least distinguish them.

Because of this, it took me quite some time to realize that the roles do not actually reflect the route direction (i.e. you do not use them to assign ways to non-reverse or reverse parts of the route, in practice you would even mostly have "forward" roles when actual one-way streets are involved), just limit the direction a way can be used. The presence of these roles is used to limit a role to just one of the route directions, but the direction to which a way then belongs is implicit (the first way with a role is always non-reverse, including subsequent connecting ways, until a way that does not connect to the non-reverse route but does connect to the split point and becomes the first reverse way. Additional ways are added to either the non-reverse or reverse route, depending on where they fit. If a way fits both, it joins both parts together again.

There are also some small things I noticed in the code that sometimes produce slightly incorrect results, such as:

• The role is only taken into account for the first way, subsequent ways are just rotated as needed to connect. There is some code to detect this (handleOnewayFollows(), but that does not seem to work).
• When a route makes a figure 8, this is shown as a single big loop for a relation without roles, but when assigning forward to all members shows it as two loops.
• For connections between subrelations, it might connect to the first/last way in reverse (i.e. a way that overlaps between two subrelations is not detected).
• See also #7681, #18718, #11233

A more generic approach might also make it easier to implement #18645 (ignoring nodes in the connection graph). Maybe also #19217 and #18018 (invalid route order after splitting a way).

I would be inclined to generalize the code, maybe not even limiting it to hardcoded non-reverse and reverse parts, but just trying to find all connections between members of the relation and show them to the user (e.g. using multiple dotted lines where needed, or combining loops and dotted lines). This could make it easier to show connections around a inserted and unconnected node, or maybe even show small disconnected parts of a route, or excursions and alternatives (though those are better mapped using super-relations AFAIU).

Generalizing this entirely might result in a non-trivial problem, though, where you could maybe have a lot of possible permutations by reversing ways (which could maybe optimize for the least disconnected ways?) and which might end up needing to cross dotted lines to render it properly (I'm not entirely sure, maybe this could borrow some ideas from GUI git clients that also show such graph structures). Also, I'm not entirely sure if showing all connections is actually helpful, since routes (and probably other relations) are often intentionally specifically structured, so if JOSM only supports the recommended / actually used structures, that could even be better than supporting any structure at all.

Even so, it might be interesting to adopt a multiple-pass approach, where a first (more generic) pass collects information about possible connections between members (possibly recursing into subrelations), and a second pass actually deciding how to orient each member and which connections to actually make. The first pass could try *all* possible connections, with the downside of making this an O(n^{2) algorithm rather than O(n) as it is now.}

Also, the interface between the calculator and the GUI could be made a bit more generic and explicit. For example, it could support an arbitrary number of "threads" through the route, even when the calculator will only be limited to non-reverse and reverse (and maybe a third one for nodes/invalid members). And making connections more explicit (i.e. explicitly store which previous member a one-way member connects to, IOW where a dotted line comes from) might make it less likely to have rendering problems than with the current largely implicit datamodel.

Ok, I think those were most of the things I encountered or considered, hopefully this is at least somewhat helpful...

[matthijs]

I also had a look at the relation sorter, which is also somewhat complex, but has a cleaner structure already, using a two-pass approach building some maps with connections and then building from that.

From reading that, I realized that one improvement that could benefit both the sorter and the connection line display, is to find sequences of ways that (within the set of relation members) have no junctions (i.e. find nodes that connect exactly two ways), since a fully-connected graph will certainly include those sequences. For all further processing, these subsequences can then be viewed as if they were a single way, making it easier to make balanced choices in sorting / display (i.e. in common case without weird extra junctions, it is trivial to detect whether a split into two oneway sequences is going to join together again or not, which helps deciding which oneway sequences form two directions of the same route segment). I think this can also be useful for the connection rendering, since it makes it easier to do a bit of lookahead with thinks like deciding whether to start a backward way, or start a disconnected new segment.

[simon04]

The following queries list similar/related issues.

• query:keywords=~sort+relation
• query:keywords=~connectivity
• query:keywords=~public-transport-v1

Personally, I'm not motivated to look into this code (again). Trying to fix outstanding issues is a rather ungrateful task. The legacy public_transport:version=1 routes containing plenty of forward/backward/alternate roles are guaranteed to give you a headache.

Patches are highly welcome, though.

[skyper]

Talking about public_transport:version=1, there is no possibility to properly sort many complex relations.

So let's talk about other routes, especially foot, walking, hiking, running, bicycle, mtb, canoe, ski, sled and road. Here we have alternatives or links with own roles and additionally some guidepostes. Forward/backward is almost solved and for most of these relations support of a few roles is the remaining problem.