Combine ways may not find best solution with oneways

[GerdP]

What steps will reproduce the problem?

1. load attached file with three oneway roads
2. press CTRL+A to select all elements
3. press C to combine the ways

What is the expected result?

A way that goes through nodes B-C-A-B-D-E-A-D so that nothing is reversed

What happens instead?

A popup appears that asks if directions should be changed (and requires further changes).

Please provide any additional information below. Attach a screenshot if possible.

Found this while looking at #22614. The algorithm in NodeGraph.buildSpanningPath() stops when it finds a path, it doesn't try to find one that doesn't involve any direction changes.
Edit: Even if I remove the way B-D JOSM doesn't find the simple solution A-B-C-A-D-E-A

Relative:URL: ^/trunk
Repository:UUID: 0c6e7542-c601-0410-84e7-c038aed88b3b
Last:Changed Date: 2023-01-03 21:28:24 +0100 (Tue, 03 Jan 2023)
Revision:18622
Build-Date:2023-01-04 02:30:56
URL:https://josm.openstreetmap.de/svn/trunk

Identification: JOSM/1.5 (18622 en) Windows 10 64-Bit
OS Build number: Windows 10 Home 2009 (19045)
Memory Usage: 261 MB / 1972 MB (135 MB allocated, but free)
Java version: 17.0.4+8-LTS, Azul Systems, Inc., OpenJDK 64-Bit Server VM
Look and Feel: com.sun.java.swing.plaf.windows.WindowsLookAndFeel
Screen: \Display0 1920×1080 (scaling 1.00×1.00)
Maximum Screen Size: 1920×1080
Best cursor sizes: 16×16→32×32, 32×32→32×32
System property file.encoding: Cp1252
System property sun.jnu.encoding: Cp1252
Locale info: en_DE
Numbers with default locale: 1234567890 -> 1234567890
VM arguments: [-Djpackage.app-version=1.5.18531, --add-modules=java.scripting,java.sql,javafx.controls,javafx.media,javafx.swing,javafx.web, --add-exports=java.base/sun.security.action=ALL-UNNAMED, --add-exports=java.desktop/com.sun.imageio.plugins.jpeg=ALL-UNNAMED, --add-exports=java.desktop/com.sun.imageio.spi=ALL-UNNAMED, --add-opens=java.base/java.lang=ALL-UNNAMED, --add-opens=java.base/java.nio=ALL-UNNAMED, --add-opens=java.base/jdk.internal.loader=ALL-UNNAMED, --add-opens=java.base/jdk.internal.ref=ALL-UNNAMED, --add-opens=java.desktop/javax.imageio.spi=ALL-UNNAMED, --add-opens=java.desktop/javax.swing.text.html=ALL-UNNAMED, --add-opens=java.prefs/java.util.prefs=ALL-UNNAMED, -Djpackage.app-path=%UserProfile%\AppData\Local\JOSM\HWConsole.exe]
Dataset consistency test: No problems found

Plugins:
+ OpeningHoursEditor (35924)
+ RoadSigns (36011)
+ apache-commons (36034)
+ buildings_tools (36011)
+ contourmerge (v0.1.9)
+ ejml (35924)
+ geotools (36028)
+ jackson (36034)
+ jaxb (35952)
+ jts (36004)
+ o5m (35893)
+ opendata (36025)
+ pbf (36034)
+ poly (35976)
+ reltoolbox (35976)
+ reverter (36043)
+ undelete (36011)
+ utilsplugin2 (36011)

Validator rules:
+ c:\josm\core\resources\data\validator\combinations.mapcss
+ c:\josm\core\resources\data\validator\geometry.mapcss
+ c:\josm\core\resources\data\validator\unnecessary.mapcss
+ d:\java_tools\JOSM\mygeometry.mapcss
+ https://josm.openstreetmap.de/josmfile?page=Rules/GermanySpecific&zip=1

Last errors/warnings:
- 00000.671 W: extended font config - overriding 'filename.Myanmar_Text=mmrtext.ttf' with 'MMRTEXT.TTF'
- 00000.674 W: extended font config - overriding 'filename.Mongolian_Baiti=monbaiti.ttf' with 'MONBAITI.TTF'
- 00001.229 E: java.security.KeyStoreException: Windows-ROOT not found. Cause: java.security.NoSuchAlgorithmException: Windows-ROOT KeyStore not available

[GerdP]

A few more remarks:

• the algorithm in class NodeGraph doesn't care about OSM specific restrictions like intersecting ways, but it won't combine ways with overlapping segments.
• sometimes the result changes when I split the selected ways first, so there is something random which makes testing difficult. I didn't find yet where this randomization happens.

[taylor.smock]

Replying to GerdP:

• sometimes the result changes when I split the selected ways first, so there is something random which makes testing difficult. I didn't find yet where this randomization happens.

I suspect this is due to how the code iterates through nodes.

Essentially, the code does a depth-first search for an "end", and then goes back up.

Example:
Let us say

• Way 1 is made up of Nodes 1, 2, 3, 4
• Way 2 is made up of Nodes 4, 5, 6, 7
• Way 3 is made up of Nodes 3, 8, 9, 10

What will happen, with the current code, is that the nodes will be processed in the following order:

• 1, 2, 3, 8, 9, 10, 4, 5, 6, 7

If we then split Way 1 at node 3, such that Way 1 has nodes 1, 2, 3 and Way 4 has nodes 3, 4, the node processing order gets a bit more complicated.

• 1, 2, 3 (branch point)
  • 8, 9, 10, 4, 5, 6, 7
  • 4, 5, 6, 7, 8, 9, 10

It really depends upon which way comes first.

[GerdP]

Yeah, don't worry. I make those remarks for myself ;)
The oneway problem can be solved if we first try to find a path from a graph that was created with createDirectedGraphFromWays(). It requires some changes elsewhere but works well. I've not yet made up my mind how to modify the data structures, my current thinking is the prepare() method should combine those parts which are without alternative. The combined NodePair instances can be removed from the graph.
The final process to build the list of nodes just has to find the correct combined parts (maybe with a pointer, maybe with a HashMap.