Repository: graphhopper/graphhopper (java)

Issue:
Incorrect handling of turn restrictions sharing the same via-way
**Describe the bug**
I have recently discovered that in some uncommon cases, Graphhopper simply fails to produce the correct driving path. It is as if Graphhopper thinks the relevant roads does not exist.

There is no apparent explanation as to why the best path is not discovered by Graphhopper. The following items were checked, but feel free to double check:
- Relevant OSM data: turn restrictions OK, access OK
- Local Graphhopper "debug" routing graph: vehicle access OK

One wild guess is that the relevant roads got wrongly rejected while doing CH.

**To Reproduce**

I offer 1 of the possibly many cases for consideration.

(Note: this is a left-hand-drive case!!! But hopefully, this does not disqualify the bug.)

Case: https://graphhopper.com/maps/?point=22.343482%2C114.131477&point=22.337654%2C114.137139&profile=car&layer=OpenStreetMap

![image](https://github.com/graphhopper/graphhopper/assets/17726797/9250f706-142a-4128-9dab-4e548b00d8ea)

It seems the detour is unnecessary.

**Expected behavior**
Indeed, the detour is unnecessary. IRL drivers would do this:

![image](https://github.com/graphhopper/graphhopper/assets/17726797/66886c8b-72c8-4912-b657-e17465d9f7d0)

**System Information**
N/A; reproduced via official Graphhopper Maps.

**Screenshots & Logs**
(Provided)

---

More cases in the neighbourhood, to show the "disappearance" of the affected road segments:

~~This does not work: https://graphhopper.com/maps/?point=22.343482%2C114.131477&point=22.340576%2C114.130486&profile=car&layer=OpenStreetMap~~

**Update: thanks to @ratrun 's comments, I reviewed the situation and realized for this specific case, Graphhopper is working as intended and I got a false alarm; however the other cases are still valid.**

![image](https://github.com/graphhopper/graphhopper/assets/17726797/56d33c4b-e68e-458a-b427-1b22c6618817)

This does not work: https://graphhopper.com/maps/?point=22.337536%2C114.137059&point=22.3377%2C114.137113&profile=car&layer=OpenStreetMap

![image](https://github.com/graphhopper/graphhopper/assets/17726797/54fea280-8bac-4587-a4b3-8e063d32db7e)

But curiously, this works: https://graphhopper.com/maps/?point=22.337536%2C114.137059&point=22.343259%2C114.131432&profile=car&layer=OpenStreetMap

![image](https://github.com/graphhopper/graphhopper/assets/17726797/80dc986e-f803-42e1-ba26-8fd83656754d)



Pull request description:
Ignore via-way restrictions that share the same via-way in the same direction
Fixes #2907 


Patch:
diff --git a/core/src/main/java/com/graphhopper/reader/osm/OSMReader.java b/core/src/main/java/com/graphhopper/reader/osm/OSMReader.java
index bebfd3491..7df36852e 100644
--- a/core/src/main/java/com/graphhopper/reader/osm/OSMReader.java
+++ b/core/src/main/java/com/graphhopper/reader/osm/OSMReader.java
@@ -581,7 +581,7 @@ public class OSMReader {
         // The restriction type depends on the vehicle, or at least not all restrictions affect every vehicle type.
         // We handle the restrictions for one vehicle after another.
         for (RestrictionTagParser restrictionTagParser : osmParsers.getRestrictionTagParsers()) {
-            LongSet viaWaysUsedByOnlyRestrictions = new LongHashSet();
+            LongSet directedViaWaysUsedByRestrictions = new LongHashSet();
             List<Pair<GraphRestriction, RestrictionType>> restrictionsWithType = new ArrayList<>(restrictions.size());
             for (Triple<ReaderRelation, GraphRestriction, RestrictionMembers> r : restrictions) {
                 if (r.second == null)
@@ -593,12 +593,15 @@ public class OSMReader {
                         // this relation is ignored by the current restriction tag parser
                         continue;
                     RestrictionConverter.checkIfCompatibleWithRestriction(r.second, res.getRestriction());
-                    // we ignore 'only' via-way restrictions that share the same via way, because these would require adding
-                    // multiple artificial edges, see here: https://github.com/graphhopper/graphhopper/pull/2689#issuecomment-1306769694
-                    if (r.second.isViaWayRestriction() && res.getRestrictionType() == RestrictionType.ONLY)
-                        for (LongCursor viaWay : r.third.getViaWays())
-                            if (!viaWaysUsedByOnlyRestrictions.add(viaWay.value))
-                                throw new OSMRestrictionException("has a member with role 'via' that is also used as 'via' member by another 'only' restriction. GraphHopper cannot handle this.");
+                    // we ignore via-way restrictions that share the same via-way in the same direction, because these would require adding
+                    // multiple artificial edges, see here: https://github.com/graphhopper/graphhopper/pull/2689#issuecomment-1306769694 and #2907
+                    if (r.second.isViaWayRestriction())
+                        for (LongCursor viaWay : r.third.getViaWays()) {
+                            // We simply use the first and last via-node to determine the direction of the way, but for multiple via-ways maybe we need to reconsider this!
+                            long directedViaWay = viaWay.value * (r.second.getViaNodes().get(0) < r.second.getViaNodes().get(r.second.getViaNodes().size() - 1) ? +1 : -1);
+                            if (!directedViaWaysUsedByRestrictions.add(directedViaWay))
+                                throw new OSMRestrictionException("has a member with role 'via' (" + viaWay.value + ") that is also used as 'via' member by another restriction in the same direction. GraphHopper cannot handle this.");
+                        }
                     restrictionsWithType.add(new Pair<>(r.second, res.getRestrictionType()));
                 } catch (OSMRestrictionException e) {
                     warnOfRestriction(r.first, e);
diff --git a/core/src/main/java/com/graphhopper/routing/util/parsers/RestrictionSetter.java b/core/src/main/java/com/graphhopper/routing/util/parsers/RestrictionSetter.java
index 37b00dda7..17fffd77e 100644
--- a/core/src/main/java/com/graphhopper/routing/util/parsers/RestrictionSetter.java
+++ b/core/src/main/java/com/graphhopper/routing/util/parsers/RestrictionSetter.java
@@ -86,7 +86,7 @@ public class RestrictionSetter {
     }
 
     private void addViaWayRestrictions(List<Pair<GraphRestriction, RestrictionType>> restrictions, BooleanEncodedValue turnRestrictionEnc) {
-        IntSet viaEdgesUsedByOnlyRestrictions = new IntHashSet();
+        IntSet directedViaEdgesUsedByRestrictions = new IntHashSet();
         for (Pair<GraphRestriction, RestrictionType> p : restrictions) {
             if (!p.first.isViaWayRestriction()) continue;
             if (ignoreViaWayRestriction(p)) continue;
@@ -96,8 +96,19 @@ public class RestrictionSetter {
             final int artificialVia = artificialEdgesByEdges.getOrDefault(viaEdge, viaEdge);
             if (artificialVia == viaEdge)
                 throw new IllegalArgumentException("There should be an artificial edge for every via edge of a way restriction");
-            if (p.second == ONLY && !viaEdgesUsedByOnlyRestrictions.add(viaEdge))
-                throw new IllegalStateException("We cannot deal with 'only' via-way restrictions that use the same via edges");
+
+            // With a single artificial edge per original edge there can only be one restriction
+            // that uses this edge as via-member **per direction**, see #2907.
+            // We can use the two via node ids to determine the via-edge direction in the restriction:
+            if (p.first.getViaEdges().size() != 1)
+                throw new IllegalStateException("At this point we assumed we were dealing with single via-way restrictions only");
+            if (viaEdge == 0 && directedViaEdgesUsedByRestrictions.contains(viaEdge))
+                // This approach does not work for edge 0...
+                throw new IllegalStateException("We cannot deal with multiple via-way restrictions if the via-edge is edge 0");
+            final int directedViaEdge = viaEdge * (p.first.getViaNodes().get(0) < p.first.getViaNodes().get(1) ? +1 : -1);
+            if (!directedViaEdgesUsedByRestrictions.add(directedViaEdge))
+                throw new IllegalStateException("We cannot deal with multiple via-way restrictions that use the same via edge in the same direction");
+
             final int artificialFrom = artificialEdgesByEdges.getOrDefault(fromEdge, fromEdge);
             final int artificialTo = artificialEdgesByEdges.getOrDefault(toEdge, toEdge);
             final int fromToViaNode = p.first.getViaNodes().get(0);


Test patch:
diff --git a/core/src/test/java/com/graphhopper/routing/util/parsers/RestrictionSetterTest.java b/core/src/test/java/com/graphhopper/routing/util/parsers/RestrictionSetterTest.java
index 2166e9d02..40574f287 100644
--- a/core/src/test/java/com/graphhopper/routing/util/parsers/RestrictionSetterTest.java
+++ b/core/src/test/java/com/graphhopper/routing/util/parsers/RestrictionSetterTest.java
@@ -16,8 +16,7 @@ import org.junit.jupiter.api.Test;
 
 import java.util.Arrays;
 
-import static org.junit.jupiter.api.Assertions.assertEquals;
-import static org.junit.jupiter.api.Assertions.assertThrows;
+import static org.junit.jupiter.api.Assertions.*;
 
 public class RestrictionSetterTest {
     private static final IntArrayList NO_PATH = IntArrayList.from();
@@ -165,6 +164,83 @@ public class RestrictionSetterTest {
         assertEquals(nodes(6, 7, 8, 9), calcPath(6, 9, turnRestrictionEnc));
     }
 
+    @Test
+    void viaWay_common_via_edge_opposite_direction() {
+        //    a   b
+        //  0---1---2
+        //      |c
+        //  3---4---5
+        //    d   e
+        int a = edge(0, 1);
+        int b = edge(1, 2);
+        int c = edge(1, 4);
+        int d = edge(3, 4);
+        int e = edge(4, 5);
+
+        BooleanEncodedValue turnRestrictionEnc = createTurnRestrictionEnc("car");
+        r.setRestrictions(Arrays.asList(
+                // A rather common case where u-turns between the a-b and d-e lanes are forbidden.
+                // Importantly, the via-edge c is used only once per direction so a single artificial edge is sufficient.
+                new Pair<>(GraphRestriction.way(b, c, e, nodes(1, 4)), RestrictionType.NO),
+                new Pair<>(GraphRestriction.way(d, c, a, nodes(4, 1)), RestrictionType.NO)
+        ), turnRestrictionEnc);
+
+        assertEquals(nodes(0, 1, 2), calcPath(0, 2, turnRestrictionEnc));
+        assertEquals(nodes(0, 1, 4, 5), calcPath(0, 5, turnRestrictionEnc));
+        assertEquals(nodes(0, 1, 4, 3), calcPath(0, 3, turnRestrictionEnc));
+        assertEquals(nodes(2, 1, 0), calcPath(2, 0, turnRestrictionEnc));
+        assertEquals(nodes(2, 1, 4, 3), calcPath(2, 3, turnRestrictionEnc));
+        assertEquals(NO_PATH, calcPath(2, 5, turnRestrictionEnc));
+        assertEquals(NO_PATH, calcPath(3, 0, turnRestrictionEnc));
+        assertEquals(nodes(3, 4, 1, 2), calcPath(3, 2, turnRestrictionEnc));
+        assertEquals(nodes(3, 4, 5), calcPath(3, 5, turnRestrictionEnc));
+        assertEquals(nodes(5, 4, 1, 0), calcPath(5, 0, turnRestrictionEnc));
+        assertEquals(nodes(5, 4, 1, 2), calcPath(5, 2, turnRestrictionEnc));
+        assertEquals(nodes(5, 4, 3), calcPath(5, 3, turnRestrictionEnc));
+    }
+
+    @Test
+    void viaWay_common_via_edge_opposite_direction_edge0() {
+        //    a   v   b
+        //  0---1---2---3
+        int v = edge(1, 2);
+        int a = edge(0, 1);
+        int b = edge(2, 3);
+
+        BooleanEncodedValue turnRestrictionEnc = createTurnRestrictionEnc("car");
+        IllegalStateException ex = assertThrows(IllegalStateException.class, () -> r.setRestrictions(Arrays.asList(
+                // This is rather academic, but for the special case where the via edge is edge 0
+                // we cannot use two restrictions even though the edge is used in opposite directions.
+                new Pair<>(GraphRestriction.way(a, v, b, nodes(1, 2)), RestrictionType.NO),
+                new Pair<>(GraphRestriction.way(b, v, a, nodes(2, 1)), RestrictionType.NO)
+        ), turnRestrictionEnc));
+        assertTrue(ex.getMessage().contains("We cannot deal with multiple via-way restrictions if the via-edge is edge 0"));
+    }
+
+    @Test
+    void viaWay_common_via_edge_same_direction() {
+        //    a   b
+        //  0---1---2
+        //      |c
+        //  3---4---5
+        //    d   e
+        int a = edge(0, 1);
+        int b = edge(1, 2);
+        int c = edge(1, 4);
+        int d = edge(3, 4);
+        int e = edge(4, 5);
+
+        BooleanEncodedValue turnRestrictionEnc = createTurnRestrictionEnc("car");
+        // Here edge c is used by both restrictions in the same direction. Supporting this
+        // with our current approach would require a second artificial edge. See #2907
+        IllegalStateException ex = assertThrows(IllegalStateException.class, () ->
+                r.setRestrictions(Arrays.asList(
+                        new Pair<>(GraphRestriction.way(a, c, d, nodes(1, 4)), RestrictionType.NO),
+                        new Pair<>(GraphRestriction.way(b, c, e, nodes(1, 4)), RestrictionType.NO)
+                ), turnRestrictionEnc));
+        assertTrue(ex.getMessage().contains("We cannot deal with multiple via-way restrictions that use the same via edge in the same direction"), ex.getMessage());
+    }
+
     @Test
     void viaWay_only() {
         //      0
@@ -185,7 +261,7 @@ public class RestrictionSetterTest {
         r.setRestrictions(Arrays.asList(
                 new Pair<>(GraphRestriction.way(a, d, f, nodes(2, 5)), RestrictionType.ONLY),
                 // we add a few more restrictions, because that happens a lot in real data
-                new Pair<>(GraphRestriction.way(c, d, g, nodes(2, 5)), RestrictionType.NO),
+                new Pair<>(GraphRestriction.node(d, 5, e), RestrictionType.NO),
                 new Pair<>(GraphRestriction.node(e, 5, f), RestrictionType.NO)
         ), turnRestrictionEnc);
         // following the restriction is allowed of course
@@ -194,7 +270,7 @@ public class RestrictionSetterTest {
         assertEquals(nodes(), calcPath(1, 3, turnRestrictionEnc));
         // taking another turn after the first turn is not allowed either
         assertEquals(nodes(), calcPath(1, 4, turnRestrictionEnc));
-        // coming from somewhere we can go anywhere
+        // coming from somewhere else we can go anywhere
         assertEquals(nodes(0, 2, 5, 6), calcPath(0, 6, turnRestrictionEnc));
         assertEquals(nodes(0, 2, 5, 7), calcPath(0, 7, turnRestrictionEnc));
     }
@@ -213,8 +289,9 @@ public class RestrictionSetterTest {
         BooleanEncodedValue turnRestrictionEnc = createTurnRestrictionEnc("car");
         assertThrows(IllegalStateException.class, () -> r.setRestrictions(Arrays.asList(
                         // These are two 'only' via-way restrictions that share the same via way. A real-world example can
-                        // be found in Rüdesheim am Rhein where vehicles either have to go straight or enter the ferry depending
-                        // on the from-way, even though they use the same via way before.
+                // be found in Rüdesheim am Rhein (49.97645, 7.91309) where vehicles either have to go straight or enter the ferry depending
+                // on the from-way, even though they use the same via way before. This is the same
+                // problem we saw in #2907.
                         // We have to make sure such cases are ignored already when we parse the OSM data.
                         new Pair<>(GraphRestriction.way(a, c, d, nodes(1, 2)), RestrictionType.ONLY),
                         new Pair<>(GraphRestriction.way(b, c, e, nodes(1, 2)), RestrictionType.ONLY)
@@ -222,6 +299,37 @@ public class RestrictionSetterTest {
         );
     }
 
+    @Test
+    void viaWay_only_twoRestrictionsSharingSameVia_different_directions() {
+        //   a   c   d
+        // 0---1---2---3
+        //     |b  |e
+        // 5--/     \--4
+        int a = edge(0, 1);
+        int b = edge(5, 1);
+        int c = edge(1, 2);
+        int d = edge(2, 3);
+        int e = edge(2, 4);
+        BooleanEncodedValue turnRestrictionEnc = createTurnRestrictionEnc("car");
+        r.setRestrictions(Arrays.asList(
+                // since the via-edge is used in opposite directions we can deal with these restrictions
+                new Pair<>(GraphRestriction.way(a, c, d, nodes(1, 2)), RestrictionType.ONLY),
+                new Pair<>(GraphRestriction.way(e, c, b, nodes(2, 1)), RestrictionType.ONLY)
+        ), turnRestrictionEnc);
+        assertEquals(nodes(0, 1, 2, 3), calcPath(0, 3, turnRestrictionEnc));
+        assertEquals(NO_PATH, calcPath(0, 4, turnRestrictionEnc));
+        assertEquals(NO_PATH, calcPath(0, 5, turnRestrictionEnc));
+        assertEquals(nodes(3, 2, 1, 0), calcPath(3, 0, turnRestrictionEnc));
+        assertEquals(nodes(3, 2, 4), calcPath(3, 4, turnRestrictionEnc));
+        assertEquals(nodes(3, 2, 1, 5), calcPath(3, 5, turnRestrictionEnc));
+        assertEquals(NO_PATH, calcPath(4, 0, turnRestrictionEnc));
+        assertEquals(NO_PATH, calcPath(4, 3, turnRestrictionEnc));
+        assertEquals(nodes(4, 2, 1, 5), calcPath(4, 5, turnRestrictionEnc));
+        assertEquals(nodes(5, 1, 0), calcPath(5, 0, turnRestrictionEnc));
+        assertEquals(nodes(5, 1, 2, 3), calcPath(5, 3, turnRestrictionEnc));
+        assertEquals(nodes(5, 1, 2, 4), calcPath(5, 4, turnRestrictionEnc));
+    }
+
     private static BooleanEncodedValue createTurnRestrictionEnc(String name) {
         BooleanEncodedValue turnRestrictionEnc = TurnRestriction.create(name);
         turnRestrictionEnc.init(new EncodedValue.InitializerConfig());